Spatial data structures are an important part of game engines, with uses in various systems such as collision detection, rendering and gameplay. Octrees, BSP trees and bounding volume hierarchies are just a few of the options available. However, for a many of applications these complicated hierarchical structures aren’t a good choice. Tree structures structures often have poor cache performance and aren’t ideally suited for SIMD or other parallel processing techniques. They can also have considerable cost when updating adding, removing or updating the positions of the objects. Instead, setting up your data in a way that allows brute force processing with highly optimized code may be faster, even if you typically end up processing a lot more objects.
The most cache friendly data structure is an array (or possibly a structure of arrays). It also allows trivial updating of objects, but for some data sets, putting all objects into a single array may be too slow. Most likely, we can process a lot of items in an array very efficiently, but the total number of objects is an order of magnitude too high to make this practical.
The next simplest method is a regular grid, where each cell stores any array of the objects inside it. Typically you can make the cells pretty big (to amortize cache misses and maintain efficient processing over the contents) and for decently distributed objects we end up processing many fewer objects. However, regular grids have some drawbacks. The first draw back is that objects might straddle multiple grid cells and need special handling. A typical solution is to store the object in every cell it overlaps, but this makes the book-keeping more complicated and can affect your ability to process cells in parallel. The second draw back is that grids have finite size, so you need to either prevent any objects from moving outside the bounds of the grid, or resize the grid. Resizing can be ugly since it involves touching everything in the grid.
The first drawback can be solved by borrowing an idea from Thatcher Ulrich’s loose octree data structure. Like the loose octree, we expand each cell of our grid by a fixed amount so that each cell overlaps its neighbors. When inserting an object into the grid, we place the object into any of the cells it is contained within. As long the object is smaller than the overlap size, we only need to store it in a single cell.
This overlap scheme affects how we traverse the grid when performing operations on the object. If we wanted to find all of the objects within a sphere, we need to test all of the grid cells whose expanded versions fall within the sphere. This means we’ll end up testing more cells than in the regular grid, but remember we are assuming that processing the objects is relatively fast due to our efficient array layout.
This grid works nicely if all of the objects are smaller than the overlap size, but if an object exceeds it, it can still can fall into multiple cells. In most applications it will probably be reasonable to impose some sort of maximum size on objects. However, this hard limit can be transformed into a “soft” one by creating an additional cell where any objects above this maximum size are placed. In the example of querying for objects in a sphere, after we tested all of the cells overlapping the sphere, we also test this “overflow” cell.
The overflow cell also allows us to deal with objects moving outside the grid. Like with the soft limit of object size, we assume that most objects will be within our predefined grid bounds, and put any objects which violate that constraint in the overflow cell. Since the number of outliers stored in that cell is small, the additional testing should be negligible.
Loose grids may not be the best candidate for all situations, but if you are looking for an easy way to spatially partition a data set into manageable parts, it can be a good option. We’ve had success with this setup for frustum/occlusion culling, broadphase collision detection and gameplay queries in the engine for Natural Selection 2.