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

  • $\begingroup$ Your best option, if I have understood the question, is Tomas Akenine-Moller box triangle overlap algorithm. fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code $\endgroup$ – ali Oct 6 '18 at 7:07
  • 2
    $\begingroup$ @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. $\endgroup$ – Chris says Reinstate Monica Oct 6 '18 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.