“Interactive topology-aware surface reconstruction” by Sharf, Lewiner, Shklarski, Toledo and Cohen-Or

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.

1. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. 2001. Point set surfaces. In Visualization, IEEE, 21–28. Google ScholarDigital Library
2. Amenta, N., and Kil, Y. J. 2004. Defining point-set surfaces. In Siggraph, ACM, 264–270. Google ScholarDigital Library
3. Amenta, N., Bern, M. W., and Kamvysselis, M. K. 1998. Crust: A new Voronoï-based surface reconstruction algorithm. In Siggraph, ACM, 415–422. Google ScholarDigital Library
4. Banchoff, T. 1967. Critical points and curvature for embedded polyhedra. Journal of Differential Geometry 1, 257–268.Google ScholarCross Ref
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
8. Curless, B., and Levoy, M. 1996. A volumetric method for building complex models from range images. In Siggraph, ACM, 303–312. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
11. Dey, T. K., and Goswami, S. 2004. Provable surface reconstruction from noisy samples. In Symposium on Computational Geometry, ACM, 330–339. Google ScholarDigital Library
12. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Siggraph, ACM, 71–78. Google ScholarDigital Library
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. Google ScholarDigital Library
14. Hughes, T. J. R. 1987. The Finite Element Method. Linear Static and Dynamic Finite Element Analysis. Prentice-Hall.Google Scholar
15. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symposium on Geometry Processing, ACM/Eurographics, 61–70. Google ScholarDigital Library
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. Google ScholarDigital Library
17. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. In Siggraph, ACM, 689–694. Google ScholarDigital Library
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. Google ScholarDigital Library
19. Li, Y., Sun, J., Tang, C.-K., and Shum, H.-Y. 2004. Lazy snapping. Transaction on Graphics 23, 3, 303–308. Google ScholarDigital Library
20. Milnor, J. W. 1963. Morse theory. Princeton University Press.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
25. Schaefer, S., and Warren, J. 2004. Dual marching cubes: Primal contouring of dual grids. In Pacific Graphics, IEEE, 70–76. Google ScholarDigital Library
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.Google Scholar
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. Google ScholarDigital Library
28. Strang, G. 1986. Introduction to Applied Mathematics. Wellesley-Cambridge.Google Scholar
29. Wang, J., and Cohen, M. F. 2005. An iterative optimization approach for unified image segmentation and matting. In ICCV, IEEE, 936–943. Google ScholarDigital Library