Graphics Reference
In-Depth Information
Pairwise tests then must be performed only for those objects that share a region. In
some cases objects are associated with just a single region, in which case neighboring
regions also must be explored for potential collisions.
In this chapter, three types of spatial partitioning methods were explored: grids,
trees, and spatial sorting. Grids are often uniform, meaning that they consist of grid
cells of equal size. When large, grids may consume large amounts of memory. One
way to reduce the memory requirements of grids is to use hashed storage, as described
in Section 7.1.3, which has the benefit of allowing the grid to be of infinite extent.
Grids can also be expressed implicitly. The implicit bit grid, in particular, is a very
efficient spatial partitioning method. The hierarchical grid addresses the problem of
objects being of greatly varying sizes, making it difficult to set a grid cell size for a
uniform grid.
One of the tree representations described was the octree. It partitions space into
eight uniform-size cells, then recursively partitions the cells in the same way. Thanks
to their regular structure, octrees can be represented linearly, obviating the need to
represent tree links using pointers, and thereby saving memory. The octree can also
be made loose, meaning that its cells are expanded to overlap partially. Loose octrees
address the problem of objects not being able to descend farther down the tree when
they straddle a splitting plane (and are only allowed to be referenced from a single
octree cell).
The
k
-d tree is a generalization of the octree in that it can represent the same
spatial partitioning as the octree, but not vice versa. The
k
-d tree divides space into
two, along one dimension at a time and at an arbitrary position. The simpler structure
of the
k
-d tree makes queries on it easier.
Spatial sorting involves maintaining all objects in a sorted structure along one or
more axes. The sorted structure is incrementally updated when objects move. Because
the structure is sorted, object collisions are detected by examining neighboring objects
without requiring a search.
Chapter 8 discusses one additional tree representation, which is a generalization
of
k
-d trees. This representation can also be used as a spatial partitioning method.
