Interactive topology-aware surface reconstruction

ABSTRACT

The reconstruction of a complete watertight model from scan data is still a difficult process. In particular, since scanned data is often incomplete, the reconstruction of the expected shape is an ill-posed problem. Techniques that reconstruct poorly-sampled areas without any user intervention fail in many cases to faithfully reconstruct the topology of the model. The method that we introduce in this paper is topology-aware: it uses minimal user input to make correct decisions at regions where the topology of the model cannot be automatically induced with a reasonable degree of confidence. We first construct a continuous function over a three-dimensional domain. This function is constructed by minimizing a penalty function combining the data points, user constraints, and a regularization term. The optimization problem is formulated in a mesh-independent manner, and mapped onto a specific mesh using the finite-element method. The zero level-set of this function is a first approximation of the reconstructed surface. At complex under-sampled regions, the constraints might be insufficient. Hence, we analyze the local topological stability of the zero level-set to detect weak regions of the surface. These regions are suggested to the user for adding local inside/outside constraints by merely scribbling over a 2D tablet. Each new user constraint modifies the minimization problem, which is solved incrementally. The process is repeated, converging to a topology-stable reconstruction. Reconstructions of models acquired by a structured-light scanner with a small number of scribbles demonstrate the effectiveness of the method.

REFERENCES

• 1: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Point set surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 2: Nina Amenta , Yong Joo Kil, Defining point-set surfaces, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 3: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 4: Banchoff, T. 1967. Critical points and curvature for embedded polyhedra. Journal of Differential Geometry 1, 257--268.
• 5: Fausto Bernardini , Joshua Mittleman , Holly Rushmeier , Cláudio Silva , Gabriel Taubin, The Ball-Pivoting Algorithm for Surface Reconstruction, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.349-359, October 1999 [doi>10.1109/2945.817351]
• 6: Boissonnat, J.-D., and Cazals, F. 2002. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Computational Geometry: Theory and Applications 22, 1--3, 185--203.
• 7: J. C. Carr , R. K. Beatson , J. B. Cherrie , T. J. Mitchell , W. R. Fright , B. C. McCallum , T. R. Evans, Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 8: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 9: Timothy A. Davis , William W. Hager, Row Modifications of a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.26 n.3, p.621-639, 2005 [doi>10.1137/S089547980343641X]
• 10: Davis, J., Marschner, S., Garr, M., and Levoy, M. 2002. Filling holes in complex surfaces using volumetric diffusion. In Symposium on 3D Data Processing, Visualization, and Transmission, University of Padova.
• 11: Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997867]
• 12: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 13: Alexander Hornung , Leif Kobbelt, Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 14: Hughes, T. J. R. 1987. The Finite Element Method. Linear Static and Dynamic Finite Element Analysis. Prentice-Hall.
• 15: Michael Kazhdan , Matthew Bolitho , Hugues Hoppe, Poisson surface reconstruction, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 16: Ravikrishna Kolluri , Jonathan Richard Shewchuk , James F. O'Brien, Spectral surface reconstruction from noisy point clouds, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057434]
• 17: Anat Levin , Dani Lischinski , Yair Weiss, Colorization using optimization, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 18: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 19: Yin Li , Jian Sun , Chi-Keung Tang , Heung-Yeung Shum, Lazy snapping, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 20: Milnor, J. W. 1963. Morse theory. Princeton University Press.
• 21: Andrew Nealen , Olga Sorkine , Marc Alexa , Daniel Cohen-Or, A sketch-based interface for detail-preserving mesh editing, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 22: Xinlai Ni , Michael Garland , John C. Hart, Fair morse functions for extracting the topological structure of a surface mesh, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 23: Yutaka Ohtake , Alexander Belyaev , Marc Alexa , Greg Turk , Hans-Peter Seidel, Multi-level partition of unity implicits, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 24: Ohtake, Y., Belyaev, A., and Seidel, H.-P. 2004. A multi-scale approach to 3D scattered data approximation with adaptive compactly supported radial basis functions. In Solid Modeling International, IEEE, 31--39.
• 25: Scott Schaefer , Joe Warren, Dual Marching Cubes: Primal Contouring of Dual Grids, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.70-76, October 06-08, 2004
• 26: Sharf, A., Lewiner, T., Shamir, A., Kobbelt, L., and Cohen-Or, D. 2006. Competing fronts for coarse-to-fine surface reconstruction. In Eurographics, Eurographics, 389--398.
• 27: Barton T. Stander , John C. Hart, Guaranteeing the topology of an implicit surface polygonization for interactive modeling, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.279-286, August 1997 [doi>10.1145/258734.258868]
• 28: Strang, G. 1986. Introduction to Applied Mathematics. Wellesley-Cambridge.
• 29: Jue Wang , Michael F. Cohen, An Iterative Optimization Approach for Unified Image Segmentation and Matting, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.936-943, October 17-20, 2005 [doi>10.1109/ICCV.2005.37]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

Keywords:
interactive tools, surface reconstruction