3
\$\begingroup\$

I've been slowly working on implementing a spatial hashing function into Bullet Physics to see how well it will work in my game engine as a general use. Though as I'm starting to design it, I do notice a few select problems about it's design.

So in the middle of research, I see that Spatial Hash functions start to suffer when objects take up too many cells.

Example: 1D's optimal case is at max 2. 2D's optimal case is 4. And 3D's optimal case is at most 8.

I can use a hierarchal method and hash larger objects to other tables to solve this.

But my biggest concern is exactly what are the best use cases for each of them?

BVH seems like it can generate a larger number of checks, and needs to bounce around on pointers

And Spatial hashing seems like it chews through memory, but is pretty good at what it does.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I don't have an answer for you but you may want to take a look at 0fps which posted a 3 part evaluation of bounded volume, spatial hash, etc. for physics engines. \$\endgroup\$
    – amitp
    Commented Jun 20, 2016 at 0:09

1 Answer 1

4
\$\begingroup\$

I believe this is largely dependent upon the implementer as well as preferred usage patterns (which can also depend on the implementer) as well as required usage patterns (which depend on domain).

Construction

As you pointed out, a spatial hash or grid can become very sub-optimal if elements are stored in a large number of cells. Hopefully you aren't duplicating the element data in that case, only indices, e.g., but it can still get explosive if you had to insert the analogical object into 100 cells as opposed to 1.

A BVH, on the other hand, can be costly to build since it can spend considerably more time determining how to split a node, especially if it's trying to achieve the best search quality using SAH, e.g. As a result even little old me can implement a grid accelerator (similar to spatial hash) in a small fraction of the time that even Intel's Embree with its cutting-edge fast SAH construction can build given the same million-triangle scene input (not saying mine would be better for raytracing, mind you, not even close).

Searching

For search times, I would generally think a well-implemented BVH has the theoretical edge unless your search queries just end up looking at a handful of cells on average. While the BVH does require descending down the tree and branching on each node, it's potentially skipping a whole lot of analogical cells that you might otherwise have to check with the spatial hash. If we can ignore construction times and focus predominantly on search times, I would think the well-implemented BVH would generally have a huge edge in many real world usage scenarios involving non-trivial searches on complex and varied data.

Use Cases

But my biggest concern is exactly what are the best use cases for each of them?

Again I don't think you can avoid a subjective answer for this one, but I actually find a grid to be my number one go-to structure for spatial partitioning, using it until I find a reason not to do so.

One of the reasons is because in most of my use case scenarios, construction time is not anywhere close to being divorced from critical execution paths. Often I need to build/update the structure almost as often if not as often as I'm searching it.

The other reason is because of my own programming abilities and lack thereof. I'm not Ingo Wald publishing R&D on the most cutting-edge BVH construction techniques (and I can still beat him if we're only timing construction). I'm not a GPGPU wizard who has figured out how to store n-ary BVHs and construct them and search them super fast on cutting-edge GPUs. I'm just a C and C++ programmer who can do a competent job when it comes to efficient memory allocation and access patterns and apply some multithreading here and SIMD there. Because of this, if I was expected to make something very competent in a week to accelerate object/object intersection for a commercial product, my probability of doing a decent job is much higher if I go with a grid instead of a BVH.

There are countless papers on how to implement BVHs using the most cutting-edge techniques, and far fewer on spatial hashes and grids. That's not necessarily because spatial hashes and grids are always sub-optimal, but because implementing them very efficiently doesn't take a wizard like Ingo Wald. It's not a PhD-level data structure to publish papers about implementing efficiently unless you are doing something very different and interesting like using a hierarchical spatial hash hybrid.

Generally if you find construction and updating the structure to be almost as time-critical if not more and you're like me, then you might get a lot more mileage out of a grid (see below about "grid" vs. "spatial hash"). If you find your critical execution paths heavily skewed towards searching, as in the case of a raytracer, or you're just so much better at implementing a BVH than I am, then you might get more mileage out of a BVH.

Search Patterns

Another reason I might find more use for a grid is because my search patterns use the data structure directly. Instead of:

for each element in scene:
    // Use spatial structure to determine collision.

... which I see many people do, I instead do:

for each cell in spatial structure:
    // Mark elements that collide in cells.

That avoids evicting the same cells over and over, keeping that memory hot and inside a cache line, and if I need rapid searches, I make sure the data for a cell and inside a cell is contiguous. If I used the previous technique for traversal, I would think the BVH again would show a bigger edge, because it can potentially keep hitting the same nodes towards the top of the hierarchy whereas the previous access pattern using a spatial hash might be accessing cells all over the place, evicting them from a cache line only to reload them again in a single loop.

Grid vs. Spatial Hash

That said, you might have noticed I use "grid" a lot. Some people refer to the idea of a grid interchangeably with a spatial hash, but I find more use for what I call a "grid".

The distinction I make is that a spatial hash is often considered to be hashing data in 2 or more dimensions into a 1-dimensional data structure. It's also often sparse. The data structure might take less memory than is needed for a dense representation or it could take considerably more, just as with a hash table.

I have found in my use cases that I can implement a more performant solution with a "sorta dense" grid, and one that stores multiple instances of a data structure. For example, I might do this for a 3-dimensional grid:

struct Slice
{
    // Cells stored in this 2D "slice".
    std::vector<Cell> cells;

    // Elements stored in this 2D "slice".
    std::vector<int> elements;
};

struct Grid
{
    // 2-dimensional slices that make up the grid.
    std::vector<Slice*> slices;
};

And sometimes even:

struct Row
{
    // Cells stored in this 1D "row".
    std::vector<Cell> cells;
    std::vector<int> elements;
};

struct Slice
{
    // Rows stored in this 2D "slice".
    std::vector<Row*> rows;
};

struct Grid
{
    // Slices stored in this 3D "grid".
    std::vector<Slice*> grid;
};

As well as sometimes:

struct Row
{
    // Occupied range of cells stored in this 1D "row".
    std::vector<Cell> cells;
    std::vector<int> elements;

    // Position of first occupied cell in row.
    int first_occupied;
};

I don't actually use vector typically but the above is just a simple illustrative example, and generally sizeof(Cell) in my cases is 32-bits or less so it's cheap to store them by the millions. That involves more heap allocations for each 2D "slice/row" of the 3D grid, but it allows me to just store a null pointer for slices/rows which are completely empty (making it "pseudo-sparse") and if the traversal patterns are one row of each slice at a time, then often the entire data of interest for the cells and elements can fit in L2 or L3. It also means I can build a separate grid in each thread given a chunk of elements and then efficiently do a multithreaded merge of all the grids that each thread outputs to produce one final grid since the merge can merge rows/slices per thread without any shared data.

So I've gotten the most use of that for my use cases. Just to recap:

  1. The answer depends heavily on the implementer, preferred usage patterns, etc.
  2. The BVH most likely has the theoretical edge in most use cases for searching.
  3. The grid and spatial hash probably has the theoretical edge in most use cases for construction and updates, at least if you can ensure that you aren't inserting each object into a boatload of cells with a cell size way too small for the common case element size.

Naturally the spatial hash and grid is also very obviously ideal even for searching if you are just, say, storing points and only searching for coincident points. There you're only going to be looking in one cell for an entire search for coincident elements, skipping the need to descend down the tree. That's a very specialized use case, however.

\$\endgroup\$
2
  • \$\begingroup\$ Out of curiosity is there any algorithmic reason that using a hashmap for spatial hashing might be a bad idea? \$\endgroup\$ Commented Dec 5, 2023 at 2:28
  • 1
    \$\begingroup\$ @AlexisPurslane Yes. For a spatial hash to perform well, bucket indexing needs to be implemented using a space-filling curve, the reason being that such an indexing scheme assures that those buckets which are close to each other spatially are also maximally close to each other in memory, i.e. that spatial locality within CPU cache is maximised, thereby avoiding expensive CPU cache misses. Regular hashmaps do not take this into account, their bucket indexing is implemented using some more spatially-naive scheme. \$\endgroup\$
    – Engineer
    Commented May 6 at 11:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .