“Shape approximation by developable wrapping” by Ion, Rabinovich, Herholz and Sorkine-Hornung – ACM SIGGRAPH HISTORY ARCHIVES

“Shape approximation by developable wrapping” by Ion, Rabinovich, Herholz and Sorkine-Hornung

  • 2020 SA Technical Papers_Ion_Shape approximation by developable wrapping

Conference:


Type(s):


Title:

    Shape approximation by developable wrapping

Session/Category Title:   Digital Geometry Processing

Presenter(s)/Author(s):


Abstract:


    We present an automatic tool to approximate curved geometries with piece-wise developable surfaces. At the center of our work is an algorithm that wraps a given 3D input surface with multiple developable patches, each modeled as a discrete orthogonal geodesic net. Our algorithm features a global optimization routine for effectively finding the placement of the developable patches. After wrapping the mesh, we use these patches and a non-linear projection step to generate a surface that approximates the original input, but is also amendable to simple and efficient fabrication techniques thanks to being piecewise developable. Our algorithm allows users to steer the trade-off between approximation power and the number of developable patches used. We demonstrate the effectiveness of our approach on a range of 3D shapes. Compared to previous approaches, our results exhibit a smaller or comparable error with fewer patches to fabricate.

References:


    1. Q. Alessio. 2012. Membrane locking in discrete shell theories. Ph.D. Dissertation. Niedersächsische Staats-und Universitätsbibliothek Göttingen.Google Scholar
    2. M. Balasubramanian, J. R. Polimeni, and E. L. Schwartz. 2009. Exact Geodesics and Shortest Paths on Polyhedral Surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 31, 6 (2009), 1006–1016. Google ScholarDigital Library
    3. P. Bo and W. Wang. 2007. Geodesic-Controlled Developable Surfaces for Modeling Paper Bending. Computer Graphics Forum 26, 3 (2007), 365–374. Google ScholarCross Ref
    4. Y. Boykov, O. Veksler, and R. Zabih. 2001. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 23, 11 (Nov 2001), 1222–1239. Google ScholarDigital Library
    5. D. Chapelle and K.-J. Bathe. 1998. Fundamental considerations for the finite element analysis of shell structures. Computers & Structures 66, 1 (1998), 19–36.Google ScholarCross Ref
    6. H.-Y. Chen, I.-K. Lee, S. Leopoldseder, H. Pottmann, T. Randrup, and J. Wallner. 1999. On Surface Approximation Using Developable Surfaces. Graphical Models and Image Processing 61, 2 (1999), 110 — 124. Google ScholarCross Ref
    7. P. Cignoni, C. Rocchini, and R. Scopigno. 1998. Metro: measuring error on simplified surfaces. Computer graphics forum 17, 2 (1998), 167–174.Google Scholar
    8. A. De Coninck, B. De Baets, D. Kourounis, F. Verbosio, O. Schenk, S. Maenhout, and J. Fostier. 2016. Needles: Toward Large-Scale Genomic Prediction with Marker-by-Environment Interaction. Genetics 203, 1 (2016), 543–555. Google ScholarCross Ref
    9. M. P. do Carmo. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall.Google Scholar
    10. D. Fuchs and S. Tabachnikov. 1999. More on paperfolding. The American Mathematical Monthly 106, 1 (1999), 27–35.Google ScholarCross Ref
    11. E. Grinspun, A. N. Hirani, M. Desbrun, and P. Schröder. 2003. Discrete Shells. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 62–67. http://dl.acm.org/citation.cfm?id=846276.846284Google Scholar
    12. P. Herholz, W. Matusik, and M. Alexa. 2015. Approximating Free-form Geometry with Height Fields for Manufacturing. Computer Graphics Forum 34, 2 (2015), 239–251. Google ScholarDigital Library
    13. A. Jacobson, D. Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. (2018). https://libigl.github.io/.Google Scholar
    14. C. Jiang, C. Wang, F. Rist, J. Wallner, and H. Pottmann. 2020. Quad-Mesh Based Isometric Mappings and Developable Surfaces. ACM Transactions on Graphics 39, 4 (2020). Google ScholarDigital Library
    15. D. Julius, V. Kraevoy, and A. Sheffer. 2005. D-charts: Quasi-developable mesh segmentation. Computer Graphics Forum 24, 3 (2005), 581–590.Google ScholarCross Ref
    16. D. Kourounis, A. Fuchs, and O. Schenk. 2018. Towards the Next Generation of Multiperiod Optimal Power Flow Solvers. IEEE Transactions on Power Systems PP, 99 (2018), 1–10. Google ScholarCross Ref
    17. S. Lawrence. 2011. Developable Surfaces: Their History and Application. Nexus Network Journal 13, 3 (2011), 701–714. Google ScholarCross Ref
    18. Y. Liu, Y. Lai, and S. Hu. 2009. Stripification of Free-Form Surfaces With Global Error Bounds for Developable Approximation. IEEE Transactions on Automation Science and Engineering 6, 4 (2009), 700–709.Google ScholarCross Ref
    19. Y. Liu, H. Pottmann, J. Wallner, Y.-L. Yang, and W. Wang. 2006. Geometric modeling with conical meshes and developable surfaces. ACM Transactions on Graphics 25, 3 (2006).Google ScholarDigital Library
    20. F. Massarwi, C. Gotsman, and G. Elber. 2007. Papercraft models using generalized cylinders. In 15th Pacific Conference on Computer Graphics and Applications (PG’07). IEEE, 148–157.Google Scholar
    21. J. Mitani and H. Suzuki. 2004. Making papercraft toys from meshes using strip-based approximate unfolding. ACM Transactions on Graphics 23, 3 (2004), 259–263.Google ScholarDigital Library
    22. J. Nocedal and S. Wright. 2006. Numerical optimization. Springer Science & Business Media.Google Scholar
    23. D. Panozzo, E. Puppo, and L. Rocca. 2010. Efficient multi-scale curvature and crease estimation. Proceedings of Computer Graphics, Computer Vision and Mathematics (Brno, Czech Rapubic 1, 6 (2010).Google Scholar
    24. K. Polthier and M. Schmies. 2006. Straightest geodesics on polyhedral surfaces. In ACM SIGGRAPH 2006 Courses. 30–38.Google Scholar
    25. H. Pottmann and J. Wallner. 1999. Approximation algorithms for developable surfaces. Computer Aided Geometric Design 16, 6 (1999), 539 — 556. Google ScholarCross Ref
    26. H. Pottmann and J. Wallner. 2001. Computational Line Geometry. Springer-Verlag, Berlin, Heidelberg.Google Scholar
    27. M. Rabinovich, T. Hoffmann, and O. Sorkine-Hornung. 2018a. Discrete Geodesic Nets for Modeling Developable Surfaces. ACM Transactions on Graphics 37, 2 (2018).Google ScholarDigital Library
    28. M. Rabinovich, T. Hoffmann, and O. Sorkine-Hornung. 2018b. The Shape Space of Discrete Orthogonal Geodesic Nets. ACM Transactions on Graphics 37, 6 (2018).Google ScholarDigital Library
    29. M. Rabinovich, T. Hoffmann, and O. Sorkine-Hornung. 2019. Modeling Curved Folding with Freeform Deformations. ACM Transactions on Graphics 38, 6 (2019).Google ScholarDigital Library
    30. K. Rose, A. Sheffer, J. Wither, M.-P. Cani, and B. Thibert. 2007. Developable Surfaces from Arbitrary Sketched Boundaries. In Proc. Symposium on Geometry Processing. 163–172. http://dl.acm.org/citation.cfm?id=1281991.1282014Google Scholar
    31. C. Schreck, D. Rohmer, S. Hahmann, M.-P. Cani, S. Jin, C. C. Wang, and J.-F. Bloch. 2015. Nonsmooth developable geometry for interactively animating paper crumpling. ACM Transactions on Graphics (TOG) 35, 1 (2015), 1–18.Google ScholarDigital Library
    32. C. Schüller, R. Poranne, and O. Sorkine-Hornung. 2018. Shape representation by zippables. ACM Transactions on Graphics (TOG) 37, 4 (2018), 78.Google ScholarDigital Library
    33. S. Sellán, N. Aigerman, and A. Jacobson. 2020. Developability of Heightfields via Rank Minimization. ACM Transactions on Graphics 39, 4 (2020). Google ScholarDigital Library
    34. I. Shatz, A. Tal, and G. Leifman. 2006. Paper Craft Models from Meshes. Visual Computer 22, 9 (Sept. 2006), 825–834. Google ScholarDigital Library
    35. J. Solomon, E. Vouga, M. Wardetzky, and E. Grinspun. 2012. Flexible developable surfaces. Computer Graphics Forum 31, 5 (2012), 1567–1576.Google ScholarDigital Library
    36. O. Sorkine, D. Cohen-Or, R. Goldenthal, and D. Lischinski. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of IEEE Visualization. IEEE Computer Society, 355–362.Google ScholarDigital Library
    37. O. Stein, E. Grinspun, and K. Crane. 2018. Developability of triangle meshes. ACM Transactions on Graphics 37, 4 (2018).Google ScholarDigital Library
    38. C. Tang, P. Bo, J. Wallner, and H. Pottmann. 2016. Interactive design of developable surfaces. ACM Transactions on Graphics 35, 2, Article 12 (2016), 12 pages.Google ScholarDigital Library
    39. F. Verbosio, A. D. Coninck, D. Kourounis, and O. Schenk. 2017. Enhancing the scalability of selected inversion factorization algorithms in genomic prediction. Journal of Computational Science 22, Supplement C (2017), 99 — 108. Google ScholarCross Ref
    40. C. C. Wang and K. Tang. 2004. Achieving developability of a polygonal surface by minimum deformation: a study of global and local optimization approaches. The Visual Computer 20, 8–9 (2004), 521–539.Google ScholarCross Ref
    41. H. Wang, D. Pellis, F. Rist, H. Pottmann, and C. Müller. 2019. Discrete Geodesic Parallel Coordinates. ACM Transactions on Graphics 38, 6, Article 173 (Nov. 2019), 13 pages. Google ScholarDigital Library
    42. H. Zhao and G. Xu. 2006. Triangular surface mesh fairing via Gaussian curvature flow. J. Comput. Appl. Math. 195, 1–2 (2006), 300–311.Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org