Graphics Reference
In-Depth Information
Chapter
7
Spatial Partitioning
Recall from Chapter 2 that pairwise processing is expensive, and that the idea of
broad-phase processing is to restrict pairwise tests to objects near enough that they
could possibly intersect.
Spatial partitioning
techniques provide broad-phase process-
ing by dividing space into regions and testing if objects overlap the same region of
space. Because objects can only intersect if they overlap the same region of space, the
number of pairwise tests is drastically reduced. This chapter explores three types of
spatial partitioning methods: grids, trees, and spatial sorting.
7.1
Uniform Grids
A very effective space subdivision scheme is to overlay space with a regular grid.
This grid divides space into a number of regions, or grid cells, of equal size. Each
object is then associated with the cells it overlaps. As only objects overlapping a
common cell could possibly be in contact, in-depth tests are only performed against
those objects found sharing cells with the object tested for collision. The farther
apart two objects are the less likely they overlap the same cells, and with an appro-
priately spaced grid only objects very likely to overlap would be subject to further
pairwise tests.
Thanks to the uniformity of the grid, accessing a cell corresponding to a particular
coordinate is both simple and fast: the world coordinate values are simply divided
by the cell size to obtain the cell coordinates. Given the coordinates to a specific cell,
neighboring cells are also trivial to locate. This conceptual as well as implementational
simplicity has made grids both a good and popular choice for space subdivision.
Grids are known by many other names, including regions, buckets, sectors, and
zones.
285
