INTERACTIVE COLLISION DETECTION FOR DEFORMABLE AND GPU OBJECTS
Author(s):
Joachim Georgii,
Jens Krüger,
Rüdiger Westermann
Paper abstract: If two closed polygonal objects with outfacing normals intersect each other there exist one or more lines
that intersect these objects at at least two consecutive front or back facing object points. In this work we
present a method to efficiently detect these lines using depth-peeling and simple fragment operations. Of
all polygons only those having an intersection with any of these lines are potentially colliding. Polygons
not intersected by the same line do not intersect each other. We describe how to find all potentially
colliding polygons and the potentially colliding pairs using a mipmap hierarchy that represents line
bundles at ever increasing width. To download only potentially colliding polygons to the CPU for
polygon-polygon intersection testing, we have developed a general method to convert a sparse texture
into a packed texture of reduced size. Our method exploits the intrinsic strength of GPUs to scan convert
large sets of polygons and to shade billions of fragments at interactive rates. It neither requires a
bounding volume hierarchy nor a pre-processing stage, so it can efficiently deal with very large and
deforming polygonal models. The particular design makes the method suitable for applications where
geometry is modified or even created on the GPU.
