UW PLSE

Tao Du

visitor-photo

InverseCSG: Automatic Conversion of 3D Models to CSG Trees

February 22nd, 2019 at 1:00pm Gates Room 371

Abstract

While computer-aided design is a major part of many modern manufacturing pipelines, the design files typically generated describe raw geometry. Lost in this representation is the procedure by which these designs were generated. In this paper, we present a method for reverse-engineering the process by which 3D models may have been generated, in the language of constructive solid geometry (CSG). Observing that CSG is a formal grammar, we formulate this inverse CSG problem as a program synthesis problem. Our solution is an algorithm that couples geometric processing with state-of-the-art program synthesis techniques. In this scheme, geometric processing is used to convert the mixed discrete and continuous domain of CSG trees to a pure discrete domain where modern program synthesizers excel. We demonstrate the efficiency and scalability of our algorithm on several different examples, including those with over 100 primitive parts. We show that our algorithm is able to find simple programs which are close to the ground truth, and demonstrate our method’s applicability in mesh re-editing. Finally, we compare our method to prior state-of-the-art. We demonstrate that our algorithm dominates previous methods in terms of resulting CSG compactness and runtime, and can handle far more complex input meshes than any previous method.

Bio

Tao Du is a 4th-year Ph.D. student in the computer fabrication group at MIT CSAIL. He received his Bachelor’s degree in Computer Software at Tsinghua University and a Master’s degree in Computer Science at Stanford University. His research interests are computational graphics, reinforcement learning, and robotics. Specifically, he is interested in developing computational tools for optimal design and control of robots. His work has been covered by news media including WIRED, IEEE Spectrum, TechCrunch, and MIT News.

Talk