Intersect

The Intersect module computes geometric intersections between polygons and segments. All intersection computations are geometrically and topologically exact, using exact arithmetic.

Include the module with:

#include <trueform/intersect.hpp>

Overview

The Intersect module computes intersection geometry without modifying the input meshes:

• Mesh-mesh intersections: Curves where two or more meshes intersect
• Self-intersections: Curves where a mesh intersects itself
• Segment intersections: Where 2D or 3D segments cross

Curves are returned as tf::curves_buffer objects for analysis, visualization, or further processing.

Supported Input

Intersection computation supports a wide range of input geometry:

• Open and closed meshes — boundaries are handled correctly
• Non-manifold edges — edges shared by 3 or more faces
• Coplanar faces — overlapping faces from the same or different meshes
• Self-intersecting geometry — meshes that intersect themselves are detected and curves are extracted
• Crossing intersection curves — where two or more curves meet at a point, crossings can be resolved by splitting curves at the crossing point. Configured via tf::intersect_config — see Intersection Configuration.

Exact Arithmetic

All mesh and segment intersection computations use exact integer arithmetic. Input coordinates are scaled to an integer range, and all geometric predicates (orientation tests, intersection point computation) are performed with exact integer arithmetic.

The lattice resolution is selected by the Int template parameter. By default it is resolved automatically from the input coordinate type:

// Auto-resolved: int32 for float input, int64 for double input
auto curves = tf::make_intersection_curves(mesh1.polygons(), mesh2.polygons());

// Explicit override
auto curves = tf::make_intersection_curves<tf::exact::int64>(
    mesh1.polygons(), mesh2.polygons());

The Int parameter controls the entire arithmetic chain via tf::exact::meta<Int>:

Intersection Configuration

tf::intersect_config bundles the knobs the intersection pipeline takes:

A config is implicitly constructible from intersect_mode, so any function that takes a config also accepts a mode directly:

tf::intersect_config{}                          // defaults
tf::intersect_mode::primitives                  // implicit from mode
tf::intersect_config{mode, 1e-6}                // mode + tolerance
tf::intersect_config{tf::intersect_mode::primitives |
                     tf::intersect_mode::within, 1e-6}

Mode

tf::intersect_mode carries the classifier and optional within request in one bitmask. The canonical spelling is primitives | within.

Within

within asks for each form's own self-intersections. Its two halves — the form's self records, and the resolution of crossings within one contour class — are one request and never separable. A one-form build implies it.

Spell it whenever a form can self-overlap, e.g. meshes concatenated into one operand; see CSG: Self-Arrangements.

Contour crossings

Crossings between contours are resolved unconditionally, not on request: between contour classes whenever a third tag exists to make such a pair, and within one class whenever the run is within. That was always the behaviour of every default; there is no flag to turn it off with.

// The N-form default already resolves what its arity can make
auto curves = tf::make_intersection_curves(tf::make_range(forms, forms + 3));

Tolerance

A non-zero tolerance is a statement about the INPUT, not about a predicate, and it promises exactly two things. ALMOST-COPLANAR IS COPLANAR: faces whose directions agree pool onto one committed plane, and a face that another form's vertex stands within the tolerance of commits a plane together with that vertex's own faces lying within the tolerance of it. ALMOST-ON-PLANE IS ON-PLANE: a vertex within the tolerance of a committed plane is dropped exactly onto it — where the plane settled, not where its face began. First the planes pull: a face commits to a plane only if its own corners move within the tolerance onto it. Then the vertices drop, bounded by the same tolerance. Everywhere the tolerance does not act it is zero: a vertex nothing pulled is not moved, and the output states it exactly as you gave it. What the pipeline arranges is that moved mesh, EXACTLY: every predicate below the placement runs at zero, so the tolerance only ever adds contacts the input states within it, and never removes one it states exactly. A plane its corners cannot follow, and a vertex no committed plane can hold within the tolerance, keep their own positions — the tolerance never invents one.

auto curves = tf::make_intersection_curves(
    mesh1.polygons(), mesh2.polygons(),
    tf::intersect_config{tf::intersect_mode::primitives, 1e-6});

A tolerance of 0 is the identity: nothing is pooled, nothing moves, no placement table is built, and the result is the exact arrangement of the input as given.

Self-Intersection Test

tf::has_self_intersections is the verdict of tf::polygon_intersections' one-form build: true exactly when that build would state a self record.

bool meets_itself = tf::has_self_intersections(polygons);

// A form already carrying the structures pays for none of them
auto form = polygons | tf::tag(tree) | tf::tag(fm) | tf::tag(mel);
bool tagged_answer = tf::has_self_intersections(form);

// The lattice is resolved from the input, or stated as everywhere else
bool at_int64 = tf::has_self_intersections<tf::exact::int64>(polygons);

This is that build's discovery tier, elections and all, stopped at the first record — so a mesh that meets itself is answered without the rest of it being seen, and a mesh that does not is the whole discovery and nothing above it. A shared vertex or edge is not itself a contact; any other touching — between neighbouring faces too — is one, and the lattice decides it exactly.

Missing structures — the tree, the face membership, the manifold edge link — are built for the call, so a bare mesh is a valid operand. The input must be 3D.

Intersection Curves

The simplest way to work with intersections is through curves — connected paths of intersection points.

Between Two Meshes

Extract intersection curves where two meshes intersect:

auto curves = tf::make_intersection_curves(mesh1.polygons(), mesh2.polygons());

Default config: primitives, exact, not within. With two meshes every contour is of the one class (A,B); crossings among them — e.g. from disjoint components of one mesh — are resolved when the run is within.

auto curves = tf::make_intersection_curves(
    mesh1.polygons(), mesh2.polygons(), tf::intersect_mode::sos);

Under sos, every contact is perturbed into a crossing, so shared or coplanar geometry is never stated. Under the default primitives, curves follow the arrangement's seam semantics: a coincident (coplanar) overlap contributes its contact border — the polyline where the coincidence ends — while the overlap's interior stays silent.

N-Mesh Intersection Curves

Extract all pairwise intersection curves from a range of meshes:

auto form0 = mesh0.polygons() | tf::tag(f0);
auto form1 = mesh1.polygons() | tf::tag(f1);
auto form2 = mesh2.polygons() | tf::tag(f2);
decltype(form0) forms[] = {form0, form1, form2};

auto curves = tf::make_intersection_curves(tf::make_range(forms, forms + 3));

Default config: primitives, exact. With 3+ meshes, contours from different mesh pairs can cross on a shared face; the arity makes such a pair possible, so those crossings are resolved.

Self-Intersection Curves

Find where a mesh intersects itself:

auto self_curves = tf::make_self_intersection_curves(mesh.polygons());

Default config: primitives, exact. A one-form build implies within, so the mesh's self records are emitted and crossings within one contour class are resolved — different face pairs of the same mesh can produce them.

Self seams are the non-manifold edges of the split surface — edges where three or more region walks meet — plus the contact borders of coincident overlaps, matching the arrangement paths.

With Precomputed Structures

All intersection functions accept plain polygons or forms with precomputed structures. When structures are pre-tagged, the function skips building them:

tf::aabb_tree<int, float, 3> tree1, tree2;
tree1.build(mesh1.polygons(), tf::config_tree(4, 4));
tree2.build(mesh2.polygons(), tf::config_tree(4, 4));

tf::face_membership<int> fm1, fm2;
fm1.build(mesh1.polygons());
fm2.build(mesh2.polygons());

tf::manifold_edge_link<int, 3> mel1, mel2;
mel1.build(mesh1.faces(), fm1);
mel2.build(mesh2.faces(), fm2);

auto form1 = mesh1.polygons() | tf::tag(tree1) | tf::tag(fm1) | tf::tag(mel1);
auto form2 = mesh2.polygons() | tf::tag(tree2) | tf::tag(fm2) | tf::tag(mel2);

auto curves = tf::make_intersection_curves(form1, form2);

With Transformations

Tagged transformations enable intersection in transformed space without copying geometry:

auto T = tf::make_transformation_from_translation(
    tf::make_vector(5.0f, 0.0f, 0.0f));

auto curves = tf::make_intersection_curves(
    mesh.polygons(),
    mesh.polygons() | tf::tag(T));

Using Curves

auto paths = curves.paths();   // Ranges of vertex indices
auto points = curves.points(); // Intersection point coordinates

for (auto path : paths) {
    bool is_closed = path.front() == path.back();
    for (auto vertex_id : path) {
        auto pt = points[vertex_id];
    }
}

Low-Level Intersection Access

For advanced use cases, direct access to intersection data structures.

Polygon Intersections

tf::polygon_intersections is the exact intersection identity of one, two, or N polygon meshes — the structure every arrangement is built on. It is reached by direct include; the module umbrella does not export it:

#include <trueform/intersect/polygon_intersections.hpp>

Forms must carry an AABB tree, a face membership and a manifold edge link — see With Precomputed Structures.

Arity and tf::intersect_config determine what is computed. There is one class and no "between" / "within" aliases: a one-form build is the self arrangement (within is implied), a two-form or N-form build always emits cross records and adds per-form self records when the config asks for within.

Every build takes a tf::exact::input_lattice — where each original vertex of each operand stands on the integer lattice, built once over the union of the operands:

tf::exact::input_lattice<int, float, tf::exact::int32> lattice;
lattice.build(
    tf::exact::make_vertex_converter<tf::exact::int32, float>(form1, form2),
    [&](int tag, auto &&f) {
      if (tag == 0)
        f(form1);
      else
        f(form2);
    },
    2, /*tolerance=*/0.0);

tf::polygon_intersections<int, float> ibp;   // lattice int per the real type

ibp.build(form1, form2, lattice, tf::intersect_mode::primitives);  // cross records
ibp.build(form1, form2, lattice,                                   // + self records
          tf::intersect_mode::primitives | tf::intersect_mode::within);

The range build and the one-form build take the same shape — a lattice over their own operands, then the forms:

ibp.build(tf::make_range(forms, forms + 3), lattice_n,   // every pair
          tf::intersect_mode::primitives);
ibp.build(form1, lattice_1, tf::intersect_mode::primitives);  // self only

Records are grouped by (tag, object):

for (auto group : ibp.intersections()) {        // all forms
    for (auto intersection : group) {
        intersection.tag;            // Which mesh
        intersection.tag_other;      // The other mesh (== tag for a self record)
        intersection.object;         // Face ID
        intersection.object_other;   // Other face ID
        intersection.id;             // Canonical point name
        intersection.target.label;   // tf::topo_type: vertex/edge/face
        intersection.target.id;      // Local index on face
        intersection.target_other.label;
        intersection.target_other.id;
    }
}

for (auto group : ibp.intersections(0)) { /* one form's groups */ }
for (const auto &rec : ibp.flat_intersections()) { /* ungrouped */ }

Point Identity

A record's id is a canonical point name in [0, ibp.n_points()), not a slot in a coordinate table: this class computes no coordinates and stores none. The name's kind is its position in that space:

for (const auto &rec : ibp.flat_intersections()) {
    if (rec.id < ibp.n_vertex_points()) {
        auto anchor = ibp.vertex_anchor(rec.id);   // {tag, vid}
    } else {
        auto edge = ibp.home_edge(rec.id);         // canonical flat vertex ids
        auto t = ibp.exact_parameter(rec.id);      // exact fraction along it
    }
}

auto offsets = ibp.vertex_offsets();               // per-form bases of the flat space
auto flat = ibp.canonical_vertex(tag, vid);        // total: unidentified maps to itself

Coincident originals collapse first, so one physical edge has one canonical name however many vertex ids spell it — duplicated vertices, edges shared across forms, and reversed instances are one carrier. Per carrier, every incident canonical point is listed in ascending exact parameter:

auto carriers = ibp.edge_carriers();   // ascending — binary-searchable
auto splits = ibp.edge_splits();       // blocks aligned with carriers

A consumer that closes coincidences on positions never reads those lists and says so before the build, which then does not construct them:

ibp.with_edge_splits(false);
ibp.build(form1, form2, tf::intersect_mode::primitives);

ibp.converter() is the lattice converter the build used: converter().deconvert(pt) takes a lattice point back to floating point.

Segment Intersections

For 2D or 3D segment collections. Points are stored as int32 internally:

tf::intersections_within_segments<int, float, 2> iws;
iws.build(segments | tf::tag(tree) | tf::tag(edge_membership));

// Access int32 intersection points
auto points = iws.intersection_points();

// Deconvert
auto &conv = iws.converter();
for (auto pt : points) {
    auto fpt = conv.deconvert(pt);
}

// Structured intersections grouped by edge
for (auto group : iws.intersections()) {
    for (auto intersection : group) {
        intersection.object;         // Edge ID
        intersection.object_other;   // Other edge ID
        intersection.id;             // Point ID
        intersection.target.label;   // vertex or edge
        intersection.target.id;      // Local index (0 or 1 for vertex)
    }
}