Problems with the basic OFG algorithm
The OFG algorithm suffers from three very serious problems:
- The algorithm supports detection of mostly convex objects. Some concave objects will work as well but there are bound to be degenerate cases that cause the algorithm to fail. It hasn't been proven mathematically that there are any cases that will cause failure but assuming there aren't is not a good idea.
- Moving objects in computer simulations are by nature problematic because time in computer systems is discrete. In numerical approximations, time is discrete and therefore object positions are calculated in time steps and are really "teleporting" in small steps to create the illusion of motion. The problem arises when the velocity of objects is very large and/or objects are very small. It is quite possible that an object will be close to another object while not colliding, yet at the next time step will be half intersecting with the other object. The problem is then what faces to test. After all, the "closest" faces the object previously had are now inside the other close object. Even more so, it's possible that if the velocity is large enough, the object might pass right through the other object without any way of us detecting this.
- In a similar fashion, rotating objects pose another problem. If objects have an angular velocity (or momentum, whichever you prefer) it's possible that before the collision some faces are the closest selection while after a small time step, other faces should be the closest selection. For example, consider a normal cube floating above a table at a small height. The closest faces to the table are naturally the two faces (triangles) that comprise the base of the cube. If the cube is about to rotate 45 degrees in one time step (very fast rotation) it wouldn't be correct checking the base of the cube against the table.
In the following subsections some solutions are presented that deal with said problems.
Solving the concavity problem
Since some objects are almost convex and some are not even close to being convex, a method is required that can handle these objects. It just so happens that concave objects can be represented by a collection of convex objects. This is implied since any object can be approximated by triangles, which are convex polygons. If there is any doubt about whether an object will cause problems with the OFG algorithm, it is best to represent it using two or more convex objects.
This presents another slight difficulty: if an object is really a collection of objects, which object's geometry is used when building the selection set?
Well, the solution to this lies in the OFG method itself, but at the object level. Just as faces, it is possible to generalize the algorithm for objects. For example, if two concave objects exists that are made out of an assortment of convex objects each, consider the following scheme:
- Find the closest object in collection A relative to the entire collection B. This implies each object in A has to have a center (this is mandatory for OFG anyway) and the entire collection has to have a center as well (averaging the centers of the objects, should be a part of initialization).
- Find the closest object in collection B relative to the object found earlier in collection A.
- Feed the two objects found to the OFG algorithm.
Solving the discrete time problem
A technique exists that makes this very easy to accomplish. Consider a 2D face passing through a wall straight to the other side. This is only possible in a computer simulation if the face is moving fast enough. If it is, it can find itself on the other side of the wall after a small time unit.
Consider connecting each vertex that comprise the face with the same vertex on an exact copy of the face but on the other side of the wall. Not only that, the copy face's position is in fact the position of the original face at the next time step (after one time unit has elapsed, this is easy to calculate). With this in mind, each pair of "connected" vertices make up an edge. Then, testing the new virtual edges created for intersection with the other object (in this case, the wall) will determine if there is a collision.
Actually, this is not enough. The following steps are in order:
- Calculate the translation of object A after a time unit elapses.
- Feed the two objects into the OFG algorithm, forgoing step 6 completely and without the bounding sphere calculations in steps 3 and 5. Also, there is no need to perform step 8 (the final step) of the OFG algorithm just yet.
- Connect each vertex in selection A with the same vertex on the virtual selection of A that is translated by the amount calculated in step 1. This gives a vector that represents the edge to test against object B.
- Test the newly created edges against the selection in object B found by the OFG algorithm. They are the most likely to be intersecting object B.
- Test the original faces in selection A against the selection in B, as was intended in step 8 of the OFG algorithm.
- Test the translated virtual selection of A against the selection of B using step 8 of the OFG algorithm.
Naturally if any collision is found the entire process is stopped and action is taken. However, since objects are "teleporting", it isn't clear which faces should have collided provided time was not discrete. Figuring out which faces collided will help determine what action to take.
There are generally two ways of solving this, others may exists:
- Using the translation found in step 1 earlier and given that it's easily possible to calculate the relative velocity of the two objects, it's possible to estimate the time of collision (therefore obtaining the delta time needed for the objects to collide).
- Moving half of the distance (half a time unit) and checking for collisions. If collision occurred, great. If not, move another half, so on and so forth. This has a time complexity of log(n) times of performing all the collision tests.
Figure: One face of the selection in A translated after one time unit.
These two methods should only be used in case a collision occurred in between time steps. If a collision occurred with the original selection or the virtual selection (the beginning position and the ending position respectively), there is no need to interpolate the collision time since the intersecting faces are known.
Solving for rotating objects
For the general case of rotating objects, the same approach as in the discrete time solution can be applied. Instead of only translating the vertices and using them to create virtual edges, rotating and then translating the vertices solves the problem. Instead of having the selection in its starting position and ending position, have the virtual selection rotated before translation so it'll be rotated at its new position. Vertices are connected in exactly the same way and figuring the moment of collision if one occurred works in exactly the same way but with rotation in mind.
Appendices
|
|
Southwest Gaming Expo
