Input Format and Manipulation

The input to any collision detection algorithm is a set of objects. The current implementation is restricted to triangles^A.1.

The usual mathematical description of a triangle is simply three noncolinear points. Rather than this, we use the indexed point list representation, common in computer graphics, shown in Figure . In this representation, a triangle's vertices are actually indices into a shared list of points.

Figure: The input data is a list of triangles and an array of points.

Because isolated triangles are rare, most points are shared between several triangles. In fact, most geometric models have, in total, about half as many points as triangles! Thus using the indexed representation often saves a substantial amount of memory^A.2, which tends to improve cache utilization and hence overall performance.

The indexed representation also allows us to store an extra property of triangles, the $prio$ field. This is the ``collision priority'', which is eventually used by the final collision detection scheme. To prevent duplicate collision checks, collision tests are only performed against objects with a lower priority. If every object has a different priority, this simply avoids duplicate collision checks.

Because objects with the same priority are never collided, we can also use the priority field to prune off unnecessary checks. For example, if we know there are no self-intersections in a rigid model, we can prevent the algorithm from ever colliding model triangles against one another by giving all the model's triangles the same priority. Or, if we aren't interested in collisions among ``static'' entities, such as trees and buildings, we can give all static entities the same priority. The RCB algorithm used includes an early-exit test if all a region's objects have the same priority.

Finally, note that the input consists of two arrays, each of which contain data of the same type. This makes bindings for other languages, such as C or FORTRAN, much simpler. In fact, the only difference between accepting C and FORTRAN triangles is that the point indices start at 0 in C, and 1 in FORTRAN.