“PH-CPF: planar hexagonal meshing using coordinate power fields” by Pluta, Edelstein, Vaxman and Ben-Chen

We present a new approach for computing planar hexagonal meshes that approximate a given surface, represented as a triangle mesh. Our method is based on two novel technical contributions. First, we introduce Coordinate Power Fields, which are a pair of tangent vector fields on the surface that fulfill a certain continuity constraint. We prove that the fulfillment of this constraint guarantees the existence of a seamless parameterization with quantized rotational jumps, which we then use to regularly remesh the surface. We additionally propose an optimization framework for finding Coordinate Power Fields, which also fulfill additional constraints, such as alignment, sizing and bijectivity. Second, we build upon this framework to address a challenging meshing problem: planar hexagonal meshing. To this end, we suggest a combination of conjugacy, scaling and alignment constraints, which together lead to planarizable hexagons. We demonstrate our approach on a variety of surfaces, automatically generating planar hexagonal meshes on complicated meshes, which were not achievable with existing methods.

1. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. 35, 6, Article 217 (Nov. 2016), 14 pages.Google ScholarDigital Library
2. Henrik Almegaard, Anne Bagger, Jens Gravesen, Bert Jüttler, and Zbynek Šír. 2007. Surfaces with Piecewise Linear Support Functions over Spherical Triangulations. In Mathematics of Surfaces XII, Ralph Martin, Malcolm Sabin, and Joab Winkler (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 42–63.Google Scholar
3. Miguel Argaez, Carlos Ramirez, and Reinaldo Sanchez. 2011. An l1-algorithm for underdetermined systems and applications. In 2011 Annual Meeting of the North American Fuzzy Information Processing Society. IEEE, 1–6.Google ScholarCross Ref
4. Omri Azencot, Etienne Corman, Mirela Ben-Chen, and Maks Ovsjanikov. 2017. Consistent functional cross field design for mesh quadrangulation. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–13.Google ScholarDigital Library
5. Omri Azencot, Orestis Vantzos, Max Wardetzky, Martin Rumpf, and Mirela Ben-Chen. 2015. Functional thin films on surfaces. In Proceedings of the 14th ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 137–146.Google ScholarDigital Library
6. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid maps for reliable quad meshing. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–12.Google ScholarDigital Library
7. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing: A Survey. Comput. Graph. Forum 32, 6 (2013), 51–76.Google ScholarDigital Library
8. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Transactions On Graphics (TOG) 28, 3 (2009), 1–10.Google ScholarDigital Library
9. Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic Global Parametrization with Rational Holonomy. ACM Trans. Graph. 36, 4, Article 89 (2017), 15 pages.Google ScholarDigital Library
10. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized global parametrization. Acm Transactions On Graphics (TOG) 34, 6 (2015), 1–12.Google ScholarDigital Library
11. Marcel Campen, Moritz Ibing, Hans-Christian Ebke, Denis Zorin, and Leif Kobbelt. 2016. Scale-invariant directional alignment of surface parametrizations. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 1–10.Google Scholar
12. Paolo Cignoni et al. 2020. vcglib: Visualization and Computer Graphics Library. https://github.com/cnr-isti-vclab/vcglib/.Google Scholar
13. Marinella Contestabile and Ornella Iuorio. 2019. A digital design process for shell structures. Proceedings of IASS Annual Symposia 2019, 15 (2019), 1–8.Google Scholar
14. Alexander Peña De Leon. 2012. Rationalisation of freeform façades: A technique for uniform hexagonal panelling. In In Beyond codes and pixels: Proceedings of the 17th International Conference on Computer-Aided Architectural Design Research in Asia. 243–251.Google Scholar
15. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Designing N-PolyVector fields with complex polynomials. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 1–11.Google ScholarDigital Library
16. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable PolyVector Fields. ACM Trans. Graph. 34, 4, Article 38 (2015), 12 pages.Google ScholarDigital Library
17. Manfredo P Do Carmo. 2016. Differential geometry of curves and surfaces: revised and updated second edition. Courier Dover Publications.Google Scholar
18. Luther Pfahler Eisenhart. 1960. A treatise on the differential geometry of curves and surfaces. Dover, New York.Google Scholar
19. Nahum Farchi and Mirela Ben-Chen. 2018. Integer-only cross field computation. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–13.Google ScholarDigital Library
20. Xiao-Ming Fu and Yang Liu. 2016. Computing Inversion-Free Mappings by Simplex Assembly. ACM Transactions on Graphics (SIGGRAPH Asia) 35, 6 (2016).Google Scholar
21. Henri Gavin. 2020. The Levenberg-Marquardt method for nonlinear least squares curve-fitting problems. Department of Civil and Environmental Engineering, Duke University (2020), 1–19. http://people.duke.edu/~hpgavin/ce281/lm.pdfGoogle Scholar
22. Viktoria Henriksson and Maria Hult. 2015. Rationalizing freeform architecture-Surface discretization and multi-objective optimization. Master’s thesis. https://hdl.handle.net/20.500.12380/231658Google Scholar
23. Kai Hormann, Bruno Lévy, and Alla Sheffer. 2007. Mesh parameterization: Theory and practice. SIGGRAPH 2007 Course Notes (2007).Google ScholarDigital Library
24. Caigui Jiang, Chengcheng Tang, Amir Vaxman, Peter Wonka, and Helmut Pottmann. 2015b. Polyhedral Patterns. ACM Trans. Graph. 34, 6, Article 172 (2015), 12 pages.Google ScholarDigital Library
25. Caigui Jiang, Jun Wang, Johannes Wallner, and Helmut Pottmann. 2014. Freeform honeycomb structures. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 185–194.Google Scholar
26. Tengfei Jiang, Xianzhong Fang, Jin Huang, Hujun Bao, Yiying Tong, and Mathieu Desbrun. 2015a. Frame Field Generation through Metric Customization. ACM Trans. Graph. 34, 4, Article 40 (2015), 11 pages.Google ScholarDigital Library
27. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. Quadcover-surface parameterization using branched coverings. In Computer graphics forum, Vol. 26. Wiley Online Library, 375–384.Google Scholar
28. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. ACM Transactions on Graphics (ToG) 32, 4 (2013), 1–10.Google ScholarDigital Library
29. Riccardo La Magna, Frédéric Waimer, and Jan Knippers. 2012. Nature-inspired generation scheme for shell structures. Proceedings of the International Symposium of the IASS-APCS Symposium, Seoul, South Korea, 2012 (2012).Google Scholar
30. John M. Lee. 2013. Introduction to smooth manifolds (2nd ed. ed.). Springer, New York.Google Scholar
31. Sven Leyffer and Ashutosh Mahajan. 2010. Nonlinear constrained optimization: methods and software. Argonee National Laboratory, Argonne, Illinois 60439 (2010).Google Scholar
32. Jian-Min Li. 2017. Timber shell structures: form-finding and structural analysis of actively bent grid shells and segmental plate shells. Stuttgart: Institute for Structural Design and Structural Design, University of Stutgart.Google Scholar
33. Jian-Min Li and Jan Knippers. 2015. Segmental Timber Plate Shell for the Landesgartenschau Exhibition Hall in Schwäbisch Gmünd—the Application of Finger Joints in Plate Structures. International Journal of Space Structures 30, 2 (2015), 123–139.Google ScholarCross Ref
34. Yufei Li, Yang Liu, and Wenping Wang. 2014. Planar hexagonal meshing for architecture. IEEE transactions on visualization and computer graphics 21, 1 (2014), 95–106.Google Scholar
35. Richard J Lisle. 2003. Dupin’s indicatrix: a tool for quantifying periclinal folds on maps. Geological magazine 140, 6 (2003), 721–726.Google Scholar
36. Hao-Yu Liu, Zhong-Yuan Liu, Zheng-Yu Zhao, Ligang Liu, and Xiao-Ming Fu. 2020. Practical Fabrication of Discrete Chebyshev Nets. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 13–26.Google Scholar
37. 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
38. Yang Liu, Weiwei Xu, Jun Wang, Lifeng Zhu, Baining Guo, Falai Chen, and Guoping Wang. 2011. General Planar Quadrilateral Mesh Design Using Conjugate Direction Field. ACM Trans. Graph. 30, 6 (2011), 1–10.Google ScholarDigital Library
39. Max Lyon, Marcel Campen, David Bommes, and Leif Kobbelt. 2019. Parametrization quantization with free boundaries for trimmed quad meshing. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–14.Google ScholarDigital Library
40. Romain Mesnil, Cyril Douthe, Olivier Baverel, and Bruno Léger. 2017. Generalised cyclidic nets for shape modelling in architecture. International Journal of Architectural Computing 15, 2 (2017), 148–168.Google ScholarCross Ref
41. Christian Müller. 2011. Conformal hexagonal meshes. Geometriae dedicata 154, 1 (2011), 27–46.Google Scholar
42. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-Aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (2014), 14 pages.Google ScholarDigital Library
43. Matthias Nieser, Jonathan Palacios, Konrad Polthier, and Eugene Zhang. 2011. Hexagonal global parameterization of arbitrary surfaces. IEEE Transactions on Visualization and Computer Graphics 18, 6 (2011), 865–878.Google ScholarDigital Library
44. Daniele Panozzo, Enrico Puppo, Marco Tarini, and Olga Sorkine-Hornung. 2014. Frame Fields: Anisotropic and Non-Orthogonal Cross Fields. ACM Trans. Graph. 33, 4, Article 134 (July 2014), 11 pages.Google ScholarDigital Library
45. Konrad Polthier and Eike Preuß. 2003. Identifying Vector Field Singularities Using a Discrete Hodge Decomposition. In Visualization and Mathematics III, Hans-Christian Hege and Konrad Polthier (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 113–134.Google Scholar
46. Helmut Pottmann. 2007. Architectural geometry. Vol. 10. Bentley Institute Press.Google Scholar
47. Helmut Pottmann, Michael Eigensatz, Amir Vaxman, and Johannes Wallner. 2015. Architectural geometry. Computers & Graphics 47 (2015), 145 — 164.Google ScholarDigital Library
48. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4 (2006), 1460–1485.Google ScholarDigital Library
49. Fernando Romero and Armando Ramos. 2013. Bridging a Culture: The Design of Museo Soumaya. Architectural Design 83, 2 (2013), 66–69.Google ScholarCross Ref
50. Andrew O Sageman-Furnas, Albert Chern, Mirela Ben-Chen, and Amir Vaxman. 2019. Chebyshev nets from commuting PolyVector fields. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–16.Google ScholarDigital Library
51. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally injective mappings. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 125–135.Google Scholar
52. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh parameterization methods and their applications. Foundations and Trends® in Computer Graphics and Vision 2, 2 (2006), 105–171.Google ScholarCross Ref
53. Daniel Sonntag, Lotte Aldinger, Simon Bechert, Martin Alvarez, Abel Groenewolt, Oliver David Krieg, Hans Jakob Wagner, Jan Knippers, and Achim Menges. 2019. Lightweight segmented timber shell for the Bundesgartenschau 2019 in Heilbronn. Proceedings of IASS Annual Symposia 26 (2019), 1–8.Google Scholar
54. Chengcheng Tang, Xiang Sun, Alexandra Gomes, Johannes Wallner, and Helmut Pottmann. 2014. Form-Finding with Polyhedral Meshes Made Simple. ACM Trans. Graph. 33, 4, Article 70 (2014), 9 pages.Google ScholarDigital Library
55. Xavier Tellier, Cyril Douthe, Laurent Hauswirth, and Olivier Baverel. 2020a. Caravel meshes: A new geometrical strategy to rationalize curved envelopes. Structures 28 (2020), 1210 — 1228.Google ScholarCross Ref
56. Xavier Tellier, Sonia Zerhouni, Guillaume Jami, Alexandre Le Pavec, Thibault Lenart, Mathieu Lerouge, Nicolas Leduc, Cyril Douthe, Laurent Hauswirth, and Olivier Baverel. 2020b. The Caravel heX-Mesh pavilion, illustration of a new strategy for gridshell rationalization. SN Applied Sciences 2 (2020), 1–12.Google ScholarCross Ref
57. Christian Troche. 2008. Planar hexagonal meshes by tangent plane intersection. Advances in architectural geometry 1, 57-60 (2008), 2.Google Scholar
58. C Troche. 2009. Planar hexagonal tesselation of freeform surfaces—manufacturing solutions and design potentials. In Proc. Design Modelling Symposium Berlin. 331–9.Google Scholar
59. Amir Vaxman. 2021. Directional Technical Reports: Seamless Integration. Google Scholar
60. Amir Vaxman et al. 2017. libhedra: geometric processing and optimization of polygonal meshes. https://github.com/avaxman/libhedra.Google Scholar
61. Amir Vaxman et al. 2019. Directional: A library for Directional Field Synthesis, Design, and Processing.Google Scholar
62. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional field synthesis, design, and processing. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 545–572.Google Scholar
63. Ryan Viertel and Braxton Osting. 2019. An approach to quad meshing based on harmonic cross-valued maps and the Ginzburg-Landau theory. SIAM Journal on Scientific Computing 41, 1 (2019), A452–A479.Google ScholarDigital Library
64. Hans Jakob Wagner, Martin Alvarez, Abel Groenewolt, and Achim Menges. 2020. Towards digital automation flexibility in large-scale timber construction: integrative robotic prefabrication and co-design of the BUGA Wood Pavilion. Construction Robotics (2020), 1–18.Google Scholar
65. Wenping Wang and Yang Liu. 2009. A note on planar hexagonal meshes. In Nonlinear Computational Geometry. Springer, 221–233.Google Scholar
66. Wenping Wang and Yang Liu. 2010. A Note on Planar Hexagonal Meshes. In Nonlinear Computational Geometry, Ioannis Z. Emiris, Frank Sottile, and Thorsten Theobald (Eds.). Springer New York, New York, NY, 221–233.Google Scholar
67. W Wang, Y Liu, D Yan, B Chan, R Ling, and F Sun. 2008. Hexagonal meshes with planar faces (TR-2008-13).Google Scholar
68. Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman. 2020. 2D Arrangements. In CGAL User and Reference Manual (5.2 ed.). CGAL Editorial Board. https://doc.cgal.org/5.2/Manual/packages.html#PkgArrangementOnSurface2Google Scholar
69. Mirko Zadravec, Alexander Schiftner, and Johannes Wallner. 2010. Designing Quad-dominant Meshes with Planar Faces. Computer Graphics Forum 29, 5 (2010), 1671–1679.Google ScholarCross Ref
70. Henrik Zimmer, Marcel Campen, Ralf Herkrath, and Leif Kobbelt. 2012. Variational tangent plane intersection for planar polygonal meshing. In AAG. 319–332.Google Scholar