Static Object-to-Object Collision-Detection Techniques

As stated earlier in this chapter, there is no universal or single generic technique for computing object-to-object collisions. Here we present a collection of the most used and most useful collision-detection techniques for 3D games using the basic set of primitive geometries shown in Figure 16.7. This is by no means an all-inclusive set because there are uncountably more possible combinations and choices for primitive object types, but they become ever more specialized and less generally useful. In any case, this is an excellent foundation for understanding basic collision techniques and developing end solutions beyond this set.

Figure 16.7: Collisions object types.

These will be additionally divided into related sections, bundled by techniques and solution complexities.

Foundation Collision Type Definitions

The first thing in any geometric-based algorithm is to decide on the data representation for that geometry. Some types have an obvious or common way of representation, such as a sphere with a center and radius, and others may have several options, such as axis-aligned bound boxes using min/max points or a center point and half-height and half-width, for example. Sometimes committing to one representation may make a later collision algorithm more expensive to compute. Usage will help dictate the design, and without prior knowledge of how the type will be used, developing an optimal solution is often error prone. The implementations chosen here lend themselves to efficient performance while attempting to stay simple to understand. For a final project, the developer may choose to use an alternative representation if there is a particular advantage to do so.

Table 16.1:   COLLISION OBJECT TYPE TABLE

	Point	Ray	Sphere	AABB	Cylinder	Plane	Triangle
Point	C	C	C	C	C	C	C
Ray	C	LL,A	C	C	LL,A	C,I	C,I
Sphere	C	C	C	C	C	C,I	F
AABB	C	C	C	C	C	F	A
Cylinder	C	LL,A	C	C	LL,A	A	A
Plane	C	C,I	C,I	F	A	X	A
Triangle	C	C,I	F	A	A	A	A

Legend

C = Collision detection

I = Intersection

A = Fallback test—can use AABB, Sphere, or Segment tests as approximations

LL = Rare case, uses 3D line-to-line intersection; see resources.

To begin, let’s first define some example objects. We will attempt to use classes from the previous math chapter where it makes sense.

For a test point or vertex, we will simply use the Vector class.

For an axis-aligned bounding box, we will choose a min/max point representation where the two points define the limits of the space that AABB is meant to contain.

Here is the minimal new class, AABoundingBox:

/**  * Axis-Aligned Bounding Box.    * The min and max fields are public so they can be set and read directly.  */ public class AABoundingBox {     public Vector3f max = new Vector3f();     public Vector3f min = new Vector3f();     public AABoundingBox()     {     }          public void setMinMax( Vector3f _min, float _max )     {         min.set( _min );         max.set( _max );     }     public void translate( Vector3f pos )     {     max.add( pos );     min.add( pos );     }     public String toString()     {         return min.x + " " + min.y + " " + min.z + " " + max.x + "         " + max.y + " " + max.z;     } }

The typical accessor setMinMax() method implements a value copy to set the min and max points. However, because the min and max points are public, they can be set directly by passing the accessor. This is intentional for maximum easy access and for the possibility of sharing points with target objects. This situation could be a problem if the user were to set them to NULL, which will cause errors in most routines because normally they would not be checking for NULL. A production class may prevent this access and additionally check for passed in NULLs for safety if the application has no need to set the min and max points directly.

There is also a convenience method for translating the box, useful for moving along with the object it is meant to contain.

And finally, the usual toString() method is included.

For a sphere we’ll use the center and radius representation, again using Vector3f.

The sphere fields are public and also have accessors that perform copying as with the AABoundingBox. The same caveats apply.

And, of course, toString() is included.

/**  * Bounding Sphere.    */ public class BoundingSphere {     public Vector3f center = new Vector3f();     public float radius = 1.0f;     public Sphere()     {     }          public Sphere( Vector3f c, float r )     {         center.set( c );         radius = r;     }     public void set( Vector3f c, float r )     {         center.set( c );         radius = r;     }     public void setCenter( Vector3f c )     {         center.set( c );     }     public void setRadius( float r )     {         radius = r;     }     public String toString()     {         return "Sphere < " + center + " Radius " + radius;     } }