Topology
The Topology module provides tools for analyzing connectivity and structure in meshes and edge meshes. It includes data structures for efficient adjacency queries and algorithms for component labeling.
Cell Membership
Cell membership maps each vertex to the cells (faces or edges) containing it. This is a fundamental structure used by other topology functions.
import trueform as tf
import numpy as np
# Triangle mesh
faces = np.array([
[0, 1, 2],
[1, 3, 2],
[2, 3, 4]
], dtype=np.int32)
points = np.random.rand(5, 3).astype(np.float32)
mesh = tf.Mesh(faces, points)
# Get face membership from mesh property (built automatically)
fm = mesh.face_membership
# fm[0] contains all faces that include vertex 0
# fm[1] contains all faces that include vertex 1, etc.
# Or compute directly from connectivity array
fm = tf.cell_membership(faces, n_ids=5)
# n_ids is the number of unique vertex IDs (number of points)
For edge meshes, use edge_membership:
edges = np.array([[0, 1], [1, 2], [2, 3]], dtype=np.int32)
points = np.random.rand(4, 3).astype(np.float32)
edge_mesh = tf.EdgeMesh(edges, points)
# Get edge membership from edge mesh property
em = edge_mesh.edge_membership
# em[1] = [0, 1] # vertex 1 is in edges 0 and 1
# Or compute directly
em = tf.cell_membership(edges, n_ids=4)
Manifold Edge Link
Manifold edge link provides adjacency information for each edge of each face. For a given face and edge, it returns the index of the adjacent face sharing that edge.
mesh = tf.Mesh(faces, points)
# Get manifold edge link from mesh property
mel = mesh.manifold_edge_link
# mel[i, j] is the face adjacent to face i across edge j
Special return values indicate edge types:
>= 0: Index of adjacent face-1: Boundary edge (no adjacent face)-2: Non-manifold edge (shared by more than 2 faces)-3: Non-manifold representative
# Compute directly from connectivity
fm = tf.cell_membership(faces, n_ids=len(points))
mel = tf.manifold_edge_link(faces, fm)
# Check edge properties
for face_id in range(len(faces)):
for edge_id in range(3): # triangles have 3 edges
neighbor = mel[face_id, edge_id]
if neighbor >= 0:
print(f"Face {face_id} edge {edge_id} -> face {neighbor}")
elif neighbor == -1:
print(f"Face {face_id} edge {edge_id} is boundary")
else:
print(f"Face {face_id} edge {edge_id} is non-manifold")
Face Link
Face link stores, for each face, all adjacent faces (those sharing an edge).
mesh = tf.Mesh(faces, points)
# Get face link from mesh property
fl = mesh.face_link
# fl[i] contains all faces connected to face i by an edge
# Compute directly
fm = tf.cell_membership(faces, n_ids=len(points))
fl = tf.face_link(faces, fm)
# Iterate over neighbors of a face
for neighbor_face in fl[0]:
print(f"Face 0 is connected to face {neighbor_face}")
Vertex Link
Vertex link stores, for each vertex, all adjacent vertices (those sharing an edge or face).
From Face Connectivity
For meshes, use vertex_link_faces to find vertices sharing a face:
mesh = tf.Mesh(faces, points)
# Get vertex link from mesh property
vl = mesh.vertex_link
# vl[i] contains all vertices that share a face with vertex i
# Compute directly
fm = tf.cell_membership(faces, n_ids=len(points))
vl = tf.vertex_link_faces(faces, fm)
# Iterate over the 1-ring neighbors of a vertex
for neighbor in vl[0]:
print(f"Vertex 0 is connected to vertex {neighbor}")
From Edge Connectivity
For edge meshes, use vertex_link_edges to find vertices sharing an edge:
edge_mesh = tf.EdgeMesh(edges, points)
# Get vertex link from edge mesh property
vl = edge_mesh.vertex_link
# vl[1] = [0, 2] # vertex 1 connects to vertices 0 and 2
# Compute directly
vl = tf.vertex_link_edges(edges, n_ids=4)
# Iterate over neighbors of a vertex
for neighbor in vl[1]:
print(f"Vertex 1 is connected to vertex {neighbor}")
K-Ring Neighborhoods
Computes k-ring neighborhoods for all vertices using breadth-first traversal. The 1-ring is the immediate neighbors, 2-ring includes neighbors of neighbors, etc.
# Build vertex link first
fm = tf.cell_membership(faces, n_ids=len(points))
connectivity = tf.vertex_link_faces(faces, fm)
# Compute 2-ring neighborhoods
k2 = tf.k_rings(connectivity, k=2)
# Access neighbors of vertex 0
neighbors = k2[0]
# Include seed vertex
k2_inclusive = tf.k_rings(connectivity, k=2, inclusive=True)
| Parameter | Type | Description |
|---|---|---|
connectivity | OffsetBlockedArray | 1-ring vertex connectivity |
k | int | Number of hops |
inclusive | bool | Include seed vertex (default False) |
Radius-Based Neighborhoods
Computes neighborhoods based on Euclidean distance via mesh traversal. For each vertex, finds all vertices reachable via mesh edges within the specified radius.
# Build vertex link first
fm = tf.cell_membership(faces, n_ids=len(points))
connectivity = tf.vertex_link_faces(faces, fm)
# Compute neighborhoods within radius 0.5
neighs = tf.neighborhoods(connectivity, points, radius=0.5)
# Access neighbors of vertex 0
neighbors = neighs[0]
# Include seed vertex
neighs_inclusive = tf.neighborhoods(connectivity, points, radius=0.5, inclusive=True)
| Parameter | Type | Description |
|---|---|---|
connectivity | OffsetBlockedArray | 1-ring vertex connectivity |
points | ndarray | Vertex positions (n, dims) |
radius | float | Maximum Euclidean distance |
inclusive | bool | Include seed vertex (default False) |
Mesh Analysis Functions
Boundary Detection
Extract boundary edges and organize them into boundary loops:
mesh = tf.Mesh(faces, points)
# Extract boundary edges from a mesh
boundary_edges = tf.boundary_edges(mesh)
# boundary_edges has shape (N, 2) - each row is [vertex_a, vertex_b]
# Extract boundary paths (connected sequences of boundary edges)
paths = tf.boundary_paths(mesh)
# Each path contains original mesh vertex indices
# Extract boundary curves with remapped point coordinates
paths, curve_points = tf.boundary_curves(mesh)
# paths: indices into curve_points (0 to N)
# curve_points: only the vertices on boundaries
# Iterate over boundary loops
for path_ids in paths:
loop_points = curve_points[path_ids]
# Process loop (e.g., plot, measure, etc.)
Closed/Open Mesh Detection
Check if a mesh is closed (watertight) or open (has boundary edges):
mesh = tf.Mesh(faces, points)
# Check if mesh is closed (no boundary edges)
if tf.is_closed(mesh):
print("Mesh is watertight")
else:
print("Mesh has holes or open boundaries")
# is_open is the inverse of is_closed
if tf.is_open(mesh):
print("Mesh has boundary edges")
A closed mesh has every edge shared by exactly two faces, making it watertight and suitable for volume calculations.
tf.boundary_edges(mesh) to get the actual boundary edges when is_open returns True.Non-Manifold Edge Detection
Identify edges that are shared by more than two faces:
mesh = tf.Mesh(faces, points)
# Find non-manifold edges
non_manifold_edges = tf.non_manifold_edges(mesh)
# Process the problematic edges
for edge in non_manifold_edges:
vertex_a = edge[0]
vertex_b = edge[1]
# Handle non-manifold edge
Manifold Detection
Check if a mesh is manifold (no edges shared by more than two faces):
mesh = tf.Mesh(faces, points)
# Check if mesh is manifold
if tf.is_manifold(mesh):
print("Mesh is manifold")
else:
print("Mesh has non-manifold edges")
# is_non_manifold is the inverse of is_manifold
if tf.is_non_manifold(mesh):
print("Mesh has edges shared by 3+ faces")
Non-manifold edges typically occur at T-junctions where three or more faces meet at a single edge.
tf.non_manifold_edges(mesh) to get the actual non-manifold edges when is_non_manifold returns True.Face Orientation
Make all faces in each connected region have consistent winding order:
mesh = tf.Mesh(faces, points)
# Orient faces consistently
new_faces = tf.orient_faces_consistently(mesh)
# Also works with tuple input
new_faces = tf.orient_faces_consistently((faces, points))
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.
manifold_edge_link, it will be reused. Otherwise, topology is computed automatically.Connected Components
Find and label connected components in meshes or graphs:
mesh = tf.Mesh(faces, points)
# Use face_link as connectivity to find connected face components
fl = mesh.face_link
num_components, labels = tf.label_connected_components(fl)
print(f"Mesh has {num_components} connected components")
You can also use different connectivity rules:
# Use vertex_link for vertex-based connectivity
vl = mesh.vertex_link
num_components, vertex_labels = tf.label_connected_components(vl)
Fixed-width connectivity:
# Each row contains neighbor indices, use -1 for missing neighbors
connectivity = np.array([
[1, -1, -1], # Node 0 connects to node 1
[0, 2, -1], # Node 1 connects to nodes 0 and 2
[1, -1, -1], # Node 2 connects to node 1
[4, -1, -1], # Node 3 connects to node 4 (separate component)
[3, -1, -1], # Node 4 connects to node 3
], dtype=np.int32)
num_components, labels = tf.label_connected_components(connectivity)
# num_components: 2
# labels: [0, 0, 0, 1, 1]
Variable-length connectivity:
# Using OffsetBlockedArray for variable neighbor counts
offsets = np.array([0, 2, 3, 4], dtype=np.int32)
data = np.array([1, 2, 0, 0], dtype=np.int32)
connectivity = tf.OffsetBlockedArray(offsets, data)
num_components, labels = tf.label_connected_components(connectivity)
With performance hint:
# For graphs with many components (> 500), provide hint for sequential algorithm
num_components, labels = tf.label_connected_components(
connectivity, expected_number_of_components=1000
)
tf.split_into_components().Volumetric Domains
A non-manifold polygon mesh bounds multiple 3D regions ("domains"). tf.domain_labels returns one label per face per side, partitioning space into volumetric components.
mesh = tf.Mesh(faces, points)
labels, n_domains, outer_shell_label = tf.domain_labels(
mesh,
ignore_open_fragments=True,
exclude_outer_shell=True,
)
# labels : ndarray of shape (n_faces, 2), dtype matches faces.dtype
# labels[f, 0] : domain containing face f with REVERSED winding
# (the side f's stored normal points INTO)
# labels[f, 1] : domain containing face f with FORWARD winding
# (the side f's stored normal points AWAY FROM)
# n_domains : number of distinct bounded domains
# outer_shell_label : sentinel label (== n_domains) under exclude_outer_shell
Both flags are keyword-only:
| Flag (kwarg) | Effect |
|---|---|
| (default) | Every face-side bounds a real domain id in [0, n_domains). |
ignore_open_fragments=True | Drop face-sides bounding open fragments (faces in MEL components carrying boundary edges) by parking them at the sentinel label n_domains. |
exclude_outer_shell=True | Fold the unbounded universe domain into the same sentinel, so only bounded interior domains receive ids. |
When the outer shell has been excluded, outer_shell_label equals n_domains (the sentinel); otherwise no face-side carries that label.
Accepts tf.Mesh or a (faces, points) tuple (triangles or dynamic n-gons via OffsetBlockedArray). 3D only.
(labels, n_domains, outer_shell_label) tuple straight to tf.split_into_domains() (see Reindex module) to extract a watertight, outward-oriented submesh per domain.Sidedness Relations
tf.sidedness_relations reports, for each manifold-edge-connected component of an arrangement, which other operands it touches at a cut and the sidedness against each operand's oriented surface. This is the primitive you reach for when you want to pick "the half of mesh_a on the +side of mesh_b" — without going through a full boolean operation, and without needing closed inputs.
(faces, points), tag_labels, _ = tf.mesh_arrangements([mesh_a, mesh_b])
arr = tf.Mesh(faces, points)
(tags, sides), (n_components, labels) = tf.sidedness_relations(arr, tag_labels)
# tags, sides : two OffsetBlockedArrays sharing the same offsets,
# keyed per component:
# tags[c] → operand tag ids the component touches
# sides[c] → sidedness values against each (int)
# n_components : total connected components in the arrangement
# labels : per-face component id (length = number of arrangement faces)
The sidedness integer maps to the C++ tf::sidedness enum:
| Value | Meaning |
|---|---|
0 | on_positive_side — component lies on the operand's +normal side at the cut |
1 | on_negative_side — component lies on the operand's -normal side at the cut |
2 | on_boundary — coplanar contact (degenerate, rare for clean arrangements) |
3 | none — selection-only sentinel; not produced by the predicate |
Each component has one entry per other operand it shares an intersection edge with. Components that don't touch any other operand at a cut (interior or fully disjoint components) get empty blocks (tags[c].size == 0).
Picking a signed half
mesh_a_components = np.unique(labels[tag_labels == 0])
mesh_b_tag = 1
on_positive_side = 0
def keeps(cid):
for t, s in zip(tags[cid], sides[cid]):
if int(t) == mesh_b_tag and int(s) == on_positive_side:
return True
return False
keep = [cid for cid in mesh_a_components if keeps(cid)]
# Lift to per-face mask, then extract the sub-mesh.
face_mask = np.isin(labels, keep)
kept_faces, kept_points = tf.reindex_by_mask((faces, points), face_mask)
Three concise steps: classify, filter components, lift to faces, extract. No DSL — just predicate + numpy indexing.
Works for open and closed cutters
The sidedness is computed via exact wedge predicates at non-manifold edges, so it works regardless of whether the operands are watertight. Closed × open (e.g. fault blocks split by a topographic surface), open × open (two intersecting surfaces), and closed × closed (classic boolean topology) all produce the same shape of result.
Performance
sidedness_relations reuses any face_membership and manifold_edge_link already built on the Mesh and caches new ones on it — subsequent calls (a second sidedness query, a boolean, a topology query) skip the rebuild. Pass a tf.Mesh rather than a raw (faces, points) tuple to keep the cache across operations.
Path Finding
Edge to Path Connection
Connect edges into paths between branch points:
edges = np.array([[0, 1], [1, 2], [2, 3]], dtype=np.int32)
paths = tf.connect_edges_to_paths(edges)
for path in paths:
print(path) # Sequence of vertices forming a path
Edges are organized into maximal paths between endpoints and junctions (vertices with degree ≠ 2). Works on any edge collection—useful for organizing boundary segments, cut curves, and graph decomposition.
Constrained Delaunay Triangulation
tf.cdt triangulates a 2D point set and recovers user-supplied constraint edges as edges of the output. Constraint edges are allowed to intersect each other — vertex–vertex, vertex–edge, and edge–edge crossings are resolved by an arrangement pre-pass that splits crossings into sub-edges and adds the intersection points to the output.
import numpy as np
import trueform as tf
# 256-vertex regular polygon outline + interior Steiner points
n_boundary = 256
theta = np.linspace(0, 2 * np.pi, n_boundary, endpoint=False)
boundary = np.column_stack([np.cos(theta), np.sin(theta)]).astype(np.float32)
steiner = np.random.default_rng(0).uniform(-1, 1, (1000, 2)).astype(np.float32)
points = np.vstack([boundary, steiner])
# Closing edges of the polygon outline
edges = np.column_stack(
[np.arange(n_boundary), (np.arange(n_boundary) + 1) % n_boundary]
).astype(np.int32)
faces, out_points = tf.cdt(points, edges)
# faces: (K, 3) int32 — triangles inside the outline
# out_points: (M, 2) float32 — vertex coordinates
Without edges, the result is the unconstrained convex-hull Delaunay triangulation of the input. With edges, only triangles inside the constrained outline are returned (parity flips at each boundary-constrained edge during a flood-fill from the convex hull).
Boundary vs. non-boundary constraints
By default every input edge is treated as a region boundary. To preserve a constraint as an edge of the output without having it split the interior in two — e.g., a feature line, an internal diagonal — pass an edge_mask:
# Rectangle (4 outline edges) + 2 diagonals through the centre
edges = np.array([
[0, 1], [1, 2], [2, 3], [3, 0], # rectangle outline
[0, 2], [1, 3], # diagonals (cross at the centre)
], dtype=np.int32)
edge_mask = np.array([True, True, True, True, False, False]) # diagonals not boundary
faces, out_points = tf.cdt(points, edges, edge_mask=edge_mask)
# All four quarter-triangles kept — the rectangle is solid, the diagonals
# remain as preserved edges but don't divide the interior.
Tracking input points through the triangulation
Pass return_index_map=True to additionally get the input-point-to-output-point map as (f, kept_ids) — same (f, kept_ids) shape as tf.cleaned and the reindex helpers, see Understanding Index Maps. For tf.cdt the map carries one extra subtlety:
f[i] == f.sizemarks input points that fell on triangles dropped by the parity filter (i.e. landed outside the constrained outline).kept_ids[k] == f.sizemarks output slots that are synthetic intersection vertices created during constraint arrangement (no original input maps onto them).
(faces, out_points), (f, kept_ids) = tf.cdt(
points, edges, return_index_map=True
)
sentinel = f.size
preserved = f != sentinel # input made it through
synthetic = kept_ids == sentinel # output slot is a new intersection vertex
The exact-arithmetic integer type used internally is auto-resolved from the input dtype: int32 for float32 input, int64 for float64 input. Edge indices are int32.