normal-estimator

Uses Jens Behley's C++ Octree to estimate normals for a set of 3D pointcloud vertices and consistently signs them using an implementation of the algorithm described in Surface Reconstruction from Unorganized Points (Hoppe et al. 1992).

Usage

Reads X Y Z triples (one per line) from STDIN and writes X Y Z NX NY NZ per line to STDOUT, preserving input order.

./normal-estimator < cloud.xyz > cloud_with_normals.xyz

Build on Linux/macOS:

g++ -O2 -std=c++11 -fopenmp main.cpp -o normal-estimator

On Windows, use the included Visual Studio solution (OpenMP is enabled in the project settings).

Algorithm

1. Tangent plane estimation — each point's normal is the smallest eigenvector of the weighted covariance of its k nearest neighbors (k = 16, found via octree radius searches that adapt to the data's bounding box, so no fixed world-unit assumptions). Neighbors are Gaussian-weighted by distance (Pauly et al. 2002) for noise robustness, covariance is accumulated in double precision, and eigenvalues come from the closed-form symmetric 3×3 solve. Degenerate (collinear) neighborhoods retry with a doubled k. This stage is parallelized with OpenMP.
2. Riemannian graph — built from the symmetrized k-NN graph. Edge cost is Hoppe's sign-invariant 1 - |n_i · n_j|, plus a small Euclidean distance term (discourages orientation from jumping gaps between separate surface sheets) and a surface-variation term λ₀/(λ₀+λ₁+λ₂) (routes propagation through flat regions before creases). Disconnected components are bridged with their shortest outgoing edge, which replaces the original paper's EMST-splicing step while keeping its connectivity guarantee.
3. Orientation propagation — Prim's algorithm with a lazy-deletion priority queue traverses the minimal spanning tree of the Riemannian graph from the highest point (seeded facing Z+), flipping each normal to agree with its tree parent.
4. Global sign check — the six bounding-box extreme points vote on whether the cloud ended up inside-out (each extreme point's normal must face outward along its axis on a closed surface); a losing vote flips every normal. This recovers from a bad seed, e.g. when the highest point lies on a vertical wall.