Opposing Face Geometry
A Collision Detection Optimization Scheme
by Eli Kara

Abstract:
OFG presents a new method for collision detection optimizations by performing a simple pre-calculation on both input objects. It is possible to reduce the number of faces necessary to check for intersection dramatically, from an order of O(mn) intersection tests to an order of O(k²), or rather to a maximum of k² + 3k test operations, where k is a predetermined constant. The pre-calculation phase is of the order of O(m + n). Therefore, for increasingly complex convex objects, the OFG method saves more and more processing time. The method's downside is that increasingly complex objects might need a very high constant and small faces are less suited for this type of optimization. The method is much better for relatively low detail 3D objects.

Introduction

Collision detection is generalized as the means to detect whether any two objects in 3D space overlap. Over the years many models and ideas were suggested that attempt to either solve the problem entirely or approximate a solution. Of course, it has been shown that detecting collisions in a very accurate way is extremely computation intensive. Yet new ways and methods have been invented to optimize or accelerate the collision detection algorithms so those will be useable in real-time environments such as 3D simulations or 3D games. The method proposed here is called OFG and attempts to do the exact same thing - to optimize the collision detection algorithm by eliminating as many checks as possible.

This article assumes the reader knows simple vector notation and operations, namely the dot product and vector sizes.

The problem

In real life, collision detection is a fact, it's simply how things work. Objects cannot occupy the same space, at least not usually. However, when dealing with computer programs it is clear that it's impossible to simulate the detail levels of the real world. In computer simulations the only way to actually define a 3D object is by defining the points from which its polygons are made. Each of these points is called a vertex, in plural - vertices. Defining a 3D object using only points connected by lines is the only way to represent a 3D object in a way that allows real-time simulations. This method is of course only an approximation, but when there are enough polygons making up an object, the approximation is very good.

The representation of a 3D object is very simple. Vertices can be connected by lines to create closed shapes called 'polygons'¹(usually triangles). A collection of faces constitutes a closed 3D object and therefore the only information at our disposal for collision detection testing is the vertices information. The problem begins by trying to create a model for collision detection. It seems highly unlikely that objects collide at exactly their vertices, and this is logically correct as well. Consider two normal cubes the same size. The two cubes can collide in an infinite number of ways and orientations, even without their vertices touching each other's or any connecting line between vertices (edges)². What is more logical is that either edges themselves pierce the other object's faces, or some variation to that effect. The question then arises, how to detect faces intersecting each other? or better yet, how to detect edges piercing other faces?

Well, the good news is that there are already good ways of testing for edges piercing faces. The bad news is that representing complex 3D objects requires a great deal of faces to look reasonably well, and since detecting intersection in an accurate way is slow in comparison to other optimized methods, this creates a big problem. In this article we will assume that detecting whether two faces intersect is a problem solved in a reasonable way and hence this article will not deal with methods for detecting actual intersection of a pair of faces, which is the most elementary test. For convenience a few methods are given in the appendix but it must be clear that OFG is a method for optimizing the entire process of object to object collision tests by dramatically reducing the number of faces needed for testing.

Basic assumptions and the most general case

In order to simplify the problem some basic assumptions need to be made. Of course these might present some problems but it must be clear that the assumptions help solve the most simple case. Later on the algorithm will be improved to circumvent some of the problems arising from the assumptions.

The assumptions that we make are as follows:

• The objects that the algorithm is dealing with are convex³ 3D objects only. It is true that the algorithm will work for some concave⁴ objects but care must be taken⁵.
• Detection of any pair of faces colliding is a well-defined and solved problem.
• Both objects have a pre-calculated center point.
• The accuracy constant k is set to be (min/max estimates)
• Object A has exactly n faces while object B has m faces.

Under these assumptions, in order to detect a collision between objects, the most simple but inefficient method of checking every face in object A against every face in object B can be used. Actually, using the brute force method works for all types of objects, convex or concave. It makes no difference to the algorithm. For the brute force method therefore an order magnitude of O(nm) represents the algorithm's time complexity. The problem with this approach is obvious - detecting collision between complex objects becomes a very long operation. The more faces objects have, the more checks are needed. For two normal cubes, each with 6 sides (two faces per side, assuming each face is a triangle), the number of checks is: 12 * 12 = 144 tests between pairs of faces.

For two objects with 100 faces each, the number increases very fast: 100 * 100 = 10,000

For two objects with 200 faces each, the number increases again to: 200 * 200 = 40,000

It is clear that this method is highly inefficient when dealing with more and more complex objects.

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:

1. Optimization: check collision between object A's bounding sphere and object B's bounding sphere.
2. Find the closest k faces of object A relative to object B.
3. Calculate the geometric center of the new selection and the bounding sphere radius.
4. Find the closest k faces of object B relative to object A's new selection of k faces.
5. Calculate the geometric center of object B's new selection of faces and their maximal bounding sphere radius.
6. Optimization: check collision between spheres to determine if there is even a chance for face collisions.
7. Sort the two sets of faces by increasing distance (optional, might be replaces by a good insertion algorithm).
8. 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(k²).

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:

1. 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:
2. 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.
3. 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.
4. 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.
5. 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:

1. 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:
2. 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.
3. 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.
4. For each , find the vector's size: and store into selection*.
5. 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(k²). 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

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:

1. 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).
2. Find the closest object in collection B relative to the object found earlier in collection A.
3. 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:

1. Calculate the translation of object A after a time unit elapses.
2. 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.
3. 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.
4. 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.
5. Test the original faces in selection A against the selection in B, as was intended in step 8 of the OFG algorithm.
6. 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:

1. 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).
2. 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.

Appendix A - Detecting collision between two faces

Up until now the problem of testing for collision between a pair of faces was a well solved problem. That meant that the algorithm assumed detecting if two faces intersect is a black box operation, the details weren't important for the algorithm itself. Still, in order to create a solid implementation of any collision detection scheme, the problem of intersecting faces must be solved. In this section two methods are presented that attempt this.

The first method is called the intersection-based collision detection and is basically an accurate way of detecting whether any two faces intersect each other. Other methods exist as well, however, the second method presented here is a hybrid method that incorporates bounding spheres and some basic geometry testing.

Intersection-based collision detection

The problem of collision detection between faces can be broken down to two stages. A well known fact is that any two planes that are parallel don't intersect each other. A plane of course is a flat, infinitely thin, infinitely long surface in 3D space. Unless the planes that contain the faces are parallel, those two planes are going to intersect each other. The first stage would be to detect if any edges of the first face intersect the plane of the second face. That ensures that the first face at least intersects the plane that contains the second face, but it is not sufficient in order to determine if the first face intersects the actual second face. This will be dealt with in the second stage.

In order to determine if any edges in the first face pierce the second face's plane, the vertices making up the edges must be examined. For simplicity, if two points that define an edge fall on one side of the plane (containing the second face), the edge does not pierce that plane. Then, generalizing for the entire face, if all edges don't pierce the plane, the face does not pierce the plane. If any edge pierces the plane it is assured that at least one edge pierces the plane. For convex polygons there are exactly two edges piercing the plane.

The only thing left to solve is how to find whether an edge pierces the plane. It so happens that all points in space that satisfy the following equation fall on the plane:

This might be familiar to you. It is called the plane equation. Any point that lies on the plane itself will evaluate the equation to be true. It so happens that any points on one "side" of the plane produce a positive sign (instead of 0) and all the points on the other "side" produce a negative sign. Therefore, if an edge is defined by two points (vertices) and solving for both vertices gives the same sign, the edge is definitely not piercing the plane. The logical extension to this is to check all edges against the plane. The check becomes very simple:

• Solve the plane equation of the second face for each vertex in the first face. If all vertices produce the same sign, the first face definitely doesn't pierce the plane in question. Creating the plane equation is easy given two vectors on that plane (three vertices of one face can give two vectors). If any vertex gives the other sign, there is a possibility of collision.

If there was any piercing by any edge, the second stage should be used to actually detect whether the edges actually pierce the second face itself, unlike the plane tested against in the first step. Actually, this step is all that is needed in order to determine if two faces intersect. However, the second stage is much slower in comparison with stage one. Stage one can be used as an optimization to rule out any faces that definitely don't collide.

Because this algorithm deals with convex polygons (faces actually), this stage will assume the same. Since step one stopped when an edge that pierces the second plane was found, and there are actually two such edges (again, for convex polygons such as triangles), there must be exactly two intersection points between the face and the plane of the other face. Using the plane equation and solving for the x,y and z coordinates of the point that represent the intersection between the plane and the edge it is possible to find those two intersection points. Those points are naturally on the plane itself.

Once two intersection points are found, in order to determine whether the edge pierced the second face itself, at least one of the points must be within the second face!

What is left then is to determine whether a point is within a convex polygon or not. If one of them is within it, there is a definite collision. If both are not within it, there is definitely no collision. There is one very simple solution to this problem, called the half-space method. The halfspace method is a method to determine if a point lies within a convex polygon. For 2D polygons this is simple. Using the line equations of the edges and solving for the point gives either 0, a negative sign or a positive sign, just like in the previous step. However, our edges are vectors in 3D space so this doesn't apply here.

What can be done instead is create a plane that is perpendicular both to the normal of the face and the edge vector. That plane divides space into two parts and therefore the point must lie either on it, or on one of its sides. The same logic from the previous stage applies here as well:

• Calculate the intersection points of the edges found piercing the plane in stage one using the second face's plane equation.
• For each edge in the second face, take the cross product of the edge vector with the normal to the face, giving a perpendicular plane.
• The points must lie either on the plane or on either side. Using the same logic as in stage one can determine this for each edge plane.
• If the point lies in the same part of space ("side") for all planes corresponding to the edges of the face, the point is within the face and therefore a collision has occurred
• If both points lie outside the planes of the edges (not all signs are the same for each point checked against the edge planes), there is definitely no collision.

Hybrid collision detection between two faces

This method is a proposed method that approximates intersection between a pair of faces. The idea is to find a bounding sphere for both faces. If the bounding spheres intersect (an easy and fast check), there is a need for a better check. If the bounding spheres do not intersect, there is definitely no intersection.

For intersecting bounding spheres, there is the possibility of collision. Consider using the logic in the previous method's stage one to determine whether edges on the first face pierce the second. Although this alone does not guarantee collision of course, coupled with the bounding spheres check it gives a reasonable chance for collision. That is, if the spheres collided AND an edge was found to be piercing the other face, most chances there is a collision. Of course, this method is only an approximation and will not give accurate results such as those provided by the intersection method. However, this method is by far much faster than the intersection based method.

Generally, the smaller the faces, the better this method works. This is because when the faces are smaller, there is less and less "free space" within the sphere. Less free space that can generate a collision between spheres but might not actually generate a collision between the faces themselves.

Appendix B - Determining k, the accuracy constant

The reasoning behind assigning a proper k value are totally up to the engine in question. In most cases in a normal 3D surface, each vertex will share a maximum of four polygons (each made of two triangles). Of course, there are cases, such as the tip of a pyramid with n sides that do not satisfy this condition. For the first case, a normal 3D surface, each vertex can be shared by 8 triangles at most and 4 at the very minimum. Therefore those values are chosen as the default accuracy range for most purposes. Assigning a different value might serve different types of geometry better though, it has to be considered carefully.

For the cases where a vertex does not share only 8 triangles (such as the tip of an n-sided pyramid), it is a definite fact that if the vertex falls within another 3D object, all of the n-sides of the pyramid will intersect the other object. Therefore, any value for k that is one or more will suffice for this type of degenerate case. It happens that any 3D geometry can be represented either by the former representation or the latter. The latter has no bearing on the assignment of k. The former has and it has been shown that a value of 6 is the best average while 8 should give good accuracy.

About this document...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The translation was initiated by Lord Soth on 2004-01-05

Footnotes

Discuss this article in the forums

Date this article was posted to GameDev.net: 2/19/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Collision Detection
Featured Articles

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!