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.
Supplemental Material
- 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
- 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
- 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
- Brown, B. J., and Rusinkiewicz, S. 2004. Non-rigid range-scan alignment using thin-plate splines. In 3DPVT, 759--765. Google Scholar
- 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
- 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
- Dey, T. 2007. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, 1 ed. Cambridge University Press. Google Scholar
- Fisher, R. 2004. Applying knowledge to reverse engineering problems. Computer-Aided Design 36, 501--510.Google ScholarCross Ref
- 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
- 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
- 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
- Gelfand, N., and Guibas, L. J. 2004. Shape segmentation using local slippage analysis. In Symp. on Geometry Processing, 214--223. Google Scholar
- Guennebaud, G., and Gross, M. 2007. Algebraic point set surfaces. ACM SIGGRAPH 26, 3, 23. Google ScholarDigital Library
- Hopcroft, J., and Tarjan, R. 1973. Algorithm 447: efficient algorithms for graph manipulation. Comm. of the ACM 16 (June), 372--378. Google ScholarDigital Library
- 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
- 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
- Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symp. on Geometry Processing, 61--70. Google ScholarDigital Library
- 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
- 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
- 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
- Mitra, N. J., and Pauly, M. 2008. Symmetry for architectural design. In Advances in Architectural Geometry, 13--16.Google Scholar
- Mitra, N. J., Guibas, L., and Pauly, M. 2007. Symmetrization. In ACM SIGGRAPH, vol. 26, #63, 1--8. Google Scholar
- 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
- 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
- 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
- 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
- Schnabel, R., Degener, P., and Klein, R. 2009. Completion and reconstruction with primitive shapes. CGF Eurographics 28, 2, 503--512.Google ScholarCross Ref
- Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In ICCV, 1824--1831. Google Scholar
- Werghi, N., Fisher, R., Ashbrook, A., and Robertson, C. 2002. Shape reconstruction incorporating multiple nonlinear geometric constraints. Constraints 7, 117--149. Google ScholarCross Ref
- Ziena, 2010. Knitro optimization software, Dec.Google Scholar
Index Terms
GlobFit: consistently fitting primitives by discovering global relations
Recommendations
GlobFit: consistently fitting primitives by discovering global relations
SIGGRAPH '11: ACM SIGGRAPH 2011 papersGiven 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 ...
Convexification for data fitting
The main results reported in this paper are two theorems concerning the use of a newtype of risk-averting error criterion for data fitting. The first states that the convexity region of the risk-averting error criterion expands monotonically as its risk-...
A note on cubic polynomial interpolation
''The NURBS Book'' [L. Piegl, W. Tiller, The NURBS Book, second edn, Springer, 1997] is very popular in the fields of computer aided geometric design (CAGD) and geometric modeling. In Section 9.5.2 of the book, the well-known problem of the local cubic ...
Comments