trueform

Modules | C++

Topology

Connectivity structures, planar embeddings, and mesh analysis.

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.

face_membership.cpp
// 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);

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.

vertex_link.cpp
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:

vertex_link_edges.cpp
// 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.

k_ring.cpp
// 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.

neighborhoods.cpp
// 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.

face_link.cpp
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.

manifold_edge_link.cpp
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

Edge Membership and Orientation

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

edge_membership.cpp
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);

Mesh Analysis Functions

Boundary Detection

Extract boundary edges and organize them into boundary loops:

boundary_detection.cpp
// 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
    }
}
For a quick boolean check without extracting edges, use tf::is_closed() or tf::is_open(). See Closed/Open Mesh Detection.

Non-Manifold Edge Detection

Identify edges that are shared by more than two faces:

non_manifold.cpp
// 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
}
For a quick boolean check without extracting edges, use tf::is_manifold() or tf::is_non_manifold(). See Manifold Detection.

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:

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

Face Orientation

Ensure consistent face orientation across the mesh:

face_orientation.cpp
// 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
tf::orient_faces_consistently(polygons | tf::tag(me_link));

// Or directly on polygons (computes topology automatically)
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.

Reverse Winding

Reverse the winding order of all faces:

reverse_winding.cpp
// 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):

is_closed.cpp
// 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:

is_closed_curve.cpp
// 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
}
To extract the actual boundary edges, use tf::make_boundary_edges() or tf::make_boundary_paths(). See Boundary Detection.

Manifold Detection

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

is_manifold.cpp
// 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);
To extract the actual non-manifold edges, use tf::make_non_manifold_edges(). See Non-Manifold Edge Detection.

Euler Characteristic

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

euler_characteristic.cpp
int chi = tf::euler_characteristic(polygons);

// For a closed genus-0 mesh (sphere-like): chi == 2
// For a torus: chi == 0

Edges are counted by iterating face edges and counting only those where the first vertex index is less than the second, avoiding double-counting of shared edges. Requires a closed manifold mesh with shared vertices (use tf::cleaned first on mesh soup).

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

Low-Level Control

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

connected_components.cpp
// 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:

connectivity_rules.cpp
// 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:

masked_components.cpp
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.cpp
// 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
);

Path Finding and Graph Algorithms

Edge to Path Connection

Connect a collection of edges into paths:

connect_edges.cpp
// 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
    }
}

Planar Graph Processing

For 2D planar graphs, trueform provides specialized algorithms. All geometric predicates use exact int32 arithmetic internally — float coordinates are automatically converted to int32 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.

For increased precision, all planar graph classes accept an optional Int template parameter:

// Default: int32 (sufficient for most inputs)
tf::planar_embedding<int> embedding;

// Higher precision: int64
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, face_splitting_paths, and ear_cutter.

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.

planar_regions.cpp
tf::planar_graph_regions<int> 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).

planar_regions_area.cpp
// 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.

planar_embedding.cpp
tf::planar_embedding<int> 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.

face_hole_relations.cpp
tf::face_hole_relations<int> 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. Float coordinates are automatically converted to int32 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.

hole_patching.cpp
tf::hole_patcher<int> 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.

The pseudosimple polygon produced by the hole patcher is the expected input format for tf::ear_cutter. Bridge vertices have the same point ID but appear at two positions in the polygon — the ear cutter detects these and handles them as shards.

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.

face_split_by_edges.cpp
tf::face_split_by_edges<int> 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

Ear Cutter

The tf::ear_cutter triangulates 2D polygons using ear clipping with exact int32 predicates. Float and double inputs are automatically converted to int32 via pt_converter. All geometric tests (orientation, containment, intersection) use int128 arithmetic internally.

ear_cutter.cpp
tf::ear_cutter<int> ec;

// Triangulate a polygon given as identity indices into a point buffer
std::vector<int> ids = {0, 1, 2, 3, 4};
ec.build(ids, points);

// Or triangulate all points in order (ids = 0, 1, 2, ...)
ec.build(points);

// Access results as blocked ranges of 3 (triangle faces)
for (auto face : ec.faces()) {
    int a = face[0], b = face[1], c = face[2];
}

// Or access the raw index buffer
const tf::buffer<int>& indices = ec.indices_buffer();

The ear cutter accepts pseudosimple polygons from hole bridging, where bridge vertices appear twice with opposite-direction edges. It also handles collinear vertices and geometric shards — slits where the polygon boundary doubles back on itself.

ear_cutter_reuse.cpp
// Float points are converted to int32 automatically
tf::ear_cutter<int> ec;
ec.build(float_polygon_ids, float_points);

// Reusable — just call build() again
ec.build(another_polygon_ids, another_points);

Invariants

The output satisfies four properties:

  1. Every input vertex appears in at least one output triangle.
  2. Every boundary edge appears exactly once — each directed edge of the input polygon is present in exactly one output triangle.
  3. Every interior edge appears exactly twice, once in each direction.
  4. Every triangle has 3 distinct vertex identities. Exception: outward shards, where the degenerate ear is the only way to include the tip vertex.

These properties matter for mesh arrangements. When a mesh face is cut by intersection curves, the resulting sub-faces are triangulated independently on each side of the cut. For the two sides to stitch into a manifold mesh, every vertex along the shared boundary must be present in both triangulations. A missing vertex leaves a gap; a missing boundary edge produces a hole.

Zero-area triangles occur in two cases: outward shards (the tip is outside the polygon, no valid diagonal exists) and residual collinear runs (collapsed collinear points fan-emitted to preserve invariant 1). Both are topologically valid — they maintain the edge structure even though they contribute no area.

Fallbacks

When ear clipping gets stuck (no convex ear found after a full loop), three fallbacks are applied in order:

  1. Shard resolution — a shard is a slit where prev and next share coordinates. The algorithm first tries a diagonal from the shard tip. If none exists (outward shard), the tip is clipped as a degenerate ear.
  2. Collinear run removal — consecutive collinear vertices are absorbed into a linked list on their predecessor node. When an ear along that edge is later clipped, the absorbed vertices are fan-expanded back into the output.
  3. Diagonal split — find any valid diagonal, split the polygon in two, triangulate each half recursively.

For polygons with more than 80 vertices, z-order hashing accelerates the ear search by limiting containment checks to spatially nearby vertices. CW input is detected via signed_area_2x and reversed internally; output triangles are flipped back to match the original winding.

Delaunay Flipper

The tf::delaunay_flipper refines an existing triangulation by flipping interior edges until the constrained Delaunay property holds. Float and double inputs are automatically converted to int32 via pt_converter. The incircle test uses int128 arithmetic internally.

delaunay_flipper.cpp
tf::delaunay_flipper<int> flipper;

// Flip edges in a triangle mesh toward Delaunay
flipper.flip(faces, points);

// With user-provided constraints (edges that must not be flipped)
flipper.flip(faces, points, [](int a, int b) {
    // return true for edges that should be preserved
    return is_polygon_boundary(a, b);
});

// Reusable — just call flip() again
flipper.flip(other_faces, other_points);

Boundary edges (shared by fewer than two triangles) and non-manifold edges (shared by more than two) are never flipped. User constraints are passed as a callable (Index, Index) -> bool for additional protection — polygon boundary edges, bridges, or any application-specific edges.

Properties

  1. Converges to the unique constrained Delaunay triangulation. Each flip strictly improves the lexicographic angle vector. No local minima exist.
  2. Cocircular points are not flipped — when inCircle == 0, either diagonal is equally valid. Skipping the flip guarantees termination.
  3. Boundary and non-manifold edges are never flipped. Boundary is detected automatically from the adjacency structure. Non-manifold edges are treated as constrained.
  4. Triangle count is unchanged — flips redistribute existing triangles without adding or removing any.
  5. Winding is preserved — detected once from the first non-degenerate triangle, applied consistently to all incircle tests.

Algorithm

Lawson edge flips with a stack of suspect edges. All interior edges are seeded onto the stack. Each iteration pops an edge, tests it with the exact incircle predicate, and flips if the opposite vertex lies strictly inside the circumcircle. After a flip, the four outer edges of the affected quadrilateral are pushed as new suspects. The stack empties when all edges satisfy the Delaunay criterion.

Adjacency is built from tf::face_membership and stored as a per-triangle neighbor array (tf::blocked_buffer<Index, 3>). After each flip, the neighbor array and the triangle buffer are updated in place.

tf::triangulated and tf::triangulated_faces use the Delaunay triangulator internally — no manual invocation is needed for standard triangulation workflows.

Delaunay Triangulator

The tf::delaunay_triangulator combines ear cutting with Delaunay flips into a single call. Same API and input requirements as tf::ear_cutter — see Ear Cutter for supported inputs (bridged holes, collinear vertices, shards) and invariants. Polygon boundary edges are automatically constrained during flipping.

delaunay_triangulator.cpp
tf::delaunay_triangulator<int> tri;
tri.build(points);

for (auto face : tri.faces()) {
    int a = face[0], b = face[1], c = face[2];
}

// Reusable
tri.build(other_points);

Spatial

Trees, search, neighbor queries, and ray casting.

Geometry

Geometric analysis, surface properties, and point cloud alignment.