Graphics Reference
In-Depth Information
Chapter
10
GPU-assisted Collision
Detection
Today, commodity graphics processing units (GPUs) have advanced to a state in
which more raw processing power is inherent in GPUs than in main CPUs. This
development is facilitated by GPUs working in a very restricted domain, allowing
rendering tasks to be parallelized across many deeply pipelined, highly specialized
computational units. This parallelism gives an overall speed advantage to GPUs, even
though GPUs typically work at lower clock speeds than CPUs. Coupled with recent
GPU improvements, such as increased programmability of vertex and pixel shaders
and the introduction of floating-point textures, the computational power of GPUs
has generated a lot of interest in mapping nonrendering-related, general-purpose
computations — normally performed on the CPU — onto the GPU. For collision
detection, there are two primary ways in which to utilize GPUs: for fast
image-space-
based
intersection techniques or as a co-processor for accelerating mathematics or
geometry calculations. Image-space-based intersection techniques rely on rasterizing
the objects of a collision query into color, depth, or stencil buffers and from that
determining whether the objects are in intersection.
Image-spaced-based techniques are generally easy to implement, work on any
rasterizable primitives (including, for example, Bezier and NURBS patches), and do
not require complex collision data structures in that they operate directly on the
rendering geometry (and therefore also deal well with deformable nonstatic geome-
try). Because the testing is performed to the resolution of the buffer(s) to which the
objects are rendered, all image-space collision detection methods are approximate.
They can therefore report collision when two objects are actually separated; for exam-
ple, when two objects separated by a small distance are far away from the rendering
viewplane. They can also report no collision when objects are in fact colliding; for
example, when the objects are so small or are so far away from the viewplane that
no pixels are rasterized when rendering the objects. These issues can be largely ame-
liorated by rendering objects as close to the viewplane as possible (without incurring
413
