Metric Program Synthesis for Inverse CSG

In this paper, we present a new method for solving the inverse constructive solid geometry (CSG) problem, which aims to generate a programmatic representation of a scene from its unstructured representation (e.g., a raster image). Our method, called metric program synthesis, hinges on the observation that many programs in the inverse CSG domain produce similar (but not identical) images. Based on this observation, we propose clustering programs based on a distance metric and constructing a version space that compactly represents "approximately correct" programs. Given a "close enough" program sampled from this version space, our approach uses a distance-guided repair algorithm to find a program that exactly matches the given image. We have implemented our proposed metric program synthesis technique in a tool called SyMetric and evaluate it in the inverse CSG domain. Our evaluation on 40 benchmarks shows that SyMetric can effectively solve inverse CSG problems that are beyond scope for existing synthesis techniques. In particular, SyMetric solves 78% of these benchmarks whereas the closest competitor can only solve 8%. Our evaluation also shows the benefits of similarity-based clustering and other salient features of our approach through a series of ablation studies.