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