Chapter 6: 3D Reconstruction Pipelines

The Ball Pivoting Algorithm reconstructs a triangle mesh by rolling a virtual ball of radius r across the point cloud surface. The ball starts at a seed triangle (three points that the ball can rest on) and pivots around each edge, rolling over the surface to find the next point it contacts. Each pivot creates a new triangle. The process continues until no more pivots are possible, then a new seed is found for disconnected regions. The ball radius is a critical parameter: too small and the mesh has holes (the ball falls through gaps); too large and fine details are smoothed over. BPA works well for relatively uniform point clouds but struggles with varying density.

Alpha shapes generalize convex hulls to non-convex shapes by controlling a parameter $\alpha$ that determines the level of detail. The algorithm computes the Delaunay triangulation (or its 3D equivalent, the Delaunay tetrahedralization) of the point set, then removes tetrahedra whose circumradius exceeds $\alpha$. The boundary of the remaining tetrahedra forms the alpha shape. Small $\alpha$ captures fine details but may produce holes; large $\alpha$ gives a smoother but less accurate surface; $\alpha = \infty$ gives the convex hull. Delaunay-based methods guarantee topological consistency (no self-intersections) and work well for point clouds that sample a well-defined surface.

The 3D Delaunay triangulation divides the convex hull of a point set into tetrahedra whose circumscribed spheres contain no other points. In 2D the same empty-circle rule maximizes the minimum angle, but that guarantee does not carry over to 3D: Delaunay tetrahedralizations routinely contain slivers, flat tetrahedra with four nearly coplanar vertices and tiny dihedral angles. The worst-case size is $O(n^2)$ tetrahedra, but for well-spread points it is linear, about 6.5 per point, and randomized incremental insertion runs in $O(n \log n)$ expected time. CGAL, Qhull and scipy.spatial.Delaunay implement it; alpha shapes, Voronoi diagrams and many surface reconstructors are built on it.

Poisson reconstruction defines the surface implicitly as the boundary of a solid region. The indicator function $\chi(x)$ equals 1 inside the object and 0 outside. The surface is where $\chi$ transitions from 0 to 1. The gradient of $\chi$ is zero everywhere except at the surface, where it equals the inward-pointing surface normal. This means the oriented point cloud (positions + normals) samples the gradient of $\chi$. To recover $\chi$, we solve the Poisson equation: $\nabla^2 \chi = \nabla \cdot \vec{V}$, where $\vec{V}$ is a vector field constructed from the input normals. The solution $\chi$ is found using a multigrid solver on an adaptive octree, and the surface is extracted as the iso-surface at an appropriate threshold.

The original Poisson reconstruction smooths the surface by solving only the divergence constraint, which can shift the surface away from the input points (over-smoothing near sharp features). Screened Poisson reconstruction (Kazhdan and Hoppe, 2013) adds a screening term that pulls the solution back toward the input points: minimize $\|\nabla^2 \chi - \nabla \cdot \vec{V}\|^2 + \alpha \|\chi(p_i) - s_i\|^2$, where $p_i$ are input point positions and $s_i$ are target values. The screening weight $\alpha$ controls the trade-off between smoothness and data fidelity. Higher $\alpha$ produces surfaces that pass closer to the input points; lower $\alpha$ gives smoother results. Screened Poisson is the default reconstruction method in MeshLab and Open3D.

Poisson reconstruction requires oriented normals (normals pointing consistently outward). If the input point cloud lacks normals, they must be estimated from local geometry. Normal estimation fits a plane to each point's k nearest neighbors using PCA (the normal is the eigenvector of the smallest eigenvalue of the covariance matrix). However, PCA normals have ambiguous sign (could point inward or outward). Normal orientation propagates a consistent direction through the point cloud using a minimum spanning tree of the Riemannian graph, where edge weights reflect normal alignment between neighbors. Getting normals wrong (inconsistent or inward-facing) produces catastrophic reconstruction artifacts: inverted surfaces, holes, and self-intersections.

Each cube in the grid has 8 corners, and each corner is classified as inside (value >= iso-value) or outside (value < iso-value). With 8 binary classifications, there are $2^8 = 256$ possible configurations. By exploiting rotational and reflective symmetries, these reduce to just 15 unique cases (or 33 with ambiguous cases resolved). A precomputed lookup table maps each configuration index (0-255) to a set of triangles. The configuration index is computed by checking each corner: if corner i is inside, bit i of the index is set. Edge intersections are interpolated linearly between the two corner values to find the exact surface crossing point.

For each edge of a cube that crosses the isosurface (one endpoint inside, one outside), the exact crossing point is found by linear interpolation between the two endpoint values. If corner A has value $v_A$ and corner B has value $v_B$, and the iso-value is $c$, the interpolation parameter is $t = (c - v_A) / (v_B - v_A)$, and the surface vertex is at position $A + t(B - A)$. This places vertices precisely where the scalar field crosses the threshold, producing a mesh that accurately tracks the isosurface. Higher-order interpolation (cubic) can improve accuracy for smooth fields but linear interpolation is standard and sufficient for most applications.

Some cube configurations are ambiguous: the lookup table could generate two different topologies (connected versus disconnected surface patches). The classic example is the saddle point case, where two diagonally opposite corners are inside and two are outside. The original marching cubes algorithm from 1987 could produce meshes with cracks between adjacent cubes. Solutions include: asymptotic decider (checking the saddle point value), marching tetrahedra (splitting each cube into tetrahedra, which have no ambiguities), and dual contouring (placing vertices inside cells rather than on edges). Post-processing steps like vertex welding (merging nearly-coincident vertices) and Laplacian smoothing improve mesh quality.

An SDF encodes a surface implicitly as the zero-crossing of a continuous function. Unlike explicit representations (meshes, point clouds) that store surface elements directly, the SDF defines the surface everywhere in space: any point can be queried to determine its distance to the surface and whether it is inside or outside. The magnitude of the SDF gives the exact distance to the closest surface point, and the gradient of the SDF at the surface equals the surface normal. SDFs can represent surfaces with arbitrary topology (genus, disconnected components) without special handling, and Boolean operations (union, intersection, difference) reduce to simple min/max operations on the SDF values.

In real-time 3D reconstruction (KinectFusion), the TSDF truncates the signed distance to a small range [-delta, delta] around the surface. Values beyond the truncation distance are clamped. The TSDF is stored on a voxel grid and updated incrementally as new depth frames arrive: each frame's depth map is converted to a local TSDF, and the running average is updated voxel-by-voxel using a weighted running mean. Truncation serves two purposes: it limits the influence of each measurement to a thin band around the surface (preventing distant geometry from affecting nearby surfaces), and it allows efficient storage (voxels far from any surface can be marked as unknown). The surface is extracted as the zero-crossing of the fused TSDF using marching cubes.

DeepSDF represents shapes as the zero level-set of a neural network that takes a 3D coordinate as input and outputs the signed distance value. Instead of storing SDF values on a grid, the continuous function is encoded in the network's weights. This provides virtually infinite resolution (query at any point), compact storage (a few MB of weights represent complex shapes), and enables shape interpolation and generation in the learned latent space. Training requires ground-truth SDF samples, which are generated by sampling points near the surface and computing their signed distances. The auto-decoder architecture learns a shape embedding space where each training shape has a latent code, and new shapes can be generated by interpolating codes.

Edge collapse is the fundamental simplification operation: select an edge, merge its two endpoint vertices into a single vertex, and remove the two triangles that shared that edge. The resulting mesh has 2 fewer triangles, 3 fewer edges, and 1 fewer vertex (matching Euler's formula). The position of the merged vertex determines the quality of the approximation. Simplest approach: place it at the midpoint. Better approach: optimize its position to minimize geometric error. The order in which edges are collapsed is driven by an error metric, with the least-error edges collapsed first. This greedy strategy produces nearly optimal simplifications.

The Quadric Error Metric (Garland & Heckbert, 1997) assigns an error to each vertex based on its distance to the original surface planes. For each vertex, a 4x4 quadric matrix Q is computed as the sum of the outer products of the planes of all adjacent faces. Collapsing edge (v1, v2) produces a new vertex v_new that minimizes the combined error v_new^T (Q1 + Q2) v_new. The optimal position is found by solving a 4x4 linear system. QEM is remarkably effective because it accounts for the flatness of the local surface: edges in flat regions (where all planes agree) have low error and are collapsed first, while edges near sharp features or high curvature have high error and are preserved longest.

Level of Detail systems store multiple simplification levels of the same mesh and switch between them based on viewing distance or screen-space coverage. A car 500 meters away uses the 1,000-triangle LOD; at 50 meters, the 10,000-triangle LOD; up close, the full 100,000-triangle mesh. Progressive meshes (Hoppe, 1996) store a base mesh plus a sequence of vertex split records (the inverse of edge collapses). Any intermediate LOD can be reconstructed by applying the appropriate number of splits. This enables smooth, continuous LOD transitions (geomorphing) without storing separate meshes. Modern game engines use nanite-style virtualized geometry that automatically selects per-triangle LOD, eliminating pop-in artifacts entirely.

UV unwrapping maps each triangle of a 3D mesh to a 2D triangle in texture space. The challenge is that most 3D surfaces cannot be flattened to 2D without some distortion (stretching or compression). The mesh is cut along seam edges to divide it into charts (patches that can be flattened individually). Each chart is parameterized (flattened) using conformal or isometric mapping that minimizes angular or area distortion. The flattened charts are then packed into a single rectangular texture atlas, maximizing space utilization. The UV coordinates of each vertex map between 3D mesh space and 2D texture space.

In photogrammetry, texture is generated by projecting the original photographs onto the reconstructed mesh. For each triangle, the algorithm selects the best source photograph (the one where the triangle is most front-facing, least occluded, and closest to the camera) and samples the color from that image. The selection considers the angle between the face normal and the camera viewing direction (oblique views cause stretching), the resolution (closer cameras give more detail), and occlusion (other geometry may block the view). Multi-band blending combines contributions from multiple photographs at different frequency bands, producing seamless textures without visible seams between photographs.

When a textured mesh is rendered, each screen pixel typically does not align with exactly one texel (texture pixel). Minification (one screen pixel covers many texels) causes aliasing (shimmering, moire patterns). Magnification (one texel covers many screen pixels) causes blockiness. Mipmapping precomputes a pyramid of progressively smaller texture versions (512x512, 256x256, ..., 1x1), and the renderer selects the appropriate mip level based on the screen-space coverage of each pixel. Trilinear filtering interpolates between two mip levels for smooth transitions. Anisotropic filtering handles oblique viewing angles by using different mip levels in different directions.