InverseCSG: Automatic Conversion of 3D Models to CSG Trees
TimeWednesday, 5 December 201810:24am - 10:45am
DescriptionWhile computer-aided design is a major part of many modern manufacturing pipelines, the design files 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 that modern program synthesizers excel in. We prove that our algorithm provides a complete search and demonstrate its efficiency and scalability 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.