How to quickly test for ray intersections against a tight group of OOBBs?

Question

I have thousands of OOBBs (object oriented bounding boxes) in 3d space which encompass simple elongated 3d meshes. They are tightly packed together.

I'd like to shoot rays into them and figure out which OOBBs get hit. Due to the number of ray intersection tests I need to perform (millions), a brute force approach against all the OOBBs will not suffice.

Originally I thought it would be easy to use some kind of spatial partitioning system to quickly narrow down potential results, but systems like BVHs or KDTrees rely on AABBs (axis aligned bounding boxes) to speed up queries and in my case those would be very inefficient (because lots of my tightly-packed OOBBs have roughly the same AABB due to the diagonal nature of the mesh they encompass).

I read about OBBTrees in the RAPID library, but it seems like they're built from the top down (start with polygon soup and subdivide into progressively smaller groups of OOBBs to form the tree), rather than bottom up (start with lots of OOBBs and build a tree from them).

Are there any other data structures that I can use to speed up my intersection tests?

Here is a picture of my OOBBs. As you can see, they are tightly packed and if you can envision what their AABB would look like, you'd see that they'd overlap to the point where an AABB-based tree would not really boost performance (because virtually all of them would get hit by a ray shooting through the center of the group).

It's worth noting that I need to query all OOBBs hit by a ray, and not just the first/closest one.

Answer 1

Probably the best is to use a 3d axis aligned grid structure. Each cell in the grid holds (a vector, array, etc) of all the oobb's that intersect that cell. 8 empty cells can be collapsed into a larger empty cell to speed traversal of empty space. For the size of the grid you will have to so some testing to find the optimal size.

Traversing that grid is trivial, you will have to start from the closest cell to the ray origin, test all the objects there, then move to the next cell along the ray. Traversing the cell is basically a 3d conservative line rasterizing, which is very light in complexity. More on that here

---

Additionally, if the data is very overlapped you may want to have a large grid (where cells are very small). In this case i would advice you to look into space filling curves to store the grid data. (z-order curve is surprisingly simple)