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?

  • Because octrees are easier to write than hashtables I suppose? – Patapom Dec 5 at 23:05
  • 1
    How is a tree easier to write than a hash table? A hash table is a one dimensional structure, and oct tree is a 4 diemnsional structure mapped onto a one dimensional memory array. I have written both and hash tables are so much simpler than oct trees. – Makogan Dec 5 at 23:08
  • 1
    Imo, the main benefit lies in the hierarchy generated by using a tree structure. This makes it so that if a ray doesn't intersect any of the upper level boxes, a large number of nodes are pruned already. In contrast, a grid need to check intersection with all of the intersected cells. This answer explains it pretty well. gamedev.stackexchange.com/questions/69776/… – gallickgunner Dec 6 at 4:45
  • Mike Acton did a relevant presentation recently :)Check out @mike_acton’s Tweet: twitter.com/mike_acton/status/1062458276812451840?s=09 – Alan Wolfe Dec 6 at 5:37
  • @gallickgunner That is only efficient for a one time collission to find the region in the tree where your data is stored. Most effects however require to sample multiple neighbouring areas (AO, emitance, diffuse reflections....). For which the Hash table is better. And you can mimick the hierarchy of the tree by using a hashed mipmap. it gives you the exact same hierarchy and the exact same asymptotic computation time. – Makogan Dec 6 at 15:43

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 ;)

New contributor
Angelo Pesce is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • You can have hash collissions just fine without need of major synchronization by limmiting the number of possible collisions to a known number (say 20) and using atomic operations on a flag. With compact oct trees like the ones generated by voxel global illumination, oct tree based algorithms you need 2 separate shaders calling each otehr in a loop to achieve memory allocation. And "normal" oct trees (the ones where you know the index based on a fixed function) create a lot of unnused memory, at that point a 3D volume is likely to be better. – Makogan Dec 6 at 1:18
  • Also i think you swapped the complexities on your explanation of asymptotic complexity being a non-issue on modern algorithms due to mutability of hardware – Makogan Dec 6 at 1:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.