New algorithm for modern quilting

Developing a foundation paper piece quilt pattern -- which looks similar to a paint-by-numbers outline -- is often non-intuitive. There are few formal guidelines for patterning and those that do exist are insufficient to assure a successful result.

"Quilting has this rich tradition and people make these very personal, cherished heirlooms but paper piece quilting often requires that people work from patterns that other people designed," said Leake, who is a member of the lab of Maneesh Agrawala, the Forest Baskett Professor of Computer Science and director of the Brown Institute for Media Innovation at Stanford. "So, we wanted to produce a digital tool that lets people design the patterns that they want to design without having to think through all of the geometry, ordering and constraints."

A paper describing this work is published and will be presented at the computer graphics conference SIGGRAPH 2021 in August.

Respecting the craft

In describing the allure of paper piece quilts, Leake cites the modern aesthetic and high level of control and precision. The seams of the quilt are sewn through the paper pattern and, as the seaming process proceeds, the individual pieces of fabric are flipped over to form the final design. All of this "sew and flip" action means the pattern must be produced in a careful order.

Poorly executed patterns can lead to loose pieces, holes, misplaced seams and designs that are simply impossible to complete. When quilters create their own paper piecing designs, figuring out the order of the seams can take considerable time -- and still lead to unsatisfactory results.

"The biggest challenge that we're tackling is letting people focus on the creative part and offload the mental energy of figuring out whether they can use this technique or not," said Leake, who is lead author of the SIGGRAPH paper. "It's important to me that we're really aware and respectful of the way that people like to create and that we aren't over-automating that process."

This isn't Leake's first foray into computer-aided quilting. She previously designed a tool for improvisational quilting, which she presented at the human-computer interaction conference CHI in May.

Quilting theory

Developing the algorithm at the heart of this latest quilting software required a substantial theoretical foundation. With few existing guidelines to go on, the researchers had to first gain a more formal understanding of what makes a quilt paper piece-able, and then represent that mathematically.

They eventually found what they needed in a particular graph structure, called a hypergraph. While so-called "simple" graphs can only connect data points by lines, a hypergraph can accommodate overlapping relationships between many data points. (A Venn diagram is a type of hypergraph.) The researchers found that a pattern will be paper piece-able if it can be depicted by a hypergraph whose edges can be removed one at a time in a specific order -- which would correspond to how the seams are sewn in the pattern.

The prototype software allows users to sketch out a design and the underlying hypergraph-based algorithm determines what paper foundation patterns could make it possible -- if any. Many designs result in multiple pattern options and users can adjust their sketch until they get a pattern they like. The researchers hope to make a version of their software publicly available this summer.

"I didn't expect to be writing my computer science dissertation on quilting when I started," said Leake. "But I found this really rich space of problems involving design and computation and traditional crafts, so there have been lots of different pieces we've been able to pull off and examine in that space."

Researchers from University of California, Berkeley and Cornell University are co-authors of this paper. Agrawala is also an affiliate of the Institute for Human-Centered Artificial Intelligence (HAI).