When it comes to quilting, determining the feasibility and order of steps in advanced patterns can be notoriously difficult – and frustrating. A new algorithm automates that process, allowing quilters to focus on design and creation.
Mackenzie Leake, a computer science graduate student at Stanford University, has been quilting since she was ten years old, but she never imagined it would be the subject of her doctoral dissertation. New prototype software for pattern-making for foundation paper piecing, a type of quilting that involves using a backing made of foundation paper to lay out and sew a quilted design, is included in that work.
Creating a foundation paper piece quilt pattern, which resembles a paint-by-numbers outline, is frequently counterintuitive. There are few formal patterning guidelines, and those that do exist are insufficient to ensure a successful outcome.
“Quilting has this rich tradition, and people make these very personal, cherished heirlooms, but paper piece quilting often requires people to work from patterns that other people designed,” said Leake, a member of Maneesh Agrawala’s lab at Stanford and the Forest Baskett Professor of Computer Science and director of the Brown Institute for Media Innovation. “As a result, we wanted to create a digital tool that allows people to design patterns without having to think about all of the geometry, ordering, and constraints.”
When it comes to the art of quilting, determining the feasibility and order of steps in advanced patterns can be notoriously complicated – and frustrating. By automating that process, a new algorithm enables quilters to focus on design and creation.
A paper describing this work is published and will be presented at the computer graphics conference SIGGRAPH 2021 in August.
Respecting the craft
Leake attributes the allure of paper piece quilts to their modern aesthetic and high level of control and precision. The quilt’s seams are sewn through the paper pattern, and the individual pieces of fabric are flipped over as the seaming process progresses to form the final design. All of this “sew and flip” action necessitates that the pattern be produced in a precise order.
Patterns that are poorly executed can result in loose pieces, holes, misplaced seams, and designs that are simply impossible to complete. When quilters design their own paper piecing patterns, determining the order of the seams can take a long time – and still result in unsatisfactory results.
“The biggest challenge we’re facing is allowing people to focus on the creative part while offloading the mental energy of determining whether they can use this technique or not,” said Leake, the paper’s lead author. “It’s critical to me that we’re aware of and respectful of how people like to create, and that we don’t over-automate that process.”
Leake’s first foray into computer-aided quilting isn’t her first. She previously created an improvisational quilting tool, which she presented at the CHI human-computer interaction conference in May.
Quilting theory
Creating the algorithm at the heart of this latest quilting software necessitated a significant theoretical foundation. With few existing guidelines to guide them, the researchers had to first gain a more formal understanding of what makes a quilt paper piece-able, and then mathematically represent that understanding.
They eventually found what they were looking for in a type of graph structure known as a hypergraph. A hypergraph can accommodate overlapping relationships between many data points, whereas “simple” graphs can only connect data points by lines. The researchers discovered that a pattern is paper piece-able if it can be represented by a hypergraph whose edges can be removed one at a time in a specific order – which corresponds to how the seams in the pattern are sewn.
The prototype software allows users to sketch out a design, and the underlying hypergraph-based algorithm determines whether any paper foundation patterns are possible. Many designs yield multiple pattern options, and users can tweak their sketch until they find one they like. The researchers hope to release a public version of their software this summer.
“When I started, I didn’t expect to be writing my computer science dissertation on quilting,” Leake said. “However, I discovered a really rich space of problems involving design, computation, and traditional crafts, so there have been a lot of different pieces we’ve been able to pull off and examine in that space.”
This paper was co-authored by researchers from the University of California, Berkeley, and Cornell University. Agrawala is also an Institute for Human-Centered Artificial Intelligence affiliate (HAI).
