Topology

The Topology module provides tools for analyzing connectivity and structure in meshes — adjacency structures, boundary detection, manifold analysis, connected components, and neighborhood queries.

Every function also has an async variant via tf.async for off-main-thread execution.

Adjacency Structures

Meshes lazily compute and cache adjacency structures on first access. These structures power the topology queries below.

import * as tf from "@polydera/trueform";

const mesh = tf.mesh(faces, points);

// Face membership — vertex → faces containing it
const fm = mesh.faceMembership;   // OffsetBlockedBuffer

// Manifold edge link — face edge → adjacent face
const mel = mesh.manifoldEdgeLink; // NDArrayInt32 [F, 3]

// Face link — face → adjacent faces (sharing an edge)
const fl = mesh.faceLink;          // OffsetBlockedBuffer

// Vertex link — vertex → connected vertices
const vl = mesh.vertexLink;        // OffsetBlockedBuffer

To precompute off the main thread:

const fm = await tf.async.computeFaceMembership(mesh);
const mel = await tf.async.computeManifoldEdgeLink(mesh);
const fl = await tf.async.computeFaceLink(mesh);
const vl = await tf.async.computeVertexLink(mesh);

Manifold Edge Link Sentinel Values

Mesh Analysis

Closed / Open

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

tf.isClosed(mesh);  // true if every edge shared by exactly 2 faces
tf.isOpen(mesh);     // true if at least one boundary edge

A closed mesh is watertight — suitable for volume calculations and boolean operations.

Manifold / Non-Manifold

A mesh is manifold when the faces around every vertex are one fan, which also says every edge carries at most two of them.

tf.isManifold(mesh);     // true if every vertex's faces are one fan
tf.isNonManifold(mesh);  // true if any edge has 3+ faces, or any vertex splits into fans

Non-manifold edges typically occur at T-junctions where three or more faces meet at a single edge; non-manifold vertices where two fans touch at a single point. Face winding does not enter the verdict.

Euler Characteristic

const chi = tf.eulerCharacteristic(mesh);  // V - E + F

Boundary Detection

Boundary Edges

Extract boundary edges — edges belonging to only one face.

const edges = tf.boundaryEdges(mesh);  // NDArrayInt32 [N, 2]

Boundary Paths

Organize boundary edges into connected loops of vertex indices.

const paths = tf.boundaryPaths(mesh);  // OffsetBlockedBuffer

Boundary Rims

Read the same boundary as rims — per rim its vertex walk, the face carrying each of its edges, and whether it closes.

const { vertices, faces, closed } = tf.boundaryRims(mesh);
// vertices : OffsetBlockedBuffer — block i is rim i walked
// faces    : OffsetBlockedBuffer — block i is the face across each of its edges
// closed   : NDArrayBool [R]     — whether rim i's last edge runs back to its first vertex

for (let i = 0; i < vertices.length; i++) {
  const rim = vertices.get(i);        // NDArrayInt32 — vertex ids in walk order
  const carriers = faces.get(i);      // NDArrayInt32 — one face per rim edge
  const isClosed = closed.data[i] !== 0;
}

Rim edge k runs from vertex k to vertex k + 1 and is carried by face k alone, so a closed rim of n vertices has n edges — the last running back to vertex 0 — and an open one has n - 1.

A rim ends where the boundary stops passing straight through, so a pinched boundary comes back as its pieces rather than as one figure eight, and a rim with two ends is reached before the closed ones. A consistently wound mesh gives rims that run the way its faces wind their boundary.

Non-Manifold Edges

Find edges shared by more than two faces.

const edges = tf.nonManifoldEdges(mesh);  // NDArrayInt32 [N, 2]

Non-Manifold Vertices

Find the vertices whose faces are not one fan — an edge at the vertex carries 3+ faces, or its faces fall into several pieces meeting at the vertex alone.

const vertices = tf.nonManifoldVertices(mesh);  // NDArrayInt32 [N], ascending

The walk is on the mesh's faceMembership, so no half-edge structure is built. Face winding does not enter the verdict, and a vertex no face names is not reported.

Neighborhoods

k-Ring

Compute k-ring neighborhoods for all vertices using breadth-first traversal. The 1-ring is the immediate neighbors, the 2-ring includes neighbors of neighbors, etc.

// 2-ring neighborhoods for all vertices
const rings = tf.kRings(mesh, 2);  // OffsetBlockedBuffer

// Include the seed vertex in each neighborhood
const ringsInc = tf.kRings(mesh, 2, true);

Radius-Based

Find all vertices reachable via mesh edges within a Euclidean distance.

// All vertices within radius 0.5
const neighs = tf.neighborhoods(mesh, 0.5);  // OffsetBlockedBuffer

// Include seed vertex
const neighsInc = tf.neighborhoods(mesh, 0.5, true);

Connected Components

From Mesh

connectedComponents computes connected components of a mesh using a specified connectivity type.

const { labels, nComponents } = tf.connectedComponents(mesh, "edge");
console.log(`${nComponents} components`);
// labels: NDArrayInt32 [F] — component ID per face

From Connectivity

labelConnectedComponents works on raw connectivity data — either an OffsetBlockedBuffer (variable-width) or an NDArrayInt32 (fixed-width, -1 for missing neighbors).

// Variable-width connectivity (e.g., faceLink)
const { labels, nComponents } = tf.labelConnectedComponents(mesh.faceLink);

// Fixed-width connectivity (e.g., manifoldEdgeLink)
const result = tf.labelConnectedComponents(mesh.manifoldEdgeLink);

Face Orientation

Make all faces in each connected region have consistent winding order.

const oriented = tf.consistentlyOriented(mesh);

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 the winding order of all faces (flips normals):

const flipped = tf.reverseWinding(mesh);

Vertex Splitting

Give every fan at a vertex a vertex of its own. The fan holding the vertex's smallest face keeps its id; every other fan takes a fresh id carrying the same coordinates, and that fan's corners are rewired onto it.

const { mesh: split, pointMap } = tf.splitNonManifoldVertices(mesh);
// split    : Mesh — same dtype as the input
// pointMap : NDArrayInt32 [P] — for each output point the input point it
//            copies, an original itself

tf.isManifold(split);  // true when no edge of the input carried 3+ faces

Faces keep their ids, their arity and their winding, and the points are the input's followed by the minted copies.

An edge 3+ faces carry is crossed by no fan, and separating the fans it holds apart would tear that edge into boundary copies. That is another verb's work: a vertex any of whose edges carries 3+ faces is left exactly as it was, and tf.nonManifoldVertices still names it. This one separates only the fans that come apart without cutting an edge.

Volumetric Domains

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

const dl = tf.domainLabels(mesh, {
  ignoreOpenFragments: true,
  excludeOuterShell: true,
});
// dl.labels           : NDArrayInt32, shape (nFaces, 2)
//   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)
// dl.nDomains         : number  (count of bounded domains)
// dl.outerShellLabel  : number  (== nDomains when excludeOuterShell is set)

Options (all bool kwargs):

When the outer shell has been excluded, outerShellLabel equals nDomains (the sentinel); otherwise no face-side carries this label.

Pass the returned DomainLabelsResult directly to tf.splitIntoDomains (see Reindex module) to extract a watertight, outward-oriented submesh per domain.

Async: await tf.async.domainLabels(mesh, opts).

Path Finding

Connect edges into continuous vertex paths between branch points and endpoints.

const paths = tf.connectEdgesToPaths(edges);  // OffsetBlockedBuffer

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 * as tf from "trueform";

// 256-vertex regular polygon outline + interior Steiner points
const nBoundary = 256;
const boundary = new Float32Array(nBoundary * 2);
for (let i = 0; i < nBoundary; i++) {
  const t = (2 * Math.PI * i) / nBoundary;
  boundary[2 * i] = Math.cos(t);
  boundary[2 * i + 1] = Math.sin(t);
}
const points = tf.ndarray(boundary, [nBoundary, 2]);

// Closing edges of the polygon outline
const eFlat = new Int32Array(nBoundary * 2);
for (let i = 0; i < nBoundary; i++) {
  eFlat[2 * i] = i;
  eFlat[2 * i + 1] = (i + 1) % nBoundary;
}
const edges = tf.ndarray(eFlat, [nBoundary, 2]);

const { faces, points: outPoints } = tf.cdt(points, { edges });
// faces:    NDArrayInt32 [K, 3] — triangles inside the outline
// outPoints: NDArrayFloat32 [M, 2] — 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 constraint 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 edgeMask:

// Rectangle (4 outline edges) + 2 diagonals through the centre
const edges = tf.ndarray(new Int32Array([
  0, 1, 1, 2, 2, 3, 3, 0,    // rectangle outline
  0, 2, 1, 3,                 // diagonals (cross at the centre)
]), [6, 2]);

// All four outline edges are region boundaries; both diagonals are not.
const edgeMask = tf.ndarray(new Int8Array([1, 1, 1, 1, 0, 0]), [6]);

const { faces, points: outPoints } = tf.cdt(points, { edges, edgeMask });
// All four quarter-triangles kept — the rectangle is solid, the
// diagonals remain as preserved edges but don't divide the interior.

Demanding the constraints verbatim

By default crossings are resolved by splitting: an output point is created where two constraints meet. Pass splitConstraints: false to demand the constraints exactly as given — if any two of them cross, the result is empty. That emptiness is the answer to "do these constraints cross", not an error.

// Rectangle outline + 2 diagonals crossing at the centre
const split = tf.cdt(points, { edges });                            // crossing split, centre point added
const verbatim = tf.cdt(points, { edges, splitConstraints: false }); // verbatim.faces.shape[0] === 0

Without crossings the two agree. The option is ignored when no edges are given.

Tracking input points through the triangulation

Pass returnIndexMap: true to additionally get the input-point-to-output-point map as an IndexMap. For tf.cdt the map carries one extra subtlety:

• f[i] === f.length (the sentinel) marks input points that fell on triangles dropped by the parity filter (i.e. landed outside the constrained outline).
• keptIds[k] === f.length marks output slots that are synthetic intersection vertices created during constraint arrangement (no original input maps onto them).

const result = tf.cdt(points, { edges, returnIndexMap: true });
const { faces, points: outPoints, indexMap } = result;
// indexMap.f       — NDArrayInt32, size = input count
// indexMap.keptIds — NDArrayInt32, size = output count

Internally the binding always works in float32 for points and int32 for face/edge indices. The exact-arithmetic integer width is auto-resolved on the C++ side from the input coordinate type.

Async

All functions are available as tf.async.isClosed(), tf.async.boundaryEdges(), tf.async.connectedComponents(), tf.async.cdt(), etc. Signatures are identical — they return Promise<T> instead of T.

const closed = await tf.async.isClosed(mesh);
const edges = await tf.async.boundaryEdges(mesh);
const rims = await tf.async.boundaryRims(mesh);
const { labels, nComponents } = await tf.async.connectedComponents(mesh, "edge");
const { mesh: split } = await tf.async.splitNonManifoldVertices(mesh);
const { faces, points: outPoints } = await tf.async.cdt(points, { edges });