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

  • ©Mackenzie Leake, Gilbert Bernstein, Abe Davis, and Maneesh Agrawala




    A mathematical foundation for foundation paper pieceable quilts



    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

ACM Digital Library Publication: