# Leveling Up

If the rules of life were really like the game Oblivion I would have woke up this morning and thought...

"So that's how you do it. What once was a struggle has now become second nature. Please distribute attribute points."

I will add +3 to my Collision Detection skill please.

I finally finished the collision detection routine in my 3D engine. This was no easy task for me and there were many times that I thought I had reached a barrier that I could not overcome. I sometimes felt at the verge of panic. All this work so far only to be defeated.

It seemed like I almost had it working several times. And the worst was when I

While although shady company, printf has been my constant companion through collision detection hell. Here is a sample of one of the last debug iterations.

But a long story short: I did it. I implemented collision detection with recursive sliding planes and gravity.

The document I found most helpful was

https://www.gamedev.net/reference/articles/article1026.asp

This wasn't a perfect article though. I found a few errors. Or at least I was not able to implement exactly what Paul was suggesting. In particular, how the sliding planes itself were calculated seemed wrong to me. Paul suggested that sliding planes be calculated like this:

When implemented like this, a sliding plane would be calculated that was not parallel to the actual triangle. Paul writes, "The normal of this [sliding] plane is the vector from the intersection point to the center of the sphere". However, this created more of a "bouncing plane" rather than a true sliding plane when I implemented this. To solve this problem, I simply used the original triangles normal for the sliding plane normal. This seems to work just fine and creates a nice smooth sliding plane on which to project the movement vector.

There were a couple of small inconsistencies that could cause problems. One, the order of arguments given in his routines were not consistent with the order that he passed them in the pseudo code. This problem was compounded by the almost cryptic variable names (i.e. r, rV, s, sR). In the psuedo code, for example, Paul would write:

However, the actual pseodo-code intersectEllipse routine does not accept the arguements in this order. Additionally, radiusVector is really a double while negativeVelocityVector is actually a vector. He also uses '*' to denote a scalar multiplication and then immediatly uses '*' to denote dot product. While it can eventually be deciphered, it caused me a little uneccesary pain. I am still in debt to Paul Nettle's document, however; I used it heavily to implement my collision detection.

One thing that Paul skipped over entirely in his article was point in polygon strategies. In the pseudo-code he would say

So I found another article that was really good at explaining these strategies, appropriately names

Another really good article was

And now I am ready to move on to another area of development. Collision detection was a huge obstacle for me to overcome and my morale has been raised considerably by being able to overcome it. I have spent so much of my free time and energy on this particular area that I seriously felt like weeping for joy when it finally worked correctly. The more time and energy I poured into this, the greater the anxiety of possible failure. But when it finally worked correctly, all that anxiety left.

Here is screenshot of the expanded test level I was using to test this. I added some stairs to make sure gravity was working as expected and created a quarter dome room to test the recursive sliding plane calls. It all looks beautiful. At least from my vantage.

"So that's how you do it. What once was a struggle has now become second nature. Please distribute attribute points."

I will add +3 to my Collision Detection skill please.

I finally finished the collision detection routine in my 3D engine. This was no easy task for me and there were many times that I thought I had reached a barrier that I could not overcome. I sometimes felt at the verge of panic. All this work so far only to be defeated.

It seemed like I almost had it working several times. And the worst was when I

*thought*I had it working. I would cautiously become optimistic only to have the chair pulled out from under me as I sat down. Inevitably, I would discover someway to clip through a corner and find the camera outside the walls of the test level.While although shady company, printf has been my constant companion through collision detection hell. Here is a sample of one of the last debug iterations.

recursion level: 1

The distance the player wants to travel is 1.100000

The player is currently at [sourcePoint] 6.184948 0.000000 0.780793

The velocity vector is -0.164489 0.000000 -1.087632

The normalized velocity vector is -0.149535 0.000000 -0.988756

The player wants to move to 6.020459 0.000000 -0.306839

The bounding sphere radius is 1.000000

Now traversing triangle list in zone object.

Now considering triangle #24.

Point 1 on triangle: 7.000000 -1.500000 0.000000

Point 2 on triangle: 12.000000 -1.500000 0.000000

Point 3 on triangle: 7.000000 3.500000 0.000000

The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000

Normalized plane normal (normal of the triangle): 0.000000 0.000000 1.000000

The distance from the sphere origin to the plane is absolute 0.780793 relative 0.780793.

NOTE: If value is negative we are dealing with a backface and no additional tests will occur.

The bounding sphere is embedded in the triangle plane.

setting planeCollisionPoint to 6.184948 0.000000 0.000000 for embedded sphere.

Plane intersection point is 6.184948 0.000000 0.000000

**** crossings: 0

The planeIntersectionPoint is not contained within the triangle

Closest Point on Triangle to the collision point: 7.000000 -1.500000 0.000000

polygonIntersectionPoint is 7.000000 -1.500000 0.000000

The distance from the polygonIntersectionPoint and the sourcePoint is 1.877218

(tt) The distance from the polygonIntersectionPoint to the sphereIntersectionPoint is -1.000000

Now considering triangle #25.

Point 1 on triangle: 7.000000 -1.500000 0.000000

Point 2 on triangle: 7.000000 3.500000 0.000000

Point 3 on triangle: 7.000000 -1.500000 -5.000000

The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000

Normalized plane normal (normal of the triangle): -1.000000 0.000000 0.000000

The distance from the sphere origin to the plane is absolute 0.815052 relative 0.815052.

NOTE: If value is negative we are dealing with a backface and no additional tests will occur.

The bounding sphere is embedded in the triangle plane.

setting planeCollisionPoint to 7.000000 0.000000 0.780793 for embedded sphere.

Plane intersection point is 7.000000 0.000000 0.780793

**** crossings: 0

The planeIntersectionPoint is not contained within the triangle

Closest Point on Triangle to the collision point: 7.000000 -0.500000 0.000000

polygonIntersectionPoint is 7.000000 -0.500000 0.000000

The distance from the polygonIntersectionPoint and the sourcePoint is 1.234483

(tt) The distance from the polygonIntersectionPoint to the sphereIntersectionPoint is -1.000000

There was no collision with any triangle. Moving sphere origin to 6.020459 0.000000 -0.306839

recursion level: 1

The distance the player wants to travel is 1.100000

The player is currently at [sourcePoint] 6.020459 0.000000 -0.306839

The velocity vector is 0.336267 0.000000 -1.047342

The normalized velocity vector is 0.305697 0.000000 -0.952129

The player wants to move to 6.356726 0.000000 -1.354181

The bounding sphere radius is 1.000000

Now traversing triangle list in zone object.

Now considering triangle #24.

Point 1 on triangle: 7.000000 -1.500000 0.000000

Point 2 on triangle: 12.000000 -1.500000 0.000000

Point 3 on triangle: 7.000000 3.500000 0.000000

The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000

Normalized plane normal (normal of the triangle): 0.000000 0.000000 1.000000

The distance from the sphere origin to the plane is absolute 0.306839 relative -0.306839.

NOTE: If value is negative we are dealing with a backface and no additional tests will occur.

Now considering triangle #25.

Point 1 on triangle: 7.000000 -1.500000 0.000000

Point 2 on triangle: 7.000000 3.500000 0.000000

Point 3 on triangle: 7.000000 -1.500000 -5.000000

The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000

Normalized plane normal (normal of the triangle): -1.000000 0.000000 0.000000

The distance from the sphere origin to the plane is absolute 0.979541 relative 0.979541.

NOTE: If value is negative we are dealing with a backface and no additional tests will occur.

The bounding sphere is embedded in the triangle plane.

setting planeCollisionPoint to 7.000000 0.000000 -0.306839 for embedded sphere.

Plane intersection point is 7.000000 0.000000 -0.306839

**** crossings: 1

The planeIntersectionPoint lies within the triangle.

The polygonIntersectionPoint equals the planeIntersectionPoint

polygonIntersectionPoint is 7.000000 0.000000 -0.306839

The distance from the polygonIntersectionPoint and the sourcePoint is 0.979541

SANITY ERROR: The polygonIntersectionPoint is within the bounding sphere.

A previous logic error did not properly detect a collision.

ABORTING

But a long story short: I did it. I implemented collision detection with recursive sliding planes and gravity.

The document I found most helpful was

*by Paul Nettle. You can find it here:***General Collision Detection for Games Using Ellipsoids**https://www.gamedev.net/reference/articles/article1026.asp

This wasn't a perfect article though. I found a few errors. Or at least I was not able to implement exactly what Paul was suggesting. In particular, how the sliding planes itself were calculated seemed wrong to me. Paul suggested that sliding planes be calculated like this:

Point slidePlaneOrigin = nearestPolygonIntersectionPoint;

Vector slidePlaneNormal = nearestPolygonIntersectionPoint - sourcePoint;

When implemented like this, a sliding plane would be calculated that was not parallel to the actual triangle. Paul writes, "The normal of this [sliding] plane is the vector from the intersection point to the center of the sphere". However, this created more of a "bouncing plane" rather than a true sliding plane when I implemented this. To solve this problem, I simply used the original triangles normal for the sliding plane normal. This seems to work just fine and creates a nice smooth sliding plane on which to project the movement vector.

There were a couple of small inconsistencies that could cause problems. One, the order of arguments given in his routines were not consistent with the order that he passed them in the pseudo code. This problem was compounded by the almost cryptic variable names (i.e. r, rV, s, sR). In the psuedo code, for example, Paul would write:

Double t = intersectEllipse(sourcePoint, radiusVector, polygonIntersectionPoint, negativeVelocityVector);

However, the actual pseodo-code intersectEllipse routine does not accept the arguements in this order. Additionally, radiusVector is really a double while negativeVelocityVector is actually a vector. He also uses '*' to denote a scalar multiplication and then immediatly uses '*' to denote dot product. While it can eventually be deciphered, it caused me a little uneccesary pain. I am still in debt to Paul Nettle's document, however; I used it heavily to implement my collision detection.

One thing that Paul skipped over entirely in his article was point in polygon strategies. In the pseudo-code he would say

if (planeIntersectionPoint is not within the current polygon)

So I found another article that was really good at explaining these strategies, appropriately names

**by Eric Haines. In fact, this article appears in Graphics Gems IV. Apparently the full article is better than the one you can find on the internet, but it is still very useful.***Point in Polygon Strategies*Another really good article was

*by David Eberly.***Intersection of Convex Objects: The Method of Separating Axes**And now I am ready to move on to another area of development. Collision detection was a huge obstacle for me to overcome and my morale has been raised considerably by being able to overcome it. I have spent so much of my free time and energy on this particular area that I seriously felt like weeping for joy when it finally worked correctly. The more time and energy I poured into this, the greater the anxiety of possible failure. But when it finally worked correctly, all that anxiety left.

Here is screenshot of the expanded test level I was using to test this. I added some stairs to make sure gravity was working as expected and created a quarter dome room to test the recursive sliding plane calls. It all looks beautiful. At least from my vantage.

0

Sign in to follow this

Followers
0

## 0 Comments

## Recommended Comments

There are no comments to display.

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now