Using spatial partitioning to reduce complexity
In this section, we will take a look at some methods to split our world space into different parts, lowering the number of instances in each of the parts. We start with the simplest variant of spatial partitioning in two or three dimensions, the grid.
Grid
In a grid, the virtual lines divide the virtual world into equally sized squares or rectangles, or equally sized cubes and cuboids.
Figure 8.1: 2D and 3D grids
While grids are easy to create, Figure 8.1 already shows some of the problems. Objects larger than the grid spacing must be placed into all overlapping grid fields, requiring checking all affected fields for other instances.
And while the vast majority of the grid will remain empty, “crowded places” inside the virtual world can lead to many instances inside a single field of the grid. Many instances mean many checks, and an uneven distribution of instances may cause slowdowns due to the...
