Databases
StackOverflow2013
Postsdbo
PORay-mesh intersection or AABB tree implementation in C++ with little overhead?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORay-mesh intersection or AABB tree implementation in C++ with little overhead?
    text
    copied!<p>Can you recommend me...</p> <ul> <li>either a proven lightweight C / C++ implementation of an AABB tree?</li> <li>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?</li> </ul> <p>"Large number" means several 100k for both rays and triangles.</p> <p>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 <code>boost</code> is ok.</p> <p>Yes, I have googled, but without success.</p> <p>I should mention that my <strong>application context</strong> 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. </p> <p><strong>Edit</strong></p> <p>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.</p> <p><img src="https://i.stack.imgur.com/uKj5m.png" alt="enter image description here"></p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload