"Spectral Surface Reconstruction From Noisy Point Clouds"

We introduce a noise-resistant algorithm for reconstructing a watertight surface from point cloud data. It forms a Delaunay tetrahedralization, then uses a variant of spectral graph partitioning to decide whether each tetrahedron is inside or outside the original object. The reconstructed surface triangulation is the set of triangular faces where inside and outside tetrahedra meet. Because the spectral partitioner makes local decisions based on a global view of the model, it can ignore outliers, patch holes and undersampled regions, and surmount ambiguity due to measurement errors. Our algorithm can optionally produce a manifold surface. We present empirical evidence that our implementation is substantially more robust than several closely related surface reconstruction programs.



Kolluri R., Shewchuk J. R., O'Brien J. F., "Spectral Surface Reconstruction From Noisy Point Clouds." Symposium on Geometry Processing 2004, Nice, France, July 8-10, pp. 11-21.

Download PDF        Talk slides          BibTex      


Project Members
Ravikrishna Kolluri       Jonathan R. Shewchuk       James F. O'Brien


 

Examples

Angel reconstruction

A watertight manifold surface triangulation reconstructed by our eigencrust algroithm from a point cloud(right, bottom) with 4000 artificial random outliers. 437 minutes reconstruction time for this data set that contains 2,008,414 points. The reconstructed surface has genus 14, whereas the source object (right, top) has genus 1.  Download the angel data set:

angel.tgz  (35MB, 72 range images, ply format)


This data set is made publicly available for non-profit use under the conditions that:

  1. Any publication cite Kolluri R., Shewchuk J. R., O'Brien J. F., "Spectral Surface Reconstruction From Noisy Point Clouds." Symposium on Geometry Processing 2004, Nice, France, July 8-10, pp. 11-21.
  2. Images or other depictions generated from the dataset include in the caption "Angel data set courtesy of the U.C. Berkeley Computer Animation and Modeling Group."

Skeleton reconstruction

Reconstruction of a densely sampled data set from a smooth surface. The reconstructed surface is a manifold of genus zero. 12.3 minutes reconstruction time for this data set that contains 327,323 points.

Range Data
Bunny reconstruction

Reconstruction of the Stanford bunny. Left: the eigencrust reconstruction of the Stanford Bunny data (raw, unsmoothed point samples with natural noise but no outliers) patches two unsampled holes in the bottom of the bunny (middle). Also shown (right) is the bunny after Laplacian smoothing. The reconstructed surface is a manifold with genus zero. 19.1 minutes reconstruction time for this data set that contains 362,272 points.

Dragon reconstruction

Eigencrust reconstruction of the Stanford dragon model from raw data. The point cloud has many outliers, which are automatically omitted from the recovered surface. 197 minutes reconstruction time for this data set that contains 1,769,513 points

Sharp Corners
Mechanical part reconstruction

Eigencrust Powercrust Hybrid

Reconstructions of a mechanical part by three algorithms. The hybrid algorithm uses the labeling produced by the eigencrust algorithm to partition the cells of the power diagram.

Noise and Outliers
Noise experiment


Eigencrust, +2l Eigencrust, +3l Eigencrust, +5l Tight Cocone +0.8l Powercrust, +2l

Stanford Bunny reconstructions from raw data, with natural noise plus added random Gaussian noise. The amount of random noise is expressed as the variance of the Gaussian noise added to each point coordinate, in terms of the average grid spacing l of the range images in the data set. The eigencrust maintains its integrity with +2 l added noise.


200 Outliers
 1200 Outliers
  1800 Outliers
 6000 Outliers
 10000 Outliers
Outliers experiment
Eigencrust

 

 


200 Outliers 1200 Outliers
200 Outliers 1200 Outliers
Hand reconstruction

Tight Cocone
Powercrust

25,256 noise-free points plus randomly added outliers. The eigencrust reconstructions maintain integrity till 1200 outliers, then begin to degrade. Tight cocone and powercrust reconstructions degrade much earlier.

 

 

Non-Manifold Data
Teapot reconstruction
  Eigencrust
 Tight Cocone Eigencrust
 Powercrust

Reconstructions from 253,859 points sampled on the Utah Teapot. The spout's splines penetrate into the body of the teapot, causing difficulties for both the Powercrust and Tight Cocone algorithms. A cutaway view shows that Powercrust mislabels as "outside" a region where the spout enters the body. Eigencrust correctly identifies the same region as "inside".