“Developability-driven piecewise approximations for triangular meshes” by Zhao, Fang, Ouyang, , Liu, et al. …

We propose a novel method to compute a piecewise mesh with a few developable patches and a small approximation error for an input triangular mesh. Our key observation is that a deformed mesh after enforcing discrete developability is easily partitioned into nearly developable patches. To obtain the nearly developable mesh, we present a new edge-oriented notion of discrete developability to define a developability-encouraged deformation energy, which is further optimized by the block nonlinear Gauss-Seidel method. The key to successfully applying this optimizer is three types of auxiliary variables. Then, a coarse-to-fine segmentation technique is developed to partition the deformed mesh into a small set of nearly discrete developable patches. Finally, we refine the segmented mesh to reduce the discrete Gaussian curvature while keeping the patches smooth and the approximation error small. In practice, our algorithm achieves a favorable tradeoff between the number of developable patches and the approximation error. We demonstrate the feasibility and practicability of our method over various examples, including seventeen physical manufacturing models with paper.

1. Alexandre Binninger, Floor Verhoeven, Philipp Herholz, and Olga Sorkine-Hornung. 2021. Developable Approximation via Gauss Image Thinning. Comput. Graph. Forum 40, 5 (2021), 289–300.Google ScholarCross Ref
2. Pengbo Bo and Wenping Wang. 2007. Geodesic-controlled developable surfaces for modeling paper bending. Comput. Graph. Forum 26, 3 (2007), 365–374.Google ScholarCross Ref
3. H-Y Chen, I-K Lee, Stefan Leopoldseder, Helmut Pottmann, Thomas Randrup, and Johannes Wallner. 1999. On surface approximation using developable surfaces. Graphical Models and Image Processing 61, 2 (1999), 110–124.Google ScholarCross Ref
4. Eitan Grinspun, Anil N Hirani, Mathieu Desbrun, and Peter Schröder. 2003. Discrete shells. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation. 62–67.Google ScholarDigital Library
5. John R Hurley and Raymond B Cattell. 1962. The Procrustes program: Producing direct rotation to test a hypothesized factor structure. Behavioral science 7, 2 (1962), 258.Google Scholar
6. Alexandra Ion, Michael Rabinovich, Philipp Herholz, and Olga Sorkine-Hornung. 2020. Shape approximation by developable wrapping. ACM Trans. Graph. 39, 6 (2020).Google ScholarDigital Library
7. Caigui Jiang, Cheng Wang, Florian Rist, Johannes Wallner, and Helmut Pottmann. 2020. Quad-mesh based isometric mappings and developable surfaces. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
8. Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-charts: Quasi-developable mesh segmentation. Comput. Graph. Forum 24, 3 (2005), 581–590.Google ScholarCross Ref
9. Martin Kilian, Simon Flöry, Zhonggui Chen, Niloy J Mitra, Alla Sheffer, and Helmut Pottmann. 2008. Curved folding. ACM Trans. Graph. 27, 3 (2008), 1–9.Google ScholarDigital Library
10. Hao Liu, Xiao-Teng Zhang, Xiao-Ming Fu, Zhi-Chao Dong, and Ligang Liu. 2019. Computational Peeling Art Design. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
11. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive Parameterizations. ACM Trans. Graph. 37, 4 (2018).Google ScholarDigital Library
12. Yang Liu, Helmut Pottmann, Johannes Wallner, Yong-Liang Yang, and Wenping Wang. 2006. Geometric Modeling with Conical Meshes and Developable Surfaces. In ACM SIGGRAPH 2006 Papers. 681–689.Google Scholar
13. Yong-Jin Liu, Yu-Kun Lai, and Shimin 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
14. Fady Massarwi, Craig Gotsman, and Gershon Elber. 2007. Papercraft models using generalized cylinders. In 15th Pacific Conference on Computer Graphics and Applications (PG’07). 148–157.Google ScholarDigital Library
15. Jun Mitani and Hiromasa Suzuki. 2004. Making papercraft toys from meshes using strip-based approximate unfolding. ACM Trans. Graph. 23, 3 (2004), 259–263.Google ScholarDigital Library
16. Helmut Pottmann and Johannes Wallner. 1999. Approximation algorithms for developable surfaces. Comput. Aided Geom. Des. 16, 6 (1999), 539–556.Google ScholarCross Ref
17. Michael Rabinovich, Tim Hoffmann, and Olga Sorkine-Hornung. 2018a. Discrete geodesic nets for modeling developable surfaces. ACM Trans. Graph. 37, 2 (2018).Google ScholarDigital Library
18. Michael Rabinovich, Tim Hoffmann, and Olga Sorkine-Hornung. 2018b. The shape space of discrete orthogonal geodesic nets. ACM Trans. Graph. 37, 6 (2018).Google ScholarDigital Library
19. Kenneth Rose, Alla Sheffer, Jamie Wither, Marie-Paule Cani, and Boris Thibert. 2007. Developable surfaces from arbitrary sketched boundaries. In Comput. Graph. Forum. 163–172.Google Scholar
20. Camille Schreck, Damien Rohmer, Stefanie Hahmann, Marie-Paule Cani, Shuo Jin, Charlie CL Wang, and Jean-Francis Bloch. 2015. Nonsmooth developable geometry for interactively animating paper crumpling. ACM Trans. Graph. 35, 1 (2015), 1–18.Google ScholarDigital Library
21. Silvia Sellán, Noam Aigerman, and Alec Jacobson. 2020. Developability of heightfields via rank minimization. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
22. Idan Shatz, Ayellet Tal, and George Leifman. 2006. Paper craft models from meshes. The Visual Computer 22, 9 (2006), 825–834.Google ScholarDigital Library
23. Justin Solomon, Etienne Vouga, Max Wardetzky, and Eitan Grinspun. 2012. Flexible developable surfaces. Comput. Graph. Forum 31, 5 (2012), 1567–1576.Google ScholarDigital Library
24. Oded Stein, Eitan Grinspun, and Keenan Crane. 2018. Developability of triangle meshes. ACM Trans. Graph. 37, 4 (2018).Google ScholarDigital Library
25. Chengcheng Tang, Pengbo Bo, Johannes Wallner, and Helmut Pottmann. 2016. Interactive design of developable surfaces. ACM Trans. Graph. 35, 2 (2016), 1–12.Google ScholarDigital Library
26. Weihua Tong, Xiankang Yang, Maodong Pan, and Falai Chen. 2020. Spectral Mesh Segmentation via ℓ0 Gradient Minimization. IEEE. T. Vis. Comput. Gr. 26, 04 (2020), 1807–1820.Google Scholar
27. Charlie CL Wang and Kai Tang. 2004. Achieving developability of a polygonal surface by minimum deformation: a study of global and local optimization approaches. The Visual Computer 20, 8 (2004), 521–539.Google ScholarDigital Library
28. Hui Wang, Davide Pellis, Florian Rist, Helmut Pottmann, and Christian Müller. 2019. Discrete geodesic parallel coordinates. ACM Trans. Graph. 38, 6 (2019).Google ScholarDigital Library