Jump to content
Sign in to follow this  
  • entries
    18
  • comments
    19
  • views
    14743

Leveling Up

Sign in to follow this  
jdaniel

397 views

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 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 General Collision Detection for Games Using Ellipsoids by Paul Nettle. You can find it here:
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 Point in Polygon Strategies 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.

Another really good article was Intersection of Convex Objects: The Method of Separating Axes by David Eberly.

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.

test level
Sign in to follow this  


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
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!