7

你能推荐我吗...

  • AABB树的经过验证的轻量级C / C ++实现？
  • 或者，另一种有效的数据结构，加上轻量级的 C/C++ 实现，来解决大量光线与大量三角形相交的问题？

“大数字”意味着射线和三角形都有几个 100k。

我知道 AABB 树是 CGAL 库的一部分，并且可能是 Bullet 等游戏物理库的一部分。但是，我不希望在我的项目中增加大量额外库的开销。理想情况下，我想使用一个小型的浮点型模板化标头实现。只要它可以轻松集成到我的项目中，我也会使用一堆 CPP 文件。依赖boost没问题。

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

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

编辑

几个答案/评论指向最近邻数据结构。我创建了一个关于使用最近邻方法处理光线网格交叉点时出现的问题的小插图。最近邻方法可以用作在许多情况下都有效的启发式方法，但我不相信它们实际上可以系统地解决问题，就像 AABB 树一样。

在此处输入图像描述

4

3 回答 3

2

虽然这段代码有点旧并且使用的是 3DS Max SDK，但它为 C++ 中的对象-对象碰撞变形提供了一个相当不错的树系统。一眼看不出来它是四叉树、AABB-tree 还是 OBB-tree（评论也有点吝啬）。

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

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

于 2013-03-03T23:03:18.333 回答
1

如果没有实时要求，我会先尝试蛮力。

1M * 1M 射线->三角形测试的运行时间不应超过几分钟（在 CPU 中）。

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

还取决于拓扑的病态程度，可以尝试将目标网格环境映射到单位立方体上（每个像素将由投影在其上的三角形列表组成）并通过单个射线-> aabb 测试 + 查找来测试初始候选对象.

鉴于反馈，还有一个更简单的选项需要考虑——将空间划分为简单的 3D 网格，其中每个维度都可以通过 x/y/z 位置的直方图甚至定期细分。

  • 100x100x100 网格的大小非常易于管理，只有 1e6 个条目
  • 要访问的最大立方体数量与直径成正比（最大 300）

  • 有约 60000 个极端细胞，这表明每个细胞有 10 个三角形

  • 警告：三角形必须放置在它们占据的每个单元格上——保守的算法将它们放置在它们不属于的单元格上；大三角形可能需要剪裁和重新组装。

于 2013-02-15T15:37:07.610 回答
1

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

它是“近似最近邻”。我知道，您正在寻找稍微不同的东西，但您可以通过以下方式来加快数据处理速度：

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

通过明智地选择搜索半径，您肯定会在不影响准确性的情况下获得相当大的加速。

于 2013-02-19T13:05:30.183 回答