“Evolutionary Piecewise Developable Approximations” by Zhao, Li, Zhang, Fang, Liu, et al. …
Conference:
Type:
Title:
- Evolutionary Piecewise Developable Approximations
Session/Category Title: All About Meshes
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We propose a novel method to compute high-quality piecewise developable approximations for triangular meshes. Central to our approach is an evolutionary genetic algorithm for optimizing the combinatorial and discontinuous fitness function, including the approximation error, the number of patches, the patch boundary length, and the penalty for small patches and narrow regions within patches. The genetic algorithm’s operations (i.e., initialization, selection, mutation, and crossover) are explicitly designed to minimize the fitness function.The main challenge is evaluating the fitness function’s approximation error as it requires developable patches, which are difficult or time-consuming to obtain. Resolving the challenge is based on a critical observation: the approximation error and the mapping distortion between an input surface and its developable approximation are positively correlated empirically. To efficiently measure distortion without explicitly generating developable shapes, we creatively use conformal mapping techniques. Then, we control the mapping distortion at a relatively low level to achieve high shape similarity in the genetic algorithm.The feasibility and effectiveness of our method are demonstrated over 240 complex examples. Compared with the state-of-the-art methods, our results have much smaller approximation errors, fewer patches, shorter patch boundaries, and fewer small patches and narrow regions.
References:
1. Pierre Alliez, Eric Colin De Verdire, Olivier Devillers, and Martin Isenburg. 2003. Isotropic surface remeshing. In 2003 Shape Modeling International. IEEE, 49–58.
2. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. Comput. Graph. Forum 27, 2 (2008), 449–458.
3. Bernd Bickel, Paolo Cignoni, Luigi Malomo, and Nico Pietroni. 2018. State of the art on stylized fabrication. Comput. Graph. Forum 37, 6 (2018), 325–342.
4. 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.
5. Pengbo Bo and Wenping Wang. 2007. Geodesic-controlled developable surfaces for modeling paper bending. Comput. Graph. Forum 26, 3 (2007), 365–374.
6. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Lévy. 2010. Polygon mesh processing. CRC press.
7. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational shape approximation. ACM Trans. Graph. 23, 3 (2004), 905–914.
8. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 3 (2002), 209–218.
9. Corentin Dumery, François Protais, Sébastien Mestrallet, Christophe Bourcier, and Franck Ledoux. 2022. Evocube: A Genetic Labelling Framework for Polycube-Maps. Comput. Graph. Forum 41, 6 (2022), 467–479.
10. Michal Edelstein, Danielle Ezuz, and Mirela Ben-Chen. 2020. ENIGMA: evolutionary non-isometric geometry MAtching. ACM Trans. Graph. 39, 4 (2020), 112–1.
11. Qing Fang, Wenqing Ouyang, Mo Li, Ligang Liu, and Xiao-Ming Fu. 2021. Computing sparse cones with bounded distortion for conformal parameterizations. ACM Trans. Graph. 40, 6 (2021), 1–9.
12. Qing Fang, Zheng-Yu Zhao, Zhong-Yuan Liu, Ligang Liu, and Xiao-Ming Fu. 2020. Metric first reconstruction for interactive curvature-aware modeling. Computer Aided Design 126 (2020), 102863.
13. 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.
14. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
15. Alexandra Ion, Michael Rabinovich, Philipp Herholz, and Olga Sorkine-Hornung. 2020. Shape approximation by developable wrapping. ACM Trans. Graph. 39, 6 (2020).
16. 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).
17. Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-charts: Quasi-developable mesh segmentation. Comput. Graph. Forum 24, 3 (2005), 581–590.
18. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412–438.
19. 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.
20. Mina Konaković, Keenan Crane, Bailin Deng, Sofien Bouaziz, Daniel Piker, and Mark Pauly. 2016. Beyond developable: computational design and fabrication with auxetic materials. ACM Trans. Graph. 35, 4 (2016), 1–11.
21. L Kou, George Markowsky, and Leonard Berman. 1981. A fast algorithm for Steiner trees. Acta informatica 15, 2 (1981), 141–145.
22. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (2002), 362–371.
23. Mo Li, Qing Fang, Wenqing Ouyang, Ligang Liu, and Xiao-Ming Fu. 2022. Computing Sparse Integer-Constrained Cones for Conformal Parameterizations. ACM Trans. Graph. 41, 4 (2022).
24. Max Limper, Nicholas Vining, and Alla Sheffer. 2018. Box cutter: atlas refinement for efficient packing via void elimination. ACM Trans. Graph. 37, 4 (2018), 153–1.
25. 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.
26. 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.
27. Jun Mitani and Hiromasa Suzuki. 2004. Making papercraft toys from meshes using strip-based approximate unfolding. ACM Trans. Graph. 23, 3 (2004), 259–263.
28. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4 (2012), 1–11.
29. Rahul Narain, Tobias Pfaff, and James F O’Brien. 2013. Folding and crumpling adaptive sheets. ACM Trans. Graph. 32, 4 (2013), 1–8.
30. Michael Rabinovich, Tim Hoffmann, and Olga Sorkine-Hornung. 2018a. Discrete geodesic nets for modeling developable surfaces. ACM Trans. Graph. 37, 2 (2018).
31. Michael Rabinovich, Tim Hoffmann, and Olga Sorkine-Hornung. 2018b. The shape space of discrete orthogonal geodesic nets. ACM Trans. Graph. 37, 6 (2018).
32. 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.
33. Yusuf Sahillioğlu. 2018. A genetic isometric shape correspondence algorithm with adaptive sampling. ACM Trans. Graph. 37, 5 (2018), 1–14.
34. 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.
35. Silvia Sellán, Noam Aigerman, and Alec Jacobson. 2020. Developability of heightfields via rank minimization. ACM Trans. Graph. 39, 4 (2020).
36. Nicholas Sharp and Keenan Crane. 2018. Variational surface cutting. ACM Trans. Graph. 37, 4 (2018), 1–13.
37. Idan Shatz, Ayellet Tal, and George Leifman. 2006. Paper craft models from meshes. The Visual Computer 22, 9 (2006), 825–834.
38. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal cone singularities for conformal flattening. ACM Trans. Graph. 37, 4 (2018), 1–17.
39. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. In ACM SIGGRAPH 2008 papers. 1–11.
40. Oded Stein, Eitan Grinspun, and Keenan Crane. 2018. Developability of triangle meshes. ACM Trans. Graph. 37, 4 (2018).
41. Chengcheng Tang, Pengbo Bo, Johannes Wallner, and Helmut Pottmann. 2016. Interactive design of developable surfaces. ACM Trans. Graph. 35, 2 (2016), 1–12.
42. 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.
43. Hui Wang, Davide Pellis, Florian Rist, Helmut Pottmann, and Christian Müller. 2019. Discrete geodesic parallel coordinates. ACM Trans. Graph. 38, 6 (2019).
44. Sameh M Yamany, Mohamed N Ahmed, and Aly A Farag. 1999. A new genetic-based technique for matching 3-D curves and surfaces. Pattern Recognition 32, 10 (1999), 1817–1820.
45. Ran Yi, Yong-Jin Liu, and Ying He. 2018. Delaunay mesh simplification with differential evolution. ACM Trans. Graph. 37, 6 (2018), 1–12.
46. Wen-Xiang Zhang, Qi Wang, Jia-Peng Guo, Shuangming Chai, Ligang Liu, and Xiao-Ming Fu. 2022. Constrained Remeshing Using Evolutionary Vertex Optimization. Comput. Graph. Forum 41, 2 (2022), 237–247.
47. Zheng-Yu Zhao, Qing Fang, Wenqing Ouyang, Zheng Zhang, Ligang Liu, and Xiao-Ming Fu. 2022. Developability-driven piecewise approximations for triangular meshes. ACM Trans. Graph. 41, 4 (2022), 1–13.
48. Zichun Zhong, Liang Shuai, Miao Jin, and Xiaohu Guo. 2014. Anisotropic surface meshing with conformal embedding. Graphical models 76, 5 (2014), 468–483.
