The collision detection module is restricted to dealing with polygonal objects --- objects that are made up of convex polygons. This restriction was chosen because of a number of factors, including the widespread use of polygonal representation for modelling objects in computer graphics, the ability to represent a wide variety of objects (although it isn't necessarily the most efficient representation), and the time restrictions of this project. Faster collision detection could have been achieved if objects had had the further restriction placed upon them of being convex polyhedra, and techniques such as those by Baraff [Bar90] or Moore [MW88] could then be used. Concave polyhedra can be broken down into convex polyhedra, but it can be difficult and the restriction would probably be too limiting.
The collision detection module can be used in two ways:
, the module will return the point of time in the interval at
which there is either only contact, or when no objects are touching.
The returned information includes the points, lines, or areas of contact.
The first method of usage is provided by calling the function
test4Intersection(), while the second is provided with
collisionDetect(). collisionDetect() follows the basic loop
of the left side of figure 
, and makes use of
test4Intersection() to carry out the object testing.
collisionDetect() is passed the database of objects, and each object
has specified a transformation to the global frame for the time t = 1. The
collision detection module assumes that there is no interpenetration for
, and that the objects move in small enough increments such that no
objects can completely pass through each other without a collision being
detected. This means that the movement of the objects must be of a small size,
relative to the size of the smallest polygons that make up the objects. If no
object interpenetration is detected at t = 1 then none took place during the
time interval, so the module can return with a time of t = 1 and also the
contact information (if any). If object intersection is found, then there
must be a point of time within the interval where things are just in contact,
so a guess at this time is made, the state of the database is backed up to
this time, and intersection testing is carried out again. This process of
guessing the time of contact, changing the state of the database, and testing
for intersection continues until the time is found where there is just contact.
Prediction of the time of contact is made using bisection: the predicted time is set as the median value of the current time interval, and if incorrect, the upper or lower interval is chosen as the next interval to look at, depending upon whether the result of the intersection test was interpenetration or no contact.
Objects are defined as type ObjNode (refer to appendix
for
this and other definitions) and contain, amongst other information, a pointer
to the object's global transform, a pointer (ctrans) to a function
which is used to
update the global transform, and a pointer to information to pass to this
update function. When the collision detection module needs to set the state of
the database at a certain time 
, it goes through all the objects, and
calls all the update functions with 
as one parameter, and the object's
info pointer as the other. The update function should set up the
object's transform for 
. If an object's transform doesn't change
during the time interval, then the pointer to the update function will be
NULL, and the global transform isn't changed.
The basic steps the module goes through to check for collisions, follows the method presented by Garcia-Alonso [GASF94] and are as follows: