我正在寻找一个图书馆或一篇论文来描述如何确定一个三角形网格是否与另一个三角形网格相交。
有趣的是，我很空虚。如果有一些方法可以在CGAL中做到这一点，它就是在逃避我。
看起来它应该是可能的，因为三角形交叉是可能的，因为每个网格包含有限数量的三角形。但我认为必须有一种比明显的O（n * m）方法更好的方法，其中一个网格有n个三角形而另一个网格有m个三角形。
我正在寻找一个图书馆或一篇论文来描述如何确定一个三角形网格是否与另一个三角形网格相交。
有趣的是，我很空虚。如果有一些方法可以在CGAL中做到这一点，它就是在逃避我。
看起来它应该是可能的，因为三角形交叉是可能的，因为每个网格包含有限数量的三角形。但我认为必须有一种比明显的O（n * m）方法更好的方法，其中一个网格有n个三角形而另一个网格有m个三角形。
我们通常使用CGAL进行的方式是 CGAL :: box_intersection_d。
这本书 实时碰撞检测 对实现这些算法有一些很好的建议。基本方法是使用空间分区或边界卷来减少需要执行的三元交叉测试的数量。
有许多好的学术套餐可以解决这个问题，包括 邻近查询包，以及其他的工作 北卡罗来纳大学GAMMA研究小组，SWIFT，I-COLLIDE和RAPID都是众所周知的。检查这些库上的许可证是否可接受。
开放动力引擎（ODE）是一个物理引擎，它包含大量交集原语的优化实现。您可以查看有关它们的三角形 - 三角形相交测试的文档 维基。
虽然它并不完全符合您的要求，但我相信CGAL也可以做到这一点 - 三角形树，用于交叉点和距离查询
我认为你缺少的搜索词是 覆盖。例如，这是一个网页 表面网格叠加。该网站有一个简短的参考书目，全部由同一作者撰写。 这是关于这个主题的另一篇论文：“使用交错生成树叠加网格构造” INFOCOM 2004：IEEE计算机和通信协会第二十三届年度联席会议。 另见GIS SE问题，“执行两个不规则三角网的叠加（TIN）“。
为了增加其他答案，还有涉及3D Minkowski和凸多面体的技术 - 凹多面体可以分解成凸面部分。查看 这个。
在 libigl，我们结束了cgal的 CGAL::box_intersection_d使网格与顶点相交 V 和面孔 F 与另一个带顶点的网格 U 和面孔 G，将成对的交叉面存储为行 IF：
igl::intersect_other(V,F,U,G,false,IF);
这将忽略自我交叉。为了完整起见，我将提到我们还在一个单独的函数中支持自交叉：
igl::self_intersect(V,F,...,IF);