An unexpected craft takes center stage in computer science Ph.D. candidate Mackenzie Leake’s M.S. ’20 Ph.D. ’21 doctoral dissertation: quilting.
Foundation paper piecing quilting — popular in the emerging modern quilting community — presents challenges in its highly technical designs, so avid quilters often must use patterns developed by others, limiting artistic opportunity. To overcome this challenge, Leake designed a software program that uses mathematics and computer science to determine possible quilting patterns for any inputted design. The app was released on Aug. 18.
Growing up with a mother who taught quilting, Leake grew passionate about the art early on.
“In the back of my mind I’ve always had this dream project of incorporating quilting into my research,” Leake said. “I’ve been making quilts since I was 8 years old, so I’ve had that hobby for a long time.”
In foundation paper piecing quilting, quilters use a printed-paper pattern as a guide to sew two pieces of fabric together. To avoid an unsightly final product, fabric must be added in the order specified by the pattern, Leake said.
Leake hoped that through her research, she could “take all of this knowledge that quilters have built up over years and translate it into a more general problem where you could do something computational with it.”
Leake, who was the lead author on the study, was joined by Gilbert Bernstein Ph.D. ’19, a postdoctoral scholar at UC Berkeley and MIT; Abe Davis B.S. ’10, an assistant professor at Cornell; and Maneesh Agrawala B.S. ’94 Ph.D. ’02, the Forest Baskett Professor of CS and director of the Brown Institute for Media Innovation. They discovered that hypergraphs could transform their quilting problem into a mathematical one.
A hypergraph is a generalization of a graph in which an edge can join any number of vertices — unlike an ordinary graph, where an edge connects exactly two vertices.
“In a standard node-link graph, an edge can only connect two nodes. The idea of a hypergraph is that you have edges that connect more than two nodes,” Agrawala said.
With the ability to connect any number of vertices, hypergraphs can accurately depict overlapping relationships like those of quilt fabric pieces. In the paper, hypergraph vertices represent cloth pieces, and hyperedges represent seams, Agrawala said.
The team tried several representations before deciding a hypergraph was the right one, according to Leake.
“We tried a normal graph. … That was tricky because we couldn’t capture everything you might want to do in a simple way. It doesn’t capture that putting this cloth in place depends on multiple other things being done,” Bernstein said.
The research team then proved that viable quilt patterns have acyclic hypergraphs, ones with some useful properties.
“It’s easier to understand it as a process,” Bernstein said. “When you’re constructing something, you do one thing, then another thing, then another thing, and you arrive at the end of the process. There’s this dependency of how things have to happen. If that dependency is circular, then you can’t construct with it.”
Acyclic hypergraphs have non-circular dependency. Using this characteristic to their advantage, the team developed software that first determines if an input design can be represented by an acyclic hypergraph, and then outputs all possible quilting patterns.
While wanting to offload tedious tasks, Leake also wanted to make sure not to over-automate quilting, because “there’s still something that you want to personalize and design and get out of the process.”
The researchers’ work will be presented at the 2021 SIGGRAPH conference, which focuses on computer graphics and interactive techniques.
In the future, Leake hopes to investigate how people think about design.
“One area we’re interested in is how you actually learn before building these tools,” Leake said. “I think there’s a ton of interesting work in that space, and we’ll see what we can do there.”