<p>Lots of things here.</p>

<ul>
<li><p>"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.</p></li>
<li><p>"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)</p></li>
<li><p>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).</p></li>
</ul>

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

<ul>
<li><p>For raytracing specifically, neither Octrees nor Hash tables are -that- popular. BVHs of AABBs are the way to go.</p></li>
<li><p>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.</p></li>
<li><p>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</p></li>
<li><p>This might help! <a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf" rel="noreferrer">http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf</a> ;)</p></li>
</ul>

CC BY-SA 4.0
2018-12-06T01:18:33.900Z
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
CC BY-SA 4.0
2018-12-06T01:19:59.477Z
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
CC BY-SA 4.0
2018-12-05T23:28:46.143Z
2018-12-05T23:28:46.143Z
Angelo Pesce
<p>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 <em>if you tuned it</em>.</p>

<p>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 <em>with no tuning</em>. 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 <em>only</em> test I had that ran faster with the spatial hash were the ones with thousands of particles and no static geometry.</p>

<p>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 <em>way</em> more effective.</p>

CC BY-SA 4.0
2018-12-14T22:36:02.503Z
"with the spatial hash were the ones with thousands of particles and no static geometry"

Awesome that's exactly what I am working on, that means my intuition about this was correct!
Makogan
CC BY-SA 4.0
2018-12-14T21:13:45.380Z
2019-12-19T18:09:04.513Z
2019-12-19T18:09:04.513Z
slembcke
<p>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.</p>

<p>Hash tables have a better average and worse case scenarios for most applications:</p>

<p>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).</p>

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

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>So why are oct trees used so much more than hash tables?</p>

CC BY-SA 4.0
2018-12-05T23:05:44.307Z
Because octrees are easier to write than hashtables I suppose?
Patapom
CC BY-SA 4.0
2018-12-05T23:08:02.860Z
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
CC BY-SA 4.0
2018-12-06T04:45:48.257Z
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.

https://gamedev.stackexchange.com/questions/69776/when-is-a-quadtree-preferable-over-spatial-hashing
gallickgunner
CC BY-SA 4.0
2018-12-06T05:37:50.287Z
Mike Acton did a relevant presentation recently :)Check out @mike_acton’s Tweet: https://twitter.com/mike_acton/status/1062458276812451840?s=09
Alan Wolfe
CC BY-SA 4.0
2018-12-06T15:43:39.750Z
@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
CC BY-SA 4.0
2018-12-06T17:01:46.513Z
@Makogan - I don't know what a hashed mimap is, but there are other cons such as the teapot in a stadium problem which occurs with grids and spatial hashing.If you are going so far to even copy the hierarchy of the tree why not just use the k-d tree/ octree itself which are more flexible as they don't divide space in uniform grids. Overall each data structure has its own pros and cons so we can't say 1 is better than the other everywhere. As for why the octree/BVH are popular, i think they perform better overall in general.
gallickgunner
<shader><algorithm><gpu><geometry><data-structure>
Why are oct trees so much more common than hash tables?
Makogan
# Why are oct trees so much more common than hash tables?

(Asked by: username_0 on 2018-12-05)

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?

**Tags:** shader, algorithm, gpu, geometry, data-structure

> **Comments:**
> **username_1**: Because octrees are easier to write than hashtables I suppose?  
> **username_0**: 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.  
> **username_2**: 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.  https://gamedev.stackexchange.com/questions/69776/when-is-a-quadtree-preferable-over-spatial-hashing  
> **username_3**: Mike Acton did a relevant presentation recently :)Check out @mike_acton’s Tweet: https://twitter.com/mike_acton/status/1062458276812451840?s=09  
> **username_0**: @username_2 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.  
> **username_2**: @username_0 - I don't know what a hashed mimap is, but there are other cons such as the teapot in a stadium problem which occurs with grids and spatial hashing.If you are going so far to even copy the hierarchy of the tree why not just use the k-d tree/ octree itself which are more flexible as they don't divide space in uniform grids. Overall each data structure has its own pros and cons so we can't say 1 is better than the other everywhere. As for why the octree/BVH are popular, i think they perform better overall in general.  

---

## 2 answers

### Answer by username_5 on 2018-12-14. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: "with the spatial hash were the ones with thousands of particles and no static geometry"  Awesome that's exactly what I am working on, that means my intuition about this was correct!  

---

### Answer by username_4 on 2018-12-05. Score: 9

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

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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  

---

