c++ - Ray-mesh交集或AABB树在C++中的实现，开销很小？

你能推荐我...

是AABB树的成熟轻量级C/C++实现吗？

还是另一种有效的数据结构，再加上轻量级的C/C++实现，可以解决将大量光线与大量三角形相交的问题？

“大数”是指光线和三角形都为100k。

我知道AABB树是CGAL库的一部分，并且可能是子弹之类的游戏物理库的一部分。但是，我不想在我的项目中增加大量额外的库。理想情况下，我想使用一个小的float型模板化仅 header 实现。只要将CPP文件轻松集成到我的项目中，我也会选择一堆CPP文件。对boost的依赖是可以的。

是的，我已经用谷歌搜索，但是没有成功。

我应该提到，我的应用程序上下文是网格处理，而不是渲染。简而言之，我将引用网格的拓扑结构从3D扫描转移到网格的几何形状。我正在从顶点并沿着引用网格的法线朝3D扫描射击光线，我需要恢复这些光线与扫描的交点。

编辑

一些答案/注释指向了最近邻居数据结构。我创建了一个小插图，说明当使用最近的邻居方法接近射线-网格相交时出现的问题。可以将最近邻居方法用作在许多情况下都可以使用的启发式方法，但是我不相信它们实际上可以像AABB树那样系统地解决问题。

最佳答案

尝试使用ANN库:
http://www.cs.umd.edu/~mount/ANN/

这是“大约最近的邻居”。我知道，您正在寻找稍微不同的东西，但是这是您可以使用它来加快数据处理速度的方法:

将点馈入ANN。

在要射线转换的每个顶点周围查询用户可选的半径(将其视为“每个网格旋钮”)，并找出在范围内的网格顶点。

仅选择该范围内的三角形，然后沿法线进行光线跟踪以找到所需的三角形。

通过明智地选择搜索半径，您一定会获得相当大的提速，而不会影响精度。