Synthesizing Structured CAD Models with Equality Saturation and Inverse Transformations

Abstract

Recent program synthesis techniques help users customize CAD models(e.g., for 3D printing) by decompiling low-level triangle meshes to Constructive Solid Geometry (CSG) expressions. Without loops or functions, editing CSG can require many coordinated changes, and existing mesh decompilers use heuristics that can obfuscate high-level structure. This paper proposes a second decompilation stage to robustly "shrink" unstructured CSG expressions into more editable programs with map and fold operators. We present Szalinski, a tool that uses Equality Saturation with semantics-preserving CAD rewrites to efficiently search for smaller equivalent programs. Szalinski relies on inverse transformations, a novel way for solvers to speculatively add equivalences to an E-graph. We qualitatively evaluate Szalinski in case studies, show how it composes with an existing mesh decompiler, and demonstrate that Szalinski can shrink large models in seconds.

arXiv comment14 pages

References in corpus (2)

• Programmatic and Direct Manipulation, Together at Last
• Lazy AC-Pattern Matching for Rewriting

Cited by in corpus (10)

• egg: Fast and Extensible Equality Saturation
• babble: Learning Better Abstractions with E-Graphs and Anti-Unification
• Reconstructing editable prismatic CAD from rounded voxel models
• Pure Tensor Program Rewriting via Access Patterns (Representation Pearl)
• ShapeMOD: Macro Operation Discovery for 3D Shape Programs
• Theory Exploration Powered By Deductive Synthesis
• ImageEye: Batch Image Processing Using Program Synthesis
• Programming-by-Demonstration for Long-Horizon Robot Tasks
• Programming by Example Made Easy
• Program Synthesis from Partial Traces