"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: 1The distance the player wants to travel is 1.100000The player is currently at [sourcePoint] 6.184948 0.000000 0.780793The velocity vector is -0.164489 0.000000 -1.087632The normalized velocity vector is -0.149535 0.000000 -0.988756The player wants to move to 6.020459 0.000000 -0.306839The bounding sphere radius is 1.000000Now traversing triangle list in zone object.Now considering triangle #24.Point 1 on triangle: 7.000000 -1.500000 0.000000Point 2 on triangle: 12.000000 -1.500000 0.000000Point 3 on triangle: 7.000000 3.500000 0.000000The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000Normalized plane normal (normal of the triangle): 0.000000 0.000000 1.000000The 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: 0The planeIntersectionPoint is not contained within the triangleClosest Point on Triangle to the collision point: 7.000000 -1.500000 0.000000polygonIntersectionPoint is 7.000000 -1.500000 0.000000The distance from the polygonIntersectionPoint and the sourcePoint is 1.877218 (tt) The distance from the polygonIntersectionPoint to the sphereIntersectionPoint is -1.000000Now considering triangle #25.Point 1 on triangle: 7.000000 -1.500000 0.000000Point 2 on triangle: 7.000000 3.500000 0.000000Point 3 on triangle: 7.000000 -1.500000 -5.000000The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000Normalized plane normal (normal of the triangle): -1.000000 0.000000 0.000000The 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: 0The planeIntersectionPoint is not contained within the triangleClosest Point on Triangle to the collision point: 7.000000 -0.500000 0.000000polygonIntersectionPoint is 7.000000 -0.500000 0.000000The distance from the polygonIntersectionPoint and the sourcePoint is 1.234483 (tt) The distance from the polygonIntersectionPoint to the sphereIntersectionPoint is -1.000000There was no collision with any triangle. Moving sphere origin to 6.020459 0.000000 -0.306839recursion level: 1The distance the player wants to travel is 1.100000The player is currently at [sourcePoint] 6.020459 0.000000 -0.306839The velocity vector is 0.336267 0.000000 -1.047342The normalized velocity vector is 0.305697 0.000000 -0.952129The player wants to move to 6.356726 0.000000 -1.354181The bounding sphere radius is 1.000000Now traversing triangle list in zone object.Now considering triangle #24.Point 1 on triangle: 7.000000 -1.500000 0.000000Point 2 on triangle: 12.000000 -1.500000 0.000000Point 3 on triangle: 7.000000 3.500000 0.000000The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000Normalized plane normal (normal of the triangle): 0.000000 0.000000 1.000000The 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.000000Point 2 on triangle: 7.000000 3.500000 0.000000Point 3 on triangle: 7.000000 -1.500000 -5.000000The origin of the plane is (a point on the triangle): 7.000000 -1.500000 0.000000Normalized plane normal (normal of the triangle): -1.000000 0.000000 0.000000The 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: 1The planeIntersectionPoint lies within the triangle.The polygonIntersectionPoint equals the planeIntersectionPointpolygonIntersectionPoint is 7.000000 0.000000 -0.306839The distance from the polygonIntersectionPoint and the sourcePoint is 0.979541SANITY ERROR: The polygonIntersectionPoint is within the bounding sphere. A previous logic error did not properly detect a collision. ABORTINGBut 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.
