Intersection

The functions intersections and 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 SurfaceMesh).

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.

all-pairs check

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.

#include "geometrycentral/surface/intersection.h"

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

Example

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

Helper Types

Result

The result is returned as a SurfaceIntersectionResult, which has 3 fields:

Field	Meaning
SurfacePoint endPoint	the point the path ended at
std::vector<Vector3> points	endpoints of segments along intersection
std::vector<std::array<size_t,2>> edges	segments along intersection, as pairs of indices into the points list
bool hasIntersections	were there any intersections?