网格到网格的交叉点
我正在寻找一个库或一篇论文来描述如何确定一个三角形网格是否与另一个三角形网格相交。
有趣的是我空了。如果有什么方法可以在 CGAL 中做到这一点，我却无法实现。
看起来这显然应该是可能的，因为三角形相交是可能的，并且每个网格包含有限数量的三角形。但我认为一定有一种比明显的 O(n*m) 方法更好的方法，其中一个网格有 n 个三角形，另一个网格有 m 个三角形。
I'm looking for a library or a paper that describes how to determine if one triangular mesh intersects another.
Interestingly I am coming up empty. If there is some way to do it in CGAL, it is eluding me.
It seems like it clearly should be possible, because triangle intersection is possible and because each mesh contains a finite number of triangles. But I assume there must be a better way to do it than the obvious O(n*m) approach where one mesh has n triangles and the other has m triangles.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我们通常使用 CGAL 的方式是使用 CGAL::box_intersection_d 。
您可以通过混合此示例与这个一个。
编辑：
从CGAL 4.12开始，现在有函数
CGAL::Polygon_mesh_processing::do_intersect()。The way we usually do it using CGAL is with CGAL::box_intersection_d.
You can make it by mixing this example with this one.
EDIT:
Since CGAL 4.12 there is now the function
CGAL::Polygon_mesh_processing::do_intersect().《实时碰撞检测》一书对于实现此类算法有一些很好的建议。基本方法是使用空间分区或包围体来减少需要执行的三重相交测试的数量。
有许多很好的学术包可以解决这个问题，包括邻近查询包，以及北卡罗来纳大学 GAMMA 研究小组、SWIFT、I-COLLIDE 和 RAPID 的其他工作包括都是众所周知的。检查这些库的许可证是否可接受。
开放动力学引擎 (ODE) 是一个物理引擎，包含大量相交基元的优化实现。您可以在其 上查看三角形-三角形相交测试的文档维基百科。
虽然这并不完全是您想要的，但我相信 CGAL 也可以做到这一点 - 三角形树，用于交集和距离查询
The book Real-Time Collision Detection has some good suggestions for implementing such algorithms. The basic approach is to use spatial partitioning or bounding volumes to reduce the number of tri-tri intersection tests that you need to perform.
There are a number of good academic packages that address this problem including the Proximity Query Package, and the other work of the GAMMA research group at University of North Carolina, SWIFT, I-COLLIDE, and RAPID are all well known. Check that the licenses on these libraries are acceptable.
The Open Dynamics Engine (ODE), is a physics engine that contains optimized implementations of a large number of intersection primitives. You can check out the documentation for the triangle-triangle intersection test on their wiki.
While it isn't exactly what you're looking for, I believe that this is also possible with CGAL - Tree of Triangles, for Intersection and Distance Queries
我认为您缺少的搜索词是覆盖。例如，这里是 Surface Mesh Overlay 上的网页。该网站有一个简短的参考书目，全部由同一作者撰写。
这是关于该主题的另一篇论文：“使用交错生成树的覆盖网格构建，”
INFOCOM 2004：IEEE 计算机和通信学会第二十三届年度联合会议。
另请参阅 GIS SE 问题“执行两个不规则三角网络 (TIN) 的叠加”。
I think the search term you are missing is overlay. For example, here is a web page on Surface Mesh Overlay. That site has a short bibliography, all by the same authors.
Here is another paper on the topic: "Overlay mesh construction using interleaved spanning trees,"
INFOCOM 2004: Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies.
See also the GIS SE question, "Performing Overlay of Two Triangulated Irregular Networks (TIN)."
为了补充其他答案，还有涉及凸多面体的 3D Minkowski 和的技术 - 凹多面体可以分解为凸部分。查看此。
To add to the other answers, there are also techniques involving the 3D Minkowski sum of convex polyhedra - concave polyhedra can be decomposed into convex parts. Check out this.
在 libigl 中，我们封装了 cgal 的
CGAL::box_intersection_d来与网格相交顶点V和面F以及另一个具有顶点U和面G的网格，存储相交对将面作为IF中的行：这将忽略自相交。为了完整起见，我会提到我们还支持在单独的函数中自相交：
In libigl, we wrap up cgal's
CGAL::box_intersection_dto intersect a mesh with verticesVand facesFwith another mesh with verticesUand facesG, storing pairs of intersecting facets as rows inIF:This will ignore self-intersections. For completeness, I'll mention that we also support self-intersections in a separate function:
其中一种方法是为每个对象构建一个包围体层次结构BVH（例如AABB树）网。
然后，我们需要找出两个网格中是否存在一对相交的三角形，并且使用构造的层次结构比检查两个网格中每个可能的三角形对要快得多（最多为对数时间复杂度）。
例如，您可以查看开源库 MeshLib，其中该算法在 findCollidingTriangles 函数，必须使用
firstIntersectionOnly=true 参数仅查找碰撞事实而不是所有碰撞三角形对。One of the approaches is to construct a bounding volume hierarchy BVH (e.g. AABB-tree) for each mesh.
Then one will need to find whether there is a pair of intersecting triangles from two meshes, and it will be much faster (at best logarithmic time complexity) using constructed hierarchies than checking every possible pair of triangles from two meshes.
For example, you can look at open-source library MeshLib where this algorithm is implemented in findCollidingTriangles function, which must be called with
firstIntersectionOnly=trueargument to find just the fact of collision instead of all colliding triangle pairs.