<p><strong>What is the fastest known method for bucketing triangles into an unbounded regular 3D grid?</strong></p>

<p>Specifically, I need an array of buckets. Random queries (which bucket is here) are not necessary, as this is not for ray-tracing (though I will include the tag because of algorithm similarity). The triangles form a closed 2-manifold mesh.</p>

<p>Currently, I'm inserting into grid cells that intersect the bounding box of the triangle (in my case, triangles are smaller than cells, so this is ok). I'm using a hash table for my grid.</p>

<p>I've also tried outputting a list of (bucket-position, triangle-index) pairs and sorting them lexicographically, which has comparable performance.</p>

<p>Thus far, I've only tried CPU approaches. I'm thinking a faster method would be to produce the pairs on the GPU, then sort on the GPU.</p>

<p>I'm having trouble finding directly relevant research papers (though it's easy to find papers on GPU sorting).</p>

CC BY-SA 4.0
2018-10-06T07:07:54.590Z
Your best option, if I have understood the question, is Tomas Akenine-Moller box triangle overlap algorithm. http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/
ali
CC BY-SA 4.0
2018-10-06T12:35:22.193Z
@ali From the question it seems he already *has* a good way of intersecting a box with a triangle (or simply doesn't care about exact intersection). What he's looking for is the higher level infrastructural way to sort the triangles into buckets (and a way to layout that bucket datastructure in the first place) independent of how that triangle-box intersection is computed on the lower level. I can't see anything in your link adressing the problems from the question. If it does, feel free to elaborate a little more, preferably in an answer.
Christian Rau
<raytracing><mesh><gpgpu>
fastest way to bucket triangles into a grid?
Taylor
# fastest way to bucket triangles into a grid?

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

**What is the fastest known method for bucketing triangles into an unbounded regular 3D grid?**

Specifically, I need an array of buckets. Random queries (which bucket is here) are not necessary, as this is not for ray-tracing (though I will include the tag because of algorithm similarity). The triangles form a closed 2-manifold mesh.

Currently, I'm inserting into grid cells that intersect the bounding box of the triangle (in my case, triangles are smaller than cells, so this is ok). I'm using a hash table for my grid.

I've also tried outputting a list of (bucket-position, triangle-index) pairs and sorting them lexicographically, which has comparable performance.

Thus far, I've only tried CPU approaches. I'm thinking a faster method would be to produce the pairs on the GPU, then sort on the GPU.

I'm having trouble finding directly relevant research papers (though it's easy to find papers on GPU sorting).

**Tags:** raytracing, mesh, gpgpu

> **Comments:**
> **username_1**: Your best option, if I have understood the question, is Tomas Akenine-Moller box triangle overlap algorithm. http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/  
> **username_2**: @username_1 From the question it seems he already *has* a good way of intersecting a box with a triangle (or simply doesn't care about exact intersection). What he's looking for is the higher level infrastructural way to sort the triangles into buckets (and a way to layout that bucket datastructure in the first place) independent of how that triangle-box intersection is computed on the lower level. I can't see anything in your link adressing the problems from the question. If it does, feel free to elaborate a little more, preferably in an answer.  

---

## 0 answers

