chapter  5
48 Pages

Spatial DataStructures

An important concept in this context is geometric coherence, as defined in Chapter 2. Geometric coherence is important because it enables us to quickly reject pairs of objects based on the region of space that they occupy. Spatial data structures, such as voxel grids, hierarchical space partitioning structures, and bounding-volume hierarchies, can be used for "capturing" geometric coherence. Basically, the data structures that are used for this purpose fall into two categories: space partitioning and model partitioning. In the following sections, we will discuss the advantages and drawbacks of data structures for each category. But first, let's explore how to deal with concave polyhedra.