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.
