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 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.
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 ...
Get Real-Time Collision Detection now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
