C++中实现Ray-mesh交点或AABB树时是否存在额外开销的问题？

Question

能否推荐一款经过验证的轻量级C/C++ AABB树实现？

或者，另外一种高效的数据结构，加上一个轻量级的C/C++实现，来解决大量光线与大量三角形相交的问题？

"大量"意味着光线和三角形都有几十万个。

我知道AABB树是CGAL库和游戏物理库（如Bullet）的一部分。但是，我不想在我的项目中增加一个巨大的额外库的负担。理想情况下，我想使用一个小型的浮点类型模板化头文件实现。只要它容易集成到我的项目中，我也可以选择一些CPP文件的东西。依赖于boost也可以。

是的，我已经谷歌过了，但没有成功。

我应该提到我的应用场景是网格处理，而不是渲染。简而言之，我正在将参考网格的拓扑结构转移到来自3D扫描的网格的几何结构中。我从参考网格的顶点和法线向3D扫描发射射线，并且需要恢复这些射线与扫描的交点。

编辑

有几个答案/评论指向最近邻数据结构。我创建了一个小插图，说明了当射线-网格相交时使用最近邻方法会出现的问题。最近邻方法可以用作在许多情况下工作的启发式方法，但我并不认为它们像AABB树一样系统地解决问题。

- DCS

---

它是室内、室外、CAD、FPS吗？几何形状是动态的还是静态的？多大比例的多边形是可见的？它是用于从单个点（或多个点==阴影缓冲区）进行渲染还是用于许多点（辐射度）？ - Aki Suihkonen

我的应用程序上下文是网格处理，而不是渲染。更具体地说，我正在将参考网格的拓扑结构转移到来自3D扫描的网格的几何形状。我沿着参考网格法线方向发射光线，朝向3D扫描，并且需要恢复这些光线与扫描的交点。可见性问题不适用于此问题。几何形状是静态的。从许多点发射光线（尽管如上所述与渲染无关）。 - DCS

八叉树怎么样？它们相当简单易实现。 - Bartek Banachewicz

@BartekBanachewicz：我认为使用八叉树存储三角形的问题在于三角形会重叠，而八叉树单元格不会重叠，或者我错了吗？我非常确定AABB树单元格（即边界框）会重叠，这就是为什么它们被用于解决这种问题的原因。 - DCS

你不能在超过一个八叉树叶子单元格中引用同一个三角形吗？ - Pete

Answer 1

虽然这段代码有点老，而且使用了3DS Max SDK，但它在C++中提供了一个相当不错的物体-物体碰撞变形树系统。一眼看不出它是四叉树、AABB树还是OBB树（注释也有点简略）。

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

这将需要从Max翻译到您自己的系统，但可能值得努力。

- Robert Templeton

---

+1 如果你能第一个提供与交集相关的代码，我会看一下。 - DCS

Answer 2

如果没有实时要求，我会首先尝试暴力破解。在CPU中运行1M * 1M光线->三角形测试不应该超过几分钟。

如果这是一个问题，第二好的办法是通过计算目标网格中三角形/多边形之间的邻接图/关系来限制搜索区域。在初始猜测失败后，可以尝试相邻的三角形。当然，这取决于缺乏自遮挡/多个击中点。(我认为这是“可见性不适用于此问题”的一种解释)。

此外，根据拓扑结构有多么病态，可以尝试将目标网格环境映射到单位立方体上(每个像素由投影在其上的三角形列表组成)，并通过单个光线->aab测试+查找来测试初始候选。

根据反馈，还有一个简单的选择需要考虑——将空间分割为简单的3D网格，其中每个维度都可以通过x/y/z位置的直方图甚至规则地细分。

• 100x100x100网格是1百万个条目的非常可管理的大小
• 要访问的立方体的最大数量与直径成比例（最多300个）

• 有约60000个极限单元，这表明每个单元大约有10个三角形

• 注意事项：必须在它们占用的每个单元上放置三角形--保守算法将它们放置到它们不属于的单元格中；大三角形可能需要剪裁和重新组装。

- Aki Suihkonen

---

很遗憾，有时间限制。否则我就不会担心数据结构了，对吧？;-) 拓扑结构还好，但形状可能比较复杂。将它们映射到单位立方体/球体/圆柱体上是行不通的（已经尝试过）。对于射线网格交点，以第一个猜测点为中心周围搜索可能会误差很大——想象一下一条射线仅穿过离其起点最近的三角形，然后击中完全不同的地方。实际上，AABB树是这个问题的规范数据结构，据我所知。我只是缺乏一个实现，而且我不确定自己是否写得出来。 - DCS

你提出的3D网格解决方案很有趣，但几乎就是AABB树的定义，只是增加了分区的层次性思想。如果我实现你的解决方案，我就非常接近实现AABB树了，而这正是我想通过提问来避免“重新发明轮子”的精神所在。此外，交叉计算可能会非常棘手，这也是我更喜欢经过验证的代码的另一个原因。然而，鉴于迄今为止收到的反馈，似乎不存在一个现成的轻量级C++实现AABB树的解决方案。 - DCS

Answer 3

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

这是“近似最近邻居”。我知道，您正在寻找略有不同的东西，但是以下是如何使用它来加速数据处理的方法：

1. 将点输入ANN。
2. 查询用户可选择（将其视为“每个网格旋钮”）的半径，以围绕要从中进行光线投射并查找在范围内的网格顶点。
3. 仅选择在该范围内的三角形，并沿法线进行光线跟踪以找到所需的三角形。

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

- Rahul Banerjee

---

你有机会看一下ANN吗？我应该补充说明，这个库不是可重入的。 - Rahul Banerjee

抱歉回复晚了，我在旅行。我知道ANN（以及其他最近邻问题的库）。问题在于最近邻搜索可以是射线网格交叉的一个不错的启发式方法，但并不保证在所有情况下都能得到正确的答案（如AABB树所做的那样）。有些情况下，正确相交三角形的顶点不在源顶点的最近邻之间。正如我在Aki Suihkonen的评论中指出的那样，想象一下一条射线只是穿过网格，然后在完全不同的地方击中它。此外，半径可能很难确定。 - DCS

我已经编辑了问题，添加了上面评论中提到的问题的插图。 - DCS

感谢您说明那些边角（字面意思！）情况。我理解为什么这是一个具有挑战性的问题。加速结构似乎是您最好的选择。 - Rahul Banerjee