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: Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. 2001. Point set surfaces. In Visualization, IEEE, 21--28.
• 2: Amenta, N., and Kil, Y. J. 2004. Defining point-set surfaces. In Siggraph, ACM, 264--270.
• 3: Amenta, N., Bern, M. W., and Kamvysselis, M. K. 1998. Crust: A new Voronoï-based surface reconstruction algorithm. In Siggraph, ACM, 415--422.
• 4: Banchoff, T. 1967. Critical points and curvature for embedded polyhedra. Journal of Differential Geometry 1, 257--268.
• 5: Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., and Taubin, G. 1999. The Ball-Pivoting Algorithm for surface reconstruction. Transactions on Visualization and Computer Graphics 5, 4, 349--359.
• 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: Carr, J., Beatson, R., Cherrie, J., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Siggraph, ACM, 67--76.
• 8: Curless, B., and Levoy, M. 1996. A volumetric method for building complex models from range images. In Siggraph, ACM, 303--312.
• 9: Davis, T. A., and Hager, W. W. 2005. Row modifications of a sparse Cholesky factorization. SIAM Journal on Matrix Analysis and Applications 26, 3, 621--639.
• 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: Dey, T. K., and Goswami, S. 2004. Provable surface reconstruction from noisy samples. In Symposium on Computational Geometry, ACM, 330--339.
• 12: Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Siggraph, ACM, 71--78.
• 13: Hornung, A., and Kobbelt, L. 2006. Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information. In Symposium on Geometry Processing, ACM/Eurographics, 41--50.
• 14: Hughes, T. J. R. 1987. The Finite Element Method. Linear Static and Dynamic Finite Element Analysis. Prentice-Hall.
• 15: Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symposium on Geometry Processing, ACM/Eurographics, 61--70.
• 16: Kolluri, R., Shewchuk, J. R., and O'Brien, J. F. 2004. Spectral surface reconstruction from noisy point clouds. In Symposium on Geometry Processing, ACM Press, 11--21.
• 17: Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. In Siggraph, ACM, 689--694.
• 18: Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., and Fulk, D. 2000. The digital Michelangelo project: 3D scanning of large statues. In Siggraph, ACM, 131--144.
• 19: Li, Y., Sun, J., Tang, C.-K., and Shum, H.-Y. 2004. Lazy snapping. Transaction on Graphics 23, 3, 303--308.
• 20: Milnor, J. W. 1963. Morse theory. Princeton University Press.
• 21: Nealen, A., Sorkine, O., Alexa, M., and Cohen-Or, D. 2005. A sketch-based interface for detail-preserving mesh editing. Transactions on Graphics 24, 3, 1142--1147.
• 22: Ni, X., Garland, M., and Hart, J. C. 2004. Fair Morse functions for extracting the topological structure of a surface mesh. In Siggraph, ACM, 613--622.
• 23: Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Sei-Del, H.-P. 2003. Multi-level partition of unity implicits. Transaction on Graphics 22, 3, 463--470.
• 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: Schaefer, S., and Warren, J. 2004. Dual marching cubes: Primal contouring of dual grids. In Pacific Graphics, IEEE, 70--76.
• 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: Stander, B. T., and Hart, J. C. 1997. Guaranteeing the topology of an implicit surface polygonization for interactive modeling. In Siggraph, ACM, 279--286.
• 28: Strang, G. 1986. Introduction to Applied Mathematics. Wellesley-Cambridge.
• 29: Wang, J., and Cohen, M. F. 2005. An iterative optimization approach for unified image segmentation and matting. In ICCV, IEEE, 936--943.

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