ABSTRACT

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 processing 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.