6

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.

OOBBs

Olivier Moindrot
  • 27,908
  • 11
  • 92
  • 91
Tyson
  • 1,226
  • 1
  • 10
  • 33
  • 1
    try rotating the ray into some space where most of the bbs are close to being aabbs and using some kind of space partitioning algorithm in that new space. another solution that applies if the object doesn't change from ray to ray except for a linear transformation: you could also generate a 3D array where each cell has a list of what triangles/oobbs intersect it, and step along the ray though that 3D array. – programmerjake May 02 '17 at 07:05
  • How dynamic is the scene? That is, how many rays will you cast until the OOBBs change, and how drastically will they change? – Angew is no longer proud of SO May 02 '17 at 07:06
  • @programmerjake Unfortunately the first suggestion won't work because the OOBBs won't always be nicely aligned like in my example image. The second option might be closer to something, but the memory footprint and preprocessing requirement could be a problem...I need the solution to work in very large 3d environments, where a 3D array wouldn't be feasible (would need billions of cells to include everything while maintaining reasonable granularity). But thanks for the suggestions. – Tyson May 02 '17 at 07:12
  • @Angew I'll be casting a few million rays before the OOBBs will change. They may change pretty drastically at each simulation step (they encompass triangles moving along arbitrary trajectories). – Tyson May 02 '17 at 07:13
  • @Tyson What about using a 3D grid, where for each cell that has too many triangles, you subdivide into a smaller grid? – programmerjake May 02 '17 at 07:15
  • @programmerjake I guess that would be similar to an octree or something? – Tyson May 02 '17 at 13:20
  • @programmerjake Actually your suggestion gave me an idea. Instead of subdividing a grid, I think I'll try to subdivide each OOBB along its longest axis until its shape is closer to a cube. Each of those subdivided OOBB will contain pointers to the underlying geometry so that no matter which one is hit, it'll still link to the mesh I want to test. I'll then partition them using a normal AABB-accellerated structure. Converting all of them into cuboids should reduce the number of them returned for any given ray. – Tyson May 02 '17 at 13:37

1 Answers1

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)

Raxvan
  • 6,257
  • 2
  • 25
  • 46