Home
People
Research
Publications

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
watertight 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 nonsmooth 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




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.
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 nonsmooth 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), 1927.
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
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), 4352.
AMLS code is available.


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

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

