Topology

The Topology module provides tools for understanding the structure and connectivity of a mesh. It contains both data structures for efficient adjacency queries and high-level algorithms for tasks like feature detection, path finding, and structural modification.

Include the module with:

#include <trueform/topology.hpp>

Connectivity Structures

To enable efficient traversal of the mesh graph, trueform provides several data structures that pre-compute adjacency information.

Face Membership

The tf::face_membership structure is a fundamental building block for other topological queries. For each vertex ID, it stores a list of all the face IDs that include that vertex.

// Assumes 'polygons' is a valid tf::polygons object
tf::face_membership<int> fm;

// Build can be called on the polygons object directly...
fm.build(polygons);

// ...or on its underlying face and point data for more control
int n_unique_ids = polygons.points().size();
int total_values = polygons.size() * 3; // Assuming triangles
fm.build(polygons.faces(), n_unique_ids, total_values);
// or simply
// fm.build(polygons);

// Query: get all faces connected to a specific vertex
for(auto face_id : fm[vertex_id]) {
    // ... do something with the face ID ...
}

// Attach to polygons via policy system
auto polygons_with_fm = polygons | tf::tag(fm);
const auto& fm_ref = polygons_with_fm.face_membership();

Convenience function:

auto fm = tf::make_face_membership(polygons);

Scoped Face Membership

tf::scoped_face_membership answers the same question and one more: not just which faces contain a vertex, but where in each face it appears. Each entry is a tf::scoped_id{id, sub_id} — the face index and the vertex's position in that face's winding.

tf::scoped_face_membership<int> sfm;
sfm.build(polygons);   // fixed-size polygons only

// ...or from blocks, with explicit sizes
sfm.build(polygons.faces(), polygons.points().size(), 3 * polygons.size());

for (auto entry : sfm[vertex_id]) {
    int face_id = entry.id;
    int corner  = entry.sub_id;   // polygons.faces()[face_id][corner] == vertex_id
}

The position type is a second template parameter defaulting to Index, so a mesh with small faces can narrow it: tf::scoped_face_membership<int, short>. tf::make_scoped_id(id, sub_id) builds one by hand.

Vertex Link

The tf::vertex_link (or "1-ring") stores, for each vertex, a list of all its adjacent (neighboring) vertices. It requires a pre-computed face_membership structure.

tf::vertex_link<int> v_link;
v_link.build(polygons.faces(), face_membership);

// Query: iterate over the 1-ring neighbors of a vertex
for(auto next_vertex_id: v_link[vertex_id]) {
    // ... do something with the neighbor vertex ID ...
}

// Attach to polygons via policy system
auto polygons_with_vl = polygons | tf::tag(v_link);
const auto& vl_ref = polygons_with_vl.vertex_link();

Convenience function:

// Builds face_membership automatically
auto v_link = tf::make_vertex_link(polygons);

// Reuses pre-built face_membership
auto v_link = tf::make_vertex_link(polygons | tf::tag(fm));

The vertex_link can also be built directly from edges or segments:

// Build from edges with orientation control
v_link.build(edges, n_unique_ids, tf::edge_orientation::bidirectional);

// Build from segments
v_link.build(segments, tf::edge_orientation::forward);

Convenience function:

// From segments with orientation control (default: bidirectional)
auto v_link = tf::make_vertex_link(segments);
auto v_link = tf::make_vertex_link(segments, tf::edge_orientation::forward);

K-Ring Neighborhoods

The tf::make_k_rings function extends the 1-ring concept to compute all vertices reachable within k hops along mesh edges.

// Build vertex link first (1-ring)
tf::vertex_link<int> v_link;
v_link.build(polygons.faces(), face_membership);

// Compute 2-ring neighborhoods for all vertices
auto k_ring_2 = tf::make_k_rings(v_link, 2);

// Query: iterate over the 2-ring neighbors of a vertex
for (auto neighbor_id : k_ring_2[vertex_id]) {
    // ... do something with the neighbor vertex ID ...
}

// Larger neighborhoods for curvature estimation, smoothing, etc.
auto k_ring_5 = tf::make_k_rings(v_link, 5);

// Include the seed vertex itself (inclusive mode)
auto k_ring_inclusive = tf::make_k_rings(v_link, 2, true);

The result is an offset_block_buffer where each block contains all vertices within k hops of the corresponding vertex. By default, the seed vertex is excluded; pass inclusive=true to include it.

Radius-Based Neighborhoods

The tf::make_neighborhoods function computes neighborhoods based on Euclidean distance rather than hop count.

// Using points with vertex_link attached
auto pts_with_vlink = polygons.points() | tf::tag(v_link);
auto neighs = tf::make_neighborhoods(pts_with_vlink, 0.5f);

// Or with a custom squared distance function
auto neighs = tf::make_neighborhoods(
    v_link,
    [&](auto seed, auto neighbor) {
        return tf::distance2(points[seed], points[neighbor]);
    },
    0.5f  // radius
);

// Query: iterate over neighbors within radius
for (auto neighbor_id : neighs[vertex_id]) {
    // ... do something with the neighbor vertex ID ...
}

// Include the seed vertex itself (inclusive mode)
auto neighs_inclusive = tf::make_neighborhoods(pts_with_vlink, 0.5f, true);

The function traverses the mesh graph (BFS) and includes vertices where the squared distance from seed is within radius². By default, the seed vertex is excluded; pass inclusive=true to include it.

Face Link

The tf::face_link stores, for each face, a list of all its adjacent faces (those that share an edge). It also requires a pre-computed face_membership structure.

tf::face_link<int> f_link;
f_link.build(polygons.faces(), face_membership);

// Query: iterate over the neighbors of a specific face
for(auto next_face_id: f_link[face_id]) {
    // ... do something with the neighbor face ID ...
}

// Attach to polygons via policy system
auto polygons_with_fl = polygons | tf::tag(f_link);
const auto& fl_ref = polygons_with_fl.face_link();

Convenience function:

// Builds face_membership automatically
auto f_link = tf::make_face_link(polygons);

// Reuses pre-built face_membership
auto f_link = tf::make_face_link(polygons | tf::tag(fm));

Manifold Edge Link

The tf::manifold_edge_link is a more advanced structure that provides detailed information about each edge of a given face. It can determine if an edge is on a boundary or if it is a "manifold" edge shared with exactly one other face.

tf::manifold_edge_link<int, 3> me_link;
me_link.build(polygons.faces(), face_membership);

// Query: iterate over the edges of a face and inspect their properties
for (const tf::manifold_edge_peer<int>& peer : me_link[face_id]) {
    std::cout << "Edge is manifold: " << (peer.is_manifold() ? "yes" : "no")
              << std::endl;
    std::cout << "Edge is boundary: " << (peer.is_boundary() ? "yes" : "no")
              << std::endl;

    // A "simple" edge is a non-boundary, manifold edge
    if (peer.is_simple()) {
        std::cout << "Edge is simple. Neighboring face id: " << peer.face_peer
                  << std::endl;
    }
}

// Attach to polygons via policy system
auto polygons_with_mel = polygons | tf::tag(me_link);
const auto& mel_ref = polygons_with_mel.manifold_edge_link();

For variable-size polygons (mixed n-gons), use tf::dynamic_size as the second template parameter:

tf::manifold_edge_link<int, tf::dynamic_size> me_link;
me_link.build(dynamic_polygons.faces(), face_membership);

Convenience function:

// Builds face_membership automatically, deduces Index and NGon from polygons
auto me_link = tf::make_manifold_edge_link(polygons);

// Reuses pre-built face_membership
auto me_link = tf::make_manifold_edge_link(polygons | tf::tag(fm));

// For variable-size polygons, NGon is deduced as tf::dynamic_size
auto me_link = tf::make_manifold_edge_link(dynamic_polygons);

The manifold_edge_peer provides several query methods:

• is_simple(): Returns true for manifold, non-boundary edges
• is_boundary(): Returns true for boundary edges
• is_manifold(): Returns true for manifold edges (not non-manifold)
• is_representative(): Used for avoiding duplicate processing of shared edges

Face-Edge Neighbors

tf::face_edge_neighbors is the one-off form of the question manifold_edge_link precomputes: given a face and one of its edges, which other faces carry that edge? It reads face_membership directly, so nothing per-face is built.

tf::small_vector<int, 6> neighbors;
tf::face_edge_neighbors(fm, polygons.faces(), face_id, v0, v1,
                        std::back_inserter(neighbors));

// Bounded output — stops when the range fills
int found[4];
auto last = tf::face_edge_neighbors(fm, polygons.faces(), face_id, v0, v1,
                                    found, found + 4);

// Callback form — return true to stop early
tf::face_edge_neighbors_apply(fm, polygons.faces(), face_id, v0, v1,
                              [](int neighbor_id) { return false; });

The _tagged variants also report where the edge sits in the neighbour, yielding std::array<Index, 2>{neighbor_face_id, edge_id_in_neighbor}:

tf::face_edge_neighbors_tagged(fm, polygons.faces(), face_id, v0, v1, out);
tf::face_edge_neighbors_tagged_apply(
    fm, polygons.faces(), face_id, v0, v1,
    [](std::array<int, 2> hit) { return false; });

Triangles take a specialised path in the untagged form. The tagged form has none, because the edge index inside the neighbour must always be computed.

Half-Edges

tf::half_edges is the mutable connectivity the Remesh module operates on. Half-edges live in one flat buffer with opposites at adjacent indices (index ^ 1), so opposite() is an XOR rather than a lookup.

tf::half_edges<int> he(polygons);          // or he.build(polygons);
auto he2 = tf::make_half_edges(polygons);  // Index deduced

// Four handle types wrap an id explicitly — an integer never becomes one
// by accident: half_edge_handle, edge_handle, vertex_handle, face_handle.
// Each has id(), is_valid() and a static invalid().
for (auto heh : he.half_edge_handles()) {
    if (!heh.is_valid()) continue;          // removed slots come back invalid
    auto v0 = he.start_vertex_handle(heh);
    auto v1 = he.end_vertex_handle(heh);
    auto f  = he.face_handle(heh);          // invalid on a boundary half-edge
}

for (auto eh : he.edge_handles()) {
    if (eh.is_valid() && he.is_simple(eh)) { /* manifold, non-boundary */ }
}

Navigation is next(), previous(), opposite(), rotated() and anti_rotated(). Queries are is_boundary(), is_simple() and is_manifold() on either a half-edge or an edge handle, plus is_boundary_vertex() and is_non_manifold_vertex().

Every navigation and query propagates invalid handles. Pass tf::unsafe as the first argument to skip the validity check in an inner loop where the handle is known good:

auto nxt = he.next(tf::unsafe, heh);

Mutation is flip() and collapse(), each guarded by its own predicate. is_collapse_ok() takes a scratch ring container (tf::buffer, tf::small_vector or std::vector) that is cleared and reused across calls:

if (he.is_flip_ok(eh))
    he.flip(eh);

tf::small_vector<int, 16> ring;
if (he.is_collapse_ok(eh, ring))
    he.collapse(eh);   // end vertex merges into start vertex

Both leave removed elements in place. compact() erases them and returns the three index maps naming what survived:

auto [face_map, vertex_map, edge_map] = he.compact();

The face field of a tf::half_edge uses sentinels: -1 boundary, -2 non-manifold, -3 orientation fault, -4 removed.

Stitched Connectivity

After two meshes are merged — a boolean, an arrangement — most faces survive whole, so their connectivity is already known. tf::stitched_face_membership and tf::stitched_manifold_edge_link reuse the sources' structures instead of rebuilding from the result, computing only the incidences that new faces created. Both are driven by the merge's tf::stitch_index_map, which tf::make_stitch_index_map reads off an arrangement's index map.

auto sim = tf::make_stitch_index_map(arrangement_map);

auto fm = tf::stitched_face_membership<int>(
    result.faces(), fm0, fm1, sim);

auto mel = tf::stitched_manifold_edge_link<int>(
    result.faces(), mel0, mel1, fm, sim, direction0, direction1);

The manifold edge link is indexed by position within a face — peer slot i belongs to the edge leaving vertex i — so it is the one structure that must know whether an output face kept its source winding. That is what direction0 / direction1 carry; after a boolean they come from tf::make_directions.

Edge Membership and Orientation

The tf::edge_membership structure provides connectivity information for edges, supporting different orientation modes:

tf::edge_membership<int> em;

// Build with different orientations
em.build(edges, n_unique_ids, tf::edge_orientation::forward);
em.build(edges, n_unique_ids, tf::edge_orientation::reverse);
em.build(edges, n_unique_ids, tf::edge_orientation::bidirectional);

// Can also build from segments
em.build(segments, tf::edge_orientation::bidirectional);

Convenience function:

// From segments with orientation control (default: bidirectional)
auto em = tf::make_edge_membership(segments);
auto em = tf::make_edge_membership(segments, tf::edge_orientation::forward);

Directed Edge Link

tf::directed_edge_link is edge-to-edge adjacency: for each directed edge it stores the edges that start where this edge ends. That is what a chain walk needs, and it is built from an edge_membership in forward orientation.

tf::edge_membership<int> em;
em.build(edges, n_unique_ids, tf::edge_orientation::forward);

tf::directed_edge_link<int> del;
del.build(edges, em);

for (auto next_edge_id : del[edge_id]) {
    // edges[next_edge_id][0] == edges[edge_id][1]
}

Mesh Analysis Functions

Boundary Detection

Extract boundary edges and organize them into boundary loops:

// Extract boundary edges from a mesh
auto boundary_edges = tf::make_boundary_edges(polygons);
// Or with pre-computed face membership
auto boundary_edges = tf::make_boundary_edges(polygons | tf::tag(face_membership));
auto boundary_edges = tf::make_boundary_edges(polygons.faces(), face_membership);

// Extract boundary paths (connected sequences of boundary edges)
auto boundary_paths = tf::make_boundary_paths(polygons);
auto boundary_curves = tf::make_curves(boundary_paths, polygons.points());

// The result is an offset_block_buffer where each block is a boundary loop
for (const auto& boundary_curve : boundary_curves) {
    for (auto vertex_id : boundary_curve.indices()) {
        // Process vertex in boundary loop
    }
    for (auto pt : boundary_curve) {
        // Process points in boundary curve
    }
}

Non-Manifold Edge Detection

Identify edges that are shared by more than two faces:

// Find non-manifold edges
auto non_manifold_edges = tf::make_non_manifold_edges(polygons);

// Or with pre-computed face membership
auto non_manifold_edges = tf::make_non_manifold_edges(polygons | tf::tag(face_membership));
auto non_manifold_edges = tf::make_non_manifold_edges(polygons.faces(), face_membership);

// Process the problematic edges
auto edges_view = tf::make_edges(non_manifold_edges);
for (const auto& edge : edges_view) {
    int vertex_a = edge[0];
    int vertex_b = edge[1];
    // Handle non-manifold edge
}

Non-Manifold Edge Fans

When you need both the non-manifold edges and the list of faces incident to each, use tf::non_manifold_edge_fans. At each non-manifold edge, three or more faces meet; the structure carries two parallel containers — per-edge endpoint pairs and per-edge incident face blocks (representative face first, then its neighbours across the edge).

auto fans = tf::make_non_manifold_edge_fans(polygons);

// Iterate edges and their incident faces in lockstep
for (std::size_t e = 0; e < fans.edges.size(); ++e) {
    auto endpoints = fans.edges[e];          // (v0, v1)
    auto incident  = fans.faces[e];          // block of face ids
    // ... walk the fan around this edge ...
}

// Or destructure the two containers directly
auto [edges, faces] = tf::make_non_manifold_edge_fans(polygons);

// Attach to polygons via policy system
auto polygons_with_fans = polygons | tf::tag(fans);
const auto& fans_ref = polygons_with_fans.non_manifold_edge_fans();

Overloads also accept pre-computed face_membership (and optionally manifold_edge_link) — the polygons overload picks the fastest path based on which policies are already attached:

auto fans = tf::make_non_manifold_edge_fans(polygons.faces(), face_membership);
auto fans = tf::make_non_manifold_edge_fans(polygons.faces(), face_membership, mel);

Non-Simple Edge Detection

To compute both boundary and non-manifold edges in a single pass, use make_non_simple_edges. It works the same way as the individual functions but returns a pair:

auto [boundary_edges, non_manifold_edges] = tf::make_non_simple_edges(polygons);

Face Orientation

Ensure consistent face orientation across the mesh:

// Requires manifold edge link to determine adjacency
tf::manifold_edge_link<int, 3> me_link;
me_link.build(polygons.faces(), face_membership);

// Orient faces consistently using flood-fill algorithm
bool orientable = tf::orient_faces_consistently(polygons | tf::tag(me_link));

// Or directly on polygons (computes topology automatically)
orientable = tf::orient_faces_consistently(polygons);

The function uses flood-fill through manifold edges to propagate orientation. Non-manifold edges act as barriers between regions. The final orientation preserves the majority area within each region - or the majority face count, when the coordinate type is integral and its lattice cannot hold a squared area.

The reversals are decided against the input winding and applied afterwards, so one call is enough. The manifold-edge component is the carrier: every orientable component comes back fully consistent. A component whose parity cycles contradict has no consistent winding to reach, so its faces are left exactly as they were. The call returns false if any component was non-orientable.

A reversal permutes a face's edge slots, so a manifold edge link passed in through the policy describes the winding it was built from, not the one the call leaves behind. Rebuild it before using its slots again.

Reverse Winding

Reverse the winding order of all faces:

// Reverse winding of all faces (flips normals)
tf::reverse_winding(polygons.faces());

This is a low-level operation that reverses the vertex order in every face, effectively flipping all face normals. For ensuring outward-facing normals on closed meshes, use tf::ensure_positive_orientation from the Geometry module instead.

Closed/Open Mesh Detection

Check if a mesh is closed (watertight) or open (has boundary edges):

// Check if mesh has no boundary edges
if (tf::is_closed(polygons)) {
    // Mesh is watertight, encloses a volume
}

// Check if mesh has boundary edges
if (tf::is_open(polygons)) {
    // Mesh has holes or open boundaries
}

// Works with pre-computed face membership
auto tagged = polygons | tf::tag(fm);
bool closed = tf::is_closed(tagged);

For curves, checks if the first and last points are the same:

// Check if curve forms a closed loop
if (tf::is_closed(curve)) {
    // Curve is a closed loop
}

if (tf::is_open(curve)) {
    // Curve has distinct endpoints
}

Manifold Detection

Check if a mesh is manifold (no edges shared by more than two faces):

// Check if mesh is manifold
if (tf::is_manifold(polygons)) {
    // All edges shared by at most 2 faces
}

// Check if mesh has non-manifold edges
if (tf::is_non_manifold(polygons)) {
    // Some edges shared by 3+ faces
}

// Works with pre-computed face membership
auto tagged = polygons | tf::tag(fm);
bool manifold = tf::is_manifold(tagged);

Euler Characteristic

Compute the Euler characteristic (V - E + F) of a polygon mesh:

int chi = tf::euler_characteristic(polygons);

// For a closed genus-0 mesh (sphere-like): chi == 2
// For a torus: chi == 0
// For a disk or any patch with one boundary loop: chi == 1
// For an uncapped tube (two boundary loops): chi == 0

Each undirected edge is counted once, by the face the manifold edge link makes its representative, so a boundary edge - which belongs to one face only - counts exactly like an interior one. The link is built internally unless the mesh is tagged with one. The mesh must have shared vertices (use tf::cleaned first on mesh soup).

Face Comparison

Faces are cyclic sequences of vertex ids, so equality is a rotation question, not an element-wise one.

// Same vertices in either cyclic direction: {0,1,2} == {1,2,0} == {0,2,1}
bool same = tf::are_faces_equal(face_a, face_b);

// Same vertices in the same cyclic direction: {0,1,2} == {1,2,0}, != {0,2,1}
bool same_winding = tf::are_oriented_faces_equal(face_a, face_b);

// Three-way: 0 = different, +1 = equal same winding, -1 = equal reversed
int cmp = tf::compare_faces(face_a, face_b);

Triangles take a compile-time specialised path; other sizes rotate to align.

Duplicate Face Masks

Two faces are duplicates when tf::are_faces_equal says so. Which of the duplicates to keep is the difference between the two masks:

tf::buffer<bool> mask;
mask.allocate(polygons.size());

// One representative of each duplicate set survives (lowest face id)
tf::compute_unique_faces_mask(polygons.faces(), fm, mask);

// Only faces that appear exactly once survive — duplicates cancel
tf::compute_unduplicated_faces_mask(polygons.faces(), fm, mask);

auto kept = tf::reindexed_by_mask(polygons, mask);

compute_unduplicated_faces_mask is the operation that cancels shared interfaces: concatenate the boundaries of two adjacent regions and the faces of their common interface appear twice with opposite winding, so dropping both leaves the boundary of the union. Faces are matched by shared vertex ids only, so coincident-but-separately-indexed copies must be merged first (tf::cleaned with remove_duplicate_primitives = false).

Both functions take a pre-allocated mask of faces.size() and initialise it themselves.

Face-Local Identifiers

Small helpers for locating an element inside a single face. Each returns the face's size when nothing matches, so the "not found" answer needs no sentinel.

auto vi = tf::vertex_id_in_face(v, face);                // corner index
auto ei = tf::edge_id_in_face(v0, v1, face);             // undirected edge
auto di = tf::directed_edge_id_in_face(v0, v1, face);    // v0 → v1 only

// Do two topological ids of one face lie on a common edge?
bool adjacent = tf::is_on_same_edge(t0, t1, face.size());

tf::is_on_same_edge takes two tf::topo_id values — the (type, index) pairs intersection records carry — and answers whether a vertex/vertex, vertex/edge or edge/edge pair shares an edge of a face of that size.

Connected Components

Convenience Functions

For common use cases, convenience functions handle topology building automatically:

// Face components connected through any shared edge
auto cl = tf::make_edge_connected_component_labels(polygons);

// Face components connected only through manifold edges
auto cl = tf::make_manifold_edge_connected_component_labels(polygons);

// Vertex components (labels per vertex, not per face)
auto cl = tf::make_vertex_connected_component_labels(polygons);

// Access results
int n_components = cl.n_components;
auto& labels = cl.labels;  // tf::buffer<Index>

These functions deduce the index type from the input polygons. If topology structures are already attached via the policy system, they are reused:

auto tagged = polygons | tf::tag(face_link);
auto cl = tf::make_edge_connected_component_labels(tagged);  // Reuses face_link

Attaching component labels to a form

tf::connected_component_labels is itself a taggable policy. Algorithms that need per-face component ids (sidedness relations, custom selection filters, debug visualization) can either build the labels internally or accept them pre-tagged on a form — no rebuild if they were already computed:

auto cl = tf::make_manifold_edge_connected_component_labels(polygons);
auto polygons_with_cl = polygons | tf::tag(cl);
const auto& cl_ref = polygons_with_cl.connected_component_labels();
// cl_ref.labels[face_id] → component id
// cl_ref.n_components

Downstream callers that detect the tagged labels skip rebuilding them, just like other tagged topology structures.

Low-Level Control

For more control over connectivity rules, use tf::label_connected_components with appliers:

// Build connectivity structures
tf::face_membership<int> fm;
tf::manifold_edge_link<int, 3> mel;
fm.build(polygons);
mel.build(polygons.faces(), fm);

// Label connected components - components connected only through manifold edges
tf::buffer<int> labels;
labels.allocate(polygons.size());

auto component_count = tf::label_connected_components(
    labels,
    tf::make_applier(mel)  // Only traverse through manifold edges
    // optionally specify, as > 500 components are more efficiently
    // found using a sequential algorithm (default is parallel)
    /*, expected_number_of_components*/
);

The index type defaults to int, suitable for most use cases. For very large meshes with billions of elements, specify int64_t:

auto component_count = tf::label_connected_components<int64_t>(
    labels, tf::make_applier(mel));

Process results using tf::enumerate

tf::parallel_for_each(tf::enumerate(labels), [&](auto pair) {
    auto [face_id, component_id] = pair;
    // Process face and its component assignment
});

You can also use different connectivity rules:

// Use face_link for standard face adjacency
tf::face_link<int> fl;
fl.build(polygons.faces(), fm);

auto face_components = tf::label_connected_components(
    labels, tf::make_applier(fl)
);

// Use vertex_link for vertex-based connectivity
tf::vertex_link<int> vl;
vl.build(polygons, fm);

tf::buffer<int> vertex_labels;
vertex_labels.allocate(polygons.points().size());
auto vertex_components = tf::label_connected_components(
    vertex_labels, tf::make_applier(vl)
);

You can also use a mask to exclude certain elements:

tf::buffer<bool> mask;
mask.allocate(polygons.size());
tf::parallel_fill(mask, true);
// Set specific mask values...

auto component_count = tf::label_connected_components_masked(
    labels, mask, tf::make_applier(mel)
);

Custom Appliers

An applier is a callable with signature (id, callback) -> void that iterates over neighbors of id and calls callback(neighbor_id) for each. You can write custom appliers for specialized connectivity rules:

// Custom applier: only connect faces that share an edge AND have similar normals
auto normal_aware_applier = [&](auto face_id, const auto& callback) {
    auto face_normal = normals[face_id];
    for (const auto& edge : mel[face_id]) {
        if (edge.is_simple()) {
            auto peer_normal = normals[edge.face_peer];
            if (tf::dot(face_normal, peer_normal) > 0.9f)
                callback(edge.face_peer);
        }
    }
};

auto component_count = tf::label_connected_components(
    labels, normal_aware_applier
);

Connectivity Type

tf::connectivity_type names the three connectivity rules as one value. The C++ layer has a dedicated function per rule, so the enum is what a caller passes when the rule is chosen at runtime — the VTK connected_components filter and make_connected_components take it directly.

Open and Closed Components

tf::set_type says whether a mesh or a component has boundary edges (open) or none (closed). tf::set_component_labels pairs a connected_component_labels with one such verdict per component:

tf::set_component_labels<int> scl;
scl.component_labels = tf::make_manifold_edge_connected_component_labels(polygons);
scl.set_types.allocate(scl.component_labels.n_components);
// ...fill set_types[c] with tf::set_type::open / ::closed

tf::containment c =
    tf::spatial::classify_point(query, polygons | tf::tag(tree), scl);

This is the form tf::spatial::classify_point consumes: a point can only be inside a closed component, so the per-component verdict is what lets one classification pass handle a mesh whose parts are not all watertight. The library ships no producer for set_types — the caller states it.

Volumetric Domains

A non-manifold polygon mesh bounds multiple 3D regions ("domains"). tf::make_domain_labels returns one label per face per side, partitioning space into volumetric components.

auto labels = tf::make_domain_labels(
    polygons,
    tf::domain_config::ignore_open_fragments
        | tf::domain_config::exclude_outer_shell);

int n_domains       = labels.n_domains;
int outer_shell     = labels.outer_shell_label;       // == n_domains here
auto d0 = labels.labels[face_id][0];   // domain containing face with REVERSED winding
                                       // (the side stored normal points INTO)
auto d1 = labels.labels[face_id][1];   // domain containing face with FORWARD winding
                                       // (the side stored normal points AWAY FROM)

tf::domain_config is a bitflag enum:

When the outer shell has been excluded, outer_shell_label equals n_domains (the sentinel); otherwise no face-side carries that label.

Sidedness Relations

For each manifold-edge-connected component of an arrangement, tf::make_sidedness_relations emits the operands the component touches at a non-manifold (cut) edge and the sidedness against each operand's oriented surface. Useful for selecting a signed half — "give me the components of mesh_a on the +normal side of mesh_b" — without going through a full boolean and without requiring the operands to be closed.

// arrangement = tf::make_mesh_arrangements({mesh_a, mesh_b, ...})
auto [relations, cl] = tf::make_sidedness_relations(arrangement, tag_labels);

// relations: offset_block_buffer<Index, tf::tagged_sidedness<Index>>
//   keyed per component. relations[c] yields a block of
//   { tag, side } entries — one per other operand the component touches.
// cl:        tf::connected_component_labels<Index> with manifold-edge
//   connectivity. cl.labels[face_id] gives the component id.

for (Index c = 0; c < cl.n_components; ++c) {
  for (auto entry : relations[c]) {
    Index operand_tag = entry.tag;
    tf::sidedness side = entry.side;   // on_positive_side / on_negative_side / on_boundary
    // ...
  }
}

Components that don't share any non-manifold edge with another operand (interior or fully disjoint pieces) get an empty block.

Picking a signed half

// Keep mesh_a (tag 0) components on the +normal side of mesh_b (tag 1).
tf::buffer<bool> per_component_keep;
per_component_keep.allocate(cl.n_components);
tf::parallel_for_each(
  tf::enumerate(relations),
  [&](auto p) {
    auto&& [c, block] = p;
    bool keep = false;
    for (auto e : block) {
      if (e.tag == 1 && e.side == tf::sidedness::on_positive_side) {
        keep = true;
        break;
      }
    }
    per_component_keep[c] = keep;
  });

// Lift per-component → per-face via tf::make_indirect_range, then reindex.
auto face_keep = tf::make_indirect_range(cl.labels, per_component_keep);
auto kept = tf::reindexed_by_mask(arrangement, face_keep);

Reusing pre-built topology

If arrangement already carries tf::tag(face_membership) and tf::tag(manifold_edge_link) from an earlier call, make_sidedness_relations reuses them. Otherwise it builds them locally. Same idiom for tf::connected_component_labels — if tagged on the input, reused; otherwise built and returned via the second tuple element.

auto fm  = tf::make_face_membership(arrangement);
auto mel = tf::make_manifold_edge_link(arrangement);
auto tagged = arrangement | tf::tag(fm) | tf::tag(mel);

// Builds connected_component_labels internally; returns the pair.
auto [relations, cl] = tf::make_sidedness_relations(tagged, tag_labels);

If you want to chain multiple sidedness queries on the same arrangement (e.g. with different tag-label rearrangements), tag the ccl too:

auto cl_tagged = arrangement | tf::tag(fm) | tf::tag(mel) | tf::tag(cl);
// Subsequent calls return only the relations buffer — ccl is reused.
auto relations_again = tf::make_sidedness_relations(cl_tagged, other_tag_labels);

Path Finding and Graph Algorithms

Edge to Path Connection

Connect a collection of edges into paths:

// Automatically connect edges into paths
auto paths = tf::connect_edges_to_paths(edges);

// The result is an offset_block_buffer of connected paths
for (const auto& path : paths) {
    for (auto vertex_id : path) {
        // Process vertex in connected path
    }
}

Path Connector

tf::path_connector is the reusable class behind connect_edges_to_paths. Keep one when tracing many edge sets: clear() retains the capacity of every internal buffer.

tf::path_connector<int, int> pc;
pc.build(edges);

for (const auto& path : pc.paths_buffer()) {
    for (auto vertex_id : path) { /* ... */ }
}

pc.clear();
pc.build(other_edges);

It deduplicates the input edges, builds a vertex link over them, then traces from every degree-1 endpoint first and closes the remaining loops. Vertex ids need not be dense — the first template parameter is the vertex identifier type and the connector maps it through a contiguous index hash map, so sparse or non-integer ids work.

Eulerian Paths

tf::find_eulerian_paths decomposes a graph into a minimal set of edge-disjoint paths covering every edge (Hierholzer). Unlike connect_edges_to_paths, it does not stop at a vertex where several edges meet — it keeps consuming them.

tf::buffer<int> path_offsets, edge_ids;

// Over explicit edges + edge membership: paths are runs of EDGE ids
tf::edge_membership<int> em;
em.build(edges, n_unique_ids, tf::edge_orientation::forward);
tf::find_eulerian_paths(edges, em, path_offsets, edge_ids);

// Over a vertex link: paths are runs of VERTEX ids
tf::buffer<int> vertex_ids;
tf::find_eulerian_paths(v_link, path_offsets, vertex_ids);

auto paths = tf::make_offset_block_range(path_offsets, edge_ids);

The outputs are appended, so one pair of buffers can accumulate the decomposition of several graphs.

Planar Graph Processing

For 2D planar graphs, trueform provides specialized algorithms. All geometric predicates are exact on an integer lattice — floating-point coordinates are converted onto it via pt_converter, and edge ordering uses exact orient2d (int128 cross products) instead of atan2. This eliminates precision issues with nearly-parallel edges and sliver regions.

build accepts any coordinate type, so nothing in these classes can name the lattice for you: every planar graph class takes it as a required Int template parameter.

// int32 suits float input
tf::planar_embedding<int, tf::exact::int32> embedding;

// int64 suits double input
tf::planar_embedding<int, tf::exact::int64> embedding;

This applies to planar_graph_regions, planar_embedding, face_hole_relations, hole_patcher, face_split_by_edges, and face_splitting_paths.

See Intersect: Exact Arithmetic for details on the precision chain.

Planar Graph Regions

Extract minimal closed regions from a planar graph. The input is a set of directed edges (both directions per undirected edge) and 2D vertex positions. The output is an offset_block_buffer of regions, each a sequence of vertex IDs forming a closed loop.

tf::planar_graph_regions<int, tf::exact::int32> pgr;
pgr.build(directed_edges, points);

// Iterate over regions
for (const auto& region : pgr) {
    for (auto vertex_id : region) {
        // Process vertex in region boundary
    }
}

The algorithm sorts outgoing edges at each vertex by polar angle using int128 cross products (no atan2). It then walks the graph: for each directed edge, find its twin at the target vertex in the sorted adjacency list and take the cyclic predecessor. This traces out all minimal regions.

Interior regions have positive signed area (CCW), the unbounded exterior region has negative signed area (CW).

// Classify regions by area sign
for (auto region : pgr) {
    auto sign = tf::exact::signed_area_sign(
        tf::make_polygon(region, points));
    if (sign > 0) { /* interior face */ }
    else           { /* exterior or hole */ }
}

Planar Embedding

Builds on planar_graph_regions to produce a complete planar embedding with face-hole relationships. Regions are classified by signed area into faces (CCW, positive) and holes (CW, negative), and each hole is assigned to its containing face.

tf::planar_embedding<int, tf::exact::int32> embedding;
embedding.build(directed_edges, points);

// Access faces and holes
auto faces = embedding.faces();
auto holes = embedding.holes();

// Get hole assignments per face
auto holes_for_faces = embedding.holes_for_faces();
tf::parallel_for_each(tf::enumerate(holes_for_faces), [&](auto pair) {
    auto [face_id, face_holes] = pair;
    for (auto hole_id : tf::make_indirect_range(face_holes, holes)) {
        // Process hole within this face
    }
});

Face-Hole Relations

The tf::face_hole_relations assigns each hole to its containing face. Given a set of faces (CCW loops) and holes (CW loops), it determines which face contains each hole by finding the smallest-area face that encloses a point from the hole. Uses an AABB tree for spatial queries and exact orient2d for point-in-polygon tests.

tf::face_hole_relations<int, tf::exact::int32> fhr;
fhr.build(faces, holes, points);

// fhr[face_id] gives the hole indices assigned to that face
for (auto [face_id, assigned_holes] : tf::enumerate(fhr)) {
    for (auto hole_id : assigned_holes) {
        // hole_id belongs inside face_id
    }
}

planar_embedding uses this internally. It can also be used standalone when faces and holes come from other sources.

Hole Patcher

Connects holes to an outer boundary, producing a single pseudosimple polygon. Floating-point coordinates are automatically converted onto the Int lattice via pt_converter. The output is a flat vertex sequence where bridge vertices appear twice — once when entering the hole and once when returning to the outer boundary.

tf::hole_patcher<int, tf::exact::int32> patcher;

std::vector<int> boundary_loop = {0, 1, 2, 3};
patcher.build(tf::make_range(boundary_loop), holes, points);

// Result is a single polygon with bridge edges
auto patched_face = patcher.face();
for (auto vertex_id : patched_face) {
    // Process vertex in patched polygon
}

If a hole shares a vertex with the outer boundary, the patcher splices directly at that vertex without adding bridge edges. Otherwise, holes are processed in order of their leftmost coordinate. For each hole, the algorithm finds the nearest visible vertex on the current boundary using a heap-based search with exact wedge and visibility tests.

Face Split by Edges

The tf::face_split_by_edges subdivides a face boundary given a set of interior edges. It classifies edges into crossings (both endpoints on the boundary), loops (closed cycles), cuts (one endpoint interior), and non-crossings (T-junctions), then extracts all resulting sub-faces and holes with their face-hole relationships.

tf::face_split_by_edges<int, tf::exact::int32> fsbe;

std::vector<int> face = {0, 1, 2, 3};
fsbe.build(tf::make_range(face), edges, points);

// Sub-faces (CCW, positive area)
for (auto sub_face : fsbe.faces()) {
    for (auto vertex_id : sub_face) { /* ... */ }
}

// Holes (CW, negative area)
for (auto hole : fsbe.holes()) {
    for (auto vertex_id : hole) { /* ... */ }
}

// Hole-to-face assignments
auto hff = fsbe.holes_for_faces();
for (auto [face_id, assigned_holes] : tf::enumerate(hff)) {
    for (auto hole_id : assigned_holes) { /* ... */ }
}

// Exact signed areas (int128)
for (auto area : fsbe.face_areas()) { /* ... */ }

Since the outer boundary is known, the algorithm can classify crossing paths directly without a full planar embedding — crossings are resolved by area ordering at shared endpoints. planar_graph_regions is used as a fallback only when non-crossing edges (T-junctions) create regions that cannot be resolved by path classification alone.

Triangulation

Constrained Delaunay Triangulator

The tf::constrained_delaunay_triangulator triangulates a 2D point set and recovers user-supplied constraint edges. Constraints may intersect each other — edge–edge crossings, T-junctions, collinear overlaps, and shared endpoints are all resolved. A crossing is resolved against the live triangulation at the moment recovery meets it: the crossing becomes a vertex and both constraints are replaced by their halves through it. A T-junction or a collinear overlap needs no new coordinate, since the vertex that resolves it is already there.

tf::constrained_delaunay_triangulator<int, float> cdt;
cdt.build(tf::make_points(points),
          tf::make_edges(tf::make_range(edges)));

auto out_pts = cdt.points();           // deconverted to float
auto faces   = cdt.make_faces();
auto labels  = cdt.region_labels();    // per-triangle parity (0/1)
auto &im     = cdt.index_map();        // input id ↔ output id

im.f()[input_id] gives the output index of an input point. im.kept_ids()[output_id] returns the surviving input ID, or the sentinel im.f().size() for vertices added at constraint intersections.

A 4-argument build(pts, edges, is_boundary, split_constraints) takes a per-edge mask: true means the edge is a region wall (parity flips when crossed), false means it's preserved as an edge but does not separate regions. The 2-argument form is a convenience that defaults the mask to all true. Use false for internal constraints — diagonals, feature lines — that you want held as edges without splitting the interior.

split_constraints (default true) is permission to create vertices. Pass false to demand the constraints verbatim: the build then refuses — build returns false and reports nothing — rather than resolve a crossing. Callers that share edges between triangulations use the refusal as their signal, resolve once with permission, and broadcast the resulting splits to every carrier of those edges, so that all of them agree on where the edge is divided. parameterized_crossings() reports each created vertex as a dyadic parameter along each parent constraint; the parameter, not the coordinate, is what transports exactly.

Properties

1. Constraints intersecting each other are handled automatically when split_constraints is set, and refused as a build failure when it is not.
2. All input points are preserved, with coincident inputs merged in the output. index_map() exposes the input↔output mapping; synthetic intersection vertices use the sentinel value.
3. Constraints appear as edges of the output, split at whatever resolution created.
4. Region labels are parity over boundary-constrained edges. Non-boundary constraints don't toggle parity.

Algorithm

Four phases: (1) weld the input points exactly and map the constraints through the weld, dropping any that lose their length to it; (2) build the convex-hull Delaunay incrementally, inserting in BRIO order (randomized rounds of Hilbert-sorted points) with a remembering location walk and apex-routed Lawson flips; (3) recover each constraint by deleting the crossed triangle strip and retriangulating both side polygons (Anglada single-pass, with a Delaunay flip per new triangle) — a constraint that meets an obstruction is split at it and both halves re-enter recovery; (4) flood-fill region labels from a hull-adjacent triangle, toggling on boundary-constrained edges.

Constrained Delaunay (make_cdt)

tf::make_cdt wraps the class above into a one-shot helper. It runs the build, filters to interior triangles via region_labels()[t] % 2 == 1, and reindexes faces and points to drop the exterior — returning a tf::polygons_buffer ready for downstream use.

auto polys = tf::make_cdt(points);                     // convex hull
auto polys = tf::make_cdt(points, edges);              // every edge a boundary
auto polys = tf::make_cdt(points, edges, is_boundary); // explicit mask

// Every constrained form takes a trailing split_constraints, default true:
auto polys = tf::make_cdt(points, edges, is_boundary, false);

// Same overloads with an additional input→output index map:
auto [polys, im] = tf::make_cdt(points, return_index_map);
auto [polys, im] = tf::make_cdt(points, edges, return_index_map);
auto [polys, im] = tf::make_cdt(points, edges, is_boundary, return_index_map);

Index is deduced from the constraint edges' own element type, and defaults to int for the point-only overloads that have no edges to deduce from. Int auto-resolves to int32 for float input or int64 for double, so neither needs to be spelled out at the call site. A build that refuses — split_constraints = false on crossing constraints — returns an empty buffer, and an empty index map with it.

Delaunay Refinement (cdt_refiner)

The tf::cdt_refiner takes the constraint-preserving CDT and refines it to a quality floor (Ruppert). The boundary triangulation is built once — constraints are never intersected — and a bad-triangle queue then drives circumcenter insertions directly, each candidate walking from its generating triangle, so there is no rebuild round and no point location.

tf::cdt_refine_config quality;
quality.min_quality     = 0.3f;   // q = (2/sqrt3) * 2A / max_edge^2, in (0, 1]
quality.split_encroached = true;  // permit midpoint splits of constraints

tf::cdt_refiner<int, float> refiner;
if (refiner.build(pts, edges, quality)) {
    auto faces  = refiner.make_faces();
    auto labels = refiner.region_labels();
    auto out    = refiner.converted_points();   // or points() for the lattice
}

The build takes the same shapes as the triangulator — with an is_boundary mask, with an additional per-edge is_splittable mask, or with neither — and a trailing cdt_region_mode. It returns false when a constraint cannot be recovered under the preserve contract; the topology is then unusable, but has_prepared_input_index_map() says whether the input index_map() published before the refusal is still valid.

Every split is recorded as a dyadic parameter of the original input edge, so callers coordinating several triangulations over shared polylines can union the records and reproduce identical split points — the parameter transports exactly, the coordinate does not.

// blocks indexed by input edge id, each sorted by parameter
for (const tf::cdt_constraint_split<int>& s : refiner.constraint_splits()[edge_id]) {
    // s.edge is the original input constraint;
    // the split sits at s.numerator / 2^s.depth along it (numerator odd)
}

Additional reads: for_each_face_adjacency(f) visits faces with neighbours and per-edge constraint flags in make_faces() order; face_constraint_owners(t) gives each edge of a face its original input constraint and the exact span it covers; constrained(f, e) is the per-edge flag alone. always_track_constraint_owners() retains ownership on the seed triangulation so constraint_collisions() can report two input constraints that cover one span.

Coord may be integral, in which case it is consumed exactly (identity conversion). To keep dyadic split positions exact on an integer lattice, reserve split-depth bits of scale headroom.

Triangulation Type

tf::triangulation_type is the selector a consumer carries when it builds triangulations over cut surfaces — notably tf::arrangement_config in the Arrangement module.

Region Labels (cdt_region_mode)

tf::cdt_region_mode selects what region_labels() states. It is the trailing argument of every constrained build — build, build_regions, and build_from_constraints on the triangulator, and build on tf::cdt_refiner — and defaults to nesting.

tf::constrained_delaunay_triangulator<int, float> cdt;

// Default: parity, so region_labels()[t] % 2 == 1 means "inside".
cdt.build(pts, edges);

// Component ids instead: each wall-bounded piece gets its own label.
cdt.build(pts, edges, tf::cdt_region_mode::components);

auto mode = cdt.region_mode();  // what the last build labelled

Only walls separate regions. A constraint the per-edge is_boundary mask marks false is preserved but re-entered, so a slit never opens a region of its own under either mode. tf::make_cdt always builds in nesting mode, because it keeps the interior by parity.

Unconstrained Delaunay Triangulator

The tf::unconstrained_delaunay_triangulator is the point-only Delaunay of the same exact kernel: a divide-and-conquer build over the exact-welded sites, deliberately retaining no constraint state, no adjacency, and no region labels. It is what tf::make_cdt(points) — the no-edges convex-hull overload — runs underneath.

tf::unconstrained_delaunay_triangulator<int, float> tri;
if (tri.build(tf::make_points(points))) {
    for (auto face : tri.faces()) {
        int a = face[0], b = face[1], c = face[2];
    }
}

// Reusable — clear() keeps the capacity.
tri.clear();
tri.build(tf::make_points(other_points));

build returns false only when fewer than three points are given or the chosen Index cannot address the topology; three or more inputs that weld to fewer than three unique positions are accepted and produce no faces. Exact duplicate coordinates retain the lowest input index.

Both policies live in tf::topology::cdt. build(points, tf::return_index_map) additionally retains an input-to-compact-vertex map, moved out with take_index_map(); that map always names compact vertices, independently of VertexPolicy.