C++中的Ray-mesh交集或AABB树实现,开销很小？
DCS*_*DCS 6 c++ geometry intersection aabb
你能推荐我吗......
- 要么是经过验证的AABB树的轻量级C/C++实现？
- 或者,另一种有效的数据结构,以及轻量级的C/C++实现,以解决大量三维光线交叉的问题？
"大数字"表示光线和三角形都有几个100k.
我知道AABB树是CGAL库的一部分,可能是像Bullet这样的游戏物理库.但是,我不希望在我的项目中增加一个巨大的额外库.理想情况下,我想使用一个小型浮点型模板化头文件实现.只要它在我的项目中轻松集成,我也会选择一堆CPP文件.依赖boost是可以的.
是的,我用Google搜索,但没有成功.
我应该提一下,我的应用程序上下文是网格处理,而不是渲染.简而言之,我将参考网格的拓扑结构从3D扫描转移到网格的几何体.我正在从顶点和参考网格的法线向3D扫描拍摄光线,我需要通过扫描恢复这些光线的交叉点.
编辑
几个答案/评论指向最近邻数据结构.我已经创建了一个关于使用最近邻方法逼近光线网格交叉点时出现的问题的小图.最近邻方法可以用作在许多情况下起作用的启发式方法,但我不相信它们实际上是系统地解决问题,就像AABB树一样.
如果没有实时要求，我会首先尝试暴力破解。
1M * 1M 光线->三角形测试的运行时间不会超过几分钟（在 CPU 中）。
如果这是一个问题，第二好的办法是通过计算目标网格中三角形/多边形之间的邻接图/关系来限制搜索区域。最初的猜测失败后，可以尝试相邻的三角形。这当然依赖于缺乏自遮挡/多个生命点。（我认为这是“可见性不适用于这个问题”的一种解释）。
另外，根据拓扑的病态程度，可以尝试将目标网格环境映射到单位立方体上（每个像素将由投影在其上的三角形列表组成），并通过单个射线-> aabb 测试 + 查找来测试初始候选者。
根据反馈，还有一个更简单的选项可供考虑 - 将空间划分为简单的 3D 网格，其中每个维度都可以通过 x/y/z 位置的直方图甚至定期进行细分。
- 100x100x100 网格的1e6 条目大小非常易于管理
- 访问的最大立方体数量与直径成正比（最多 300）
大约有 60000 个极端单元，这表明每个单元有 10 个三角形
注意事项：三角形必须放置在它们占据的每个单元格上——保守的算法将它们放置在它们不属于的单元格上；大三角形可能需要修剪和重新组装。