Mesh to mesh intersections

computational-geometry mesh surface triangulation
Doug McClean picture Doug McClean · Nov 1, 2011 · Viewed 9.1k times · Source

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.

Answer

sloriot picture sloriot · Nov 2, 2011

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

Related questions

Algorithm or software for slicing a mesh

What is the right approach for slicing a 3D mesh? The mesh are all closed surfaces and the slices need to be binary images of what's inside the mesh. So for example, a mesh representing a sphere and slice images …

Read More
Mesh Generation for Computational Science in Python

I have a need for a Python module/package that provides a mesh on which I can do computational science? I am not doing graphics, so I don't think the blender package is what I want. Does anyone know of …

Read More
How to determine if a list of polygon points are in clockwise order?

Having a list of points, how do I find if they are in clockwise order? For example: point[0] = (5,0) point[1] = (6,4) point[2] = (4,5) point[3] = (1,5) point[4] = (1,0) would say that it is anti-clockwise (or counter-clockwise, for some people).

Read More