Surface Reconstruction by Layer Peeling
ChiWan Lim and TiowSeng Tan
School of Computing
Abstract 
Given an input point cloud P in R^{3}, this paper proposes a novel algorithm to identify surface neighbors of each point p Î P respecting the underlying surface S, and then to construct a piecewise linear surface for P. The algorithm utilizes the simple knearest neighborhood in constructing local surfaces. It makes use of two concepts: a local convexity criterion to extract a set of surface neighbors for each point, and a global projection test to determine an order for the reconstruction. Our algorithm not only produces a topologically correct surface for wellsampled point sets, but also adapts well to handle undersampled point sets. Furthermore, the computational cost of the algorithm increases almost linearly in the size of the point cloud. It thus scales well to deal with large input point sets. 
CR Categories: I.3.5 [Computer Graphics]: Curve, surface, solid, and object representations. Keywords: Surface Reconstruction, Mesh Generation, Geometric Modeling, Sampling, Scattered data Full Text: The
Visual Computer, vol. 22, no. 911, September 2006, pp. 593603. (Special
Issue: The 2006 Pacific Graphics, 1113 October, Video Download: LayerPeeling.mov (22.1M) Executable (version 1.0, 3 Dec 2006): click here to download page. PhD thesis. (6M), presentation (25.5M)

More Results 
We have implemented our algorithm on a Pentium IV 3.0GHz, 4GB DDR2 RAM and nVidia GeForce 6600 with 256MB DDR3 video memory. Part 1: Regularly Sampled Point Sets In this first part, we apply our Layer Peeling Algorithm on various point sets.



Part 2: UnderSampled Point Sets In this second part, we regularly downsampled the point sets and test our algorithm on it.



Part 3: Irregularly Sampled Point Sets In this final part, we demonstrate the flexibility of our Layer Peeling Algorithm on three irregularly sampled point sets. 


The point models were obtained from the follow URL: http://www.cs.princeton.edu/gfx/proj/sugcon/models/ http://graphics.stanford.edu/data/3Dscanrep/
Acknowledgements This research is supported by the National University of Singapore under grants R252000216112 and R252000254112. The authors can be contacted at: limchiwa @ gmail.com, and tants @ comp.nus.edu.sg ã11 October 2006, 3 December 2006, 28 Feb 2008, 13 March 2008, Computer Graphics Research Laboratory, School of Computing, National University of Singapore. 
