An Algorithmic Approach to Obtain Generalized 2D Meander Patterns

Year: 2017 Authors: Saeid Zarrinmehr; Negar Kalantar; Ergun Akleman; Alireza Borhani; Mahmood Ettehad; Shinjiro Sueda

Core claim

A simple remeshing method can generate a large subset of generalized 2D meander patterns, including the original Ivanišević pattern and its extensions on arbitrary 2-manifold surfaces.

Topics

2D meander patterns, remeshing algorithm, general tilings, kerfing

Domains

graph combinatorics, topological meshes, symmetry groups, decorative pattern design, architectural kerfing, parametric illustration

Methods

remeshing, vertex insertion, rotation system, polygonal mesh processing

Media

polygonal meshes, wood panels, plywood

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2017 Conference Proceedings

An Algorithmic Approach to Obtain Generalized 2D Meander Patterns

Saeid Zarrinmehr

Negar Kalantar

Ergun Akleman

Alireza Borhani

Mahmood Ettehad

Shinjiro Sueda

Texas A&M University

Abstract

In this paper, we present an algorithmic approach to obtain a large subset of all possible 2D meander patterns with a simple remeshing algorithm. Our algorithm is basically a remeshing that can be applied to any polygonal mesh to produce 2D meander patterns. The algorithm, when applied to regular (4,4) tiling pattern, provides the original meander pattern invented by Dujam Ivanišević. Moreover, since these meander patterns are obtained by a remeshing algorithm, by changing parameters it is possible to control the local properties of the pattern for creating illustrations drawn with meander patterns.

(a) An example of 1D symmetric periodic meander patterns from Etruscan amphora from 470 B.C. [19].

(b) 2D symmetric periodic meander pattern designed by Dujam Ivanišević. Figure 1: 1D and 2D meander patterns. 2D meander pattern is invented by Dujam Ivanišević in 2014 [13].

1 Introduction and Motivation

Meander patterns are repeated labyrinth-like motifs that were commonly used in Hellenistic art to decorate borders or artworks [15]. Edwin Reissman recently classified a few meander patterns in Hellenistic art [19]. Figure 1 shows one of the most common meander patterns that consists of S-shaped patterns that are interlocked together. Examples known from the Hellenistic period are almost always one-dimensional repeated patterns as shown in this figure. In 2014, Dujam Ivanišević discovered a new 2D wallpaper meander pattern to be used as relief cuts to turn rigid materials into flexible panels [13] (See Figure 2). In architectural practice, the process of relief cutting to obtain flexible panels is called kerfing. After Ivanišević shared his discovery in 2015 in his instructables website [14], this particular pattern became so successful for kerfing that designers and architects used it to obtain flexible panels from wood and shared their experiences in blogs and YouTube such as [21]. In 2016, a few new 2D meander patterns were presented in architectural blogs [14, 18] (See Figure 3). However, the resulting kerfing from these patterns do not become as flexible as the original pattern, as visually demonstrated by Ivanišević [14].

Zarrinmehr et al.

Figure 2: Highly flexible plywood obtained by relief cutting by 2D meander pattern invented by Dujam Ivanišević (Images courtesy of Dujam Ivanišević).

(a) A pattern attributed to Robert Lang.

(b) A pattern introduced by an anonymous person.

(c) Extensions of the original pattern to circular patterns and hexagonal grid by M. S. Raynolds [18].

Figure 3: Other Symmetric Meander Patterns motivated by Dujam Ivanišević’s work.

One problem with these 2D meander patterns is that they are wallpaper patterns that can only be generated using basic symmetry operations such as rotation and translation [20, 5]. Using symmetry operations, we can only create exact copies of the original pattern. With such a wallpaper approach, it is hard to generalize these motifs into general tilings.

In this paper, we present an algorithmic approach to obtain a large subset of all possible 2D meander patterns with a simple remeshing method. Our algorithm is conceptually based on subdivision methods in computer graphics that can allow us to obtain any semi-regular mesh [8]. Similar to subdivision algorithms, our algorithm can be applied to any polygonal mesh such as regular or semi-regular polyhedra and allow us to create consistent meander patterns on any 2-manifold surface. In planar surfaces starting from regular (4,4) grid pattern [3, 4] pattern invented by Ivanišević.

To summarize, our contributions in this particular paper can be listed as follows: (1) We have developed a remeshing algorithm to generalize the 2D meander pattern into a more general setting; and (2) By applying this algorithm to polygonal meshes, we can cover any 2-manifold surface with a meander pattern.

2 General Meander Pattern Generation

Meander patterns consist of spiral forms, which are one of the most common shapes found in nature, mathematics, and art [1]. A particularly interesting use of spirals that is related to meander patterns is to cover surfaces with spiral patterns with interlocking $n$ -branched spiral trees. Such spiral tree structures are used to construct Erdely’s Spidrons [11, 12] and Akleman’s Twirling Sculptures [1]. Initial algorithm for creating twirling sculptures provides a base for our algorithm (See Figure 4).

The twirling sculpture algorithm starts with an initial 2-manifold polygonal mesh that is represented with the combinatorial structure of a graph and an associated “rotation system” [10, 2]. Figure 4a shows a portion of a 2-manifold mesh that consists of two quadrilaterals. In a 2-manifold mesh, every edge can be represented by two half-edges pointing in opposite directions [16]. The boundary of every face in a 2-manifold mesh can always be described with a cyclically ordered sequence of half-edges, which can be considered as n

An Algorithmic Approach to Obtain Generalized 2D Meander-Patterns

(a) Initial Mesh

(b) Half-Edges. Figure 4: The main algorithm for twirling sculptures creates interlocking spirals [1] (Images courtesy of Ergun Akleman).

(c) Rotation directions.

(d) Interlocking Spirals.

vectors going around the face in a consistent order (all clockwise or all counter-clockwise) (See Figure 4b). This consistent order is the key to creating interlocking spiral branches using rotation order, as shown in Figure 4d.

Our initial intuition was that a straightforward use of Akleman’s twirling sculpture algorithm [1]—with some minor adjustments—would be sufficient to obtain a generalized version 2D meander patterns. However, this intuition turned out to be wrong. Even though we did obtain flexible sheets, our sheets was not as flexible as the ones created with the original meander pattern. To identify the differences between various patterns, we first need a formal representation that can be used to classify these meander patterns.

In the 2D meander pattern invented by Ivanišević, each cut always consists of four spiral branches, and each spiral branch of any 4-branched spiral tree is interlocked with another spiral branch of another 4-branched spiral tree. On the other hand, the pattern in Figure 3b is different in the sense that each spiral tree consists of 6 branches, and each spiral branch of any 6-branched spiral block is also interlocked with another spiral branch of another 6-branched spiral tree. The left meander pattern in Figure 3c is different from the other two in the sense that (1) each spiral tree is 3-branched, and (2) each spiral branch of any 4-branched spiral tree is interlocked with two spiral branches of two other 3-branched spiral trees.

In conclusion, these meander patterns can be classified by two numbers: the number of spiral branches in a given spiral tree and the number of interlocking spirals. As a result, [4,2] refers the original meander pattern discovered by Ivanišević; [6,2] refers the meander pattern in Figure 3b; and [3,3] refers the left meander pattern in Figure 3c. On the other hand, the twirling sculptures algorithm turns an $n$ -valence vertex into an $n$ -branched spiral tree, and $m$ -sided face gives $m$ interlocked spiral branches. Therefore, (1) a regular rectangular grid turns into a [4,4] meander pattern; (2) a regular triangular grid turns into a [6,3] meander pattern; (3) a regular hexagonal grid turns into a [3,6] meander pattern. In other words, the straightforward

Figure 5: Interlocked Spirals on surfaces that is used to construct twirling sculptures (Images courtesy to Ergun Akleman).

Zarrinmehr et al.

1- Original polygon

2- Quadrangulation

3- 1st Rotation of Vertex_Indices

4- 2nd Rotation of Vertex_Indices

5-3rd Rotation of Vertex_Indices

6-4th Rotation of Vertex_Indices

7-5th Rotation of Vertex_Indices

8-6th Rotation of Vertex_Indices

9-The Resulting Relief-Cut Pattern Figure 6: The steps of basic algorithm.

application of the twirling sculpture algorithm cannot generate [4,2], [6,2], or [3,3] meander patterns.

A careful examination of the differences between the patterns shows that [4, 2], [6, 2] and [3, 3] are obtained by methodical “pruning” of some of the branches that remove some of the trees. For instance, [4, 2] is obtained by removing every other 4-branched tree in a [4, 4] pattern, and [3, 3] is obtained by removing every other 3-branched tree in a [6, 3] pattern. [6, 2] comes from a 6.3.6.3 semi-regular mesh (See [8] for the definition) and is obtained by removing 3-armed trees. Our initial finite element analysis also confirmed our intuition that the tree removal helps to make patterns more flexible.

Since spiral trees stem from vertices, if the vertices of the initial mesh is 2-colorable we can simply remove every other tree. This corresponds to creating only every other tree during remeshing process. In other words, if the mesh is vertex 2-colorable, we can always remove every other tree.

Although a general mesh is not necessarily vertex 2-colorable, there exists remeshing algorithms that can turn any polygonal mesh into meshes whose vertices are 2-colorable. In this paper, we chose vertex insertion [6], which is the remeshing algorithm of the popular Catmull-Clark subdivision scheme [9], to obtain vertex 2-colorable meshes.

2.1 Vertex Insertion Remeshing for 2D Meander Patterns

Vertex insertion is one of the simplest remeshing algorithms. It is obtained by first inserting a vertex in the center of each face and each edge. Then, each face-vertex (the vertices inserted to center of each each face) is connected with its edge-vertices (the vertices inserted to centers of boundary edges of the original face). This process turns each $m$-sided original face into $m$ quadrilaterals (See Figure 6.2). The vertices of the resulting mesh is always 2-colorable since we can always paint edge-vertices in one color and the rest (original vertices and face-vertices) in another color. The operation also creates a 2-manifold mesh, and therefore, rotation orders are still consistent as shown Figure 6.2.

We then apply a spiral creating algorithm starting from original and face-vertices. Since each spiral is created inside of a quadrilateral, this algorithm is relatively simple as shown in Figure 6. Since we do not use edge-vertices to create spirals, they are simply eliminated. This process turns any $m$-sided polygon into an $m$-branched spiral trees and each spiral branch of any spiral tree is interlocked with a spiral branch of another spiral tree. Therefore, this algorithm produces locally $(m,2)$ structures where $m$ can be any integer defined by number of sides of the initial faces of the initial mesh.

Figure 8 shows two semi-regular meander patterns obtained by applying our algorithm to regular and semi-regular tilings. The meander pattern shown in Figure 8b turned out to be very flexible.

3 Conclusion and Future Work

In this paper, we have introduced a remeshing algorithm to obtain generalized 2D meander patterns that are locally in the form of $(n,2)$. This method cannot create the $(3,3)$ and $(6,2)$ patterns shown in Figure 3. We have recently observed that it is possible to obtain the $(6,2)$ pattern with a variation of this algorithm by replacing vertex insertion with another simple remeshing algorithm [17]. We further observed that it is possible to generalize the $(3,3)$ pattern by proving honeycomb subdivision algorithm [7], which can produce 2-colorable vertices when applied meshes with 2-colorable vertices. We report these results in the near future once we have implemented them. This work was partially supported by the National Science Foundation under Grants NSF-EFRI-1240483, NSF-CMMI-1548243 and NSF-ECCS-1547075.

References

• [1] Ergun Akleman. Twirling sculptures. Journal of Mathematics, 3(1):1–10, 2009.
• [2] Ergun Akleman and Jianer Chen. Guaranteeing the 2-manifold property for meshes with doubly linked face list. International Journal of Shape Modeling, 5(02):159–177, 1999.
• [3] Ergun Akleman and Jianer Chen. Regular meshes. In Proceedings of the 2005 ACM symposium on Solid and physical modeling, pages 213–219. ACM, 2005.
• [4] Ergun Akleman and Jianer Chen. Regular mesh construction algorithms using regular handles. In Shape Modeling and Applications, 2006. SMI 2006. IEEE International Conference on, pages 27–27. IEEE, 2006.
• [5] Ergun Akleman, Jianer Chen, and Burak Meric. Web-based intuitive and effective design of symmetric tiles. In Proceedings of the 2000 ACM workshops on Multimedia, pages 1–4. ACM, 2000.
• [6] Ergun Akleman, Jianer Chen, Vinod Srinivasan, and Fusun Eryoldas. A new corner cutting scheme with tension and handle-face reconstruction. International Journal of Shape Modeling, 7(02):111–128, 2001.

[7] Ergun Akleman and Vinod Srinivasan. Honeycomb subdivision. In Proc. 17th Int. Symp. Computer & Information Sc, pages 137–141, 2002.

• [8] Ergun Akleman, Vinod Srinivasan, and Esan Mandal. Remeshing schemes for semi-regular tilings. In Shape Modeling and Applications, 2005 International Conference, pages 44–50. IEEE, 2005.
• [9] Edwin Catmull and James Clark. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer-aided design, 10(6):350–355, 1978.
• [10] Jack Edmonds. A combinatorial representation of polyhedral surfaces. Notices of the American Mathematical Society, 7(2), 1960.
• [11] Daniel Erdelyi. Some surprising properties of the spidrons. In Bridges’2005, Mathematical Connections in Art, Music and Science, pages 179–186, 2005.
• [12] Daniel Erdelyi. Spidron domain: The expending spidron universe. In Bridges’2006, Mathematical Connections in Art, Music and Science, pages 549–550, 2006.
• [13] Dujam Ivanišević. Super flexible laser cut plywood: lab.kofaktor.hr/en/portfolio/super-flexible-laser-cut-plywood/, 2014.
• [14] Dujam Ivanišević. Super flexible double curvature surface - laser cut plywood: www.instructables.com/id/super-flexible-duble-curvature-surface-laser-cut-p/, 2015.
• [15] Carl Kerenyi. Dionysos: Archetypal image of indestructible life, trans. Ralph Manheim. New Jersey, 1976.
• [16] Martti Mäntylä. An introduction to solid modeling. Computer science press, 1988.
• [17] Jörg Peters and Ulrich Reif. The simplest subdivision scheme for smoothing polyhedra. ACM Transactions on Graphics (TOG), 16(4):420–431, 1997.
• [18] Martin Raynsford. Flexible sheets: msraynsford.blogspot.com/2016/01/flexible-sheet-2.html, January 2016.
• [19] Erwin Reissmann. Different types of meander in greek art: blogmymaze.wordpress.com/2012/06/07/different-types-of-meanders-in-greek-art/, June 2012.
• [20] Doris Schattschneider. The plane symmetry groups: their recognition and notation. The American Mathematical Monthly, 85(6):439–450, 1978.
• [21] Jason Webb. Kerfing pattern: www.youtube.com/watch?v=sdojmhzc9yq, September 2015.

An Algorithmic Approach to Obtain Generalized 2D Meander-Patterns

(a) Initial Planar Mesh

(b) Application of Vertex Insertion Algorithm

(c) Rotation directions and vertex indexing. (d) Relief-cuts obtained by starting indexed vertices indicated in Figure 7c with red circles. (e) Final Relief-Cuts obtained by removing original mesh and quads. Figure 7: An example of overall algorithm working on a general mesh.

Zarrinmehr et al.

(a) 2D Meander-Patter obtained from Regular Hexagonal Tiling. (b) 2D Meander-Patter obtained from Semiregular 8.8.4 Tiling. Figure 8: Two examples of new 2D meander patterns obtained from regular and semi-regular tilings.