sponsors gamedev.net search:

The Opposing Face Geometry algorithm OFG is a method that at its basic level attempts to find in the simplest way the closest geometry elements two objects have. The algorithm attempts to find the closest faces both objects have in relation to one another while the number of desired faces to be found is determined by the accuracy constant k. The OFG method consists of the following steps, each described in more detail in the following sections: Optimization: check collision between object A's bounding sphere and object B's bounding sphere. Find the closest k faces of object A relative to object B. Calculate the geometric center of the new selection and the bounding sphere radius. Find the closest k faces of object B relative to object A's new selection of k faces. Calculate the geometric center of object B's new selection of faces and their maximal bounding sphere radius. Optimization: check collision between spheres to determine if there is even a chance for face collisions. Sort the two sets of faces by increasing distance (optional, might be replaces by a good insertion algorithm). Test the two sets of faces against each other, starting with the closest pairs of faces. Analysis: It's clear from the above steps that there are some preliminary preparations before any actual checks are done between faces. The time complexity of steps 1, 3, 5 and 6 is rather fixed: 2 operations, 3k operations, 3k operations and 2 operations again respectively and therefore contribute only little overhead to the entire process. Step 7 is basically a sorting operation for an array of k elements. If care is taken to insert the elements in an almost-sorted fashion, it is possible to use sorting algorithms that operate at almost O(n) on each of the arrays, or better. Since n=k in this case, O(2k) can be added to the overhead of the algorithm however up until now the overhead presented by these steps is rather constant no matter the complexity of the objects and is said to be geometry independent. It will be shown that step 2 requires a time complexity of O(n) while step 4 requires a time complexity of O(m). Therefore the geometry dependant time complexity (and hence the most important one) is O(n+m). As for step 8, the worst case scenario of testing k faces against k faces is O(k2). Note: The accuracy constant k plays a major role in the OFG algorithm. The higher k is, more faces are selected for testing and therefore more accurate collisions can be detected. Typical values are from 4 to 8 faces and the reasoning for this is explained later on in the appendix. Step 1 - Checking for the possibility of a collision There is no real need to test any faces at all if the objects are far away from each other. This is logical but presents a problem: since objects are almost always non-spherical, one has to define a range from which no face testing will be performed and for a shorter range, face testing will be performed. But if the objects are non-spherical, what kind of range can be used that will also be efficient enough? Well, the answer is of course, compounding each of the objects within their own bounding spheres. If the spheres don't overlap, it is certain that there is no collision. If the spheres overlap, there is the possibility of a collision and tests must be performed. It is quite simple creating a bounding sphere for each object and since a sphere is always the same when rotated (invariant when rotated), calculation of the bounding sphere and the object's geometrical center can be done at the initialization stage, usually when objects are loaded. Calculating the geometric center is exactly finding the average of all the vertices that comprise an object: This relation gives the X coordinate of the object's center point by summing all X coordinates of all vertices in the object. Notice that in this relation n is NOT the number of faces but the number of vertices of the object. The same calculation can be done for the Y and Z coordinates. The weight functions W can be used to give different weights to vertices but in order to find the geometric center it is usually sufficient to use 1 for any W of any vertex. After the center is found it is simply a matter of iterating the vertices again and finding the farthest vertex from the center and using that distance as the compound radius. Step 2 - Finding the closest k faces of object A relative to B The first step in the OFG algorithm is to find the closest geometry object A has in relation to object B. In order to do this in an efficient manner, one very important assumption must be made: Object B can be considered as a point object located at its center (object centers have been shown in step 1). This assumption is not a simple one, there is a lot of reasoning behind it. Mainly, in order to find the closest faces object A has relative to B, it is obvious that distances of faces must be considered. The problem is that finding the smallest distances between every face in A and every face in B has a time complexity of O(nm), just as the easiest brute force method presented as the general case. Of course, this will not do. The idea is to attempt to find distances of all faces in object A, relative to only one geometry property in B. That way, checking every face in A against only one geometry property of object B yields a time complexity of O(n), where n is the number of faces in object A. The question then arises: what kind of geometric property an entire object has that can be used to represent the entire object? Physicists sometimes assume very distant objects are a point object when trying to simplify problems in physics because when an object is very far, the contribution from any irregularities in the object's geometry are negligible. For our purposes, this assumption is correct for any distance, mainly due to the fact that this algorithm deals strictly with convex 3D objects. For that reason, the closest faces an object can have to another object are the faces closest to the other object's center. It is always true that if a certain face is closer to object B's center than another face, it is generally closer to object B than the other face. Taking the 3 vertices (or more, depending on the engine involved) that constitute a face, it is possible to find that face's center in exactly the same way as finding an object's center. Using the center coordinate coupled with the two object's positions it is possible to automatically calculate a vector from the center of any face to the center of the other object. In summary, the steps necessary to find the closest k faces of object A are: Using both object's positions, calculate the relative position vector. Assuming is the center of object A (x,y,z - a 3D vector) and the center of object B, the vector connecting the center points is then: Start looping through all faces of object A, find each face center relative to object A's center. Total time complexity is O(n). It takes less operations to calculate the faces centers than to do it in the beginning and apply transformations on them. For each face, find the vector connecting its center with object B's center, using the simple relation: , where is the vector connecting the center of face i with the center of object B, the relative positions of the two object's centers and is the position of the face relative to object A's center (the object it belongs to). Of course, i = 0,1,2,3...,n. For each , find the vector's size: and store into selection*. Of course, the size itself is irrelevant, as is the direction of the vector. The only important quantity is the vector's size squared. Note that there is no need to take the square root because if a certain face's squared vector size is larger than another face's squared vector size, the same holds for the actual sizes themselves. Depending on the insertion technique used to insert the distances (squared sizes of the relative position vectors), find the smallest k distances which should be straightforward if the insertion was done in an efficient way, and remember their corresponding faces. * Note: Several methods are available that create a semi-sorted array of k elements. Figure: Finding object A face vectors relative to object B's center Step 3 - Calculate the geometric center of the selection and its bounding sphere After finding the closest k faces of object A relative to B it is important to be able to do quick tests in order to check the possibility of a collision between faces. For that reason and another reason outlined in step 4, the center of the new selection must be found and its bounding sphere. Assuming the previous step has found the necessary k faces, finding the center is as simple as finding the average of all the selected faces centers. Remember, the selection itself is just a means to remember which faces are the closest, and each face has its center coordinate and a vector connecting the center of the face with the center of object B. Therefore we have: Where is of course the center of the new selection and is the position of the i'th face center relative to the object's center (as always). The resulting vector is the position of the new selection center relative to our object's (A) center. Once the center is found, the farthest vertex from the new selection center gives the bounding sphere radius. This is a preparation phase for a later step where the possibility of face collision should be tested. Step 4 - Finding the closest k faces of object B relative to the new selection This part of the algorithm is very similar to step 2 in that it finds the closest faces in B relative to some point. However in this case the point that distances are calculated to is NOT object A's center. Rather, taking the center of the new selection found in step 2 and calculated in step 3 is better. True, for truly convex objects such as spheres there is no difference. Finding the faces in B that are closest to the generally closest faces in A yields better results. Not only is that more accurate but it helps the algorithm deal with objects that are not truly convex but only close to being convex. Since this step is so similar to step 2, only the summary of the steps needed is presented: Calculate the relative position vector between object B's center and the center of the new selection of k faces found earlier. Assuming is the center of object B and the center of the selection in object A, the vector connecting the center points is then: Start looping through all faces of object B, find each face center relative to the center of the selection in object A. Total time complexity is O(m). It takes less operations to calculate the faces centers than to do it in the beginning and apply transformations on them. For each face, find the vector connecting its center with the center of the selection in object A, using the simple relation: , where is the vector connecting the center of face i with the center of the selection in object A, the relative positions of the center of object B and the center of the selection in object A and is the position of the face relative to object B's center (the object it belongs to). Of course, i = 0,1,2,3...,m. For each , find the vector's size: and store into selection*. Depending on the insertion technique used to insert the distances (squared sizes of the relative position vectors), find the smallest k distances which should be straightforward if the insertion was done in an efficient way, and remember their corresponding faces. * Note: Several methods are available that create a semi-sorted array of k elements. Step 5 - Calculate the geometric center of the new selection and its bounding sphere In essence, step 5 is identical to step 3 only it operates on the newly selected faces in object B. Averaging the faces with the following relation: Will give the center of the newly selected faces in object B relative to B's center naturally. Once the bounding sphere radii of both the selection from object A and B are known it is a simple matter to accomplish the next step, step 6. Step 6 - Test collision between the two selections' bounding spheres The last step before any accurate collision tests is the bounding sphere test for the two selections. Up until now the only test done is the bounding sphere test for the two objects that determine if there is a chance for a collision. Now that there are two sets of faces that have a bounding sphere, it is a simple matter of testing whether or not the spheres intersect in order to determine whether real geometry tests should be performed. Denoting with the center of the selection in object A and the center of the selection in object B, the radii as and respectively, in order to determine if there is intersection the following relation holds: What this relation means is that if the size of the vector that connects the centers, squared, is smaller/equal to the sum of the radii, squared, there is the possibility of a collision between faces in the selections. Actually, the real check is against the square roots of both expressions but it holds for the squares too. There is no need to waste valuable processing time in order to perform two square root operations. The size of the vector is naturally a dot product of it with itself. Step 7 - Sort the two selections in ascending order This step can be omitted if wanted but it can help gain a small performance boost. Assuming two selections exist with k elements in each (the elements being the faces to be checked), this step just sorts each of the selections, from the face with the smallest distance to the face with the largest distance. The order of each sorting operation can vary depending on the algorithm and the insertion technique used earlier when building the selection sets. If the selections are almost sorted, even a simple algorithm such as bubble sort can work in a reasonable time (bubblesort works at O(k) for almost sorted arrays). The algorithm to choose from is really up to the programmers implementing this step. It depends entirely on the insertion method used earlier and there are several good sorting algorithms. Step 8 - Perform intersection tests on the two selection sets If the algorithm made it this far, it is now time to examine the geometry itself for collision. As input, there are two selections of k faces each, the closest faces between the two objects. Under the assumptions made earlier, the problem of testing for intersection of a pair of faces is a well solved problem (again, see the appendix for ways of doing this), therefore in this subsection a summary of the testing method is described. As mentioned earlier, k can be between 4 and 8. It is possible to examine all the faces in one set against all the faces in the other set. After all, there are k faces in each set and there are two sets, thus the worst case time complexity is O(k2). This holds true no matter what but certain optimizations on the order of the tests can make a difference. Problems with the basic OFG algorithm

Contents   Introduction   The Opposing Face Geometry algorithm   Problems with the basic OFG algorithm   Appendices   Printable version   Discuss this article