Mesh to mesh intersections

Question

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.

Piston

The 'obvious' approach will give false negatives if one of the meshes is completely inside the other. – Destructionist

I'm interested in collisions between the meshes as zero-thickness surfaces. I see how that would happen if I was interested in collisions between the meshes interpreted as polyhedra. – Piston

See also triangle-triangle here – Caporal

Answer 1

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().

Doglike

The examlpes 4 and 5 are very helpful for beginners. However it is not clear how to create a tree structure of AABBs in order to speed up the whole process. Furthermore the examples are more clear for the self-intersection case. In case of two separate meshes it is not very clear (and I guess that throwing all the triangles/boxes in one vector is not optimal at all). Any suggestions one the above? – Sunil

You need to use one vector per mesh and use CGAL::box_intersection_d(). – Doglike

Since CGAL 4.12 there is now the function [CGAL::Polygon_mesh_processing::do_intersect()](doc.cgal.org/latest/Polygon_mesh_processing – Doglike

Answer 2

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

Walden

Answer 3

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)."

Jefferey

Answer 4

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.

Destructionist

Answer 5

In libigl, we wrap up cgal's CGAL::box_intersection_dto intersect a mesh with vertices V and faces F with another mesh with vertices U and faces G, storing pairs of intersecting facets as rows in IF:

igl::intersect_other(V,F,U,G,false,IF);

This will ignore self-intersections. For completeness, I'll mention that we also support self-intersections in a separate function:

igl::self_intersect(V,F,...,IF);

Sarette

Answer 6

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=true argument to find just the fact of collision instead of all colliding triangle pairs.

Jennettejenni