Loose Grids

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.

6 Responses to “Loose Grids”

  1. Niklas Frykholm said:

    Mar 06, 12 at 5:26 pm

    A data structure I really like is a “hash grid”. It works as a grid or a loose grid but all the cells are stored in a flat array:

    Cell cells[MAX_CELLS];

    And to go from a position (x,y) to a cell index you do:

    i = hash( floor(x/grid_size), floor(y/grid_size) )

    I.e. you just hash the cell position to a value in the range 0..MAX_CELLS-1. Two nice things about this solution, is that it takes care of the problem with objects ending up “outside” the grid and that it decouples the number of cells from the grid size, so you can choose grid_size based on your object sizes, and MAX_CELLS based on the object count and the maximum objects you want to end up in the same cell.

    With this solution you don’t know that objects are in the same part of the grid just because they ended up in the same cell. They could be at different (x,y) coordinates that just happen to hash to the same cell index. So you must do an extra check for that. But typically you do such checks anyway (and just use the grid for “broad phase” culling).

  2. Manuel Kugelmann said:

    Mar 07, 12 at 7:47 am

    Yeah, Spatial Hashing is very useful. Used this with good results for caching 3d (position) and 6d (position and direction) illumination data in a ray tracing experiment.
    In fact you could see it as a variation of the row*col mapping of a regular grid to a 1d array. You are just using a different mapping function (which can have collisions in its mapping).

  3. Basit @ PHP Tutorials said:

    May 01, 12 at 3:46 am

    Very nice tutorial, It helps me alot. Thanks for writing for us :)

  4. Bottes UGG said:

    Oct 15, 12 at 3:38 pm

    Bottes UGG vous proposons de haute qualité et de styles et de couleurs différentes. … à chaud à un prix raisonnable dans notre prise de bottes UGG pas cher.Bottes Ugg france en ligne!ugg pas cher boutique soldes,acheter maintenant 55% de réduction!

  5. Daily Programming Blog said:

    Nov 28, 12 at 6:40 pm

    Thanks I had a lot to work with grids for a web-application at my traineeship so your post was really interesting for me.

  6. Kitchen Renovations On A Budget said:

    Aug 04, 13 at 11:21 am

    Look for a company? You can also decide to completely 3
    remodel recessed light your pool area with several changes including technology
    and safety upgrades, surface changes, aesthetic features and even your pool shape.
    He even un-Islamically pulled back her head scarf and stretched her skin to show how
    he would do it. I must stress, there are also emotional factors that
    come into play, and they are everywhere on this playful front door and porch.


Leave a Reply