CInDeR : collision and interference detection in real time using graphics hardware

Abstract

Collision detection is a vital task in almost all forms of computer animation and physical simulation. It is also one of the most computationally expensive and therefore a frequent impediment to efficient implementation of real-time graphics applications. s We describe how graphics hardware can be used as a geometric co-processor to carry out the bulk of the computation involved with collision detection. Methods for performing out this task are described in the context of two different forms of collision detection and using two separate portions of the hardware graphics pipeline. We first demonstrate how a programmable vertex engine can be used to perform all of the computation required for a closed-form particle simulation in which the particles may impact with a variety of surfaces. The technique is used for both visual simulation and to report collision data back to an application running on the computer's CPU. The second form of collision detection involves using frame buffer operations to implement a ray-casting algorithm which detects static interference between solid polygonal objects. The algorithm is linear in both the number of objects and number of polygons and requires no pre-processing or special data structures.