Dou*_*ean 11 mesh surface triangulation computational-geometry
我正在寻找一个图书馆或一篇论文来描述如何确定一个三角形网格是否与另一个三角形网格相交.
有趣的是,我很空虚.如果有一些方法可以在CGAL中做到这一点,它就是在逃避我.
看起来它应该是可能的,因为三角形交叉是可能的,因为每个网格包含有限数量的三角形.但我认为必须有一种比明显的O(n*m)方法更好的方法,其中一个网格有n个三角形而另一个网格有m个三角形.
《实时碰撞检测》一书对于实现此类算法有一些很好的建议。基本方法是使用空间分区或包围体来减少需要执行的三重相交测试的数量。
有许多很好的学术包可以解决这个问题，包括Proximity Query Package以及北卡罗来纳大学 GAMMA 研究小组的其他工作，SWIFT、I-COLLIDE 和 RAPID 都是众所周知的。检查这些库的许可证是否可接受。
开放动力学引擎 (ODE) 是一个物理引擎，包含大量相交基元的优化实现。您可以在其wiki上查看有关三角形-三角形相交测试的文档。
虽然这不完全是您正在寻找的，但我相信使用 CGAL -三角形树，用于交叉点和距离查询也是可能的
我认为您缺少的搜索词是“overlay”。例如，这是一个关于Surface Mesh Overlay的网页。该网站有一个简短的参考书目，全部由同一作者撰写。这是关于该主题的另一篇论文：“使用交错生成树的覆盖网格构造”， INFOCOM 2004：IEEE 计算机和通信协会第二十三届年度联合会议。另请参阅 GIS SE 问题“执行两个不规则三角网络 (TIN) 的叠加”。