Surface Reconstruction

Surface Reconstruction

Home

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.

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

N. Amenta, S. Choi, T. K. Dey and N. Leekha.

A simple algorithm for homeomorphic surface reconstruction

. Proc. 16^th Sympos. Comput. Geom., 2000, 213--222.


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.

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.

T. K. Dey and J. Giesen. Detecting undersampling in surface reconstruction. Proc. 17th Ann.Sympos.Comput. Geom., (2001), 257--263.

We adapt our cocone algorithm to handle surfaces with boundaries. The samples detected as boundary samples do not choose any triangle. The neighboring interior samples choose correct triangles for them in many cases. Cocone code is available.


Reconstructed Monkey saddle	Reconstructed Foot	Oilpump. Regions of sharp edgesand high curvatures are detected (red)

There is a new software Peel which may work better for detecting boundaries from dense samples

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.

T. K. Dey and S. Goswami. Tight Cocone: A water-tight surface reconstructor. Journal of Computing and Information Science in Engineering, Vol. 3 (2003), 302--307.


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

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.

Reconstruction of surfaces from slices

S. W. Cheng and T. K. Dey. Improved construction of Delaunay based contour surfaces. Proc. ACM Sympos. Solid Modeling and Applications 99 1999, 322-323.


Reconstructed human heart from contours in MRI data	Reconstructed human pelvis from contours from MRI datat

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