Why are oct trees so much more common than hash tables?

Question

When reading papers I commonly find Oct tree implementations of geometry representations to sort the data. However whenever I think about the problem hash tables seem better overall.

Hash tables have a better average and worse case scenarios for most applications:

For example for ray tracing an oct tree, near misses will cause you to iterate through a binary tree substructure, which is O(nlogn) whereas the hash table is O(n).

Hash tables are easier to generate in the GPU, as they do not require any logical position in memory other than their hash position.

Most advantages tree structures have over hash tables do not seem to hold on the GPU either.

In graphics we don't like re-allocating memory so we usually over allocate memory in VRAM just to be able to reuse a data structure. So the property binary trees have (being memory efficient) doesn't seem very relevant for GPU applications.

Data coherence for caching doesn't seem to hold either. For a GPU generated tree, asynchronicity makes it very difficult to guarantee that logically close values also get stored close to one another in the underlying memory. So you will end up jumping around pointers anyway.

It is also much easier to enforce certain GPU friendly heuristics in a hash table than in a tree. For example limiting the number of hash lookups to a fixed number, say 20 and using the same logic to prevent warps from executing different branch code. in essence you can always check the 20 potential collisions and just interpolate the result with the cell containing the key. In a tree the traversal through the data structure is a lot more dependent on the data itself and less on the data structure.

So why are oct trees used so much more than hash tables?

Answer 1

My 2 cents from writting the Chipmunk2D physics engine is that spatial hashing is great when you have a lot of objects that are all the same size. I had a demo 10 years ago that ran with 20k interacting particles on a Core 2 Duo in real time. The spatial hash worked great for that if you tuned it.

I've since replaced the spatial hash with a binary AABB tree as the the default structure. It's far from perfect, but it was faster than the spatial hash in the average case with no tuning. It also was easier to add a temporal component to it so I could incrementally update a set of potential collisions. With all of that in place, the only test I had that ran faster with the spatial hash were the ones with thousands of particles and no static geometry.

As for octrees... Meh, I never use them. Basic quad/octrees don't really fit real data as well as the plethora of other BVHs you can use. Basic AABB trees are nearly as simple, and way more effective.

Answer 2

Lots of things here.

• "When reading papers". What papers? If the topic of the paper is about something other than the spatial partitioning structure, it could be fair to use whatever knowing that the basic ideas will translate to other structures. Or not, hard to say.

• "For example for ray tracing an oct tree, near misses will cause you to iterate through a binary tree substructure, which is O(nlogn) whereas the hash table is O(n)". Big O notation means nothing at all in this context. You are dealing with a particular technology at a particular scale when you talk about things that depend on implementation details. An O(nlogn) algorithm might be much slower than an O(n) one for the "n" that is realistic today, it happens all the times. And while you might say, in 10 years that might change, sure, that might be the case, but in the same 10 years your GPU might look completely different and thus the state of the art algorithms need to change regardless. That's common, if you look at GPU algorithms (and GPUs specifically are still evolving quite a bit)

• What octree? What hash table? There are lots of choices there. For example "...as they do not require any logical position in memory other than their hash position". That's true only if you have no hash collisions, yes? If you have collisions then whatever strategy you use (probing or linked lists) you'll need to synchronize between threads, so the build is not so easy to implement on a GPU. Conversely, for octrees if you wanted to "overallocate" as you suggest then you could allocate a full tree, and indexing would then be equally only dependent on position. In fact, if you do some math you can see that in such cases octrees become just a way to swizzle a grid (e.g. compare the van Ende Boas layout with a grid in Morton order... nice exercise).

There are lots of other things I could say, but let me cut to the chase here.

• For raytracing specifically, neither Octrees nor Hash tables are -that- popular. BVHs of AABBs are the way to go.

• The main benefit of Octrees over hashed grid is that your cell resolution adapts to the geometry. Grids won't, you have to chose a cell size and that might be too small in certain parts of the scene and too big in certain others.

• There are a -lot- of variants and a -lot- of implementation details. Naive octrees should probably never be used in practice as they are too deep / not wide enough. If you make an octree "larger" by having say, a 4x4x4 grid with 4x4x4 grids nested in each non-empty cells, you create what it's called a hierarchical grid. So grids and octrees exist on a spectrum, where octrees are the most "deep", grids are the most "shallow" (just one level, a single grid globally in the scene), and hierarchical grids can trade between the two

• This might help! http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf ;)