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

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

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

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

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

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

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

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
}

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.

Connected Components

Find and label connected components in meshes or graphs using proper trueform 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<int>(
    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*/ 
);

// Process results using tf::enumerate
tf::parallel_apply(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<int>(
    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<int>(
    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<int>(
    labels, mask, tf::make_applier(mel)
);

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_apply(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.

Topology Policies

The topology module integrates with trueform's policy system to automatically attach connectivity information to geometric objects:

topology_policies.cpp

// Polygon with face membership
auto polygons_with_topology = polygons | tf::tag(face_membership);

// Access the topology
const auto& fm = polygons_with_topology.face_membership();

Spatial

Trees, forms, search, neighbor queries, and ray casting.

Geometry

Normal computation and geometric analysis.