System and method for reducing the complexity of performing broad-phase collision detection on GPUS

摘要

One embodiment of the present invention sets forth a technique for efficiently performing broad phase collision detection using parallel spatial subdivision. The technique involves organizing candidate objects according to a hashed representation of each object centroid, constructing a cell identification (ID) array, sorting the cell ID array, creating a collision cell list, and traversing the collision cell list. The result is a candidate list of object groups that may collide, based on an initial assessment of spatial proximity. Whether a given pair of objects actually collides is determined by a precise narrow phase collision analysis.

主权项

1. A method for performing a collision detection analysis for a plurality of graphics objects, the method comprising:
initializing a cell identifier (ID) array that includes memory space for entries corresponding to a first bounding sphere associated with a first graphics object and entries corresponding to a second bounding sphere associated with a second graphics object; generating an unsorted cell ID array that includes one or more entries corresponding to the first bounding sphere and one or more entries corresponding to the second bounding sphere, wherein each entry in the unsorted cell ID array includes a cell ID number and an object ID; generating a sorted cell ID array based on the cell ID number associated with each entry in the unsorted cell ID array; generating a collision cell list based on the sorted cell ID array; setting a cell type to a first cell type; and traversing the collision cell list with a plurality of threads to perform a narrow phase collision detection analysis on each collision cell included in the collision cell list having only the first cell type.