两个三角形网格的交集

Question

目前我正在寻找一种有效的算法来计算两个三角形网格的交集。我在网上搜索过，但没有找到有价值的材料。《实时碰撞检测》一书是一本很有帮助的书，但对于我的任务来说太复杂了。我还找到了这篇文章：Triangle to Triangle CollisionDetection in 3D。不过我希望找到有关该算法的详细描述。

问候 慢跑

Answer 1

这取决于网格大小，测试每个网格中的每个三角形仅在小网格中有效，因为它具有 n^2 复杂度。

为了解决这个问题，大多数算法首先使用 空间分割 将空间细分为更小的空间，然后分别处理每个空间。

对于空间分割，大多数算法使用八叉树或 BSP树，但是如果您不需要使事情复杂化，您可以将空间细分为 n 个框，然后检查每个框中的三角形三角形相交