Modules | C++

Geometry

Geometric analysis, surface properties, and point cloud alignment.

The Geometry module provides tools for computing geometric properties of meshes, including normals, curvatures, triangulation, and point cloud alignment.

Include the module with:

#include <trueform/geometry.hpp>

Mesh Generation

Generate common primitive meshes for testing, or as building blocks.

Sphere

Create a UV sphere mesh:

make_sphere_mesh.cpp

// Index defaults to int, RealType deduced from radius
auto sphere = tf::make_sphere_mesh(1.0f, 20, 20);  // radius, stacks, segments
// Returns tf::polygons_buffer<int, float, 3, 3>

// Specify index type for interop with other libraries
auto sphere = tf::make_sphere_mesh<uint32_t>(1.0f, 20, 20);

Cylinder

Create a cylinder mesh centered at origin along the z-axis:

make_cylinder_mesh.cpp

// Index defaults to int, RealType deduced from radius/height
auto cylinder = tf::make_cylinder_mesh(1.0f, 2.0f, 20);  // radius, height, segments
// Returns tf::polygons_buffer<int, float, 3, 3>

// Specify index type for interop with other libraries
auto cylinder = tf::make_cylinder_mesh<uint32_t>(1.0f, 2.0f, 20);

Box

Create an axis-aligned box mesh centered at origin:

make_box_mesh.cpp

// Index defaults to int, RealType deduced from dimensions
auto box = tf::make_box_mesh(2.0f, 1.0f, 3.0f);  // width, height, depth
// Returns tf::polygons_buffer<int, float, 3, 3> (8 vertices, 12 triangles)

// Subdivided box for deformation/simulation (vertices shared at edges/corners)
auto box = tf::make_box_mesh(2.0f, 1.0f, 3.0f, 4, 2, 6);  // + width_ticks, height_ticks, depth_ticks

// Specify index type for interop with other libraries
auto box = tf::make_box_mesh<uint32_t>(2.0f, 1.0f, 3.0f);
auto box = tf::make_box_mesh<uint32_t>(2.0f, 1.0f, 3.0f, 4, 2, 6);

Plane

Create a flat rectangular plane mesh in the XY plane, centered at origin:

make_plane_mesh.cpp

// Index defaults to int, RealType deduced from dimensions
auto plane = tf::make_plane_mesh(10.0f, 5.0f);  // width, height
// Returns tf::polygons_buffer<int, float, 3, 3> (4 vertices, 2 triangles)

// Subdivided plane for deformation/simulation
auto plane = tf::make_plane_mesh(10.0f, 5.0f, 20, 10);  // + width_ticks, height_ticks

// Specify index type for interop with other libraries
auto plane = tf::make_plane_mesh<uint32_t>(10.0f, 5.0f);
auto plane = tf::make_plane_mesh<uint32_t>(10.0f, 5.0f, 20, 10);

All generated meshes have consistent outward-facing normals (positive orientation).

Normal Computation

Polygon Normals

Compute face normals for polygon meshes:

compute_normals.cpp

// Compute polygon normals for all polygons
auto polygon_normals = tf::compute_normals(polygons);

// Result is a unit_vectors_buffer with one normal per face
for (auto normal : polygon_normals.unit_vectors()) {
    // Each normal is a tf::unit_vector<T, 3>
    auto [nx, ny, nz] = normal;
}

// Access underlying flat memory for export
float* normal_data = polygon_normals.data_buffer().data();

Point Normals

Compute vertex normals by averaging adjacent face normals. This requires the polygons to have both face_membership and normals tagged:

compute_point_normals.cpp

// First compute polygon normals
auto polygon_normals = tf::compute_normals(polygons);

// Build face membership for adjacency queries
auto fm = tf::make_face_membership(polygons);

// Tag the polygons with topology and normals
auto tagged_polygons = polygons
    | tf::tag(fm)
    | tf::tag_normals(polygon_normals.unit_vectors());

// Compute point normals (averages adjacent face normals)
auto point_normals = tf::compute_point_normals(tagged_polygons);

// Result is a unit_vectors_buffer with one normal per vertex
for (auto normal : point_normals.unit_vectors()) {
    auto [nx, ny, nz] = normal;
}

Point normals are computed by summing the normals of all faces adjacent to a vertex and normalizing the result.

Curvature Analysis

Compute surface curvature properties at each vertex by fitting a quadric to the local k-ring neighborhood.

Principal Curvatures

Compute the two principal curvatures (k0, k1) at each vertex:

make_principal_curvatures.cpp

auto [k0, k1] = tf::make_principal_curvatures(polygons);

for (auto [k0_i, k1_i] : tf::zip(k0, k1)) {
    float gaussian = k0_i * k1_i;          // Gaussian curvature
    float mean = (k0_i + k1_i) / 2;        // Mean curvature
}

To also compute principal directions:

make_principal_directions.cpp

auto [k0, k1, d0, d1] = tf::make_principal_directions(polygons);

for (auto [k0_i, k1_i, d0_i, d1_i] : tf::zip(k0, k1, d0, d1)) {
    // d0_i is the direction of maximum curvature k0_i
    // d1_i is the direction of minimum curvature k1_i
}

The k-ring size defaults to 2. For smoother estimates, increase k:

auto [k0, k1] = tf::make_principal_curvatures(polygons, /*k=*/3);
auto [k0, k1, d0, d1] = tf::make_principal_directions(polygons, /*k=*/3);

With pre-allocated buffers:

For repeated computations or custom memory management, use compute_principal_curvatures:

compute_principal_curvatures.cpp

tf::buffer<float> k0, k1;
k0.allocate(polygons.points().size());
k1.allocate(polygons.points().size());

tf::compute_principal_curvatures(polygons, k0, k1);

// With directions
tf::unit_vectors_buffer<float, 3> d0, d1;
d0.allocate(polygons.points().size());
d1.allocate(polygons.points().size());

tf::compute_principal_curvatures(polygons, k0, k1, d0, d1);

The functions use the policy system. You can tag precomputed structures:

auto tagged = tf::make_polygons(faces, points | tf::tag_normals(normals))
    | tf::tag(vertex_link);

auto [k0, k1] = tf::make_principal_curvatures(tagged);

Shape Index

Shape index maps principal curvatures to -1, 1 characterizing local surface type:

Index Range	Surface Type
[-1, -5/8)	Concave ellipsoid (cup)
[-5/8, -3/8)	Concave cylinder (trough)
[-3/8, 3/8)	Hyperboloid (saddle)
[3/8, 5/8)	Convex cylinder (ridge)
5/8, 1	Convex ellipsoid (cap)

make_shape_index.cpp

auto shape_index = tf::make_shape_index(polygons);

The k-ring size defaults to 2. For smoother estimates, increase k:

auto shape_index = tf::make_shape_index(polygons, /*k=*/3);

With pre-allocated buffer:

compute_shape_index.cpp

tf::buffer<float> shape_index;
shape_index.allocate(polygons.points().size());

tf::compute_shape_index(polygons, shape_index);

The functions use the policy system. You can tag precomputed structures:

auto tagged = tf::make_polygons(faces, points | tf::tag_normals(normals))
    | tf::tag(vertex_link);

auto shape_index = tf::make_shape_index(tagged);

Orientation

Ensure Positive Orientation

For closed meshes, ensure faces are oriented so that normals point outward (positive signed volume):

ensure_positive_orientation.cpp

// First orients faces consistently, then flips all if signed volume is negative
tf::ensure_positive_orientation(polygons);

// Skip consistency step if mesh is already consistently oriented
tf::ensure_positive_orientation(polygons, true);

This function:

Calls tf::orient_faces_consistently (unless is_consistent = true)
Computes the signed volume of the mesh
Reverses all face windings if the signed volume is negative

Signed volume is positive when face normals point outward from a closed mesh. This function ensures the mesh has the standard "outward-facing normals" convention.

Triangulation

Convert polygon meshes to triangle meshes using ear-cutting triangulation.

Triangle Indices

Get triangle indices from polygons without copying point data:

triangulated_faces.cpp

// Returns tf::blocked_buffer<Index, 3>
auto triangle_faces = tf::triangulated_faces(polygons);

for (auto triangle : triangle_faces) {
    auto [v0, v1, v2] = triangle;
}

Single Polygon

Triangulate a single polygon:

triangulated_single.cpp

// From single polygon - returns tf::polygons_buffer<int, RealT, Dims, 3>
auto triangle_mesh = tf::triangulated(polygon);

for (auto triangle : triangle_mesh.polygons()) {
    auto [pt0, pt1, pt2] = triangle;
}

Polygon Mesh

Triangulate a polygon mesh (quads, n-gons, dynamic):

triangulated.cpp

// From polygon range - returns tf::polygons_buffer<Index, RealT, Dims, 3>
auto triangle_mesh = tf::triangulated(polygons);

for (auto triangle : triangle_mesh.polygons()) {
    auto [pt0, pt1, pt2] = triangle;
}

See Polygons Buffer for details on accessing the underlying data.

Uses the ear-cutting algorithm. For polygons with more than 80 vertices, z-order curve indexing is used. For N-dimensional polygons, faces are projected to 2D before triangulation.

When a curve lies on a plane (e.g., isocontours extracted from a mesh surface), it can be triangulated into a filled polygon. Simply reinterpret the curves as polygons using tf::make_polygon or tf::make_polygons and use the same algorithm:

Triangulate a single curve:

triangulated_curve.cpp

// curve is a range of 3D points forming a closed planar loop
auto triangle_mesh = tf::triangulated(tf::make_polygon(curve));

Triangulate multiple curves:

triangulated_curves.cpp

// curves is a tf::curves (paths + points)
auto triangle_mesh = tf::triangulated(
    tf::make_polygons(curves.paths(), curves.points()));

Point Cloud Alignment

Compute rigid transformations to align point sets. Choose a method based on your scenario:

Scenario	Function	Notes
Known correspondences	`fit_rigid_alignment`	Optimal closed-form solution
Known correspondences + scale	`fit_similarity_alignment`	Includes uniform scale
No correspondences, need initialization	`fit_obb_alignment`	Coarse alignment
No correspondences, need refinement	`fit_icp_alignment`	Full ICP loop
Custom ICP with special logic	`fit_knn_alignment`	Single ICP step

All alignment functions support lazy transformation tagging. Instead of copying transformed points, tag an initial transformation onto the source and the function applies it on-the-fly:

// Tag initial transform - no data copy
auto T_delta = tf::fit_icp_alignment(X.points() | tf::tag(T_init), Y_with_tree, config);

// Returns DELTA transformation (source_world -> target_world)
// Compose with initial transform for total:
auto T_total = tf::transformed(T_init, T_delta);

→ Point Cloud Alignment Example — A complete walkthrough from OBB initialization through ICP convergence.

With Correspondences

These methods require paired points where X[i] corresponds to Y[i].

Rigid Alignment (fit_rigid_alignment)

Use the Kabsch/Procrustes algorithm for optimal rotation + translation. Returns a DELTA transformation mapping source world coordinates to target world coordinates.

Point-to-Point — Minimizes Euclidean distance:

fit_rigid_alignment.cpp

// X and Y must have the same number of points, X[i] corresponds to Y[i]
// Returns delta: source_world -> target_world
auto T_delta = tf::fit_rigid_alignment(X.points(), Y.points());

Point-to-Plane — When target has normals, minimizes distance along normal direction:

fit_rigid_alignment_p2l.cpp

auto Y_with_normals = Y.points() | tf::tag_normals(normals.unit_vectors());
auto T = tf::fit_rigid_alignment(X.points(), Y_with_normals);

Point-to-Plane with Normal Weighting — When both have normals, uses normal agreement for weighting:

fit_rigid_alignment_weighted.cpp

auto X_with_normals = X.points() | tf::tag_normals(source_normals.unit_vectors());
auto Y_with_normals = Y.points() | tf::tag_normals(target_normals.unit_vectors());
auto T = tf::fit_rigid_alignment(X_with_normals, Y_with_normals);

Similarity Alignment (fit_similarity_alignment)

When scales may differ, use similarity alignment (rotation + translation + uniform scale):

fit_similarity_alignment.cpp

auto T = tf::fit_similarity_alignment(X.points(), Y.points());

// Extract scale factor
float scale = std::sqrt(T(0,0)*T(0,0) + T(1,0)*T(1,0) + T(2,0)*T(2,0));

Without Correspondences

These methods work when point correspondences are unknown or point counts differ.

Coarse Alignment (fit_obb_alignment)

Align using oriented bounding boxes (OBBs) for initialization. Returns a DELTA transformation mapping source world coordinates to target world coordinates.

fit_obb_alignment.cpp

// No correspondence required - points can have different counts
// Returns delta: source_world -> target_world
auto T_delta = tf::fit_obb_alignment(X.points(), Y.points());

OBB alignment is inherently ambiguous up to 180° rotations about each axis. Without disambiguation, the function returns one valid alignment out of 4 possible.

To resolve the ambiguity, attach a tree to the target:

fit_obb_alignment_disambiguated.cpp

// Build tree on target for disambiguation
tf::aabb_tree<int, float, 3> tree(Y.points(), tf::config_tree(4, 4));
auto Y_with_tree = Y.points() | tf::tag(tree);

// Tests all 4 orientations, returns the one with lowest chamfer distance
auto T = tf::fit_obb_alignment(X.points(), Y_with_tree);

Iterative Refinement (fit_icp_alignment)

Refine any initial alignment using ICP. This is the main entry point for iterative closest point registration.

// Configure ICP
tf::icp_config config;
config.max_iterations = 50;
config.n_samples = 1000;            // subsample for speed
config.k = 1;                       // k=1 is classic ICP
config.min_relative_improvement = 1e-6f;

// Build tree on target
tf::aabb_tree<int, float, 3> tree(Y.points(), tf::config_tree(4, 4));

Point-to-Point — Classic ICP using nearest neighbor distance:

fit_icp_alignment.cpp

auto target = Y.points() | tf::tag(tree);
auto T = tf::fit_icp_alignment(X.points() | tf::tag(T_init), target, config);

Point-to-Plane — When target has normals, converges 2-3x faster:

fit_icp_alignment_p2l.cpp

auto target = Y.points()
    | tf::tag(tree)
    | tf::tag_normals(normals.unit_vectors());

auto T = tf::fit_icp_alignment(X.points() | tf::tag(T_init), target, config);

Point-to-Plane with Normal Weighting — When both have normals, uses normal agreement for weighting:

fit_icp_alignment_weighted.cpp

auto X_with_normals = X.points() | tf::tag(T_init)
    | tf::tag_normals(source_normals.unit_vectors());

auto Y_with_normals = Y.points() | tf::tag(tree)
    | tf::tag_normals(target_normals.unit_vectors());

auto T = tf::fit_icp_alignment(X_with_normals, Y_with_normals, config);

icp_config parameters:

Parameter	Default	Description
`max_iterations`	100	Maximum iterations
`min_relative_improvement`	1e-6	Convergence threshold
`ema_alpha`	0.3	EMA smoothing factor
`n_samples`	1000	Subsample size (0 = all)
`k`	1	Nearest neighbors
`sigma`	-1	Gaussian width (-1 = adaptive)
`outlier_proportion`	0	Outlier rejection ratio

Single ICP Step (fit_knn_alignment)

For custom ICP pipelines (multi-start, early termination, special convergence logic), use fit_knn_alignment. Returns a DELTA transformation mapping source world coordinates to target world coordinates. Supports the same variants as fit_icp_alignment.

Point-to-Point:

fit_knn_alignment.cpp

// Returns delta: source_world -> target_world
auto T_iter = tf::fit_knn_alignment(X.points() | tf::tag(T_accum), Y_with_tree, {.k = 1});
T_accum = tf::transformed(T_accum, T_iter);  // Compose: total = old_total @ delta

Point-to-Plane:

fit_knn_alignment_p2l.cpp

auto Y_with_normals = Y.points() | tf::tag(tree) | tf::tag_normals(normals.unit_vectors());
auto T_iter = tf::fit_knn_alignment(X.points() | tf::tag(T_accum), Y_with_normals, {.k = 1});

Point-to-Plane with Normal Weighting:

fit_knn_alignment_weighted.cpp

auto X_with_normals = X.points() | tf::tag(T_accum) | tf::tag_normals(source_normals.unit_vectors());
auto Y_with_normals = Y.points() | tf::tag(tree) | tf::tag_normals(target_normals.unit_vectors());
auto T_iter = tf::fit_knn_alignment(X_with_normals, Y_with_normals, {.k = 1});

knn_alignment_config parameters:

Parameter	Default	Description
`k`	1	Nearest neighbors (k=1 is classic ICP)
`sigma`	-1	Gaussian width (-1 = adaptive to k-th neighbor distance)
`outlier_proportion`	0	Outlier rejection ratio

For soft correspondences, use k > 1 with Gaussian weighting:

auto T_soft = tf::fit_knn_alignment(X.points(), Y_with_tree, {.k = 5, .sigma = -1.f});

Error Metrics

Chamfer Error

Compute one-way chamfer error (mean nearest-neighbor distance) between point sets:

chamfer_error.cpp

// Target must have tree policy for efficient search
tf::aabb_tree<int, float, 3> tree(Y.points(), tf::config_tree(4, 4));
auto Y_with_tree = Y.points() | tf::tag(tree);

// One-way error: mean distance from X to nearest point in Y
float error_xy = tf::chamfer_error(X.points(), Y_with_tree);

// For symmetric chamfer distance, compute both directions
tf::aabb_tree<int, float, 3> tree_x(X.points(), tf::config_tree(4, 4));
auto X_with_tree = X.points() | tf::tag(tree_x);
float error_yx = tf::chamfer_error(Y.points(), X_with_tree);
float symmetric = (error_xy + error_yx) / 2.0f;

Chamfer error is asymmetric. For alignment quality assessment, computing both directions gives a more complete picture.

Both source and target accept transformation tagging. Use this to evaluate alignment quality without copying transformed points:

float error = tf::chamfer_error(X.points() | tf::tag(T), Y_with_tree);

Smoothing

Laplacian Smoothing

Smooth point positions by iteratively moving vertices towards their neighbors' centroid:

laplacian_smoothed.cpp

// Build vertex connectivity
auto vlink = tf::make_vertex_link(polygons);

// Tag points with vertex link
auto points_with_link = points | tf::tag(vlink);

// Smooth: 100 iterations, lambda=0.5 (how much to move towards centroid)
auto smoothed = tf::laplacian_smoothed(points_with_link, 100, 0.5f);

// Result is a points_buffer with smoothed positions
for (auto pt : smoothed.points()) {
    // Use smoothed point
}

Parameters:

iterations: Number of smoothing passes
lambda: Movement factor in 0,1. 0 = no movement, 1 = move fully to centroid

Laplacian smoothing shrinks the mesh. For volume-preserving smoothing, use Taubin smoothing below.

Taubin Smoothing

Smooth point positions while preserving volume by alternating shrink (positive λ) and inflate (negative μ) passes:

taubin_smoothed.cpp

// Build vertex connectivity
auto vlink = tf::make_vertex_link(polygons);

// Tag points with vertex link
auto points_with_link = points | tf::tag(vlink);

// Smooth: 50 iterations, lambda=0.5, pass-band frequency kpb=0.1
auto smoothed = tf::taubin_smoothed(points_with_link, 50, 0.5f, 0.1f);

// Result is a points_buffer with smoothed positions
for (auto pt : smoothed.points()) {
    // Use smoothed point
}

Parameters:

iterations: Number of smoothing passes (each pass = shrink + inflate)
lambda: Shrink factor in (0,1]. Controls smoothing strength (default: 0.5)
kpb: Pass-band frequency in (0,1). Controls volume preservation (default: 0.1)

The inflate factor μ is computed automatically as μ = 1 / (kpb - 1/λ) to ensure the smoothing filter passes through zero at frequency kpb, preventing low-frequency shrinkage.

Unlike Laplacian smoothing, Taubin smoothing preserves mesh volume by alternating contraction and expansion. Use this when volume preservation is important.

Topology

Connectivity structures, planar embeddings, and mesh analysis.

Remesh

Decimation, isotropic remeshing, and edge collapse.