“A mathematical foundation for foundation paper pieceable quilts” by Leake, Bernstein, Davis and Agrawala

Foundation paper piecing is a popular technique for constructing fabric patchwork quilts using printed paper patterns. But, the construction process imposes constraints on the geometry of the pattern and the order in which the fabric pieces are attached to the quilt. Manually designing foundation paper pieceable patterns that meet all of these constraints is challenging. In this work we mathematically formalize the foundation paper piecing process and use this formalization to develop an algorithm that can automatically check if an input pattern geometry is foundation paper pieceable. Our key insight is that we can represent the geometric pattern design using a certain type of dual hypergraph where nodes represent faces and hyperedges represent seams connecting two or more nodes. We show that determining whether the pattern is paper pieceable is equivalent to checking whether this hypergraph is acyclic, and if it is acyclic, we can apply a leaf-plucking algorithm to the hypergraph to generate viable sewing orders for the pattern geometry. We implement this algorithm in a design tool that allows quilt designers to focus on producing the geometric design of their pattern and let the tool handle the tedious task of determining whether the pattern is foundation paper pieceable.

1. Ingrid Alteneder. 2020. Adorable Animal Quilting. Page Street.Google Scholar
2. Aric Bartle, Alla Sheffer, Vladimir G. Kim, Danny M. Kaufman, Nicholas Vining, and Floraine Berthouzoz. 2016. Physics-Driven Pattern Adjustment for Direct 3D Garment Editing. ACM Trans. Graph. 35, 4, Article 50 (July 2016), 11 pages. Google ScholarDigital Library
3. Floraine Berthouzoz, Akash Garg, Danny M. Kaufman, Eitan Grinspun, and Maneesh Agrawala. 2013. Parsing Sewing Patterns into 3D Garments. ACM Trans. Graph. 32, 4, Article 85 (July 2013), 12 pages. Google ScholarDigital Library
4. Bernd Bickel, Paolo Cignoni, Luigi Malomo, and Nico Pietroni. 2018. State of the Art on Stylized Fabrication. Computer Graphics Forum 37 (2018). http://vcg.isti.cnr.it/Publications/2018/BCMP18Google Scholar
5. Johann Brault-Baron. 2016. Hypergraph Acyclicity Revisited. ACM Comput. Surv. 49, 3, Article 54 (Dec. 2016), 26 pages. Google ScholarDigital Library
6. Christopher Carlson, Nina Paley, Theodore Gray, et al. 2015. Algorithmic quilting. In Proceedings of Bridges 2015: Mathematics, Music, Art, Architecture, Culture. Tessellations Publishing, 231–238.Google Scholar
7. Marge M Coahran and Eugene Fiume. 2005. Sketch-Based Design for Bargello Quilts.. In SBM. 165–174.Google Scholar
8. Arnout Cosman. 2012. Quilt Assistant v2.24. https://quiltassistant.com/Google Scholar
9. Erik D Demaine and Martin L Demaine. 2002. Recent results in computational origami. In Origami3: Third International Meeting of Origami Science, Mathematics and Education. 3–16.Google Scholar
10. Phoebe Moon Designs. 2020. The seven deadly sins of foundation paper piecing. https://phoebemoon.com/tutorials/paper-piecing.htmGoogle Scholar
11. Mario Deuss, Daniele Panozzo, Emily Whiting, Yang Liu, Philippe Block, Olga Sorkine-Hornung, and Mark Pauly. 2014. Assembling self-supporting structures. ACM Trans. Graph. 33, 6 (2014), 214–1.Google ScholarDigital Library
12. Carol Doak. 2011. 50 Little Paper-Pieced Blocks: Full-Size Patterns to Mix & Match. C&T Publishing.Google Scholar
13. ElectricQuilt. 2017. Electric Quilt 8 (EQ8). https://electricquilt.com/Google Scholar
14. Ronald Fagin. 1983. Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30, 3 (July 1983), 514–550. Google ScholarDigital Library
15. Yohsuke Furuta, Nobuyuki Umetani, Jun Mitani, Takeo Igarashi, and Yukio Fukui. 2010. A Film Balloon Design System Integrated with Shell Element Simulation.. In Eurographics (Short Papers). 33–36.Google Scholar
16. Akash Garg, Andrew O Sageman-Furnas, Bailin Deng, Yonghao Yue, Eitan Grinspun, Mark Pauly, and Max Wardetzky. 2014. Wire mesh design. ACM Transactions on Graphics 33, 4 (2014).Google ScholarDigital Library
17. Hayley Grzych. 2018. Beginner-friendly foundation paper piecing. https://weallsew.com/beginner-friendly-foundation-paper-piecingGoogle Scholar
18. Emmanuel Iarussi, Wilmot Li, and Adrien Bousseau. 2015. WrapIt: Computer-Assisted Crafting of Wire Wrapped Jewelry. ACM Trans. Graph. 34, 6, Article 221 (Oct. 2015), 8 pages. Google ScholarDigital Library
19. Takeo Igarashi and John F Hughes. 2002. Clothing manipulation. In Proceedings of the 15th annual ACM symposium on User interface software and technology. 91–100.Google ScholarDigital Library
20. Yuki Igarashi and Takeo Igarashi. 2010. Holly: A drawing editor for designing stencils. IEEE Computer Graphics and Applications 30, 4 (2010), 8–14.Google ScholarDigital Library
21. Yuki Igarashi and Jun Mitani. 2015. Patchy: An interactive patchwork design system. In ACM SIGGRAPH 2015 Posters. 1–1.Google ScholarDigital Library
22. Sylvia Kaptein. 2020. Curved paper piecing: again, but different. https://blog.bernina.com/en/2020/01/curved-paper-piecing-again-but-different/Google Scholar
23. Lily Kerns. 2020. Designing a Foundation Pieced Block from a Photograph. https://www.academyofquilting.com/library/free-lessons/designing-a-foundation-pieced-block-from-a-photograph/Google Scholar
24. M. Kilian, S. Flöry, Z. Chen, N. J. Mitra, A. Sheffer, and H. Pottmann. 2008. Curved Folding. ACM Transactions on Graphics 27, 3 (2008), #75, 1–9.Google ScholarDigital Library
25. Maria Larsson, Hironori Yoshida, Nobuyuki Umetani, and Takeo Igarashi. 2020. Tsugite: Interactive Design and Fabrication of Wood Joints. In Proceedings of the 33rd Annual ACM Symposium on User Interface Software and Technology. 317–327.Google ScholarDigital Library
26. Yifei Li, David E Breen, James McCann, and Jessica Hodgins. 2019. Algorithmic Quilting Pattern Generation for Pieced Quilts. (2019), 9.Google Scholar
27. Chenxi Liu, Jessica Hodgins, and James McCann. 2017. Whole-cloth quilting patterns from photographs. In Proceedings of the Symposium on Non-Photorealistic Animation and Rendering – NPAR ’17. ACM Press, Los Angeles, California, 1–8. Google ScholarDigital Library
28. Nancy Mahoney. 2016. Learn to Paper Piece: A visual guide to piecing with precision. Martingale.Google Scholar
29. James McCann, Lea Albaugh, Vidya Narayanan, April Grow, Wojciech Matusik, Jennifer Mankoff, and Jessica Hodgins. 2016. A compiler for 3D machine knitting. ACM Transactions on Graphics 35, 4 (July 2016), 1–11. Google ScholarDigital Library
30. Jun Mitani and Hiromasa Suzuki. 2004. Making papercraft toys from meshes using strip-based approximate unfolding. ACM transactions on graphics (TOG) 23, 3 (2004), 259–263.Google Scholar
31. Yuki Mori and Takeo Igarashi. 2007. Plushie: an interactive design system for plush toys. In ACM SIGGRAPH 2007 papers. 45–es.Google ScholarDigital Library
32. Vidya Narayanan, Lea Albaugh, Jessica Hodgins, Stelian Coros, and James McCann. 2018. Automatic machine knitting of 3D meshes. ACM Transactions on Graphics (TOG) 37, 3 (2018), 1–15.Google ScholarDigital Library
33. PreQuilt. 2020. PreQuilt. https://prequilt.com/Google Scholar
34. Quiltster. 2020. Quiltster | Digital Quilt Planner. https://www.quiltster.com/Google Scholar
35. Sarah Elizabeth Sharp. 2018. Adventures in Paper Piecing & Design. Stash Books.Google Scholar
36. Mélina Skouras, Bernhard Thomaszewski, Bernd Bickel, and Markus Gross. 2012. Computational design of rubber balloons. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 835–844.Google Scholar
37. Mélina Skouras, Bernhard Thomaszewski, Peter Kaufmann, Akash Garg, Bernd Bickel, Eitan Grinspun, and Markus Gross. 2014. Designing inflatable structures. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–10.Google ScholarDigital Library
38. Gillian Smith. 2017. Generative Design for Textiles: Opportunities and Challenges for Entertainment AI.. In AIIDE. 115–121.Google Scholar
39. The Quilting Company. 2017. Quilting in America 2017. https://fabshopnet.com/wp-content/uploads/downloads/qia_summary.pdfGoogle Scholar
40. Cesar Torres, Wilmot Li, and Eric Paulos. 2016. ProxyPrint: Supporting Crafting Practice through Physical Computational Proxies. In Proceedings of the 2016 ACM Conference on Designing Interactive Systems (DIS ’16). Association for Computing Machinery, New York, NY, USA, 158–169. Google ScholarDigital Library
41. Nobuyuki Umetani, Danny M Kaufman, Takeo Igarashi, and Eitan Grinspun. 2011. Sensitive couture for interactive garment modeling and editing. ACM Trans. Graph. 30, 4 (2011), 90.Google ScholarDigital Library
42. Katja Wolff and Olga Sorkine-Hornung. 2019. Wallpaper Pattern Alignment along Garment Seams. ACM Trans. Graph. 38, 4, Article 62 (July 2019), 12 pages. Google ScholarDigital Library
43. Linda Worland. 2020. Designing Paper Pieced Patterns. https://www.paperpanache.com/designing-paper-piecingGoogle Scholar
44. Jiaxian Yao, Danny M Kaufman, Yotam Gingold, and Maneesh Agrawala. 2017. Interactive design and stability analysis of decorative joinery for furniture. ACM Transactions on Graphics (TOG) 36, 2 (2017), 1–16.Google ScholarDigital Library