Graphics Reference
In-Depth Information
1.1.7
Chapter 8: BSP Tree Hierarchies
One of the most versatile tree structures for representing collision detection data is
the binary space partitioning (BSP) tree. BSP trees can be used to partition space
independently from the objects in the space. They can also be used to partition the
boundary of an object from the space it is in, thereby effectively forming a volume
representation of the object. Chapter 8 talks about robustly constructing BSP trees
and how to perform tests on the resulting trees.
1.1.8
Chapter 9: Convexity-based Methods
Chapter 9 looks at a number of more advanced methods for performing collision
queries on convex objects, exploiting the special properties of convex objects. Pre-
sented are hierarchical representations, the V-Clip closest feature algorithm, the
mathematical optimization methods of linear and quadratic programming, the effi-
cient Gilbert-Johnson-Keerthi algorithm, and a separating vector algorithm due to
Chung and Wang.
1.1.9
Chapter 10: GPU-assisted Collision Detection
PC commodity graphics cards have advanced to a point at which they incorporate
more computational power than the main PC CPU. This change has triggered an
interest in outsourcing computations to the graphics card. Chapter 10 takes a brief
look at how to perform collision detection tests using graphics hardware.
1.1.10
Chapter 11: Numerical Robustness
Even the smallest errors in a collision detection system can lead to catastrophic fail-
ures, such as objects failing to collide with world geometry and thus falling out of the
world. This chapter discusses the robustness problems associated with working with
floating-point arithmetic and suggests approaches to dealing with these problems.
1.1.11
Chapter 12: Geometrical Robustness
Whereas Chapter 11 looked at how to perform calculations robustly, Chapter 12
considers the problem of taking an arbitrary set of polygons and turning it into well-
formed geometry, suitable for input into a collision detection system. Presented are
methods for welding of vertices, removal of gaps and cracks, merging of coplanar
faces, and decomposition of objects into convex (or triangular) pieces.
