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.

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:

Planar Graph Regions

Extract regions (faces) from a planar graph embedding:

planar_regions.cpp
tf::planar_graph_regions<int, double> pgr;
pgr.build(directed_edges, points);

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

Planar Embedding

Create a complete planar embedding with face-hole relationships:

planar_embedding.cpp
tf::planar_embedding<int, double> embedding;
embedding.build(directed_edges, points);

// Access faces and holes using tf::make_indirect_range
auto faces = embedding.faces();
auto holes = embedding.holes();
auto face_areas = embedding.face_areas();
auto hole_areas = embedding.hole_areas();

// Get hole relationships using tf::zip and tf::enumerate
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
    }
});

Hole Patching

Patch holes in 2D polygonal regions:

hole_patching.cpp
tf::hole_patcher<int> patcher;

// Build takes a boundary loop, holes to patch, and point coordinates
std::vector<int> boundary_loop = {0, 1, 2, 3}; // outer boundary
tf::faces<SomePolicy> holes; // collection of hole boundaries
tf::points<SomePolicy> points; // 2D point coordinates

patcher.build(boundary_loop, holes, points);

// Get the resulting patched face
auto patched_face = patcher.face();
for (auto vertex_id : patched_face) {
    // Process vertex in patched polygon
}
The hole patcher uses a sophisticated algorithm to connect holes to the outer boundary while avoiding self-intersections.

Spatial

Trees, search, neighbor queries, and ray casting.

Geometry

Geometric analysis, surface properties, and point cloud alignment.