Ray-mesh intersection or AABB tree implementation in C++ with little overhead?

Question

Can you recommend me...

• either a proven lightweight C / C++ implementation of an AABB tree?
• or, alternatively, another efficient data-structure, plus a lightweight C / C++ implementation, to solve the problem of intersecting a large number of rays with a large number of triangles?

"Large number" means several 100k for both rays and triangles.

I am aware that AABB trees are part of the CGAL library and probably of game physics libraries like Bullet. However, I don't want the overhead of an enormous additional library in my project. Ideally, I'd like to use a small float-type templated header-only implementation. I would also go for something with a bunch of CPP files, as long as it integrated easily in my project. Dependency on boost is ok.

Yes, I have googled, but without success.

I should mention that my application context is mesh processing, and not rendering. In a nutshell, I'm transferring the topology of a reference mesh to the geometry of a mesh from a 3D scan. I'm shooting rays from vertices and along the normals of the reference mesh towards the 3D scan, and I need to recover the intersection of these rays with the scan.

Edit

Several answers / comments pointed to nearest-neighbor data structures. I have created a small illustration regarding the problems that arise when ray-mesh intersections are approached with nearest neighbor methods. Nearest neighbors methods can be used as heuristics that work in many cases, but I'm not convinced that they actually solve the problem systematically, like AABB trees do.

Siberia

Is it indoor, outdoor, CAD, FPS? Is the geometry dynamic or static? How large percentage of the polygons is visible? Is it for rendering from a single point (or multiple points == shadow buffer) or lots of points (radiosity)? – Corroboree

My application context is mesh processing, and not rendering. More specifically, I'm transferring the topology of a reference mesh to the geometry of a mesh from a 3D scan. I'm shooting rays along the normals of the reference mesh towards the 3D scan, and I need to recover the intersection of these rays with the scan. Questions of visibility do not apply to this problem. The geometry is static. Rays are shot from lots of points (though it has nothing to do with rendering, as pointed out above). – Siberia

What about octrees? They are fairly simple to implement. – Krishnakrishnah

@BartekBanachewicz: I think the problem with octrees for storing triangles is that triangles overlap and octree cells don't, or am I wrong here? I'm pretty sure that AABB tree cells (i.e the bounding boxes) do overlap, and that's why they are used for this kind of problems. – Siberia

Can't you put a reference to the same triangle in >1 octree leaf cell? – Segregation

Answer 1

While this code is a bit old and using the 3DS Max SDK, it gives a fairly good tree system for object-object collision deformations in C++. Can't tell at a glance if it is Quad-tree, AABB-tree, or even OBB-tree (comments are a bit skimpy too).

http://www.max3dstuff.com/max4/objectDeform/help.html

It will require translation from Max to your own system but it may be worth the effort.

Townes

+1 for being the first answer that points to intersection related code! I'll have a look at it. – Siberia

Answer 2

If there's no real time requirements, I'd first try brute force.

1M * 1M ray->triangle tests shouldn't take much more than a few minutes to run (in CPU).

If that's a problem, the second best thing to do would be to restrict the search area by calculating a adjacency graph/relation between the triangles/polygons in the target mesh. After an initial guess fails, one can try the adjacent triangles. This of course relies on lack of self occlusion / multiple hit points. (which I think is one interpretation of "visibility doesn't apply to this problem").

Also depending on how pathological the topologies are, one could try environment mapping the target mesh on a unit cube (each pixel would consists of a list of triangles projected on it) and test the initial candidate by a single ray->aabb test + lookup.

Given the feedback, there's one more simple option to consider -- space partitioning to simple 3D grid, where each dimension can be subdivided by the histogram of the x/y/z locations or even regularly.

• 100x100x100 grid is of very manageable size of 1e6 entries
• the maximum number of cubes to visit is proportional to the diameter (max 300)

• There are ~60000 extreme cells, which suggests an order of 10 triangles per cell

• caveats: triangles must be placed on every cell they occupy -- a conservative algorithm places them to cells they don't belong to; large triangles will probably require clipping and reassembly.

Corroboree

Unfortunately, there are time requirements. Otherwise I would not worry about data structures, wouldn't I? ;-) The topologies are ok, but the shapes can be complex. Mapping them on a unit cube / sphere / cylinder won't work (tried it already). Searching in the surroundings of a first guess can be pretty far off for ray mesh intersection - think of a ray just passing the closest triangle to its origin and then hitting some where completely different. Actually, the AABB tree is the canonical data structure for this problem, afaik. I just lack an implementation, and I'm hesitant write one myself. – Siberia

The 3D grid solution you propose is interesting, but almost the definition of an AABB tree, which only adds the idea of making the partitioning hierarchical. If I implement your solution I'm very close to implementing an AABB tree, which is what I wanted to avoid by asking my question, in the spirit of not "re-implementing the wheel". Also, intersection computations can be nasty numerically, which is another reason why I prefer proven code. Given the feedback so far, however, it seems likely that a ready-to-use lightweight C++ implementation of AABB trees does not exist. – Siberia

Answer 3

Try the ANN library: http://www.cs.umd.edu/~mount/ANN/

It's "Approximate Nearest Neighbors". I know, you're looking for something slightly different, but here's how you can use this to speed up your data processing:

1. Feed points into ANN.
2. Query a user-selectable (think of this as a "per-mesh knob") radius around each vertex that you want to ray-cast from and find out the mesh vertices that are within range.
3. Select only the triangles that are within that range, and ray trace along the normal to find the one you want.

By judiciously choosing the search radius, you will definitely get a sizable speed-up without compromising on accuracy.

Therine

Did you get a chance to look at ANN? I should add that this library is not re-entrant. – Therine

Sorry for answering late, I'm traveling. I know ANN (and other libraries for nearest neighbor problems). The problem is that a nearest neighbor search can be a decent heuristic for ray mesh intersection, but is does not guarantee a correct answer in all cases (as an AABB tree does). There are cases where the vertices of the correct intersected triangle are not among the nearest neighbors of the source vertex. As pointed out in my comment on Aki Suihkonen, think of a ray just passing the mesh and then hitting it somewhere completely different. Also, the radius can be tricky to determine. – Siberia

I have edited the question, adding an illustration of the problems mentioned in the comment above. – Siberia

Thanks for illustrating those corner (literally!) cases. I understand why this is a challenging problem. An acceleration structure appears to be your best bet. – Therine