selfIntersections find intersections between a pair of triangle meshes, or between a mesh and itself.
Intersections are meaningful only for meshes that have an extrinsic geometry, encoded via an
EmbeddedGeometryInterface (e.g. a
VertexPositionGeometry). These routines assume the meshes are triangle meshes, but otherwise works with arbitrary polygon soup (encoded via
Intersections are returned as an “edge soup,” i.e., a collection of line segments with no explicit connectivity between shared endpoints.
Triangle-triangle intersections are computed using Tomas Moller’s 1997 triangle intersection routine, provided here.
The current implementation does a naive all-pairs check, which takes O(nm) time (or O(n^2) time in the case of self-intersections). This makes the methods very slow for large meshes. A natural future improvement would be to perform hierarchical collision checking.
SurfaceIntersectionResult intersections(EmbeddedGeometryInterface& geometry1, EmbeddedGeometryInterface& geometry2);
Find all intersections between two meshes.
geometry1: the geometry of the first mesh
geometry2: the geometry of the second mesh
SurfaceIntersectionResult selfIntersections(EmbeddedGeometryInterface& geometry);
Find all intersections between non-adjacent pairs of triangles in a single mesh, i.e., triangles that do not share vertices or edges. (Adjacent triangles are excluded, since otherwise we would find all the mesh vertices and edges in addition to more global intersections.) Note that for polygon soup, where triangles have identical vertex locations but there is no explicit connectivity, intersections will still be found between adjacent triangles (such as the triangles in the eyes of the model pictured above).
geometry: the input geometry
#include "geometrycentral/surface/surface_mesh.h" #include "geometrycentral/surface/meshio.h" #include "geometrycentral/surface/intersection.h" // Load two meshes std::unique_ptr<SurfaceMesh> mesh1, mesh2; std::unique_ptr<VertexPositionGeometry> geometry1, geometry2; std::tie(mesh1, geometry1) = readSurfaceMesh(filename1); std::tie(mesh2, geometry2) = readSurfaceMesh(filename2); // Find self-intersections in mesh1 SurfaceIntersectionResult r1 = selfIntersections( *geometry1 ); // Find intersections between the two meshes SurfaceIntersectionResult r12 = intersections( *geometry1, *geometry2 );
The result is returned as a
SurfaceIntersectionResult, which has 3 fields:
||the point the path ended at|
||endpoints of segments along intersection|
||segments along intersection, as pairs of indices into the
||were there any intersections?|