Algorithms to Construct Designs for Foundation Paper Piecing of Quilt Patchwork Layers

Year: 2022 Authors: Anton Bakker; Tom Verhoeff

Core claim

Any polygonal mesh design can be transformed into a two-stage foundation paper piecing plan, with optimizations for fewer sections, pieces, and better layout.

Topics

foundation paper piecing, quilt patchwork, polygonal meshes, sewing-plan algorithms

Domains

computational geometry, polygonal tilings, graph-like meshes, optimization, quilt design, textile patterning, generative art, patchwork construction

Methods

recursive cutting, convex hull line selection, sewing-order planning, heuristic optimization

Media

fabric, paper foundation, quilt blocks, computer-generated renderings

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 2022 Conference Proceedings

Algorithms to Construct Designs for Foundation Paper Piecing of Quilt Patchwork Layers

Anton Bakker ${}^1$ and Tom Verhoeff ${}^2$

${}^1$ Norfolk, VA, USA; antonbakker.com, antonbakker30@gmail.com ${}^2$ Dept. of Math. & CS, Eindhoven University of Technology; T. Verhoeff@tue.nl

Abstract

We explore some algorithms to construct designs for foundation paper piecing. The input is a block consisting of multiple polygonal regions, and the output is a way to split the block into sections and each section into pieces, such that each section is foundation paper pieceable, and also the block is foundation paper pieceable from the sections. The output is accompanied by the order in which its pieces and sections must be sewn together. In particular, it is interesting that every design can be made foundation paper pieceable in at most two stages. We consider various criteria to optimize designs.

Introduction

Both authors have a background in designing mathematical art involving closed paths in 3D space. Bakker focuses on computational techniques to find closed paths in lattices satisfying structural constraints, including symmetries [1]. Verhoeff explores mathematical techniques to find closed paths, inspired by Koos Verhoeff [7], including paths that are not lattice based [6]. Bakker got interested in tilings, when Doris Schattschneider pointed him to the Conway criterion [5]. These criteria very much resemble the constraints he imposes on his 3D paths, but now applied to closed 2D paths. He incorporated in his software constraints that force parallel path segments and centro-symmetric path segments, so that closed 2D paths are constructed satisfying the Conway criterion. This way all kinds of nice tiles that allow periodic tilings can be generated.

Figure 1: Periodic tilings on quilts (computer generated images).

Periodic tilings make for nice quilt patterns (see Fig. 1). This naturally leads to the question of how to realize such tilings as a patchwork. One technique often employed in constructing a quilt top patchwork is foundation paper (FP) piecing. With FP piecing, the sewing plan is printed on a paper sheet, which also

Bakker and Verhoeff

serves as the foundation onto which pieces of fabric are stitched together, one by one. Each next piece is added by stitching it along a single straight seam. At the end, the foundation paper is removed (the stitching has conveniently perforated it to simplify this removal). The primary question we address is how to construct a sewing plan for a given tile. A secondary question is to ask for efficient or even optimal plans.

Definitions and Problem Statement

We will first give some (informal) definitions of the relevant concepts. We start from a polygonal tile satisfying the Conway criterion (here, 4 centro-symmetric sides; Fig. 2, left), so that it can be used in a periodic tiling (Fig. 2, middle). Next, we consider a unit cell for this tiling, that serves as block of a patchwork (Fig. 2, right). Unit cells typically are parallelograms (squares, rectangles, diamonds) or equilateral triangles. The tiling partitions the block into (colored) polygons. also known as a mesh consisting of faces and edges (the mesh in Fig. 2, right, has 5 faces). Usually the resulting mesh is not FP pieceable, that is, there exists no FP-piecing sewing plan to assemble all faces (being the pieces) into a completed block.

Figure 2: Tile satisfying Conway criteria (left); periodic tiling (middle); unit cell (right).

We want an algorithm to partition the mesh into sections and each section into pieces, such that each section is FP pieceable, and also the block is FP pieceable when using those sections as pieces. Note that this involves a two-stage approach to assemble a block. We show that no more than two stages are needed.

For mathematically precise definitions of mesh, seam, and sewing plan, and for the theorem that characterizes when a mesh is FP pieceable, see [4].

Algorithms

Our first algorithm is a straightforward way to achieve the intended goal.

1. If the mesh has no interior vertices (e.g., consists of a single face), then it is FP pieceable, because it only has non-intersecting interior edges that cut across the entire region. Return a list of just one section, using the interior edges as seams between pieces (the sewing order is easy to determine).
2. If it has interior vertices, find a line through an interior vertex of the mesh, such that no interior vertices appear on one side. This is always possible (use convex hull; Fig. 3, left). We optimize this step later.
3. The region without interior points serves as our last section to sew on. It is FP pieceable (see Step 1).
4. Recurse at Step 1 with the mesh that remains on the other side of the cut line (Fig. 3, middle). The recursion terminates because in each step at least one interior vertex is removed (it becomes a boundary vertex). Append the section of Step 3 to the recursive result.

Algorithms to Construct Designs for Foundation Paper Piecing of Quilt Patchwork

Layers

Figure 3: Cut line in Step 2 (left); reduced mesh in Step 4 (middle); candidate cuts along edges (right).

The number of iterations can be reduced by using a cut line through two interior vertices in Step 2. This is always possible when there are at least two interior vertices, and was done in Fig. 3 (left). Thus, the number sections is at most $\lceil V/2\rceil +1$ , where $V$ is the number of interior vertices. If more points are collinear, this may offer an opportunity to reduce the number of sections further. The mesh in Fig.3 (left) has 12 interior vertices. Fig. 4 (left) shows a possible sewing plan with $\lceil 12/2\rceil +1=7$ sections resulting from this algorithm.

It would be even better if the cut line contains an interior mesh edge (or more than one), because that seam is certainly needed. This occurs in Fig. 4 (middle), resulting in fewer pieces. However, this is not always possible, as illustrated in Fig. 3 (right), where all candidate cut lines containing an interior mesh edge have interior vertices on both sides. Nevertheless, it turns out to be possible in many designs that we tried. See supplementary material for further examples with sewing plans.

29 pieces in 7 sections

23 pieces in 7 sections

20 pieces in 3 sections Figure 4: Three sewing plans for the tile of Fig. 2 with varying numbers of sections and pieces.

Another optimization is possible, because we use an unnecessarily strong (but easy to ensure) condition to get a region that is FP pieceable, viz. that the region contains no interior vertices. At the expense of some extra computation effort, we could check for each candidate line (through one or more interior vertices, preferably containing interior edges) whether either side is FP pieceable ‘as is’ (cf. [4]), even if it contains interior vertices or could be made FP pieceable with auxiliary cuts (for our algorithms, see the supplementary material). Fig. 4 (right) shows a sewing plan with only three sections, two of which contain interior vertices, but which nevertheless could be made FP pieceable with auxiliary cuts (dashed in the figure).

When multiple cut lines are possible, it is interesting to see what optimizations make sense. For instance, we may want to minimize (a) the number of sections; (b) the number of pieces; (c) the total seam length.

Bakker and Verhoeff

Moreover, we may want to avoid small pieces. E.g., the sewing plain in Fig. 4 (left) has some small pieces. This would be avoided by the vertical cut line through the rightmost two interior vertices (Fig. 4, middle). Another criterion could be the desire to print each section plan on one A4-sheet.

Conclusion

We have shown how to construct a two-stage foundation paper (FP) pieceable design for any polygonal mesh. The algorithm is fairly efficient and generally applicable. Bakker has implemented several variants using Rhino and Grasshopper, outputting annotated sewing instructions following the conventions of FP piecing. Computer renderings were created via Houdini.

Two other Bridges papers related to quilts are [2, 3]. The first covers algorithmic stitch patterns to combine quilt layers, which we also want to look into. The other is about symmetries of quilt designs.

For future work, we are interested in improving the implementation and optimization heuristics for these algorithms. We would like to apply them to create challenging and appealing designs for real-world use.

References

[1] A. Bakker and T. Verhoeff. “Artistic Rendering of Curves via Lattice Paths.” Proceedings of Bridges 2017: Mathematics, Art, Music, Architecture, Education, Culture. D. Swart, C. H. Séquin, and K. Fenyvesi, Eds. Phoenix, Arizona: Tessellations Publishing, 2017. pp. 447-450. Available online at http://archive.bridgesmathart.org/2017/bridges2017-447.pdf.

[2] C. Carlson, N. Paley, and T. Gray. “Algorithmic Quilting.” Proceedings of Bridges 2015: Mathematics, Music, Art, Architecture, Culture. K. Delp, C. S. Kaplan, D. McKenna, and R. Sarhangi, Eds. Phoenix, Arizona: Tessellations Publishing, 2015. pp. 231-238. Available online at http://archive.bridgesmathart.org/2015/bridges2015-231.html.

[3] K. Hebb. “The Mathematics of Quilting: A Quilter’s Tacit Knowledge of Symmetry, Tiling and Group Theory.” Meeting Alhambra, ISAMA-BRIDGES Conference Proceedings. J. Barrallo, N. Friedman, J. A. Maldonado, J. Martínez-Aroza, R. Sarhangi, and C. Séquin, Eds. Granada, Spain: University of Granada, 2003. pp. 511-520. Available online at http://archive.bridgesmathart.org/2003/bridges2003-511.html.

[4] M. Leake, G. Bernstein, A. Davis, and M. Agrawala. “A Mathematical Foundation for Foundation Paper Pieceable Quilts.” ACM Trans. Graph., vol. 40, no. 4, jul 2021, pp. 1-14. https://doi.org/10.1145/3450626.3459853.

[5] D. Schattschneider. “Will It Tile? Try the Conway Criterion!” Mathematics Magazine, vol. 53, no. 4, 1980, pp. 224-233. http://www.jstor.org/stable/2689617.

[6] M. van Veenendaal and T. Verhoeff. “Pretty 3D Polygons: Exploration and Proofs.” Proceedings of Bridges 2021: Mathematics, Art, Music, Architecture, Culture. D. Swart, F. Farris, and E. Torrence, Eds. Phoenix, Arizona: Tessellations Publishing, 2021. pp. 111-118. http://archive.bridgesmathart.org/2021/bridges2021-111.html.

[7] T. Verhoeff. “Some Memories of Koos Verhoeff (1927-2018).” Proceedings of Bridges 2018: Mathematics, Art, Music, Architecture, Education, Culture. E. Torrence, B. Torrence, C. Séquin, and K. Fenyvesi, Eds. Phoenix, Arizona: Tessellations Publishing, 2018. pp. 3-6. Available online at http://archive.bridgesmathart.org/2018/bridges2018-3.pdf.