Orienting raw point sets by global contraction and visibility voting

We present a global method for consistently orienting a defective raw point set with noise, non-uniformities and thin sharp features. Our method seamlessly combines two simple but effective techniques-constrained Laplacian smoothing and visibility voting-to tackle this challenge. First, we apply a Laplacian contraction to the given point cloud, which shrinks the shape a little bit. Each shrunk point corresponds to an input point and shares a visibility confidence assigned by voting from multiple viewpoints. The confidence is increased (resp. decreased) if the input point (resp. its corresponding shrunk point) is visible. Then, the initial normals estimated by principal component analysis are flipped according to the contraction vectors from shrunk points to the corresponding input points and the visibility confidence. Finally, we apply a Laplacian smoothing twice to correct the orientation of points with zero or low confidence. Our method is conceptually simple and easy to implement, without resorting to any complicated data structures and advanced solvers. Numerous experiments demonstrate that our method can orient the defective raw point clouds in a consistent manner. By taking advantage of our orientation information, the classical implicit surface reconstruction algorithms can faithfully generate the surface. (C) 2011 Elsevier Ltd. All rights reserved.