computational-geometry - 网格到网格的交叉点

Question

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

有趣的是，我空空如也。如果在 CGAL 中有某种方法可以做到这一点，那我就想不通了。

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

score 8 · Accepted Answer

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

您可以通过将此示例与此示例混合来实现。

编辑：

score 4 · Accepted Answer

Real-Time Collision Detection一书为实现此类算法提供了一些很好的建议。基本方法是使用空间分区或边界体来减少您需要执行的三三相交测试的数量。

有许多很好的学术包可以解决这个问题，包括Proximity Query Package ，以及北卡罗来纳大学 GAMMA 研究小组的其他工作，SWIFT、I-COLLIDE 和 RAPID 都是众所周知的。检查这些库上的许可证是否可接受。

开放动态引擎 (ODE) 是一种物理引擎，包含大量相交基元的优化实现。您可以在他们的wiki上查看三角形-三角形相交测试的文档。

虽然这不是您正在寻找的东西，但我相信这也可以通过 CGAL -三角形树，用于相交和距离查询

score 1 · Accepted Answer

我认为您缺少的搜索词是overlay。例如，这里有一个关于Surface Mesh Overlay的网页。该站点有一个简短的参考书目，全部由同一作者撰写。这是有关该主题的另一篇论文：“使用交错生成树的叠加网格构造”， INFOCOM 2004：IEEE 计算机和通信协会第二十三届年度联合会议。另请参阅 GIS SE 问题“执行两个不规则三角网络 (TIN) 的叠加”。

score 1 · Accepted Answer

在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);

score 1 · Accepted Answer

为了增加其他答案，还有涉及凸多面体的 3D Minkowski 和的技术 - 凹多面体可以分解为凸部分。看看这个。

5 回答 5