网格到网格交点

Question

我正在寻找一个库或一篇论文，它描述了如何确定一个三角形网格是否与另一个三角形网格相交。

有趣的是，我一无所获。如果在CGAL中有什么方法可以做到这一点，那我就难倒了。

这看起来显然应该是可能的，因为三角形相交是可能的，并且因为每个网格包含有限数量的三角形。但我假设一定有比明显的O(n*m)方法更好的方法，其中一个网格有n个三角形，另一个网格有m个三角形。

Answer 1

我们通常使用CGAL的方式是使用CGAL::box_intersection_d。

您可以通过将此example与此one混合使用来实现它。

编辑：

从CGAL4.12开始，现在有了函数CGAL::Polygon_mesh_processing::do_intersect()。

Answer 2

Real-Time Collision Detection一书对实现这样的算法有一些很好的建议。基本方法是使用空间分区或边界体积来减少您需要执行的三三交叉点测试的数量。

有许多很好的学术包可以解决这个问题，包括Proximity Query Package，GAMMA research group at University of North Carolina的其他工作，SWIFT，I-COLLIDE和RAPID都是众所周知的。检查这些库上的许可证是否可接受。

Open Dynamics Engine (ODE)是一个物理引擎，包含大量交集原语的优化实现。您可以在他们的wiki上查看三角形-三角形交集测试的文档。

虽然这并不是您想要的，但我相信使用CGAL - Tree of Triangles, for Intersection and Distance Queries也是可能的。

Answer 3

我认为您遗漏的搜索词是overlay。例如，这里有一个关于Surface Mesh Overlay的网页。该网站有一个简短的参考书目，全部出自同一作者之手。这是另一篇关于这个主题的论文："Overlay mesh construction using interleaved spanning trees，“Infocom2004: IEEE计算机和通信学会的第23届年度联席会议。另请参阅GIS问题“Performing Overlay of Two Triangulated Irregular Networks (TIN)”。