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

Question

Can you recommend me ...

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

“Large number” means several 100,000 for both rays and triangles.

I know that AABB trees are part of the CGAL library and possibly game physics libraries like Bullet. However, I do not want the overhead of a huge additional library in my project. Ideally, I would like to use a small plug-in template version for headers only. I would also go for something with a bunch of CPP files if it integrates easily into my project. The boost dependency is fine.

Yes, I have googled, but to no avail.

I should mention that my application context is grid processing, not rendering. In a nutshell, I transfer the topology of the referenced mesh to the mesh geometry from 3D scanning. I shoot rays from the vertices and along the normals of the reference grid for 3D scanning, and I need to restore the intersection of these rays using scanning.

Edit

Several responses / comments pointed to the data structures of the nearest neighbor. I created a small illustration about the problems that arise when approaching ray intersections with the nearest neighboring methods. Nearest neighbor methods can be used as heuristics, which work in many cases, but I'm not sure that they actually solve the problem systematically, like the AABB trees do.

Answer 1

If there are no real-time requirements, I would first try brute force.

1M * 1M ray-> triangle tests should not take more than a few minutes (on the CPU).

If this is a problem, the second thing to do is to limit the search area by calculating the graph / adjacency relation between triangles / polygons in the target grid. After the initial assumption fails, you can try neighboring triangles. This, of course, depends on the lack of self-spell / multiple hit points. (which, in my opinion, is one interpretation of "visibility does not apply to this problem").

In addition, depending on how pathological the topologies are, you can try to display the environment of the target cell on a single cube (each pixel will consist of a list of triangles projected onto it) and check the initial candidate for one ray-> abab test + search.

Given the feedback, there is another simple option - dividing the space into a simple 3D grid, where each measurement can be divided into a histogram of x / y / z locations or even regularly.

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

• There are ~ 60,000 extreme cells, which implies an order of 10 triangles per cell

• Cautions: triangles should be placed on each cell that they occupy - a conservative algorithm places them in cells to which they do not belong; large triangles are likely to require clipping and reassembly.

Answer 2

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

These are "approximate closest neighbors." I know you are looking for something a little different, but here is how you can use this to speed up data processing:

• Submission of points in ANN.
• Request a custom selection (think of it as a “handle for each grid”) of the radius around each vertex that you want to give to the beam, and find out the vertices of the grid that are within the range.
• Select only the triangles within this range, and trace the beam along the normal to find the one you want.

Reasonably choosing a search radius, you will definitely get significant acceleration without compromising accuracy.

Answer 3

Although this code is a bit old and with the help of SDS 3DS Max, it gives a pretty good tree-like system for collisions deformations of objects and objects in C ++. It is impossible to say if it is a Quad-tree, AABB-tree or even an OBB-tree (comments are also a bit scarce).

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

This will require a transfer from Max to your own system, but it can be worth the effort.