“Semantics and Scheduling for Machine Knitting Compilers” by Lin, Narayanan, Ikarashi, Ragan-Kelley, Bernstein, et al. …

  • ©Jenny Lin, Vidya Narayanan, Yuka Ikarashi, Jonathan Ragan-Kelley, Gilbert Bernstein, and James (Jaimy) McCann

Conference:


Type:


Title:

    Semantics and Scheduling for Machine Knitting Compilers

Session/Category Title: Fabulous Fabrication: From Knitting to Circuits

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Machine knitting is a well-established fabrication technique for complex soft objects, and both companies and researchers have developed tools for generating machine knitting patterns. However, existing representations for machine knitted objects are incomplete (do not cover the complete domain of machine knittable objects) or overly specific (do not account for symmetries and equivalences among knitting instruction sequences). This makes it difficult to define correctness in machine knitting, let alone verify the correctness of a given program or program transformation. The major contribution of this work is a formal semantics for knitout, a low-level Domain Specific Language for knitting machines. We accomplish this by using what we call the fenced tangle, which extends concepts from knot theory to allow for a mathematical definition of knitting program equivalence that matches the intuition behind knit objects. Finally, using this formal representation, we prove the correctness of a sequence of rewrite rules; and demonstrate how these rewrite rules can form the foundation for higher-level tasks such as compiling a program for a specific machine and optimizing for time/reliability, all while provably generating the same knit object under our proposed semantics. By establishing formal definitions of correctness, this work provides a strong foundation for compiling and optimizing knit programs.

References:


    1. C.C. Adams. 1994. The Knot Book. W.H. Freeman, New York, NY.
    2. Roland Aigner, Mira Alida Haberfellner, and Michael Haller. 2022. SpaceR: Knitting Ready-Made, Tactile, and Highly Responsive Spacer-Fabric Force Sensors for Continuous Input. In Proceedings of the 35th Annual ACM Symposium on User Interface Software and Technology (Bend, OR, USA) (UIST ’22). Association for Computing Machinery, New York, NY, USA, Article 68, 15 pages.
    3. Lea Albaugh, Scott Hudson, and Lining Yao. 2019. Digital Fabrication of Soft Actuated Objects by Machine Knitting. In Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems (CHI ’19). Association for Computing Machinery, New York, NY, USA, 1–13.
    4. Lea Albaugh, James McCann, Scott E. Hudson, and Lining Yao. 2021. Engineering Multifunctional Spacer Fabrics Through Machine Knitting. In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems (Yokohama, Japan) (CHI ’21). Association for Computing Machinery, New York, NY, USA, Article 498, 12 pages.
    5. Sarah-Marie Belcastro. 2009. Every Topological Surface Can Be Knit: A Proof. Journal of Mathematics and the Arts 3, 2 (2009), 67–83.
    6. Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An Automated End-to-end Optimizing Compiler for Deep Learning. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (Carlsbad, CA, USA) (OSDI’18). USENIX Association, Berkeley, CA, USA, 579–594. http://dl.acm.org/citation.cfm?id=3291168.3291211
    7. Gabriel Cirio, Jorge Lopez-Moreno, and Miguel A. Otaduy. 2015. Efficient Simulation of Knitted Cloth Using Persistent Contacts. In Proceedings of the 14th ACM SIGGRAPH / Eurographics Symposium on Computer Animation (Los Angeles, California) (SCA ’15). Association for Computing Machinery, New York, NY, USA, 55–61.
    8. Ryan Doenges, Mina Tahmasbi Arashloo, Santiago Bautista, Alexander Chang, Newton Ni, Samwise Parkinson, Rudy Peterson, Alaia Solko-Breslin, Amanda Xu, and Nate Foster. 2021. Petr4: Formal Foundations for P4 Data Planes. Proc. ACM Program. Lang. 5, POPL, Article 41 (jan 2021), 32 pages.
    9. Sergei Grishanov, Vadim Meshkov, and Alexander Omelchenko. 2009. A topological study of textile structures. Part I: An introduction to topological methods. Textile Research Journal 79, 8 (2009), 702–713.
    10. Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. 2001. Featherweight Java: A Minimal Core Calculus for Java and GJ. ACM Trans. Program. Lang. Syst. 23, 3 (may 2001), 396–450.
    11. Yuka Ikarashi, Gilbert Louis Bernstein, Alex Reinking, Hasan Genc, and Jonathan Ragan-Kelley. 2022. Exocompilation for Productive Programming of Hardware Accelerators. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (San Diego, CA, USA) (PLDI 2022). Association for Computing Machinery, New York, NY, USA, 703–718.
    12. Benjamin Jones, Yuxuan Mei, Haisen Zhao, Taylor Gotfrid, Jennifer Mankoff, and Adriana Schulz. 2021. Computational Design of Knit Templates. ACM Trans. Graph. 41, 2, Article 16 (dec 2021), 16 pages.
    13. Levi Kapllani, Chelsea Amanatides, Genevieve Dion, and David E. Breen. 2022. Loop Order Analysis of Weft-Knitted Textiles. Textiles 2, 2 (2022), 275–295.
    14. Levi Kapllani, Chelsea Amanatides, Geneviève Dion, Vadim Shapiro, and David E. Breen. 2021. TopoKnit : A Process-Oriented Representation for Modeling the Topology of Yarns in Weft-Knitted Textiles. CoRR abs/2101.04560 (2021), 22 pages. arXiv:2101.04560 https://arxiv.org/abs/2101.04560
    15. Alexandre Kaspar, Liane Makatura, and Wojciech Matusik. 2019a. Knitting Skeletons: A Computer-Aided Design Tool for Shaping and Patterning of Knitted Garments. In Proceedings of the 32nd Annual ACM Symposium on User Interface Software and Technology (New Orleans, LA, USA) (UIST ’19). Association for Computing Machinery, New York, NY, USA, 53–65.
    16. Alexandre Kaspar, Tae-Hyun Oh, Liane Makatura, Petr Kellnhofer, and Wojciech Ma-tusik. 2019b. Neural Inverse Knitting: From Images to Manufacturing Instructions. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, Long Beach, California, USA, 3272–3281.
    17. Alexandre Kaspar, Kui Wu, Yiyue Luo, Liane Makatura, and Wojciech Matusik. 2021. Knit Sketching: From Cut & Sew Patterns to Machine-Knit Garments. ACM Trans. Graph. 40, 4, Article 63 (jul 2021), 15 pages.
    18. Casimir Kuratowski. 1922. Sur l’opération Ā de l’Analysis Situs. Fundamenta Mathematicae 3, 1 (1922), 182–199. http://eudml.org/doc/213290
    19. Mackenzie Leake, Gilbert Bernstein, Abe Davis, and Maneesh Agrawala. 2021. A Mathematical Foundation for Foundation Paper Pieceable Quilts. ACM Trans. Graph. 40, 4, Article 65 (jul 2021), 14 pages.
    20. Xavier Leroy, Sandrine Blazy, Daniel Kästner, Bernhard Schommer, Markus Pister, and Christian Ferdinand. 2016. CompCert – A Formally Verified Optimizing Compiler. In ERTS 2016: Embedded Real Time Software and Systems. SEE, Toulouse, France. http://xavierleroy.org/publi/erts2016_compcert.pdf
    21. Jenny Lin and James McCann. 2021. An Artin Braid Group Representation of Knitting Machine State with Applications to Validation and Optimization of Fabrication Plans. In 2021 IEEE International Conference on Robotics and Automation (ICRA). Institute of Electrical and Electronics Engineers, New York, NY, USA, 1147–1153.
    22. Jenny Lin, Vidya Narayanan, and James McCann. 2018. Efficient Transfer Planning for Flat Knitting. In Proceedings of the 2Nd ACM Symposium on Computational Fabrication (SCF ’18). ACM, New York, NY, USA, 1:1–1:7.
    23. Shashank G Markande and Elisabetta Matsumoto. 2020. Knotty Knits are Tangles in Tori. In Proceedings of Bridges 2020: Mathematics, Art, Music, Architecture, Education, Culture, Carolyn Yackel, Robert Bosch, Eve Torrence, and Kristóf Fenyvesi (Eds.). Tessellations Publishing, Phoenix, Arizona, 103–112. http://archive.bridgesmathart.org/2020/bridges2020-103.html
    24. James McCann. 2017. The “Knitout” (.k) File Format. [Online]. Available from: https://textiles-lab.github.io/knitout/knitout.html.
    25. James McCann, Lea Albaugh, Vidya Narayanan, April Grow, Wojciech Matusik, Jennifer Mankoff, and Jessica Hodgins. 2016. A Compiler for 3D Machine Knitting. ACM Trans. Graph. 35, 4 (July 2016), 49:1–49:11.
    26. J.R. Munkres. 2000. Topology. Prentice Hall, Incorporated. https://books.google.com/books?id=XjoZAQAAIAAJ
    27. Georges Nader, Yu Han Quek, Pei Zhi Chia, Oliver Weeger, and Sai-Kit Yeung. 2021. KnitKit: A Flexible System for Machine Knitting of Customizable Textiles. ACM Trans. Graph. 40, 4, Article 64 (jul 2021), 16 pages.
    28. Vidya Narayanan, Lea Albaugh, Jessica Hodgins, Stelian Coros, and James McCann. 2018. Automatic Machine Knitting of 3D Meshes. ACM Trans. Graph. 37, 3 (Aug. 2018), 35:1–35:15.
    29. Vidya Narayanan, Kui Wu, Cem Yuksel, and James McCann. 2019. Visual knitting machine programming. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–13.
    30. Jifei Ou, Daniel Oran, Don Derek Haddad, Joseph Paradiso, and Hiroshi Ishii. 2019. SensorKnit: Architecting textile sensors with machine knitting. 3D Printing and Additive Manufacturing 6, 1 (2019), 1–11.
    31. Mariana Popescu, Matthias Rippmann, Andrew Liew, Lex Reiter, Robert Johann Flatt, Tom Van Mele, and Philippe Block. 2020. Structural design, digital fabrication and construction of the cable-net and knitted formwork of the KnitCandela concrete shell. Structures 31 (2020), 1287–1299.
    32. Mariana Popescu, Matthias Rippmann, Tom Van Mele, and Philippe Block. 2018. Automated Generation of Knit Patterns for Non-developable Surfaces. In Humanizing Digital Reality, De Rycke K. et al. (Ed.). Springer, Singapore.
    33. Virginia Postrel. 2020. The fabric of civilization : how textiles made the world. Basic Books, Hachette Book Group, New York.
    34. Ante Qu and Doug L. James. 2021. Fast Linking Numbers for Topology Verification of Loopy Structures. ACM Trans. Graph. 40, 4, Article 106 (jul 2021), 19 pages.
    35. Jonathan Ragan-Kelley, Andrew Adams, Sylvain Paris, Marc Levoy, Saman Amarasinghe, and Frédo Durand. 2012. Decoupling Algorithms from Schedules for Easy Optimization of Image Processing Pipelines. ACM Trans. Graph. 31, 4, Article 32 (jul 2012), 12 pages.
    36. Aristides A.G. Requicha. 1977. Mathematical Models of Rigid Solid Objects. Production Automation Project, University of Rochester, Rochester, New York 14627 28 (1977), 74 pages.
    37. Vanessa Sanchez, Kausalya Mahadevan, Gabrielle Ohlson, Moritz A. Graule, Michelle C. Yuen, Clark B. Teeple, James C. Weaver, James McCann, Katia Bertoldi, and Robert J. Wood. 2023. 3D Knitting for Pneumatic Soft Robotics. Advanced Functional Materials n/a, n/a (2023), 2212541. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/adfm.202212541
    38. Shima Seiki. 2011. SDS-ONE Apex3. [Online]. Available from: http://www.shimaseiki.com/product/design/sdsone_apex/flat/.
    39. Shima Seiki. 2019. SDS-ONE Apex4. [Online]. Available from: https://www.shimaseiki.com/product/design/.
    40. Soft Byte Ltd. 1999. Designaknit. [Online]. Available from: https://www.softbyte.co.uk/designaknit.htm.
    41. Michel Steuwer, Toomas Remmelg, and Christophe Dubach. 2017. Lift: A Functional Data-Parallel IR for High-Performance GPU Code Generation. In Proceedings of the 2017 International Symposium on Code Generation and Optimization (Austin, USA) (CGO ’17). IEEE Press, New York, NY, USA, 74–85.
    42. Stoll. 2011. M1Plus pattern software. [Online]. Available from: http://www.stoll.com/stoll_software_solutions_en_4/pattern_software_m1plus/3_1.
    43. Jenny Underwood. 2009. The design of 3D shape knitted preforms. Ph. D. Dissertation. Fashion and Textiles, RMIT University.
    44. Chenming Wu, Haisen Zhao, Chandrakana Nandi, Jeffrey I. Lipton, Zachary Tatlock, and Adriana Schulz. 2019. Carpentry Compiler. ACM Transactions on Graphics 38, 6 (2019), Article No. 195. presented at SIGGRAPH Asia 2019.
    45. Haisen Zhao, Max Willsey, Amy Zhu, Chandrakana Nandi, Zachary Tatlock, Justin Solomon, and Adriana Schulz. 2022. Co-Optimization of Design and Fabrication Plans for Carpentry. ACM Trans. Graph. 41, 3, Article 32 (mar 2022), 13 pages.

Additional Images:

©Jenny Lin, Vidya Narayanan, Yuka Ikarashi, Jonathan Ragan-Kelley, Gilbert Bernstein, and James (Jaimy) McCann

ACM Digital Library Publication:


Overview Page: