Synthesizing structured CAD models with equality saturation and inverse transformations
- 11 June 2020
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
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.Keywords
Funding Information
- NSF (CCF-1813166)
This publication has 24 references indexed in Scilit:
- Automatically improving accuracy for floating point expressionsACM SIGPLAN Notices, 2015
- Symmetry in 3D Geometry: Extraction and ApplicationsComputer Graphics Forum, 2013
- Lazy AC-Pattern Matching for RewritingElectronic Proceedings in Theoretical Computer Science, 2012
- Equality-Based Translation Validator for LLVMLecture Notes in Computer Science, 2011
- Verified validation of lazy code motionACM SIGPLAN Notices, 2009
- Formal verification of translation validatorsACM SIGPLAN Notices, 2008
- Efficient RANSAC for Point‐Cloud Shape DetectionComputer Graphics Forum, 2007
- On the decidability of phase ordering problem in optimizing compilationPublished by Association for Computing Machinery (ACM) ,2006
- Simplify: a theorem prover for program checkingJournal of the ACM, 2005
- DenaliACM SIGPLAN Notices, 2002