Method of Separating Axes
This final section of the puzzle deals with how to figure out if two objects are going to be colliding in the immediate future. Most of these functions take an Elapsed variable which is important to understand so I'm going to take a moment to shed some light on it. The job of the collision detection step is to figure out whether or not the two objects are going to be colliding within Elapsed seconds. This time represents how much time has passed since the last time the Physics engine updated everything. The physics engine wants to know if it can move the objects forward in time by Elapsed seconds without having a collision. Any collision that happens after Elapsed seconds is of no interest for this check. Also, in a perfect collision detection system all of the objects would not be penetrating. However we have seen that in some cases they are, and we have seen how to handle that. In any event, on to the code. In this case all of the functions are found in CollisionSolver.cpp in the REnginePhysics project:
This function is the main entry point for checking to see if two rigid bodies will collide within a given time step. The inputs are as follows:
- Obj1 and Ob2: the two objects that you want to check for a collision.
- Elapsed: the time elapsed since last physics step, explained above.
- CacheStamp: this is for optimizations. If this value is different then it was last time then you have to assume that the two objects have moved and will need to be recalculated. If it is the same then you can reuse them (which is a big time saver).
- Report: if a collision is found this object contains the information we need to know, where the collision happened (in world coords), the collision normal (as perceived by Obj1) and the time the collision happened (ie 0.2 seconds in the future).
The first step in this function is to try the absolutely cheapest, fastest, crudest check to see whether or not the objects collided. If you where to wrap each object in a sphere, then move that sphere to all possible positions it can be in during the Elapsed time, you would be describing a very large sphere. You then find the distance between those two spheres. If that distance is greater then the combined radii, then the 2 spheres do not intersect, and there's no way the objects intersect, and we can just return false and forget about it. If the two spheres do intersect then we have to go deeper.
This function is really where all the serious work is coordinated. It is a recursive function, calling into itself to work down the child trees of the input polyhedra. The inputs are:
- Poly1 and Poly2: The 2 polyhedra the we want to test for collision.
- Axis1 and Axis2: Position and rotation info for the 2 polyhedra.
- V1 and V2: linear velocity for the 2 polyhedra.
- AV1 and AV2: angular velocity for the 2 polyhedra.
- Elapsed: same as in the RCollisionSolver::CheckCollision argument.
- CacheStamp: same as in the RCollisionSolver::CheckCollision argument. It actualy gets applied within this function.
- Report: same as in the RCollisionSolver::CheckCollision argument.
It's worth taking a moment to explain the state of the polyhedra passed into this function. The RConvexPolyhedron object is basically just a copy of the RCollisionModel that has been moved and rotated into world coords. The act of moving and rotating all the points is pretty expensive, so we try to do it only when we're completely sure it needs to be done. In the begining of this function we tell the polyhedron to update its axis to the current one, and we pass in a cache stamp. The polyhedron will perform the expensive move and rotation and then save that cache stamp. If we ask it again with the same cache stamp it will just return. In any event, after the calls to UpdateAxis we know that the polyhedron are now in world coords. Note that their children may not be (but we'll check them later).
The next step is to check the bounding boxes using the OBBOBBCollision function. This function will return false if the OBBs do not collide. If the OBBs don't collide, then these polyhedra do not collide and we can exit the function. If they do collide then we need to start looking further.
The next step is to see if the current polyhedra is a parent node or a leaf node. If it is a parent node then it has no physical representation of its own, it simply has children. In this case we need to step down the child trees and compare them with each other. This is done by recursively calling this function. This will continue until we get to a leaf node and then RConvexPolyhedron::GetKids::size() function will return 0.
If we get past the parent checks then we will be at the leaf node check. At this point we have 2 polyhedra that actually are a bunch of points, lines, and planes in space that need to be checked. We will now need to break them down further and start thinking of them as a collection of triangles. Unfortunately this means we have a pretty large set of triangles that needs to be compared against another large set of triangles. This starts to add up to a a large number of comparisons. In order to cut this down a bit what we do is compare all of the triangles in one polyhedra with the OBB of the other. If a triangle does not collide with the OBB, then there's no need to check it against all of the triangles in the other polyhedra. In this manner we reduce the problem to two sets of triangles that actually may collide. Now we need to walk through these lists and compare the triangles against each other.
To do this comparison we use the TriTriCollision function. This function will be explained in detail below, but at this high level point it's worth noting that it is actually only half of the solution. A full implementation would find the contact point and the contact normal. However we actually only need this info if the contact point we find happens to be the first point of contact of the triangle sets. So we defer the cost of finding this info until we think we actually need to find it. All of the info we need in order to find this is stored in the CollisionInfo structure that was pass in.
If the TriTriCollision function returns true then the 2 triangles do collide. There are 2 scenarios for a collision. In a perfect world the collision info would be telling us that a collision is going to happen at some point in the near future. However we have to remember the imperfect penetrating case. If these triangles are penetrating the Collision info will report a contact time of zero. In this case we are building up a collision normal by averaging the normals of all of the triangles that have penetrated. This is an imperfect solution, I'm not really sure what the best answer is, but averaging the normals provides a good result. If the Report.ContactTime variable is not zero then we are in a situation where the tested triangles may be penetrating, or they may be colliding in the future. The first thing we want to do is figure out exactly where the triangles are colliding. We do this with the FindContactPoint function. This function is conceptually the second half of the TriTriCollision function. It consumes the stored data that the TriTriCollision function produced. It finds the collision normal and time of contact. If the contact time turns out to be zero, then the triangles are penetrating and we need to store the normal so we can begin to find the average normal. If the time is greater then zero then the normal is the separating axis that collided last.
We work through this loop until we have checked every triangle against every other triangle. When we are done if we have found no collisions then these objects do not collide and we return false. If we find collisions then we normalize the collision normal and return true.
This function applies the method of separating axis to a pair of Oriented Bounding Boxes. The inputs are:
- OBB1 and OBB2: the two bounding boxes you want to compare.
- VelocityDiff: the relative velocity between the two OBBs.
- Elapsed: elapsed time (in seconds).
This function is conceptually really simple, it just does the separating axes thing. It's complex in this case because I use all the optimizations laid out in David Eberly's paper "Dynamic Collision Detection using Oriented Bounding Boxes." If you look through the paper you'll see I pretty much just copy and paste what he explains. If you want to be less efficient and more clear about it then you can replace it with a more cut and dry check of every potential separating axes with the OBBs.
This function is pretty much the same as OBBOBBCollision except it checks an OBB against a triangle.
- OBB: input OBB.
- Triangle: the input triangle.
- VelocityDiff: relative velocity
- Elapsed: elapsed time (in seconds)
Follows exactly the same mold as OBBOBBCollision except we're checking triangles against OBBs. This is handy when we have 2 convex polyhedra that may be colliding. It would be expensive to test every triangle against every other triangle. However testing all the triangles in object A against the OBB of object B will return a reduced set of triangles to test. We use this trick in PolyPolyCollision.
If it weren't for the optimizations this would be a cut and dry triangle separating axes test. However the optimizations make it a bit hard to follow, so I'll lay it out here. The input:
- Tri1 and Tri2: the two triangles we want to check for collision.
- VelocityDiff: relative velocity between the two triangles.
- Elapsed: elapsed time (in seconds).
- MaxTime: any collision found after this time is dissregarded as no collision. In practice this value is set to the minimum collision time for the convex polyhedra
- ProjectionReport: These values are used to find the contact point later (if it's needed).
Using the method of separating axes it's pretty easy to figure out if two triangles collide, and at what time. Finding out exactly where they collide starts to get computationally expensive. Since we are only interested in the first contact, it makes no sense to find every contact point. So this function figures out whether or not the two triangles collide, and at what time. It also stores some of the info it found along the way. If it turns out that this particular collision is the first one, then this info is used later. It also uses some optimizations that I'll now explain. The major part to consider is the cheats used to find projection information of a triangle along various vectors. In an unoptimized approach you would simply take the dot product of the three edges against the separating axis you are testing. However you can quickly see that this is a waste of time if the axis happens to be the triangle's normal (in which case all three points project to the same point along the axis). Similarly you can apply this kind of thinking to find optimizations for all the points. Or at least David Eberly can, and that's exactly what he did in his paper, "Dynamic Collision Detection using Oriented Bounding Boxes". Please give that a read if you're interested in a more mathematical proof. I use the optimizations he lays out to find the projections of the three points, and then I pass those values to the StoreTriangleProjectionInfo function. That function is a helper function so I won't be giving it its own section. Basically what it does is take the values I pass it, and store those in the TriangleProjectionInfo structure. This function sorts and stores the three triangle indexes, as well as recording the min and max values. It also (and most confusingly) stores information about how the triangle is projected onto the axis. There are 4 possible options as laid out in the ProjectionType enumerated type:
- ProjConvergence: all 3 points project to the same point
- Proj2Min1Max: 2 points project to a minimum, 1 projects to a maximum
- Proj1Min2Max: 1 point projects to a minimum, 2 project to a maximum
- ProjDivergence: all 3 points project to different points
The Min and Max data is needed right away in order to figure out whether or not the triangles collide (indeed it's just the min and max projections of the triangle on the separating axis). The other data is only necessary if these triangles turn out to be the ones that collide first, and that particular axis happens to be the one that is separating for longest.
In any event, once the triangle has been reduced to a TriangleProjectionInfo structure, I then pass those structures on to the TriangleProjectionCollision function to see if they intersect along that axis. If they do intersect then the function will return true. The function will also return the time of the intersection if that time is greater then the time passed in. This sounds confusing at first since we're trying to find the first contact time. However the method of separating axes says that if there is no collision on an axis, then there is no collision. So the first time of contact is the first moment when there is intersection on ALL of the axes. This means that the greatest time is the one we're interested in. If this time has changed then we need to store the current axis in the ProjectionReport. This is what will be used later to find the contact point (if indeed this turns out to be the first contact point).
This is simply a helper function for TriTriCollision. I won't go into a detailed explanation. It's given the three points of the triangle projected onto the vector. It needs to sort these points and store some into about the projection into the TriangleProjectionInfo structure. It should be pretty easy to follow.
This is also just a helper function for the TriTriCollision function. Given two projections and the speed (all along a vector) it will find the time of contact (if that time is greater then the passed in time) and information about which side the second triangle is on. I'll step through the first half here. If the max value of Proj2 is less then the min value of Proj1 then Proj2 is to the left of Proj1. If the speed of Proj2 is negative then it is moving away (to the left) and there is no chance for a collision. If it is moving towards Proj1 then I find the distance between them and divide by the speed to get the time it will take them to collide (simple v=d/t thing). If this time is greater then the CollisionTime I will update the CollisionTime.
Find the actual point of contact between two triangles.
- Tri1 + Tri2: The two triangles that are touching.
- Proj1 + Proj2: The projections of those triangles on the axis of intersection (as found in our TriTriCollision function).
- V1 + V2: velocities of the two triangles.
- SideInfo: Whether Tri2 is to the left or right of Tri1 (along the axis of intersection).
- ContactTime: The time of contact (as found in TriTriCollision).
- Point: What we're trying to figure out, the point of contact.
This function is a really important one. It is called from the PolyPolyCollision function only when we have found that two triangles are intersecting and we suspect they may be the first contact point. You will notice the comment above the function, which I will expand on now. There are many different ways in which 2 triangles can collide. A point from one triangle can hit the face of the other. An edge from one triangle can hit an edge of the other. Many of these collision types are reduandant. Consider the case of an edge of one triangle hitting the face of a another. If the first triangle is smaller, and the entire edge fits in the face of the second triangle, then we also have 2 collisions where the end points of the edge collide with the face. If the first triangle is larger and the points at the end of the edge do not collide, then the edge will collide with the edges of the second triangle. You can see that an edge to face collision is not possible without other collisions happening at the same time. Therefore we do not need to perform the math to find it. If an edge and a face collide that is considered to not be a collision, because I know that at the same time there is either going to be a point to face collision, or an edge to edge collision.
With that in mind, let's look at how this function works. If SideInfo is SideRight it means that the second triangle is to the right of the first. If the projection info for the first triangle says that a lone point is to the far right, then that point must be the point of contact. In this case I just move the point to where it will be at the collision time given its current velocity. Similarly if the second triangle (to the right) has one lone point sticking out on the left side, then that must be the point of contact. If it turns out that the first triangle (on the left) has a flat edge colliding with the second triangle, and the second triangle also has a flat edge colliding, then this is an edge to edge collision. And we call the EdgeEdgeIntersection function to find the point of contact. All other combinations of points, edges, and faces are uninteresting to us when the the second triangle is to the right. When the second triangle is to the left then we run the same kind of checks but just reversing everything.
In the unfortunate case where we have an overlap then we need to find out where the two triangles collide. I use TriTriIntersection to help find this out. Since two triangles collide along a line, I just try to return a point halfway along the line.
The rest of this file is just helper functions to figure out where 2 lines or two triangles intersect. You can swap out my functions with ones that work better for you. I don't even understand the triangle to triangle intersection, but am deeply in debt to Thomas Moller for publishing it online.
In Summary...