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

Mode

tf::intersect_mode is a bitmask that controls intersection computation and contour crossing resolution. Flags are combined with |.

Base modes (choose one):

Contour crossing resolution (optional, combine with base mode):

Self-intersections (optional, combine with base mode):

Each function sets appropriate defaults — see the individual function documentation in Intersect and Arrangement modules.

// Explicit mode with crossing resolution
auto curves = tf::make_intersection_curves(
    tf::make_range(forms, forms + 3),
    tf::intersect_mode::primitives | tf::intersect_mode::resolve_crossing_contours);

Tolerance

A non-zero tolerance is a statement about the INPUT, not about a predicate, and it is spent entirely on making the input something the exact pipeline can process. Faces whose quantized directions agree are POOLED, and a pool commits one exact plane through original vertices of its own members; every vertex then moves at most the tolerance from where you put it — onto its pool's committed plane where it has one, and otherwise onto a lattice point of the quantized planes its own faces stand on: the meet of three at a corner, a line of two on a crease, its own tangent plane where the surface is smooth. What the pipeline arranges is that moved mesh, EXACTLY: every predicate below the placement runs at zero. Two features closer than the tolerance therefore meet only when the placement puts them on the same lattice point — a weld is identity, not proximity, and one form's rim is never dragged onto another's wall for being near it. Nothing is promised of the output mesh; the tolerance is a licence to move the input, not a bound on the result.

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.

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 mode: the bare primitives — the crossing-resolution flag is arity-derived, and at two operands it is off. 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 by resolve_self_crossing_contours or 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 mode: primitives | resolve_crossing_contours. With 3+ meshes, contours from different mesh pairs can cross on a shared face — crossings are resolved by default.

Self-Intersection Curves

Find where a mesh intersects itself:

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

Default mode: primitives | resolve_contours. Both cross-contour and self-crossing resolution are enabled, since different face pairs of the same mesh can produce crossing contours.

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 (the within bit is implied), a two-form or N-form build always emits cross records and adds per-form self records when the mode carries self_intersections.

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

ibp.build(form1, form2, tf::intersect_mode::primitives);          // cross records
ibp.build(form1, form2,                                           // + self records
          tf::intersect_mode::primitives | tf::intersect_mode::within);
ibp.build(tf::make_range(forms, forms + 3),                       // every pair
          tf::intersect_mode::primitives);
ibp.build(form1, tf::intersect_mode::primitives);                 // self only

// With int64 precision
tf::polygon_intersections<int, float, tf::exact::int64> ibp64;
ibp64.build(form1, form2, tf::intersect_mode::primitives);

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)
    }
}