Arrangement

The Arrangement module splits meshes and segments along intersection curves and classifies regions. It builds on the Intersect module for computing intersections, then embeds these curves into mesh topology by splitting faces and creating new connectivity. All operations are geometrically and topologically exact.

Include the module with:

#include <trueform/arrangement.hpp>

Overview

The Arrangement module provides operations at several levels:

Mesh arrangements: Decompose two or more meshes into classified regions — the complete intersection problem
Segment arrangements: Split 2D or 3D segments at all intersection points

All arrangement operations return a face_labels buffer that maps each output face back to the index of the original face it came from in the source mesh. This enables attribute transfer and provenance tracking. Multi-mesh arrangements additionally return tag_labels — which input mesh each face belongs to.

The mesh arrangements (tf::make_mesh_arrangements, tf::make_polygon_arrangements) support an optional tf::return_curves parameter that additionally returns the explicit curve geometry as a tf::curves_buffer. Segment arrangements do not take it.

The arrangement operations (tf::make_mesh_arrangements, tf::make_polygon_arrangements) additionally support an optional tf::return_index_map parameter. In place of the loose tag_labels / face_labels buffers it returns a single index-map struct that relates both the points and faces of the output back to the input, plus a forward map from each input point to its output index. See Index Maps.

For repeated computation on the same or moving geometry, build structures once and tag them, or use tagged transformations. See With Precomputed Structures and With Transformations.

Supported Input

Embedding and arrangement operations inherit the same robustness as the Intersect module:

Open and closed meshes — boundaries are handled correctly
Non-manifold edges — edges shared by 3 or more faces
Coplanar faces — overlapping faces are classified (aligned/opposing boundary)
Self-intersecting geometry — detected and resolved
Crossing intersection curves — where curves from different mesh pairs meet on a face, crossings can be resolved by splitting curves at the crossing point. Configured via tf::intersect_config; each function sets appropriate defaults.

Region classification additionally requires that intersection curves split the meshes into separate inside/outside regions. Input meshes should be PWN (piecewise winding number) — locally consistent orientation.

To detect where a single mesh's own polygons intersect each other, use tf::make_polygon_arrangements.

Coordinate Precision

All arrangement operations use exact integer arithmetic internally. The lattice resolution is selected by the Int template parameter and resolves automatically from the input coordinate type:

Input scalar	Resolved `Int`
`float`	`tf::exact::int32`
`double`	`tf::exact::int64`
any other	`tf::exact::int32` (fallback)

// Auto-resolved
auto [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    mesh1.polygons(), mesh2.polygons());

// Explicit override
auto [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements<tf::exact::int64>(
    mesh1.polygons(), mesh2.polygons());

This applies to all arrangement operations: make_mesh_arrangements, make_polygon_arrangements, and make_segment_arrangements.

See Intersect: Exact Arithmetic for the full precision chain.

Output Coordinate Type

The output mesh's scalar type is controlled by an optional second template parameter, OutputCoordinateType. It defaults to the input mesh's real type. Any floating-point type may be supplied.

The two template parameters can be set independently:

// Both auto: Int from input scalar, output matches input
auto [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    float_mesh1.polygons(), float_mesh2.polygons());

// Explicit Int, output auto (matches input)
auto [mesh, tag_labels, face_labels] =
    tf::make_mesh_arrangements<tf::exact::int64>(
        float_mesh1.polygons(), float_mesh2.polygons());

// Auto Int, explicit output type
auto [mesh, tag_labels, face_labels] =
    tf::make_mesh_arrangements<tf::none_t, double>(
        float_mesh1.polygons(), float_mesh2.polygons());

// Both explicit
auto [mesh, tag_labels, face_labels] =
    tf::make_mesh_arrangements<tf::exact::int64, double>(
        float_mesh1.polygons(), float_mesh2.polygons());

The template slots follow one law, on one axis: an entry that constructs an arrangement takes the lattice Int first and OutputCoordinateType second; an entry that reads an already-built graph takes only OutputCoordinateType, because the graph's type has already fixed its Int and the graph holds the converter. Every arrangement function that takes forms constructs, so both slots apply — pass tf::none_t in either to keep its default. The reads on a built arrangement graph take the output slot alone.

Internally the pipeline carries intersection points at full precision regardless of OutputCoordinateType; the parameter only governs the coordinate type at output emission.

Mesh Arrangements

Mesh arrangements decompose intersecting meshes into classified regions. This is the complete solution to the intersection problem — every region is returned with labels indicating origin and spatial classification.

Two-Mesh Arrangements

mesh_arrangements.cpp

auto [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    mesh1.polygons(), mesh2.polygons());

Returns a single merged mesh with per-face labels:

tag_labels: Which input mesh each face came from (0 or 1)
face_labels: Index of the original face in its source mesh that each output face came from

With curves:

mesh_arrangements_curves.cpp

auto [mesh, tag_labels, face_labels, curves] = tf::make_mesh_arrangements(
    mesh1.polygons(), mesh2.polygons(), tf::return_curves);

Default mode: the bare primitives — not tf::arrangement_config's own primitives | resolve_crossing_contours default, because the crossing-resolution flag is arity-derived and at two operands it is off. Every contour is then 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 [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    mesh1.polygons(), mesh2.polygons(), tf::intersect_mode::primitives);

With tolerance: to recover the intended topology on inputs that carry float-precision drift, pass an intersect_config with a non-zero tolerance. See Intersection Configuration.

mesh_arrangements_tolerance.cpp

auto [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    mesh1.polygons(), mesh2.polygons(),
    tf::intersect_config{tf::intersect_mode::primitives, 1e-6});

Arrangement Configuration

Every arrangement entry point takes a tf::arrangement_config — the intersection run plus the triangulation built over the cut surfaces:

struct arrangement_config {
  intersect_config intersect;        // mode + tolerance
  triangulation_type triangulation;  // cdt (default) or refined_cdt
};

It is implicitly constructible from an intersect_config, an intersect_mode, or a triangulation_type alone, so a call site spells only the part it cares about:

arrangement_config.cpp

// intersect settings only — default cdt triangulation
auto r0 = tf::make_mesh_arrangements(
    a.polygons(), b.polygons(),
    tf::intersect_config{tf::intersect_mode::primitives, 1e-6});

// quality-refined triangulation, default intersect settings
auto r1 = tf::make_mesh_arrangements(
    a.polygons(), b.polygons(), tf::triangulation_type::refined_cdt);

// both
auto r2 = tf::make_mesh_arrangements(
    a.polygons(), b.polygons(),
    {tf::intersect_config{tf::intersect_mode::primitives, 1e-6},
     tf::triangulation_type::refined_cdt});

triangulation_type::refined_cdt quality-refines the cut surfaces (Ruppert circumcenter insertion with negotiated boundary splits), so shared boundaries stay watertight by construction. Refinement adds Steiner points, so the output carries more vertices and triangles than the plain cdt.

N-Mesh Arrangements

Decompose a range of meshes into classified regions:

n_mesh_arrangements.cpp

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 [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    tf::make_range(forms, forms + 3));

// With curves
auto [mesh, tag_labels, face_labels, curves] = tf::make_mesh_arrangements(
    tf::make_range(forms, forms + 3), tf::return_curves);

The tag_labels values range from 0 to N-1, indicating which input mesh each face originated from.

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.

auto [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    tf::make_range(forms, forms + 3),
    tf::intersect_mode::primitives | tf::intersect_mode::resolve_contours);

Self-Intersection Arrangements

Decompose a single mesh at its self-intersection curves:

self_arrangements.cpp

auto [mesh, face_labels, curves] = tf::make_polygon_arrangements(
    merged.polygons(), tf::return_curves);

Returns the split mesh with per-face labels identifying connected regions.

Default mode: primitives | resolve_contours | within — the self path always runs within, and the default spells it so the boundary is visible.

auto [mesh, face_labels] = tf::make_polygon_arrangements(
    merged.polygons(),
    tf::intersect_mode::primitives | tf::intersect_mode::resolve_crossing_contours);

Index Maps

Passing tf::return_index_map to an arrangement returns a single index-map struct in place of the loose tag_labels / face_labels buffers. It relates both the points and faces of the output back to the input, and adds a forward map from each input point to its output index — everything the operation already computes internally, surfaced instead of discarded.

Two-mesh and N-mesh arrangements return a tf::mesh_arrangement_index_map:

index_map.cpp

auto [mesh, imap] = tf::make_mesh_arrangements(
    mesh1.polygons(), mesh2.polygons(), tf::return_index_map);

// N-mesh: identical struct, tags range 0..N-1
auto [nmesh, nimap] = tf::make_mesh_arrangements(
    tf::make_range(forms, forms + 3), tf::return_index_map);

Member	Indexed by	Maps to
`point_tag_labels`	output point	input mesh tag (`0..N-1`); created → `n_tags`
`point_labels`	output point	input point id within its mesh; created → `n_output_points`
`face_tag_labels`	output face	input mesh tag
`face_labels`	output face	input face id within its mesh
`point_f`	`[tag][input point id]`	output point index (forward); unmapped → `n_output_points`
`uncut_faces`	`[tag]`	`{begin, end}` output faces of that mesh that stayed uncut — outside them, every face is a piece of a cut face
`n_original_points`	—	outputs `≥` this are created points
`n_tags`	—	number of input meshes; the tag axis `end` sentinel
`n_output_points`	—	total output points; the point-id `end` sentinel

Single-mesh arrangements return a tf::polygon_arrangement_index_map — the same, minus the tag axis (one mesh): members point_labels, face_labels, point_f (indexed point_f[input point id]), and the same three boundary fields.

index_map_self.cpp

auto [mesh, imap] = tf::make_polygon_arrangements(
    merged.polygons(), tf::return_index_map);

Created points and the end sentinel. Output points split into kept originals [0, n_original_points) and created intersection points [n_original_points, n_output_points). A created point has no input origin, so each inverse axis carries an end sentinel — the tag ends at n_tags, the point id at n_output_points — the same idiom tf::index_map uses for unmapped entries. Test for one by position or by tag; the point-id sentinel is not reliable, because point_labels holds an id in its own form's space, which may reach that value:

bool is_created = o >= imap.n_original_points;
// equivalently (N-mesh):  imap.point_tag_labels[o] == imap.n_tags

The forward point_f emits n_output_points for any input point with no output. Faces never carry a sentinel — a cut face is a piece of an input face, so it always keeps a real origin.

Carrying attributes across an arrangement. Because the inverse labels are output-indexed and the forward map is input-indexed, per-vertex attributes transfer in a single pass:

index_map_attributes.cpp

auto [mesh, imap] = tf::make_mesh_arrangements(
    mesh1.polygons(), mesh2.polygons(), tf::return_index_map);

for (std::size_t o = 0; o < mesh.polygons().points().size(); ++o) {
    if (int(o) >= imap.n_original_points)
        continue; // created point — interpolate from neighbours instead
    int tag = imap.point_tag_labels[o];
    int in  = imap.point_labels[o];
    out_attr[o] = input_attr[tag][in];
}

Float input, integer output. As with tf::return_curves, when the input is floating-point and OutputCoordinateType is integral, the converter is appended as a trailing tuple element:

index_map_int.cpp

auto [mesh, imap, converter] =
    tf::make_mesh_arrangements<tf::none_t, std::int32_t>(
        mesh1.polygons(), mesh2.polygons(), tf::return_index_map);

auto p = converter.deconvert(mesh.polygons().points()[0]); // integer point back to float

Relationship to Boolean Operations

Mesh arrangements provide the complete decomposition from which any boolean operation can be reconstructed:

Union (A ∪ B): Outside regions from both meshes + aligned boundary
Intersection (A ∩ B): Inside regions from both meshes + aligned boundary
Difference (A \ B): Outside regions from A + inside regions from B with opposing boundary

Use arrangements when you need complete control over region selection, multiple boolean results from the same intersection, or per-region analysis.

Boolean Operations

tf::make_boolean is the two-operand case of the CSG arrangement and lives in the CSG module, exported by <trueform/csg.hpp>.

The Arrangement Graph

Every entry point above materialises a mesh. tf::make_arrangement_graph stops one level short and returns a tf::arrangement_graph — the arrangement of a set of forms, everything below classification: the intersection identity, the per-plane triangulation, the coplanar stacks, and the unified created-points table. Build it once, then read off it as often as you like — the reads cost no new geometric work.

arrangement_graph.cpp

auto graph = tf::make_arrangement_graph(mesh1.polygons(), mesh2.polygons());

auto surface = tf::make_arrangement_mesh(graph);      // the full arrangement mesh
auto curves  = tf::make_intersection_curves(graph);   // the seam network

It takes the same operand shapes as tf::make_csg_graph:

Operands	Meaning
one form	that form's self arrangement (`tf::intersect_mode::within` is implied)
two forms	a pair, which may be of different form types
a range of forms	N operands, tagged `0..N-1`

arrangement_graph_operands.cpp

auto self  = tf::make_arrangement_graph(soup.polygons());
auto pair  = tf::make_arrangement_graph(a.polygons(), b.polygons());
auto n_ary = tf::make_arrangement_graph(tf::make_range(forms));

Every overload takes an optional tf::arrangement_config and the same Int template parameter as the arrangement functions:

auto graph = tf::make_arrangement_graph<tf::exact::int64>(
    tf::make_range(forms), tf::triangulation_type::refined_cdt);

Missing tf::face_membership, tf::manifold_edge_link, and tf::tree structures are built in parallel and owned by the graph; a frame is never built, since it states a transformation only the caller knows. A single form or a pair is copied in, but a range of forms is stored as the view it is — the graph must not outlive the container behind it.

tf::make_arrangement_mesh(graph) materialises the full arrangement mesh, and takes tf::return_source_ids for the (tag_labels, face_labels) provenance pair or tf::return_index_map for the index map — the same shapes tf::make_mesh_arrangements returns, without re-running the pipeline. A one-form graph has no tag axis: tf::return_source_ids gives the face ids alone, and the map is a tf::polygon_arrangement_index_map.

The graph is classification-free. Boolean expressions, domain decomposition, and the outer shell are the CSG module's tier — build a tf::csg_graph for those.

Intersection Curves

tf::make_intersection_curves(graph) reads the seam network off an arrangement — the polylines where surfaces cross — as a tf::curves_buffer:

arrangement_curves.cpp

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

Edges are connected into maximal polylines. A coincident (coplanar) overlap contributes its contact border — the polyline where the coincidence ends — while the overlap's interior stays silent. Within a single tag (a self arrangement) a seam is a non-manifold edge.

The output coordinate type is the leading template parameter, defaulting to the input forms' real type. An integral type emits the curves on the exact lattice, and the graph carries the converter that produced it:

auto curves = tf::make_intersection_curves<double>(graph);

auto lattice = tf::make_intersection_curves<tf::exact::int32>(graph);
auto p = graph.converter().deconvert(lattice.points()[0]); // lattice point back to float

The standalone tf::make_intersection_curves(a, b) builds its own arrangement per call and appends that converter to the return for integer output; the graph overload returns the curves buffer alone, because you already hold the graph. The CSG module's tf::make_intersection_curves(csg_graph) is the same read on a classified graph.

Segment Arrangements

Split 2D or 3D segments at all intersection points. Returns the subdivided segments with labels mapping each sub-edge to its original edge:

segment_arrangements.cpp

auto [result, edge_labels] = tf::make_segment_arrangements(segments);

The input segments can be plain or pre-tagged with tree and edge_membership structures. The output is a tf::segments_buffer with all intersections resolved and edges split.

segment_arrangements_3d.cpp

// Also works for 3D segments
tf::segments_buffer<int, float, 3> segments_3d;
// ... fill with data ...

auto [result, edge_labels] = tf::make_segment_arrangements(segments_3d.segments());

// edge_labels[i] = index of the original edge that output edge i came from

Planar Embedding

To compute the faces (regions) induced by the split segments, use tf::planar_embedding from the Topology module:

segment_planar_embedding.cpp

auto [result, edge_labels] = tf::make_segment_arrangements(segments);

tf::planar_embedding<int, tf::exact::int32> pe;
pe.build(result.segments());

for (auto [face, hole_ids] : tf::zip(pe.faces(), pe.holes_for_faces())) {
    auto polygon = tf::make_polygon(face, result.points());
    for (auto hole : tf::make_indirect_range(hole_ids, pe.holes())) {
        auto hole_polygon = tf::make_polygon(hole, result.points());
    }
}

With Precomputed Structures

All arrangement functions accept plain polygons or forms with precomputed spatial and topological structures. When structures are pre-tagged, the function skips building them — useful for repeated operations on the same mesh:

arrangement_precomputed.cpp

tf::aabb_tree<int, float, 3> tree;
tree.build(mesh.polygons(), tf::config_tree(4, 4));

tf::face_membership<int> fm;
fm.build(mesh.polygons());

tf::manifold_edge_link<int, 3> mel;
mel.build(mesh.polygons().faces(), fm);

auto tagged = mesh.polygons() | tf::tag(tree) | tf::tag(fm) | tf::tag(mel);

// Use tagged form in any arrangement operation
auto [arranged, tag_labels, face_labels] =
    tf::make_mesh_arrangements(tagged, other_tagged);

With Transformations

Tagged transformations enable operations in transformed space without copying geometry. Build structures once, then apply different transformations per operation:

arrangement_transformed.cpp

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

// Arrangement between original and translated mesh
auto [arranged, tags, faces] = tf::make_mesh_arrangements(
    mesh.polygons(),
    mesh.polygons() | tf::tag(T));

// Arrangements with per-mesh transforms
auto T0 = tf::make_transformation_from_translation(
    tf::make_vector(0.5f, 0.0f, 0.0f));
auto T1 = tf::make_transformation_from_translation(
    tf::make_vector(-0.5f, 0.0f, 0.0f));

auto [mesh, tag_labels, face_labels] = tf::make_mesh_arrangements(
    mesh1.polygons() | tf::tag(T0),
    mesh2.polygons() | tf::tag(T1));

Intersect

Exact mesh intersections and self-intersections.

Iso

Scalar field crossings, isocontours, isocurve embedding, and isobands.