Functional programming for compiling and decompiling computer-aided design

Abstract

Desktop-manufacturing techniques like 3D printing are increasingly popular because they reduce the cost and complexity of producing customized objects on demand. Unfortunately, the vibrant communities of early adopters, often referred to as "makers," are not well-served by currently available software pipelines. Users today must compose idiosyncratic sequences of tools which are typically repurposed variants of proprietary software originally designed for expert specialists.

This paper proposes fundamental programming-languages techniques to bring improved rigor, reduced complexity, and new functionality to the computer-aided design (CAD) software pipeline for applications like 3D-printing. Compositionality, denotational semantics, compiler correctness, and program synthesis all play key roles in our approach, starting from the perspective that solid geometry is a programming language.

Specifically, we define a purely functional language for CAD called LambdaCAD and a polygon surface-mesh intermediate representation. We then define denotational semantics of both languages to 3D solids and a compiler from CAD to mesh accompanied by a proof of semantics preservation. We illustrate the utility of this foundation by developing a novel synthesis algorithm based on evaluation contexts to "reverse compile" difficult-to-edit meshes downloaded from online maker communities back to more-editable CAD programs. All our prototypes have been implemented in OCaml to enable further exploration of functional programming for desktop manufacturing.

References

1. Celena Alcock, Nathaniel Hudson, and Parmit K. Chilana. 2016. Barriers to Using, Customizing, and Printing 3D Designs on Thingiverse. In Proceedings of the 19th International Conference on Supporting Group Work (GROUP ’16). ACM, New York, NY, USA, 195–199.
2. Rajeev Alur, Loris D’Antoni, Sumit Gulwani, Dileep Kini, and Mahesh Viswanathan. 2013. Automated Grading of DFA Constructions. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI ’13). AAAI Press, 1976–1982. http://dl.acm.org/citation.cfm?id=2540128.2540412
3. M. Artin. 2011. Algebra. Pearson Prentice Hall. https://books.google.com/books?id=S6GSAgAAQBAJ
4. Mark S. Baldwin, Gillian R. Hayes, Oliver L. Haimson, Jennifer Mankoff, and Scott E. Hudson. 2017. The Tangible Desktop: A Multimodal Approach to Nonvisual Computing. ACM Trans. Access. Comput. 10, 3, Article 9 (Aug. 2017), 28 pages.
5. Nikola Banovic, Rachel L. Franz, Khai N. Truong, Jennifer Mankoff, and Anind K. Dey. 2013. Uncovering Information Needs for Independent Spatial Learning for Users Who Are Visually Impaired. In Proceedings of the 15th International ACM SIGACCESS Conference on Computers and Accessibility (ASSETS ’13). ACM, New York, NY, USA, Article 24, 8 pages.
6. Blender. 2018. Blender. (2018). https://www.blender.org/ .
7. James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. 2016. Optimizing Synthesis with Metasketches. SIGPLAN Not. 51, 1 (Jan. 2016), 775–788.
8. CGAL. 2018. CGAL. (2018). https://www.cgal.org .
9. Xiang ‘Anthony’ Chen, Stelian Coros, Jennifer Mankoff, and Scott E. Hudson. 2015. Encore: 3D printed augmentation of everyday objects with printed-over, affixed and interlocked attachments. In Special Interest Group on Computer Graphics and Interactive Techniques Conference, SIGGRAPH ’15, Los Angeles, CA, USA, August 9-13, 2015, Posters Proceedings. 3:1.
10. Xiang ‘Anthony’ Chen, Jeeeun Kim, Jennifer Mankoff, Tovi Grossman, Stelian Coros, and Scott E. Hudson. 2016. Reprise: A Design Tool for Specifying, Generating, and Customizing 3D Printable Adaptations on Everyday Objects. In Proceedings of the 29th Annual Symposium on User Interface Software and Technology, UIST 2016, Tokyo, Japan, October 16-19, 2016. 29–39.
11. M. de Berg. 1997. Computational Geometry: Algorithms and Applications. Springer. https://books.google.com/books?id= _vAxRFQcNA8C
12. P. Delfs, M. ¨ Tows, and H.-J. Schmid. 2016. Optimized build orientation of additive manufactured parts for improved surface quality and build time. Additive Manufacturing 12, Part B (2016), 314 – 320.
13. James Demmel and Yozo Hida. 2004. Fast and Accurate Floating Point Summation with Application to Computational Geometry. Numerical Algorithms 37, 1 (01 Dec 2004), 101–112.
14. Jérémie Dumas, An Lu, Sylvain Lefebvre, Jun Wu, and Christian Dick. 2015. By-example Synthesis of Structurally Sound Patterns. ACM Trans. Graph. 34, 4, Article 137 (July 2015), 12 pages.
15. Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, and Paul Zimmermann. 2007. MPFR: A Multipleprecision Binary Floating-point Library with Correct Rounding. ACM Trans. Math. Softw. 33, 2, Article 13 (June 2007).
16. Salomé Galjaard, Sander Hofman, and Shibo Ren. 2015. New Opportunities to Optimize Structural Designs in Metal by Using Additive Manufacturing. Springer International Publishing, Cham, 79–93.
17. Geomagic Design X. 2018. Geomagic Design X. (2018). https://www.3dsystems.com/software/geomagic- design- x .
18. David Goldberg. 1991. What Every Computer Scientist Should Know About Floating-point Arithmetic. Comput. Surveys 23, 1 (March 1991), 5–48.
19. GrabCAD. 2018. GrabCAD. (2018). https://grabcad.com/ .
20. T. Grimm. 2004. User’s Guide to Rapid Prototyping. Society of Manufacturing Engineers.
21. Anhong Guo, Jeeeun Kim, Xiang ‘Anthony’ Chen, Tom Yeh, Scott E. Hudson, Jennifer Mankoff, and Jeffrey P. Bigham. 2017. Facade: Auto-generating Tactile Interfaces to Appliances. In Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems (CHI ’17). ACM, New York, NY, USA, 5826–5838.
22. Megan Hofmann, Julie Burke, Jon Pearlman, Goeran Fiedler, Andrea Hess, Jon Schull, Scott E. Hudson, and Jennifer Mankoff. 2016a. Clinical and Maker Perspectives on the Design of Assistive Technology with Rapid Prototyping Technologies. In Proceedings of the 18th International ACM SIGACCESS Conference on Computers and Accessibility (ASSETS ’16). ACM, New York, NY, USA, 251–256.
23. Megan Hofmann, Jeffrey Harris, Scott E. Hudson, and Jennifer Mankoff. 2016b. Helping Hands: Requirements for a Prototyping Methodology for Upper-limb Prosthetics Users. In Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems (CHI ’16). ACM, New York, NY, USA, 1769–1780.
24. Megan Kelly Hofmann. 2015. Making Connections: Modular 3D Printing for Designing Assistive Attachments to Prosthetic Devices. In Proceedings of the 17th International ACM SIGACCESS Conference on Computers and Accessibility (ASSETS ’15). ACM, New York, NY, USA, 353–354.
25. Kai Hormann and Alexander Agathos. 2001. The Point in Polygon Problem for Arbitrary Polygons. Comput. Geom. Theory Appl. 20, 3 (Nov. 2001), 131–144.
26. Nathaniel Hudson, Celena Alcock, and Parmit K. Chilana. 2016. Understanding Newcomers to 3D Printing: Motivations, Workflows, and Barriers of Casual Makers. In Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems (CHI ’16). ACM, New York, NY, USA, 384–396.
27. ImplicitCAD. 2018. ImplicitCAD. (2018). http://www.implicitcad.org/ .
28. Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010. Oracle-guided Component-based Program Synthesis. In Proceedings of the 32Nd ACM/IEEE International Conference on Software Engineering - Volume 1 (ICSE ’10). ACM, New York, NY, USA, 215–224.
29. Rajeev Joshi, Greg Nelson, and Keith Randall. 2002. Denali: A Goal-directed Superoptimizer. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI ’02). ACM, New York, NY, USA, 304–314.
30. Jeeeun Kim, Anhong Guo, Tom Yeh, Scott E. Hudson, and Jennifer Mankoff. 2017. Understanding Uncertainty in Measurement and Accommodating its Impact in 3D Modeling and Printing. In Proceedings of the 2017 Conference on Designing Interactive Systems, DIS ’17, Edinburgh, United Kingdom, June 10-14, 2017. 1067–1078.
31. P. Kim. 2013. Rigid Body Dynamics for Beginners: Euler Angles & Quaternions. CreateSpace Independent Publishing Platform. https://books.google.com/books?id=bJEengEACAAJ
32. Venkat Krishnamurthy and Marc Levoy. 1996. Fitting Smooth Surfaces to Dense Polygon Meshes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’96). ACM, New York, NY, USA, 313–324.
33. James McCann, Lea Albaugh, Vidya Narayanan, April Grow, Wojciech Matusik, Jennifer Mankoff, and Jessica K. Hodgins. 2016. A compiler for 3D machine knitting. ACM Trans. Graph. 35, 4 (2016), 49:1–49:11.
34. James McCrae, Nobuyuki Umetani, and Karan Singh. 2014. FlatFitFab: Interactive Modeling with Planar Sections. In Proceedings of the 27th Annual ACM Symposium on User Interface Software and Technology (UIST ’14). ACM, New York, NY, USA, 13–22.
35. Autodesk. Meshmixer. 2018. Autodesk. Meshmixer. (2018). http://www.meshmixer.com/ .
36. Stefanie Mueller, Sangha Im, Serafima Gurevich, Alexander Teibrich, Lisa Pfisterer, François Guimbretière, and Patrick Baudisch. 2014a. WirePrint: 3D Printed Previews for Fast Prototyping. In Proceedings of the 27th Annual ACM Symposium on User Interface Software and Technology (UIST ’14). ACM, New York, NY, USA, 273–280.
37. Stefanie Mueller, Tobias Mohr, Kerstin Guenther, Johannes Frohnhofen, and Patrick Baudisch. 2014b. faBrickation: Fast 3D Printing of Functional Objects by Integrating Construction Kit Building Blocks. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI ’14). ACM, New York, NY, USA, 3827–3834.
38. Chandrakana Nandi, Anat Caspi, Dan Grossman, and Zachary Tatlock. 2017. Programming Language Tools and Techniques for 3D Printing. In 2nd Summit on Advances in Programming Languages (SNAPL 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Benjamin S. Lerner, Rastislav Bodík, and Shriram Krishnamurthi (Eds.), Vol. 71. Schloss Dagstuhl– Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 10:1–10:12.
39. OFF. 2018. OFF Files. (2018). http://www.geomview.org/docs/html/OFF.html .
40. OpenSCAD. 2018. OpenSCAD. (2018). http://www.openscad.org/ .
41. Pavel Panchekha, Alex Sanchez-Stern, James R. Wilcox, and Zachary Tatlock. 2015. Automatically Improving Accuracy for Floating Point Expressions. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’15). ACM, New York, NY, USA, 1–11.
42. Phitchaya Mangpo Phothilimthana, Tikhon Jelvis, Rohin Shah, Nishant Totla, Sarah Chasins, and Rastislav Bodik. 2014. Chlorophyll: Synthesis-aided Compiler for Low-power Spatial Architectures. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14). ACM, New York, NY, USA, 396–407.
43. Phitchaya Mangpo Phothilimthana, Aditya Thakur, Rastislav Bodik, and Dinakar Dhurjati. 2016. Scaling Up Superoptimization. SIGPLAN Not. 51, 4 (March 2016), 297–310.
44. Powershape. 2018. Powershape. (2018). https://www.autodesk.com/products/powershape/overview .
45. Rhinoceros. 2018. Rhinoceros. (2018). https://www.rhino3d.com/ .
46. Eric Schkufza, Rahul Sharma, and Alex Aiken. 2013. Stochastic Superoptimization. SIGPLAN Not. 48, 4 (March 2013), 305–316.
47. Adriana Schulz, Ariel Shamir, David I. W. Levin, Pitchaya Sitthi-amorn, and Wojciech Matusik. 2014. Design and Fabrication by Example. ACM Trans. Graph. 33, 4, Article 62 (July 2014), 11 pages.
48. J.R. Shewchuk. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. 18 (10 1997), 305–363.
49. SketchUp. 2018. SketchUp. (2018). http://www.sketchup.com/ .
50. P. Smid. 2003. CNC Programming Handbook: A Comprehensive Guide to Practical CNC Programming. Industrial Press. https://books.google.com/books?id=JNnQ8r5merMC
51. Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph.D. Dissertation. University of California, Berkeley.
52. Solidworks. 2018. Solidworks. (2018). http://www.solidworks.com/ .
53. SpaceClaim. 2018. SpaceClaim. (2018). http://www.spaceclaim.com/en/Solutions/ReverseEngineering.aspx .
54. Ondrej Stava, Juraj Vanek, Bedrich Benes, Nathan Carr, and Radomír Měch. 2012. Stress Relief: Improving Structural Strength of 3D Printable Objects. ACM Trans. Graph. 31, 4, Article 48 (July 2012), 11 pages.
55. Ivan E. Sutherland. 1964. Sketch Pad a Man-machine Graphical Communication System. In Proceedings of the SHARE Design Automation Workshop (DAC ’64). ACM, New York, NY, USA, 6.329–6.346.
56. Alexander Teibrich, Stefanie Mueller, François Guimbretière, Robert Kovacs, Stefan Neubert, and Patrick Baudisch. 2015. Patching Physical Objects. In Proceedings of the 28th Annual ACM Symposium on User Interface Software & Technology (UIST ’15). ACM, New York, NY, USA, 83–91.
57. Enabling The Future. 2018. Enabling The Future. (2018). http://enablingthefuture.org .
58. Thingiverse. 2018a. Hexagonal Candle Holder. (2018). https://www.thingiverse.com/thing:756968 .
59. Thingiverse. 2018b. Thingiverse. (2018). http://www.thingiverse.com/ .
60. Thingiverse. 2018c. Ultimate 22 Hex-Wrench Holder. (2018). https://www.thingiverse.com/thing:1752602 .
61. Thingiverse. 2018d. Welcome To Customizer. (2018). https://www.thingiverse.com/customizer .
62. Abhishek Udupa, Arun Raghavan, Jyotirmoy V. Deshmukh, Sela Mador-Haim, Milo M.K. Martin, and Rajeev Alur. 2013. TRANSIT: Specifying Protocols with Concolic Snippets. SIGPLAN Not. 48, 6 (June 2013), 287–296.
63. Nobuyuki Umetani and Ryan Schmidt. 2013. Cross-sectional Structural Analysis for 3D Printing Optimization. In SIGGRAPH Asia 2013 Technical Briefs (SA ’13). ACM, New York, NY, USA, Article 5, 4 pages.
64. 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.
65. Chenglong Wang, Alvin Cheung, and Rastislav Bodik. 2017. Synthesizing Highly Expressive SQL Queries from Input-output Examples. SIGPLAN Not. 52, 6 (June 2017), 452–466.
66. Qingnan Zhou, Julian Panetta, and Denis Zorin. 2013. Worst-case Structural Analysis. ACM Trans. Graph. 32, 4, Article 137 (July 2013), 12 pages.
67. Paul Zimmermann. 2010. Reliable Computing with GNU MPFR. In Proceedings of the Third International Congress Conference on Mathematical Software (ICMS’10). Springer-Verlag, Berlin, Heidelberg, 42–45. http://dl.acm.org/citation.cfm?id= 1888390.1888400

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

• Theory of computation

  • Semantics and reasoning

    • Program semantics