“GlobFit: consistently fitting primitives by discovering global relations” by Li, Wu, Chrysanthou, Sharf, Cohen-Or, et al. …

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.

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 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 ScholarCross 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 Scholar
4. Brown, B. J., and Rusinkiewicz, S. 2004. Non-rigid range-scan alignment using thin-plate splines. In 3DPVT, 759–765. Google 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 ScholarCross 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 Scholar
7. Dey, T. 2007. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, 1 ed. Cambridge University Press. Google Scholar
8. Fisher, R. 2004. Applying knowledge to reverse engineering problems. Computer-Aided Design 36, 501–510.Google ScholarCross 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 ScholarDigital 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 ScholarDigital 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 Scholar
12. Gelfand, N., and Guibas, L. J. 2004. Shape segmentation using local slippage analysis. In Symp. on Geometry Processing, 214–223. Google Scholar
13. Guennebaud, G., and Gross, M. 2007. Algebraic point set surfaces. ACM SIGGRAPH 26, 3, 23. Google ScholarDigital Library
14. Hopcroft, J., and Tarjan, R. 1973. Algorithm 447: efficient algorithms for graph manipulation. Comm. of the ACM 16 (June), 372–378. Google ScholarDigital 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 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 ScholarDigital Library
17. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symp. on Geometry Processing, 61–70. Google ScholarDigital 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 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 ScholarDigital 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 Scholar
21. Mitra, N. J., and Pauly, M. 2008. Symmetry for architectural design. In Advances in Architectural Geometry, 13–16.Google Scholar
22. Mitra, N. J., Guibas, L., and Pauly, M. 2007. Symmetrization. In ACM SIGGRAPH, vol. 26, #63, 1–8. Google 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 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 ScholarCross 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 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 ScholarCross Ref
27. Schnabel, R., Degener, P., and Klein, R. 2009. Completion and reconstruction with primitive shapes. CGF Eurographics 28, 2, 503–512.Google ScholarCross Ref
28. Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In ICCV, 1824–1831. Google Scholar
29. Werghi, N., Fisher, R., Ashbrook, A., and Robertson, C. 2002. Shape reconstruction incorporating multiple nonlinear geometric constraints. Constraints 7, 117–149. Google ScholarCross Ref
30. Ziena, 2010. Knitro optimization software, Dec.Google Scholar