trueform

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 transformations to align point sets. Methods are organized by whether they require known point correspondences.

With Correspondences

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

Rigid Alignment (Point-to-Point)

Use the Kabsch/Procrustes algorithm for optimal rotation + translation:

fit_rigid_alignment.cpp

// X and Y must have the same number of points
// X[i] corresponds to Y[i]
tf::points_buffer<float, 3> X = /* source points */;
tf::points_buffer<float, 3> Y = /* target points */;

// Compute optimal rigid transformation T such that T(X) ≈ Y
auto T = tf::fit_rigid_alignment(X.points(), Y.points());

// Apply the transformation
for (auto x : X.points()) {
    auto y_approx = tf::transformed(x, T);
}

The algorithm minimizes the sum of squared distances between transformed source points and target points.

Rigid Alignment (Point-to-Plane)

When the target has normals attached, fit_rigid_alignment automatically uses point-to-plane minimization instead of point-to-point. This minimizes the distance along the normal direction rather than Euclidean distance:

fit_rigid_alignment_p2l.cpp

// Compute point normals on target mesh
auto fm = tf::make_face_membership(target_polygons);
auto normals = tf::compute_point_normals(target_polygons | tf::tag(fm));

// Tag normals onto target points
auto Y_with_normals = Y.points() | tf::tag_normals(normals.unit_vectors());

// Automatically uses point-to-plane minimization
auto T = tf::fit_rigid_alignment(X.points(), Y_with_normals);

Point-to-plane is particularly useful when correspondences are approximate (e.g., from nearest-neighbor search) rather than exact vertex-to-vertex matches.

Similarity Alignment

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

fit_similarity_alignment.cpp

// X[i] corresponds to Y[i], but scales may differ
auto T = tf::fit_similarity_alignment(X.points(), Y.points());

// T includes uniform scaling - 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.

OBB-Based Alignment

Align using oriented bounding boxes (OBBs):

fit_obb_alignment.cpp

// No correspondence required - points can have different counts
tf::points_buffer<float, 3> X = /* source points */;
tf::points_buffer<float, 3> Y = /* target points */;

// Align OBB axes and centers
auto T = tf::fit_obb_alignment(X.points(), Y.points());

// The transformation maps X's OBB to Y's OBB
for (auto x : X.points()) {
    auto y_approx = tf::transformed(x, T);
}

This method:

Computes the OBB of each point set
Aligns the principal axes
Aligns the OBB centers

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

To resolve the ambiguity, attach a tree policy to the target. The function will test all 4 orientations and select the one with lowest chamfer distance:

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

// Now returns the correct orientation
auto T = tf::fit_obb_alignment(X.points(), Y_with_tree);

KNN Alignment (ICP Step: Point-to-Point)

For iterative closest point (ICP) registration, use k-nearest neighbor alignment. This finds correspondences via nearest neighbor search and computes a rigid transformation:

fit_knn_alignment.cpp

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

// Single ICP iteration: find correspondences, fit rigid transform
auto T_iter = tf::fit_knn_alignment(X.points(), Y_with_tree);

// For soft correspondences, use k > 1 neighbors with Gaussian weighting
auto T_soft = tf::fit_knn_alignment(X.points(), Y_with_tree,
                                     /*k=*/5, /*sigma=*/-1);

The k parameter controls how many neighbors to use (k=1 is classic ICP). With k>1, correspondences are weighted by a Gaussian kernel where sigma defaults to the k-th neighbor distance.

KNN Alignment (ICP Step: Point-to-Plane)

When the target has normals attached, fit_knn_alignment automatically uses point-to-plane ICP, which typically converges 2-3x faster than point-to-point:

fit_knn_alignment_p2l.cpp

// Build tree and compute normals on target
tf::aabb_tree<int, float, 3> tree(Y.points(), tf::config_tree(4, 4));
auto fm = tf::make_face_membership(target_polygons);
auto normals = tf::compute_point_normals(target_polygons | tf::tag(fm));

// Tag both tree and normals onto target
auto Y_with_normals = Y.points()
    | tf::tag(tree)
    | tf::tag_normals(normals.unit_vectors());

// Automatically uses point-to-plane ICP
auto T_iter = tf::fit_knn_alignment(X.points(), Y_with_normals,
                                     /*k=*/5, /*sigma=*/-1);

Point-to-plane ICP converges faster because it allows sliding along the surface. On smooth surfaces, expect 2-3x fewer iterations to reach the same error level compared to point-to-point.

Working with Transformations

All alignment and error functions support transformation tagging. Instead of copying transformed points, tag the accumulated transformation and let the function apply it lazily:

alignment_with_transforms.cpp

// Tag source with accumulated transformation
auto T_accum = tf::fit_obb_alignment(source.points(), target_with_tree);
// Tag transformation onto points - no copy
auto source_transformed = source_subset0 | tf::tag(T_accum);
// ICP step works on transformed points
auto T_iter = tf::fit_knn_alignment(source_transformed, target_with_tree, k);
// Accumulate transformation
T_accum = tf::transformed(T_accum, T_iter);
// Chamfer error also accepts tagged points
float error = tf::chamfer_error(source_subset1 | tf::tag(T_accum), target_with_tree);

This avoids copying point data at each iteration. The transformation is composed and applied only when needed.

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

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, consider Taubin smoothing (alternating positive/negative lambda values).

Topology

Connectivity structures, planar embeddings, and mesh analysis.

Intersect

Mesh intersections, self-intersections, and scalar field isocontours.