“Carpentry compiler” by Wu, Zhao, Nandi, Lipton, Tatlock, et al. …
Conference:
Type(s):
Title:
- Carpentry compiler
Session/Category Title: Building Knowledge
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Traditional manufacturing workflows strongly decouple design and fabrication phases. As a result, fabrication-related objectives such as manufacturing time and precision are difficult to optimize in the design space, and vice versa. This paper presents HL-HELM, a high-level, domain-specific language for expressing abstract, parametric fabrication plans; it also introduces LL-HELM, a low-level language for expressing concrete fabrication plans that take into account the physical constraints of available manufacturing processes. We present a new compiler that supports the real-time, unoptimized translation of high-level, geometric fabrication operations into concrete, tool-specific fabrication instructions; this gives users immediate feedback on the physical feasibility of plans as they design them. HELM offers novel optimizations to improve accuracy and reduce fabrication time as well as material costs. Finally, optimized low-level plans can be interpreted as step-by-step instructions for users to actually fabricate a physical product. We provide a variety of example fabrication plans in the carpentry domain that are designed using our high-level language, show how the compiler translates and optimizes these plans to generate concrete low-level instructions, and present the final physical products fabricated in wood.
References:
1. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.Google ScholarDigital Library
2. Marc Alexa, Kristian Hildebrand, and Sylvain Lefebvre. 2017. Optimal Discrete Slicing. ACM Trans. Graph. 36, 1, Article 64b (Jan. 2017). Google ScholarDigital Library
3. Mehdi Baba-Ali, David Marcheix, and Xavier Skapin. 2009. A method to improve matching process by shape characteristics in parametric systems. Computer-Aided Design and Applications 6, 3 (2009), 341–350.Google ScholarCross Ref
4. Moritz Bächer, Bernd Bickel, Emily Whiting, and Olga Sorkine-Hornung. 2017. Spin-it: Optimizing Moment of Inertia for Spinnable Objects. Commun. ACM 60, 8 (July 2017), 92–99. Google ScholarDigital Library
5. Sorav Bansal and Alex Aiken. 2006. Automatic Generation of Peephole Superoptimizers. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XII). ACM, New York, NY, USA, 394–403. Google ScholarDigital Library
6. Bernd Bickel, Moritz Bächer, Miguel A. Otaduy, Hyunho Richard Lee, Hanspeter Pfister, Markus Gross, and Wojciech Matusik. 2010. Design and Fabrication of Materials with Desired Deformation Behavior. ACM Trans. Graph. 29, 4, Article 63 (July 2010), 10 pages. Google ScholarDigital Library
7. Bernd Bickel, Paolo Cignoni, Luigi Malomo, and Nico Pietroni. 2018. State of the Art on Stylized Fabrication. Computer Graphics Forum 37, 6 (2018), 325–342. Google ScholarCross Ref
8. Rafael Bidarra, Paulos J Nyirenda, and Willem F Bronsvoort. 2005. A feature-based solution to the persistent naming problem. Computer-Aided Design and Applications 2, 1–4 (2005), 517–526.Google ScholarCross Ref
9. Christian Brecher, Mirco Vitr, and Jochen Wolf. 2006. Closed-loop CAPP/CAM/CNC process chain based on STEP and STEP-NC inspection tasks. International Journal of Computer Integrated Manufacturing 19, 6 (2006), 570–580.Google ScholarCross Ref
10. Edmund Burke, Robert Hellier, Graham Kendall, and Glenn Whitwell. 2006. A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem. Operations Research 54, 3 (2006), 587–601. arXiv:https://doi.org/10.1287/opre.1060.0293 Google ScholarDigital Library
11. Chengkai Dai, Charlie C. L. Wang, Chenming Wu, Sylvain Lefebvre, Guoxin Fang, and Yong-Jin Liu. 2018. Support-free Volume Printing by Multi-axis Motion. ACM Trans. Graph. 37, 4, Article 134 (July 2018), 14 pages. Google ScholarDigital Library
12. DDX. 2019. EasyWOOD, CAD/CAM software for 5 axis woodworking, nesting true shape | DDX. http://www.ddxgroup.com/en/software/easywood. (2019).Google Scholar
13. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (April 2002), 182–197. Google ScholarDigital Library
14. Yue Dong, Jiaping Wang, Fabio Pellacini, Xin Tong, and Baining Guo. 2010. Fabricating Spatially-varying Subsurface Scattering. ACM Trans. Graph. 29, 4, Article 62 (July 2010), 10 pages. Google ScholarDigital Library
15. Tao Du, Adriana Schulz, Bo Zhu, Bernd Bickel, and Wojciech Matusik. 2016. Computational Multicopter Design. ACM Transactions on Graphics 35, 6 (Nov. 2016), 227:1–227:10.Google ScholarDigital Library
16. FeatureScript. 2019. Weclome to FeatureScript. (2019). https://cad.onshape.com/FsDoc/.Google Scholar
17. Chi-Wing Fu, Peng Song, Xiaoqi Yan, Lee Wei Yang, Pradeep Kumar Jayaraman, and Daniel Cohen-Or. 2015. Computational Interlocking Furniture Assembly. ACM Trans. Graph. 34, 4, Article 91 (July 2015), 11 pages. Google ScholarDigital Library
18. Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. 2017. Program Synthesis. Foundations and Trends in Programming Languages 4, 1–2 (2017), 1–119. Google ScholarCross Ref
19. E Hopper and B.C.H Turton. 2001. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research 128, 1 (2001), 34 — 57. Google ScholarCross Ref
20. Rajeev Joshi, Greg Nelson, and Keith Randall. 2002. Denali: A Goal-directed Superoptimizer. SIGPLAN Not. 37, 5 (May 2002), 304–314. Google ScholarDigital Library
21. Mina Konaković, Keenan Crane, Bailin Deng, Sofien Bouaziz, Daniel Piker, and Mark Pauly. 2016. Beyond Developable: Computational Design and Fabrication with Auxetic Materials. ACM Trans. Graph. 35, 4, Article 89 (July 2016), 11 pages. Google ScholarDigital Library
22. Bongjin Koo, Jean Hergel, Sylvain Lefebvre, and Niloy J. Mitra. 2017. Towards Zero-Waste Furniture Design. IEEE Transactions on Visualization and Computer Graphics 23, 12 (Dec 2017), 2627–2640. Google ScholarCross Ref
23. David H. Laidlaw, W. Benjamin Trumbore, and John F. Hughes. 1986. Constructive Solid Geometry for Polyhedral Objects. In Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’86). ACM, New York, NY, USA, 161–170. Google ScholarDigital Library
24. Yanxiang Lan, Yue Dong, Fabio Pellacini, and Xin Tong. 2013. Bi-scale Appearance Fabrication. ACM Trans. Graph. 32, 4, Article 145 (July 2013), 12 pages. Google ScholarDigital Library
25. Manfred Lau, Akira Ohgawara, Jun Mitani, and Takeo Igarashi. 2011. Converting 3D Furniture Models to Fabricatable Parts and Connectors. In ACM SIGGRAPH 2011 Papers (SIGGRAPH ’11). ACM, New York, NY, USA, Article 85, 6 pages. Google ScholarDigital Library
26. Honghua Li, Ruizhen Hu, Ibraheem Alhashim, and Hao Zhang. 2015. Foldabilizing Furniture. ACM Trans. Graph. 34, 4, Article 90 (July 2015), 12 pages. Google ScholarDigital Library
27. J. I. Lipton, A. Schulz, A. Spielberg, L. H. Trueba, W. Matusik, and D. Rus. 2018. Robot Assisted Carpentry for Mass Customization. In 2018 IEEE International Conference on Robotics and Automation (ICRA). IEEE, Brisbane, QLD, Australia, 1–8. Google ScholarCross Ref
28. Sheng-Jie Luo, Yonghao Yue, Chun-Kai Huang, Yu-Huan Chung, Sei Imai, Tomoyuki Nishita, and Bing-Yu Chen. 2015. Legolization: Optimizing LEGO Designs. ACM Trans. Graph. 34, 6, Article 222 (Oct. 2015), 12 pages. Google ScholarDigital Library
29. Li-Ke Ma, Yizhonc Zhang, Yang Liu, Kun Zhou, and Xin Tong. 2017. Computational design and fabrication of soft pneumatic objects with desired deformations. ACM Transactions on Graphics (TOG) 36, 6 (2017), 239.Google ScholarDigital Library
30. Henry Massalin. 1987. Superoptimizer: A Look at the Smallest Program. In Proceedings of the Second International Conference on Architectual Support for Programming Languages and Operating Systems (ASPLOS II). IEEE Computer Society Press, Los Alamitos, CA, USA, 122–126. Google ScholarCross Ref
31. 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, Article 49 (July 2016), 11 pages. Google ScholarDigital Library
32. Yuki Mori and Takeo Igarashi. 2007. Plushie: An Interactive Design System for Plush Toys. ACM Trans. Graph. 26, 3, Article 45 (July 2007). Google ScholarDigital Library
33. Pascal Müller, Peter Wonka, Simon Haegler, Andreas Ulmer, and Luc Van Gool. 2006. Procedural Modeling of Buildings. ACM Trans. Graph. 25, 3 (July 2006), 614–623. Google ScholarDigital Library
34. Chandrakana Nandi, James R. Wilcox, Pavel Panchekha, Taylor Blau, Dan Grossman, and Zachary Tatlock. 2018. Functional Programming for Compiling and Decompiling Computer-aided Design. Proc. ACM Program. Lang. 2, ICFP, Article 99 (July 2018), 31 pages. Google ScholarDigital Library
35. Step NC. 2019. Step-nc. (2019). http://www.step-nc.org/index.htm.Google Scholar
36. Charles Gregory Nelson. 1980. Techniques for Program Verification. Ph.D. Dissertation. Stanford University, Stanford, CA, USA. AAI8011683.Google Scholar
37. Pavel Panchekha, Alex Sanchez-Stern, James R. Wilcox, and Zachary Tatlock. 2015. Automatically Improving Accuracy for Floating Point Expressions. SIGPLAN Not. 50, 6 (June 2015), 1–11. Google ScholarDigital Library
38. David A. Patterson and Carlo H. Sequin. 1981. RISC I: A Reduced Instruction Set VLSI Computer. In Proceedings of the 8th Annual Symposium on Computer Architecture (ISCA ’81). IEEE Computer Society Press, Los Alamitos, CA, USA, 443–457. http://dl.acm.org/citation.cfm?id=800052.801895Google Scholar
39. Phitchaya Mangpo Phothilimthana, Aditya Thakur, Rastislav Bodik, and Dinakar Dhurjati. 2016. Scaling Up Superoptimization. SIGPLAN Not. 51, 4 (March 2016), 297–310. Google ScholarDigital Library
40. Przemyslaw Prusinkiewicz, Mark Hammel, Jim Hanan, and Radomir Mech. 1996. Lsystems: from the theory to visual models of plants. In Proceedings of the 2nd CSIRO Symposium on Computational Challenges in Life Sciences, Vol. 3. Citeseer, 1–32.Google Scholar
41. Open CASCADE SAS. 2019. OPEN CASCADE. (2019). https://www.opencascade.org.Google Scholar
42. Christian Schüller, Roi Poranne, and Olga Sorkine-Hornung. 2018. Shape Representation by Zippables. ACM Trans. Graph. 37, 4, Article 78 (July 2018), 13 pages. Google ScholarDigital Library
43. Adriana Schulz, Ariel Shamir, Ilya Baran, David I. W. Levin, Pitchaya Sitthi-Amorn, and Wojciech Matusik. 2017. Retrieval on Parametric Shape Collections. ACM Transactions on Graphics 36, 1 (Jan. 2017), 11:1–11:14.Google ScholarDigital Library
44. Michael Schwarz and Pascal Müller. 2015. Advanced Procedural Modeling of Architecture. ACM Trans. Graph. 34, 4, Article 107 (July 2015), 12 pages. Google ScholarDigital Library
45. Mélina Skouras, Stelian Coros, Eitan Grinspun, and Bernhard Thomaszewski. 2015. Interactive Surface Design with Interlocking Elements. ACM Trans. Graph. 34, 6, Article 224 (Oct. 2015), 7 pages. Google ScholarDigital Library
46. Alexei Sokolov, J Richard, VK Nguyen, Ian Stroud, W Maeder, and P Xirouchakis. 2006. Algorithms and an extended STEP-NC-compliant data model for wire electro discharge machining based on 3D representations. International Journal of Computer Integrated Manufacturing 19, 6 (2006), 603–613.Google ScholarCross Ref
47. RSA Solutions. 2019. woodCAD|CAM. https://www.rsasolutions.com/products/woodcadcam/. (2019).Google Scholar
48. Peng Song, Chi-Wing Fu, Yueming Jin, Hongfei Xu, Ligang Liu, Pheng-Ann Heng, and Daniel Cohen-Or. 2017. Reconfigurable Interlocking Furniture. ACM Trans. Graph. 36, 6, Article 174 (Nov. 2017), 14 pages. Google ScholarDigital Library
49. Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. 2009. Equality Saturation: A New Approach to Optimization. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’09). ACM, New York, NY, USA, 264–276. Google ScholarDigital Library
50. The FreeCAD Team. 2019. FreeCAD Your own 3D parametric modeler. (2019). https://www.freecadweb.org/.Google Scholar
51. Jumyung Um, Matthieu Rauch, Jean-Yves Hascoët, and Ian Stroud. 2017. STEP-NC compliant process planning of additive manufacturing: remanufacturing. The International Journal of Advanced Manufacturing Technology 88, 5–8 (2017), 1215–1230.Google ScholarCross Ref
52. Nobuyuki Umetani, Takeo Igarashi, and Niloy J. Mitra. 2012. Guided Exploration of Physically Valid Shapes for Furniture Design. ACM Trans. Graph. 31, 4, Article 86 (July 2012), 11 pages. Google ScholarDigital Library
53. Čeli APS. 2019. Woodwork for Inventor – Furniture design software. https://www.woodworkforinventor.com. (2019).Google Scholar
54. Kiril Vidimče, Szu-Po Wang, Jonathan Ragan-Kelley, and Wojciech Matusik. 2013. OpenFab: A Programmable Pipeline for Multi-material Fabrication. ACM Trans. Graph. 32, 4, Article 136 (July 2013), 12 pages. Google ScholarDigital Library
55. Philip Wadler. 1990. Linear Types Can Change the World!. In PROGRAMMING CONCEPTS AND METHODS. North.Google Scholar
56. L. Wang and E. Whiting. 2016. Buoyancy Optimization for Computational Fabrication. Computer Graphics Forum 35, 2 (2016), 49–58. Google ScholarCross Ref
57. D. Whitfield and M. L. Soffa. 1990. An Approach to Ordering Optimizing Transformations. SIGPLAN Not. 25, 3 (Feb. 1990), 137–146. Google ScholarDigital Library
58. Deborah L. Whitfield and Mary Lou Soffa. 1997. An Approach for Exploring Code Improving Transformations. ACM Trans. Program. Lang. Syst. 19, 6 (Nov. 1997), 1053–1084. Google ScholarDigital Library
59. SQ Xie and Xun Xu. 2006. A STEP-compliant process planning system for sheet metal parts. International Journal of Computer Integrated Manufacturing 19, 6 (2006), 627–638.Google ScholarCross Ref
60. Xun W Xu and Stephen T Newman. 2006. Making CNC machine tools more open, interoperable and intelligent – a review of the technologies. Computers in Industry 57, 2 (2006), 141–152. Google ScholarDigital Library
61. J. Zhang and L. Xing. 2017. A Survey of Multiobjective Evolutionary Algorithms. In 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC), Vol. 1. 93–100. Google ScholarCross Ref
62. Haisen Zhao, Hao Zhang, Shiqing Xin, Yuanmin Deng, Changhe Tu, Wenping Wang, Daniel Cohen-Or, and Baoquan Chen. 2018. DSCarver: Decompose-and-spiral-carve for Subtractive Manufacturing. ACM Trans. Graph. 37, 4, Article 137 (July 2018), 14 pages. Google ScholarDigital Library
