“Unconventional patterns on surfaces” by Meekes and Vaxman

We present a unified method to meshing surfaces with unconventional patterns, both periodic and aperiodic. These patterns, which have so far been studied on the plane, are patterns comprising a small number of tiles, that do not necessarily exhibit translational periodicity. Our method generalizes the de Bruijn multigrid method to the discrete setting, and thus reduces the problem to the computation of N-Directional fields on triangle meshes. We work with all cases of directional symmetries that have been little studied, including odd and high N. We address the properties of such patterns on surfaces and the challenges in their construction, including order-preservation, seamlessness, duality, and singularities. We show how our method allows for the design of original and unconventional meshes that can be applied to architectural, industrial, and recreational design.

1. Ergun Akleman, Vinod Srinivasan, and Esan Mandal. 2005. Remeshing Schemes for Semi-Regular Tilings. In Proceedings of the International Conference on Shape Modeling and Applications 2005. 44–50.Google ScholarDigital Library
2. Pierre Alliez, Stéphane Tayeb, and Camille Wormser. 2021. 3D Fast Intersection and Distance Computation. In CGAL User and Reference Manual (5.2.1 ed.). CGAL Editorial Board. https://doc.cgal.org/5.2.1/Manual/packages.html#PkgAABBTreeGoogle Scholar
3. Robert Ammann, Branko Grünbaum, and Geoffrey Shephard. 1992. Aperiodic tiles. Discrete & Computational Geometry 8, 1 (1992), 1–25.Google ScholarDigital Library
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. Robert Berger. 1966. The undecidability of the domino problem. American Mathematical Soc.Google Scholar
6. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013. Integer-Grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4, Article 98 (July 2013), 12 pages. Google ScholarDigital Library
7. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-Integer Quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages. Google ScholarDigital Library
8. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-Up: Shaping Discrete Geometry with Projections. Comput. Graph. Forum 31, 5 (Aug. 2012), 1657–1667. Google ScholarDigital Library
9. Bram Custers and Amir Vaxman. 2020. Subdivision Directional Fields. ACM Transactions on Graphics (TOG) 39, 2 (2020), 1–20.Google ScholarDigital Library
10. Nicolaas de Bruijn. 1981. Algebraic theory of Penrose’s non-periodic tilings of the plane. Kon. Nederl. Akad. Wetensch. Proc. Ser. A 43, 84 (1981), 1–7.Google Scholar
11. Nicolaas de Bruijn. 1986. Dualization of multigrids. Le Journal de Physique Colloques 47, C3 (1986), C3–9.Google ScholarCross Ref
12. Fernando de Goes, Mathieu Desbrun, and Yiying Tong. 2016. Vector field processing on triangle meshes. In ACM SIGGRAPH 2016 Courses. 1–49.Google ScholarDigital Library
13. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Designing N-PolyVector Fields with Complex Polynomials. Comput. Graph. Forum 33, 5 (Aug. 2014), 1–11.Google ScholarDigital Library
14. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable PolyVector Fields. ACM Trans. Graph. 34, 4, Article 38 (July 2015), 12 pages. Google ScholarDigital Library
15. Hans-Christian Ebke, David Bommes, Marcel Campen, and Leif Kobbelt. 2013. QEx: Robust Quad Mesh Extraction. ACM Trans. Graph. 32, 6, Article 168 (Nov. 2013), 10 pages. Google ScholarDigital Library
16. Branko Grünbaum and Geoffrey Colin Shephard. 1987. Tilings and patterns. Courier Dover Publications.Google Scholar
17. James E Humphreys. 2012. Introduction to Lie algebras and representation theory. Vol. 9. Springer Science & Business Media.Google Scholar
18. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.Google Scholar
19. Caigui Jiang, Chengcheng Tang, Amir Vaxman, Peter Wonka, and Helmut Pottmann. 2015. Polyhedral Patterns. ACM Trans. Graph. 34, 6, Article 172 (Oct. 2015), 12 pages. Google ScholarDigital Library
20. 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
21. Craig S. Kaplan. 2017. Interwoven Islamic Geometric Patterns. In Proceedings of Bridges 2017: Mathematics, Art, Music, Architecture, Education, Culture, David Swart, Carlo H. Séquin, and Kristóf Fenyvesi (Eds.). Tessellations Publishing, Phoenix, Arizona, 71–78. Available online at http://archive.bridgesmathart.org/2017/bridges2017-71.pdf.Google Scholar
22. Craig S. Kaplan and David H. Salesin. 2004. Islamic Star Patterns in Absolute Geometry. ACM Trans. Graph. 23, 2 (April 2004), 97–119. Google ScholarDigital Library
23. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally Optimal Direction Fields. ACM Trans. Graph. 32, 4, Article 59 (July 2013), 10 pages. Google ScholarDigital Library
24. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2015. Stripe Patterns on Surfaces. ACM Trans. Graph. 34 (2015). Issue 4.Google Scholar
25. L. S. Levitov. 1988. Local rules for quasicrystals. Comm. Math. Phys. 119, 4 (1988), 627–666. https://projecteuclid.org:443/euclid.cmp/1104162600Google ScholarCross Ref
26. Yufei Li, Yang Liu, and Wenqiang Wang. 2014. Planar Hexagonal Meshing for Architecture. In IEEE Transactions on Visualization & Computer Graphics (ieee transactions on visualization & computer graphics ed.), Vol. 21. IEEE, 95. https://www.microsoft.com/en-us/research/publication/planar-hexagonal-meshing-architecture/Google Scholar
27. 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
28. Peter J. Lu and Paul J. Steinhardt. 2007. Decagonal and Quasi-Crystalline Tilings in Medieval Islamic Architecture. Science 315, 5815 (2007), 1106–1110. arXiv:https://science.sciencemag.org/content/315/5815/1106.full.pdf Google ScholarCross Ref
29. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-Aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (July 2014), 14 pages. Google ScholarDigital Library
30. Matthias Nieser. 2012. Parameterization and Tiling of Polyhedral Surfaces. Ph.D. Dissertation. Freie Universität Berlin.Google Scholar
31. 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
32. Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer Science & Business Media.Google Scholar
33. Jonathan Palacios and Eugene Zhang. 2007. Rotational symmetry field design on surfaces. ACM Transactions on Graphics (TOG) 26, 3 (2007), 55–es.Google ScholarDigital Library
34. Chi-Han Peng, Helmut Pottmann, and Peter Wonka. 2018. Designing Patterns Using Triangle-Quad Hybrid Meshes. ACM Trans. Graph. 37, 4, Article 107 (July 2018), 14 pages. Google ScholarDigital Library
35. Roger Penrose. 1979. Pentaplexity a class of non-periodic tilings of the plane. The mathematical intelligencer 2, 1 (1979), 32–37.Google Scholar
36. 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
37. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4 (Oct. 2006), 1460–1485. Google ScholarDigital Library
38. Raphael Robinson. 1971a. Undecidability and nonperiodicity for tilings of the plane. Inventiones mathematicae 12, 3 (1971), 177–209.Google Scholar
39. Raphael M. Robinson. 1971b. Undecidability and nonperiodicity for tilings of the plane. Inventiones mathematicae 12, 3 (1971), 177–209. Google ScholarCross Ref
40. 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
41. Majorie Senechal. 1995. Quasicrystals and Geometry. Cambridge Publishing Company.Google Scholar
42. D. Shechtman, I. Blech, D. Gratias, and J. W. Cahn. 1984. Metallic Phase with Long-Range Orientational Order and No Translational Symmetry. Phys. Rev. Lett. 53 (Nov 1984), 1951–1953. Issue 20. Google ScholarCross Ref
43. Toshikazu Sunada. 2006. Why do diamonds look so beautiful? Expositions of current mathematics 2006, Spring-Meeting (2006), 26–35.Google Scholar
44. Hamish Todd et al. 2018. A Class of Spherical Penrose-Like Tilings with Connections to Virus Protein Patterns and Modular Sculpture. In Bridges 2018 Conference Proceedings. Tessellations Publishing, 237–244.Google Scholar
45. Amir Vaxman. 2021. Directional Technical Reports: Seamless Integration. Google Scholar
46. Amir Vaxman et al. 2019. Directional: A library for Directional Field Synthesis, Design, and Processing. Google ScholarCross Ref
47. Amir Vaxman and Mirela Ben-Chen. 2015. Dupin meshing: A parameterization approach to planar hex-dominant meshing. Technion IIT CS Technical Report (2015).Google Scholar
48. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. Computer Graphics Forum 35, 2 (2016), 545–572. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.12864 Google ScholarDigital Library
49. Hans Walser. 2000. Lattice geometry and pythagorean triangles. Zentralblatt für Didaktik der Mathematik 32, 2 (2000), 32–35.Google ScholarCross Ref
50. 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.1.1 ed.). CGAL Editorial Board. https://doc.cgal.org/5.1.1/Manual/packages.html#PkgArrangementOnSurface2Google Scholar
51. Steffen Weißmann, Ulrich Pinkall, and Peter Schröder. 2014. Smoke Rings from Smoke. ACM Trans. Graph. 33, 4, Article 140 (July 2014), 8 pages. Google ScholarDigital Library
52. T Yamamoto. 1994. Validated computation of polynomial zeros by the Durand-Kerner method. Topics in validated computations (1994), 27–53.Google Scholar
53. Xingchen Ye, Jun Chen, M. Eric Irrgang, Michael Engel, Angang Dong, Sharon C. Glotzer, and Christopher B. Murray. 2017. Quasicrystalline nanocrystal superlattice with partial matching rules. Nature Materials 16, 2 (2017), 214–219. Google ScholarCross Ref