skip to main content
research-article

GlobFit: consistently fitting primitives by discovering global relations

Published:25 July 2011Publication History
Skip Abstract Section

Abstract

Given a noisy and incomplete point set, we introduce a method that simultaneously recovers a set of locally fitted primitives along with their global mutual relations. We operate under the assumption that the data corresponds to a man-made engineering object consisting of basic primitives, possibly repeated and globally aligned under common relations. We introduce an algorithm to directly couple the local and global aspects of the problem. The local fit of the model is determined by how well the inferred model agrees to the observed data, while the global relations are iteratively learned and enforced through a constrained optimization. Starting with a set of initial RANSAC based locally fitted primitives, relations across the primitives such as orientation, placement, and equality are progressively learned and conformed to. In each stage, a set of feasible relations are extracted among the candidate relations, and then aligned to, while best fitting to the input data. The global coupling corrects the primitives obtained in the local RANSAC stage, and brings them to precise global alignment. We test the robustness of our algorithm on a range of synthesized and scanned data, with varying amounts of noise, outliers, and non-uniform sampling, and validate the results against ground truth, where available.

Skip Supplemental Material Section

Supplemental Material

tp034_11.mp4

References

  1. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2003. Computing and rendering point set surfaces. IEEE TVCG 9, 1, 3--15. Google ScholarGoogle Scholar
  2. Benko, P., Martin, R. R., and Várady, T. 2001. Algorithms for reverse engineering boundary representation models. Computer-Aided Design 33, 11, 839--851.Google ScholarGoogle ScholarCross RefCross Ref
  3. Bokeloh, M., Wand, M., and Seidel, H.-P. 2010. A connection between partial symmetry and inverse procedural modeling. ACM SIGGRAPH 29, 104:1--104:10. Google ScholarGoogle Scholar
  4. Brown, B. J., and Rusinkiewicz, S. 2004. Non-rigid range-scan alignment using thin-plate splines. In 3DPVT, 759--765. Google ScholarGoogle Scholar
  5. Byrd, R., Gilbert, J. C., and Nocedal, J. 2000. A trust region method based on interior point techniques for nonlinear programming. Mathematical Programming 89, 1, 149--185.Google ScholarGoogle ScholarCross RefCross Ref
  6. Carr, J. C., Beatson, R. K., Cherrie, J. B., 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 Proc. of ACM SIGGRAPH, 67--76. Google ScholarGoogle Scholar
  7. Dey, T. 2007. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, 1 ed. Cambridge University Press. Google ScholarGoogle Scholar
  8. Fisher, R. 2004. Applying knowledge to reverse engineering problems. Computer-Aided Design 36, 501--510.Google ScholarGoogle ScholarCross RefCross Ref
  9. Fleishman, S., Cohen-Or, D., and Silva, C. T. 2005. Robust moving least-squares fitting with sharp features. ACM SIGGRAPH 24, 544--552. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Gal, R., Shamir, A., Hassner, T., Pauly, M., and Cohen-Or, D. 2007. Surface reconstruction using local shape priors. In Symp. on Geometry Processing, 253--262. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Gal, R., Sorkine, O., Mitra, N. J., and Cohen-Or, D. 2009. iWIRES: An analyze-and-edit approach to shape manipulation. ACM SIGGRAPH 28, 3, #33, 1--10. Google ScholarGoogle Scholar
  12. Gelfand, N., and Guibas, L. J. 2004. Shape segmentation using local slippage analysis. In Symp. on Geometry Processing, 214--223. Google ScholarGoogle Scholar
  13. Guennebaud, G., and Gross, M. 2007. Algebraic point set surfaces. ACM SIGGRAPH 26, 3, 23. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Hopcroft, J., and Tarjan, R. 1973. Algorithm 447: efficient algorithms for graph manipulation. Comm. of the ACM 16 (June), 372--378. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Proc. of ACM SIGGRAPH, 71--78. Google ScholarGoogle Scholar
  16. Kanatani, K. 2008. Statistical optimization for geometric fitting: Theoretical accuracy bound and high order error analysis. Int. Journal of Computer Vision 80, 167--188. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symp. on Geometry Processing, 61--70. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Li, G., Liu, L., Zheng, H., and Mitra, N. J. 2010. Analysis, reconstruction and manipulation using arterial snakes. ACM SIGGRAPH ASIA 29, 152:1--152:10. Google ScholarGoogle Scholar
  19. Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007. Parameterization-free projection for geometry reconstruction. ACM SIGGRAPH 26, 3, 22. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Mehra, R., Zhou, Q., Long, J., Sheffer, A., Gooch, A., and Mitra, N. J. 2009. Abstraction of man-made shapes. ACM SIGGRAPH ASIA, 137:1--137:10. Google ScholarGoogle Scholar
  21. Mitra, N. J., and Pauly, M. 2008. Symmetry for architectural design. In Advances in Architectural Geometry, 13--16.Google ScholarGoogle Scholar
  22. Mitra, N. J., Guibas, L., and Pauly, M. 2007. Symmetrization. In ACM SIGGRAPH, vol. 26, #63, 1--8. Google ScholarGoogle Scholar
  23. Mullen, P., Goes, F. D., Desbrun, M., Cohen-Steiner, D., and Alliez, P. 2010. Signing the unsigned: Robust surface reconstruction from raw pointsets. In Symp. on Geometry Processing, 1733--1741.Google ScholarGoogle Scholar
  24. Oztireli, C., Guennebaud, G., and Gross, M. 2009. Feature preserving point set surfaces based on non-linear kernel regression. Computer Graphics Forum 28, 2, 493--501.Google ScholarGoogle ScholarCross RefCross Ref
  25. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. 2008. Discovering structural regularity in 3D geometry. ACM SIGGRAPH 27, 3, #43, 1--11. Google ScholarGoogle Scholar
  26. Schnabel, R., Wahl, R., and Klein, R. 2007. Efficient ransac for point-cloud shape detection. Computer Graphics Forum 26, 2, 214--226.Google ScholarGoogle ScholarCross RefCross Ref
  27. Schnabel, R., Degener, P., and Klein, R. 2009. Completion and reconstruction with primitive shapes. CGF Eurographics 28, 2, 503--512.Google ScholarGoogle ScholarCross RefCross Ref
  28. Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In ICCV, 1824--1831. Google ScholarGoogle Scholar
  29. Werghi, N., Fisher, R., Ashbrook, A., and Robertson, C. 2002. Shape reconstruction incorporating multiple nonlinear geometric constraints. Constraints 7, 117--149. Google ScholarGoogle ScholarCross RefCross Ref
  30. Ziena, 2010. Knitro optimization software, Dec.Google ScholarGoogle Scholar

Index Terms

  1. GlobFit: consistently fitting primitives by discovering global relations

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image ACM Transactions on Graphics
            ACM Transactions on Graphics  Volume 30, Issue 4
            July 2011
            829 pages
            ISSN:0730-0301
            EISSN:1557-7368
            DOI:10.1145/2010324
            Issue’s Table of Contents

            Copyright © 2011 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 25 July 2011
            Published in tog Volume 30, Issue 4

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • research-article

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader