Real-Time Collision Detection
Download
Content Overview
Chapter 2: Collision Detection Design Issues
This chapter talks about issues that must be considered when constructing a collision
detection system and what factors affect the design. Such factors include how objects
are represented, how many of them there are, how they move, and what types of
collision queries the user wants to pose. Chapter 2 also introduces terminology used
throughout the rest of the book.
Chapter 3: A Math and Geometry Primer
Any nontrivial collision detection system requires a large portion of geometryoriented
mathematics to work out the if, when, and where of collision queries.Chapter 3 introduces the mathematical and geometrical concepts necessary to
understand the material explored in the remaining chapters
Chapter 4: Bounding Volumes
To accelerate collision queries, simple geometrical objects such as spheres and boxes
are initially used to represent objects of more complex nature. Only if the “simple”
bounding volumes (which are large enough to encapsulate complex objects) collide
are tests performed on the complex geometry. Chapter 4 describes several bounding
volume types, how to perform intersection tests on them, and how to fit a bounding
volume to a complex object.
Chapter 5: Basic Primitive Tests
Having introduced some intersection tests in the previous chapter, Chapter 5
describes, in detail, a large number of tests for determining intersection status and
distance between pairs of objects of varying types, including lines, rays, segments,
planes, triangles, polygons, spheres, boxes, cylinders, and polyhedra. Both static and
moving objects are considered in these tests.
Chapter 6: Bounding Volume Hierarchies
For large objects and for collections of objects, performance benefits can be had by
constructing hierarchies of bounding volumes over the object(s). Such hierarchies
provide quick identification of objects or parts of an object that cannot possibly participate
in a collision, allowing queries to restrict testing to a small number of objects
or object parts. Chapter 6 talks about desired characteristics of bounding volume hierarchies
and ways in which to construct and perform queries over them. The chapter
also explores efficient ways of representing these hierarchies.
Chapter 7: Spatial Partitioning
When a large number of objects are considered for collision, the objects must be
partitioned into small disjoint subgroups to facilitate fast tests (by avoiding the worstcase
quadratic behavior of testing all objects against all other objects). The bounding
volume hierarchies discussed in Chapter 6 represent one way of performing such
partitioning. Chapter 7 examines other partitioning approaches, based on grids, trees,
and object sorting
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
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. Presented
are hierarchical representations, the V-Clip closest feature algorithm, the
mathematical optimization methods of linear and quadratic programming, the efficient
Gilbert–Johnson–Keerthi algorithm, and a separating vector algorithm due to
Chung and Wang.
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.
Chapter 11: Numerical Robustness
Even the smallest errors in a collision detection system can lead to catastrophic failures,
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.
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 wellformed
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.
Chapter 13: Optimization
The last chapter of the book talks about how to take the efficient data structures
and algorithms presented throughout the book and make them even more efficient
by targeting and tuning them for a particular hardware platform. Large performance
gains can be had by optimizing code to take advantage of memory hierarchies (caches)
and of code and data parallelism. Chapter 13 presents detailed descriptions on how
to perform such optimizations.
Home Programming Real-Time Collision Detection