Game Development Reference

In-Depth Information

Some of the primitive collisions have completely different algorithms that can

determine whether there is a contact without generating the contacts themselves. If

such an algorithm exists and it is fast enough, it can be useful to call it as a first stage:

if (inContact())

{

findContacts();

}

These are the collision detection algorithms often found in books on game graphics.

In many cases, however, the work that the quick check would have to do is the

same as required during contact generation. The speed-up of doing both would be

minimal for the number of times we'd get a no-contact in the test. In these cases the

contact generation algorithm can be used on its own.

13.3

P
RIMITIVE
C
OLLISION
A
LGORITHMS

Each of the collision algorithms in this chapter checks for contact and generates con-

tact data structures for different combinations of primitives. Some of the algorithms

are guaranteed to return only zero or one contact (the sphere-sphere collision, for

example). We could have these algorithms return the contacts directly.

Other algorithms can return zero, one, or several contacts. In this case we need a

more flexible way for the algorithm to return the contacts it generates. The simplest

way to do this is to start with an array or list of possible contacts. This array is then

passed into each contact generation routine. If the routine finds contacts, it can write

them into the array.

In the code on the CD I have encapsulated this process into a class:

Excerpt from include/cyclone/collide_fine.h

/**

* A helper structure that contains information for the detector to use

* in building its contact data.

*/

struct CollisionData

{

/** Holds the contact array to write into. */

Contact *contacts;

/** Holds the maximum number of contacts the array can take. */

unsigned contactsLeft;

};

Each contact generation routine has the same form: