Surface Reconstruction




Reconstructing surfaces from sample points in a faithful way is a difficult challenge . The problem appears in applications such as CAD designs, medical imaging , visualization, reverse engineering and so on. Recent advances in modern laser technology have made it easier to generate a lot of sample from the boundary of an object. A piecewise linear approximation to the sampled surface  is a goal to achieve in this research. The reconstructed surface should be topologically equivalent to the sampled surface and also geometrically close.  For point clouds we use aVoronoi based algorithm  called  Cocone. This uses a single Voronoi diagram computation. For dense samples from smooth surfaces this algorithm works nicely. For surfaces with boundaries, for water-tight surfaces, for large data sets and noisy point clouds  we have developed different versions of Cocone which are called Cocone, Tight Cocone, Super Cocone and Robust Cocone. Recently (June 2013) we have SingularCocone which works for surfaces with non-smooth features.

The software for all these four versions are available.

This book ``Curve and Surface Reconstruction: Algorithms with Mathematical Analysis" published by Canbridge U. Press contains the theory and algorithms for Cocone and related approaches.

We have also developed AMLS method for smoothing  noisy point cloud data.
circle23_blue.gif   Reconstruction of surfaces from unorganized data by Cocone.
We simplified the proof and the algorithm of crust in this paper. As a result the implementation and proof of correctness get simplified substantially. The algorithm uses the concept of complemented cones in the Voronoi diagram as shown below. We call this algorithm as the cocone algorithm. A merged version of our paper with that of Amenta and Choi appeared in SoCG 2000 conference.
Cocone in  2D and  3D
Reconstructed Club (some garbage triangles near high curvature regions
Reconstructed Foot. The boundary is not detected.
Reconstructed Mannequin. Garbage triangles near high curvature regions such as eyes, ears, lips.

circle23_blue.gif   Detection of Undersampling

    We detect undersampling  from the samples. Boundaries, regions of sharp edges, corners or high curvatures where undersampling usually takes place are detected by this algorithm. This algorithm can be used with crust or our cocone algorithm to make them robust and detect boundaries.

circle23_blue.gif    Filling holes with Tight cocone

    After reconstruction with undersampling detection we are sometimes left with small holes. We stitch these holes with Delaunay triangles. We get almost `perfect' reconstruction in many cases. The details appear in the following papers.
    Holes in the ear (undersamplingfor high curvature)
    Holes are stitched 
    Perfect Mannequin

    Holes in Knot (undersampling for nearby features 
    Holes are stitched
    Perfect Knot

    Holes in Oilpump (undersampling 
    for non-smooth edges) 
    Holes are stitched 
    Perfect Oilpump
circle23_blue.gif Reconstruction from large data
    We extend the cocone algorithm to handle large data in the range of million points. We avoid computing the Delaunay/Voronoi diagram of the entire point set. Instead, we divide the data into chunks using an octree subdivision and then apply cocone on each chunk. The matching of surface pieces from adjacent octree cells are obtained by a `padding mechanism' and some loacl properties of cocone. We have computed a surface from a data of 3.5 million points in 3hrs 18 minutes with a PIII 733Mhz, 512MB,10GB PC.

    T. K. Dey, J. Giesen and J. Hudson. Delaunay based shape reconstruction from large data. IEEE Symposium in  Parallel and Large Data Visualization and Graphics, (2001), 19--27.

    SuperCocone code is available.
    Happy Buddha, 543,652 points, 28 minutes.
     Blade, 882,954 points, 50 minutes
    Lucy25, 3,505,407 points, 198 minutes.

circle23_blue.gif Reconstruction of surfaces from slices circle23_blue.gif Smooth Reconstruction by AMLS
    We use an implicit surface for point cloud data smoothing. The moving least squares, MLS in short, are known for smoothing point cloud data. We take a simple form of MLS and modify it to adapt to the feature sizes of the sampled surface. We call it the adaptive MLS or AMLS in short. The projection onto AMLS is achieved by Newton iterations which is faster than the usual MLS projections. Further, it has other advantages over the standard MLS.

    T. K. Dey and J. Sun. An Adaptive MLS Surface for Reconstruction with Guarantees. IEEE Symposium on Geometry Processing, (2005), 43--52.

    AMLS code is available.

    Max Planck: Noise (left) is smoothed (right) by AMLS
    Hand: Noise (left) is smoothed (right) by AMLS