Computer-Aided Design (CAD) has become increasingly popular due to the benefits of user-customized parts and the affordability of desktop manufacturing devices like 3D printers and laser cutters. The computational fabrication workflow typically starts with designing a model in CAD, compiling it down to a triangle mesh (such as STL (stl)), slicing the mesh into horizontal 2D layers to generate G-code (gcode), and finally sending the G-code to a desktop manufacturing device.
A wide range of CAD tools (solidworks; openscad; onshape; fusion) are available for the first step, i.e., making a model. These tools tend to have a steep learning curve and new users struggle to construct models from scratch (chilana2). As an alternative, many users rely on crowdsourced designs from online repositories (thing; grabcad). The majority of designs in these repositories are shared in triangle mesh formats (stl). Triangle meshes have already been compiled down from CAD designs, and thus support a simpler “download and print” workflow. However, customizing triangle meshes is often difficult since all higher-level design information has been compiled away (chilana1).
Recent work in program synthesis (inverse; csgnet; reincarnate) has begun addressing this problem with techniques to decompile meshes back into programmatic Constructive Solid Geometry (CSG) models (csgparam) equivalent to the input mesh. These approaches only synthesize flat, i.e., branch- and loop-free, CSG models. While flat CSGs are more editable than meshes, they can still be several hundreds or thousands of lines long for models with repetitive structures. Existing synthesis tools do not infer parameters to control such repetitive structures, which limits their usefulness. We call this the design parameter inference problem.
This paper presents ShrinkRay, a technique for addressing the design parameter inference problem. ShrinkRay provides new program synthesis techniques for translating flat CSG representations to parameterized CAD models in a domain-specific language dubbed LambdaCAD. LambdaCAD’s functional programming features support designs that are more compact and editable than flat CSGs.
Figure 1 shows a rendered gear model111 For a mechanical gear or gear system, other constraints like meshing additionally must be taken in to account. The mechanics of such systems is beyond the scope of this paper. and snippets of its 8,000 line STL, 300 line CSG, and 16 line parameterized LambdaCAD program. Changing the gear’s tooth count in STL would be roughly as difficult as starting over and designing a new gear model. Recent work decompiling meshes to CSGs can help, e.g., by identifying the geometry of the gear’s teeth, but actually changing the tooth count in CSG still requires manually editing the position and orientation of each tooth.
ShrinkRay automatically synthesizes the parameterized 16 line LambdaCAD representation of the gear in Figure 1. The tooth count of 60 is clearly exposed in the program’s “loop,” an indexed map function (Mapi) inside a Fold. The Mapi takes a list of teeth (shown by Repeat (Tooth, 60)), and applies a function (Rotate (0, 0, 360 i / 60, Translate (120, 0, 0, c))) to orient and position every tooth based on its index, . This makes changing the tooth count trivial: the user simply needs to change 60 to the new tooth count.
Figure 2 shows ShrinkRay’s high-level architecture. It coordinates two cooperating procedures, an uninterpreted component and an arithmetic component, that manipulate an E-graph (nelson) which represents a set of LambdaCAD programs equivalent to the flat CSG input. The uninterpreted component infers repeated structure, i.e., where part of a CSG could be the result of a Mapi or Fold, using semantics-preserving syntactic rewrite rules for the CSG domain. The arithmetic component uses constraint solvers to infer the arguments to combinators like Mapi and Fold, including both functions like the rotations and translations in the output of Figure 1
and parameters like the tooth count of a gear. Importantly, these techniques are robust to noise in the input models, which occurs due to geometric computations performed in floating-point arithmetic.
In general, there is no one “correct” way to
parameterize a flat CSG —
different choices may make
various kinds of edits easier.
Thus, after both uninterpreted and arithmetic updates
saturate the E-graph,
ShrinkRay uses a cost function to generate the
top-k parametrized LambdaCAD programs.
Returning the top-k models allows
a user to choose the parameterization
that best meets their needs.
In summary, this paper’s contributions include:
A novel algorithm that addresses the Design Parameter Inference problem by decomposing it into two subproblems: an uninterpreted part and an arithmetic part. The algorithm uses E-graphs to combine domain-specific rewrites and function solvers that respectively perform uninterpreted and arithmetic generalizations.
A particular set of semantics-preserving rewrites and algorithms for function and loop inference that can parameterize real-world designs.
An implementation of the algorithm as a tool, ShrinkRay, in OCaml which will be open-sourced and publicly available.
An evaluation of ShrinkRay on 16 real-world CAD models collected from popular online repositories. This evaluation shows that ShrinkRay can, on average, reduce program size by 64%, expose the underlying repetitive structure for 81% of models, and parameterize CAD programs with AST-depth over 60 in under 5 minutes.
The rest of the paper is organized as follows: Section 2 provides background on CSG, which is the input to ShrinkRay, and provides an illustrative running example. Sections 3, 4, and 5 detail ShrinkRay’s core uninterpreted and arithmetic components. Section 6 presents an empirical evaluation of ShrinkRay. Section 7 presents key reusable insights, and discusses limitations and future work. Section 8 presents related work, and Section 9 concludes.
2. Language and Algorithm Overview
(Left) shows CSG, the input language to ShrinkRay, which programmatically represents solid models. CSG is a common representation in CAD tools for parametric modeling(openscad; implicit; fusion). In this paper, we focus on three aspects of CSG:
Solid primitives include cubes, cylinders, hexagonal prisms, spheres, etc. To simplify presentation, we assume these primitives are always canonicalized, i.e., they are of unit length, placed at the origin , and their principle axes are parallel to the axes.
An affine transformation on a 3D vector,, is of the form , where is a matrix and is a vector. Scale and Rotate
are linear transformations which are represented only using. Translate is a non-linear transformation which is represented by the vector . We consider three affine transformations in this paper: Scale, Rotate, and Translate. Typically, CAD tools do not expose the matrices to designers and only use them internally. Designers use a 3D vector based format.
Boolean operators such as union, difference, and intersection perform the geometric analogs of their set-theoretic counterparts and can be composed with affine transformations to construct a variety of models.
These language features are sufficient for writing many interesting models, including the flat CSG model for the gear (based on a Thingiverse model (gear)) rendered in Figure 1. Figure 4 shows part of the gear’s 300 line implementation in flat CSG. The program representing this model is the ”tooth” used with a different degree of rotation, translated to the correct location in 3D space, union-ed n_teeth times which, in this case, is set to 60. This representation, while smaller than the mesh, does not expose the repetitive structure of the model because the CSG language is not sufficiently expressive.
Figure 6(Right) shows the core of LambdaCAD, a superset of CSG extended with standard functional programming language features. ShrinkRay parameterizes the flat CSG gear model into 16 lines of LambdaCAD. This program uses functions to parameterize over the repetitive structure latent in the flat CSG input. In this case, ShrinkRay identifies that the same geometry (Tooth) occurs repeatedly, but under varying affine transformations. The parametrized model in Figure 4 provides several benefits over the flat CSG in Figure 4. First, the parametrized model is an order of magnitude shorter. Second, it is parametric, which makes it much easier to change the number of teeth in the gear. Such customization is difficult in the flat CSG model because it requires the designer to manually update the rotation and position of each gear tooth.
ShrinkRay synthesizes LambdaCAD programs from flat CSG models. Figure 5 shows a single iteration of the main ShrinkRay loop. At the core of our approach is an E-graph which syntactic rewrites and arithmetic solvers for inferring loops and functions populate with equivalence information. Several ShrinkRay subcomponents perform iterative analysis or search; their bounds are controlled by the fuel argument. In our evaluation, a single iteration of the main loop was sufficient for parametrizing real-world models, though it can easily be run repeatedly.
ShrinkRay first constructs an E-graph (nelson) with the initial abstract syntax tree (AST) of the flat CSG (Line 3 in Algorithm Figure 5), and then populates the E-graph using the procedures described below.
Syntactic rewrites (Line 4), Section 3
ShrinkRay applies a set of syntactic rewrites to detect syntactic equivalences between various expressions. For instance, our rule database contains a rewrite that identifies when repeated unions can be rewritten as a Fold over a list of CSGs. In the gear example, [fontsize=] Union (Rotate (0, 0, 6, Translate (125, 0, 0, Tooth)), Union (Rotate (0, 0, 12, Translate (125, 0, 0, Tooth)), … )) can be rewritten as: [fontsize=] Fold (Union, Empty, Cons (Rotate (0, 0, 6, Translate (125, 0, 0, Tooth)), Cons (Rotate (0, 0, 12, Translate (125, 0, 0, Tooth)), … )))
List manipulation (Line 5-6), Section 4.3
After applying syntactic rewrites, the list in the Fold example above contains 60 rotated and translated tooth primitives. Due to other rewrite rules, the elements in this list may have multiple equivalent variants in the E-graph. ShrinkRay chooses a consistent variant for each element. After “determinizing” the list in this way, ShrinkRay then reorders the elements using several criteria, e.g., sorting the vectors in affine transformations lexicographically.
Function inference (Line 7), Section 4
Next, ShrinkRay invokes domain-specific solvers to infer a function over the determinized list. For the gear example, ShrinkRay finds the Mapi function whose input is the following nested list of nested affine transformations: [fontsize=] [ [Rotate (0, 0, 6); Translate (125, 0, 0)] ; [Rotate (0, 0, 12); Translate (125, 0, 0)] ; … ] from which ShrinkRay finds a function for the rotations based on the index: where 60 is the number of teeth. Since all the translations are the same, the function for translation is simply the constant function . In this example, inferring the function for Mapi was sufficient to expose the internal structure of the model because there is only one “loop” in the gear. For more complex models, where a single function inference is not possible or sufficient, ShrinkRay infers nested Mapis and multiple nested loops.
Top-k (Line 8-9), Section 5.1
ShrinkRay uses a cost function to extract the top-k best programs. Our default cost function measures the size of a model in terms of the number of nodes. The model in Figure 4 is the best among the top-k (with k=5).
3. E-graphs and Syntactic Rewrites
This section provides a brief background on E-graphs and presents semantics-preserving syntactic rewrites for inferring uninterpreted CAD equivalences (Figure 5, line 4).
E-graphs (nelson) efficiently encode sets of equivalent expressions and provide an interface for adding additional equivalences. An E-graph is a set of eclasses where each eclass represents a set of equivalent expressions. Each eclass is a set of enodes where each enode represents an operator applied to some eclasses (encoded as edges from the enode to its argument eclasses). E-graphs maintain the congruence closure over the set of expressions they represent. New expressions can be added to the E-graph and additional equivalences represented by merging eclasses. This interface supports encoding domain-specific equivalences as rewrite rules : whenever an eclass represents an expression matching pattern under substitution , the eclass representing is found (or constructed), and is merged with . Additional analyses can similarly apply other means to expand the E-graph by constructing and merging eclasses. E-graphs help mitigate the phase ordering problem (aiken-phase-ordering; phase-ordering-decide) since rewrites do not destructively update the program ShrinkRay is seeking to improve. Instead, after applying a rewrite, the old program is retained, i.e., both the old and new expressions are stored in the same eclass. After populating an E-graph via repeatedly applying rewrites and other analyses, the best enode from each eclass can be computed for a given cost function (which may recursively depend on costs of argument eclasses), and a stream of lowest-cost expressions can be extracted.
Figure 7 shows an example of a small E-graph where one syntactic rewrite rule for lifting a translate from a Union has been applied once. The eclass that contains the union of the two affinely-transformed children, translate (1, 2, 3, c) and translate (1, 2, 3, c’), initially has only one enode (Union). The affine lifting rule matches this eclass and merges it with a new eclass that contains an enode corresponding to the equivalent expression where the Translate has been factored out of the Union.
3.2. Semantics-Preserving Syntactic Rewrites
ShrinkRay provides 40 semantics-preserving rewrites categorized into 4 main sets, including key CAD domain-specific equivalences, which are used to expand an E-graph during search. These rewrites implement the core of ShrinkRay’s uninterpreted component.
Combining boolean and affine transformations
For any boolean operator and any affine transformation , distributes over : . (a) shows this generic rule for lifting affine transformations, as well two concrete examples for (Union, Translate) and (Rotate, Diff). These are applicable when the transformations in both children of the boolean operation have the same type and arguments.
Since affine transformations are closed under composition, when two or more affine transformations are nested in a CSG, they can be reordered or merged. A key insight from our work is that, to enable parameter inference, composing multiple affine transformations of different types should be avoided. This is because the internal affine transformation matrix hides structural information inherent in the CSG which then has to be exposed by decomposing combined transformations.
We implemented a set of rewrites that reorder affine transformations; a representative sample is shown in (b). We derived these rewrites geometrically and checked their validity with a computer algebra system (wolfram)
. For rotation about all axes, complete reordering is not possible without support for additional affine transformations like skew and shear, which we leave as future work.
Designs can have two or more consecutive affine transformations of the same type:
. We have found that collapsing these can facilitate finding closed-form functions in later phases of synthesis. (c) shows ShrinkRay’s rewrites that collapse nested same-type affine transformations. These rewrite were also derived geometrically and checked with a computer algebra system (wolfram). For rotation, we implemented rules for axis-aligned cases.
(d) shows rewrites for replacing a sequence of binary operations with a Fold. Following OCaml syntax, we use for list construction and for list append.
ShrinkRay provides rewrites based on standard properties of union, difference, and intersection, e.g., (not shown in Figure 8).
Together, these rewrites can significantly simplify designs—they find expressions equivalent to the flat CSG input that use folds over lists as well variously re-ordered and re-factored affine transformations. However uninterpreted syntactic rewrites alone cannot infer loop parameters or closed forms of repeated affine transformations which are required for models like the gear from Figure 1.
4. Function Inference
Even after applying syntactic rewrites, there is more structure that can be discovered from a model. For example, consider the flat program in Figure 2 which is a union of 5 cubes, translated along the x-axis. Application of the Fold rewrite finds the following equivalent program: [fontsize=] Fold ( Union, Empty, Cons (Translate (2.0, 0.0, 0.0, Unit), Cons (Translate (4.0, 0.0, 0.0, Unit), Cons (Translate (6.0, 0.0, 0.0, Unit), Cons (Translate (8.0, 0.0, 0.0, Unit), Cons (Translate (10.0, 0.0, 0.0, Unit), Nil)))))) Figure 9 shows part of the E-graph (for two of the cubes) after this Fold rule has been applied. Since the list over which the Fold is applied has the same affine transformation (Translation) applied to the same child (Unit) with different vectors, the function inference component of ShrinkRay searches for an arithmetic function to represent these vectors. Note that if the type of the transformation were not the same, or the children were different, the function solver would not apply this modification because it would not guarantee semantic preservation.
Classical syntactic rewrites are not sufficient for function inference because unlike the uninterpreted changes rewrites make, these require arithmetic reasoning. Therefore, we introduce a new architecture that interfaces the E-graph with domain-specific function solvers shown on Line 7 in Figure 5. From the folded program, the function solver extracts the vectors in the affine transformations: [(2.0, 0.0, 0.0); (4.0, 0.0, 0.0), …, (10.0, 0.0, 0.0)] and searches for a function that can be applied to all the elements in the list using a Mapi. In this case, the function is:
ShrinkRay populates the E-graph with a Mapi node that uses this function (Figure 9)—in the list’s eclass, it adds a new enode corresponding to:
4.1. Finding the functions
In mathematics, a closed form is defined as an expression that can be evaluated using a finite number of operations. In this paper, a closed form may contain constants, variables, arithmetic operations (+, -, x, /), trigonometric functions, and polynomials.
ShrinkRay’s function inference searches for a closed form for a list of vectors. In general, it is impossible to find such a form without constraining the space of possible solutions because there can be arbitrary forms that can represent a given input vector list. To make the problem tractable, we have implemented a library of three domain-specific arithmetic function solvers to find such closed forms. As we explain in Section 6, we developed a benchmark suite based on models from online repositories and we found that these forms were sufficient to capture the structure in 87% of the models. The architecture of our function inference implementation is extensible and additional function solvers that use different algorithms can be implemented and plugged in as required.
Given a list of vectors, , ShrinkRay’s function solver attempts to find a closed form for each component, i.e., for , , and , as a function of its index, , in the corresponding lists from the following classes:
first degree polynomial:
second degree polynomial:
For the first two we use Z3 (z3). For the third we implemented our own trigonometric solver based on non-linear least squares regression, since Z3 does not support transcendental functions. The function solver searches for both polynomial and non-linear trigonometric solutions and returns the form that has the largest coefficient of determination, or in other words, the best fit.
Inferring Functions using Z3
For first and second degree polynomials, we encode closed form inference as a constraint satisfaction problem. The constraints are given by the list of vectors () and we use Z3 to solve for the parameters and .
A direct encoding does not work, however, because input data is generally noisy. CSGs provided by existing tools are generated from meshes represented with floating-point values which suffer from roundoff errors. For example, a CSG may contain the following vectors: [(0.0, 0.0, 5.001); (0.0, 0.0, 10.00001); (0.0, 0.0, 14.9998); (0.0, 0.0, 20.0)] No first- or second-degree polynomial can generate this list. Fortunately, exact closed form inference is typically not necessary. In fact, having an approximate but easier-to-interpret solution is preferable for editability. In Section 6 we provide a case study that demonstrates inferred functions for noisy models.
One possibility would be to encode the constraints in the SMT-theory of floating-points (z3). This approach is not practical due to limited scalability of the decision procedures which rely on a bitvector encoding, and the fact that it is generally not known whether the noise is only due to roundoff errors.
We thus handle noisy data by explicitly adding a tolerance to our constraints:
for all vector component x, y, z paired with their index, i, in the list. The resulting constraints are in the real-valued nonlinear theory, for which existing decision procedures scale well enough for our use case. Using this approach, function inference returns for the example set of vectors above.
For examples involving rotation, often 222The ensures is always constrained. is a desirable closed form since trigonometric functions are periodic over multiples of . One way to solve the problem is to add as a constraint for Z3. However, this may cause other vectors that are not used with a rotation to be modeled unintuitively or worse, incorrectly. For example, can also be represented using this formula when
, but it may not be intuitive to do so. In order to avoid this problem, we use a heuristic for handling rotations. Before the E-graph makes a call to the function solvers, we check if the type of the affine transformation is aRotate: if so, then we convert the output of the solver to the form .
Finding function using non-linear regression
For many models, the above functions may not capture the structure in the underlying vectors; examples include vectors related using periodic functions over the domain of integers. For such models, after trying the above two polynomial forms, the function solver attempts to find a third form using a nonlinear function solver. This solver encodes periodicity in the form of sine waves (), and computes the parameters,values. For example, given the following input: [(-1.0, -1.0, 0.0); (-1.0, 1.0, 0.0); (1.0, -1.0, 0.0); (1.0, 1.0, 0.0)] the function solver finds the following function:
Nested Affine Transformations
Most nontrivial models use nested affine transformations, an example of which is shown in Figure 10 (L): the union of three unit cubes, each of which are scaled, rotated, and translated. ShrinkRay attempts to find closed forms for such models for each layer of affine transformation. For this particular program, the function solver module first extracts the three layers:
|Translate (2.0, 4.0, 6.0), Translate (4.0, 6.0, 8.0), Translate (6.0, 8.0,10.0)|
|Rotate (30.0, 0.0, 0.0), Rotate (45.0, 0.0, 0.0), Rotate (60.0, 0.0, 0.0)|
|Scale (1.0, 3.0, 5.0), Scale (3.0, 5.0, 7.0), Scale (5.0, 7.0, 9.0)|
and solves each layer separately. In this case, the resulting LambdaCAD program that contains a triple nested Mapi is shown in Figure 10 (R).
4.2. Managing non-determinism
The previous section explained Line 7 of Figure 5 which is the function solving component. This section explains Line 5 where ShrinkRay invokes a determinizer (Figure 9 second step). The purpose of the function solvers is to find closed forms to represent affine transformation vectors. These solvers operate over lists of 3D vectors.
However, the E-graph does not explicitly contain such lists of vectors. It has eclasses with lists of affine transformed CADs from which ShrinkRay extracts the vectors and sends them to the function inference component. Such a list of affine transformed CADs can often be non-deterministic—the rewrites over affine transformations described in Section 3 can lead to multiple semantically equivalent lists in the E-graph. This is problematic for the function solvers (both the ones using Z3, and the non-linear solver) because it is not obvious how they can solve for a non-deterministic query. ShrinkRay solves this problem by limiting the non-determinism within the E-graph and not exposing it to the function solvers. It uses a heuristic to choose one deterministic list of affine transformed CADs from which to extract vectors and model them. The heuristic ensures uniformity in the list—for every element of the list, when there is a single affine transformation, the heuristic ensures that every element has the same type of transformation, for nested affine transformations, it ensures that the order of the types is the same.
For example, consider the following program with doubly nested affine transformations after applying Fold rules: [fontsize=] Fold (Union, Empty, Cons ( Rotate (30.0, 0.0, 0.0, Scale (1.0, 3.0, 5.0, unit)), Cons ( Rotate (45.0, 0.0, 0.0, Scale (3.0, 5.0, 7.0, unit)), Cons ( Rotate (60.0, 0.0, 0.0, Scale (5.0, 7.0, 9.0, unit)), Nil)))) The first rule in (b) on reordering Scale and Rotate will apply in this program. For each element in the list, an equivalent version of with reordered affine transformations will be added to ’s eclass. To construct a concrete query for the solver, ShrinkRay must select from the (potentially) exponentially many possible affine transformation orderings. Typically, getting a closed form solution from the solver requires using an ordering which is consistent across each list element. The list determinizer resolves this by first picking an element and respecting the same order of affine transformations for all other elements.
4.3. List Manipulations
In Line 6 in Figure 5, ShrinkRay modifies the E-graph to sort lists of CAD expressions to aid function solving. In Figure 2, this is one of the external modifications to the E-graph, the other ones being the function and loop inference algorithms. Figure 11 demonstrates the algorithm for list manipulation. The simplest modification is lexicographically sorting a list of affine transformed CADs using the vectors in the transformations. Other manipulations that we have implemented are regrouping lists based on the child of the affine transformations, and regrouping based on common values of x, y, z, coordinates.
ShrinkRay only applies list reordering in the context of a Fold because its objective is to help the function solver find a closed form that applies to the elements in the list over which the fold is applied.
First it uses pattern matching to identify folds (Line 13, 14) in the E-graph. This returns pairs of eclasses containingfolds, and lists of substitutions where a substitution is a mapping from a pattern variable to eclasses (Line 15). For example, for a Fold, the list of substitutions would include a substitution for the function, the accumulator, and the list. The algorithm iterates over these substitutions and invokes a function called manip on them (Line 3). Since list manipulation happens after determinizer, the manip function looks for the value of the eclass where a match occurred for the list (Line 6-7), sorts it (Line 8), creates a new enode for a Fold with the sorted list (Line 9), makes an eclass for this enode if it does not exist (Line 10), and finally merges the eclass with the eclass of the original Fold (Line 11).
5. Nested Loop Inference
Structures that nested loops can capture appear often in designs. We already saw how function inference handles singly-nested loops and nested affine transformations. ShrinkRay is also capable of inferring some forms of nested loops. While in theory, our loop inference approach is general enough to handle arbitrary nesting of loops, we have found that in practice supporting up to three nested loops is sufficient for most designs since the most common practice in this domain is to have a loop for each dimension x, y, and z. In fact, based on our experiments, double and single loops are the most common; triply nested loops in this domain are rarely used.
The goal for loop inference is: given a list of affine transformed CAD programs, find a doubly or triply nested loop that is an equivalent representation. As Figure 5 shows, both function and loop inference happen after the determinizer has computed a deterministic value for eclasses containing lists. The input to loop inference is then a list of 3-tuples which represents the vectors of the affine transformed CAD list. If the list of CADs has nested affine transformations, loop inference finds loops only for the outer most affine transformations. The algorithm works in two steps: first it looks for loops that are regular, i.e. each row has the same number of columns. To find such loops, it uses m-factorization and m-index-set. If this search is not successful, the algorithm searches for more generic loops.
m-factorization and m-index-sets
Let be the list of affine transformed CADs and let be its length. ShrinkRay’s Loop inference algorithm performs m-factorization of , where . It removes the trivial factors, i.e., 1 and , since those do not lead to interesting nested loops. Using the non-trivial factors, it computes m-index-set for following Figure 13. ShrinkRay uses these index sets together with the input list of vectors to form queries for the function solver. If a closed form is found, then the index set and the corresponding factorization is the resulting loop bound. For example, consider the problem of searching a doubly-nested loop for the following list: [(-1.0, -1.0, 0.0); (-1.0, 1.0, 0.0); (1.0, -1.0, 0.0); (1.0, 1.0, 0.0)]
There are four elements in the list and we want a doubly-nested loop, so . Let the loop variables be and . 2-factorization for 4 gives us the factors (2, 2), after eliminating 1 and 4 (trivial factors). Figure 13 returns the following two index-sets: [[0; 0; 1; 1]; [0; 1; 0; 1]]. From these sets loop inference makes the tuples: (0, 0), (0, 1), (1, 0) and (1, 1), where the first element corresponds to and the second corresponds to . It then pairs with and with and queries the function solvers. For example, the first degree polynomial queries for are:
which are satisfied by the formula: .
If the loop is not regular, i.e., there are rows with different number of columns, this approach does not work. ShrinkRay then searches for more general loops of a certain category. In this part of the search, the algorithm regroups the input vector list by common coordinates—for example, in a 2D irregular grid given a list of vectors, it groups all vectors with the same values together, and searches for a closed form function for the varying -values. For every value of x, ShrinkRay thus finds a loop for y in the form of a Fold. The final outcome is then a Fold over the folds for the y-values. The same principle applies to 3D irregular grids.
For some inputs ShrinkRay synthesizes multiple “correct” LambdaCAD programs, each of which is useful for certain kinds of edits. Thus, returning only a single program does not fully leverage the advantages of design parametrization. In the final steps of Algorithm Figure 5 (Line 8-9), for every eclass, ShrinkRay finds the top-k best programs using a cost function and then returns top-k best programs from the E-graph.
We implemented ShrinkRay in 3000 LOC of OCaml. It includes our own implementation of an E-graph solver. We used Z3 (z3) as a constraint solver for finding polynomial closed forms up to degree 2. Our trigonometric solver implementation uses the Owl library (owl) for matrix operations.
We ran all experiments on macOS version 10.14.3
with a 2.3 GHz, Intel Core i5 processor. Timing numbers are reported in seconds
as an average of three runs. We used the @deriving library
from Janestreet Core (core)
to serialize LambdaCAD programs as s-expressions. For our
experiments, we implemented a serializer from OpenSCAD’s language to
s-expressions that ShrinkRay operates on. We provide a translation from LambdaCAD (the output of ShrinkRay) to OpenSCAD so that the results can be validated by
rendering the models and comparing with the rendering of the input CSG.
We are interested in the following research questions:
Can ShrinkRay handle real world applications?
How does ShrinkRay compare against human-written programs?
How diverse are the solutions generated by ShrinkRay?
Can ShrinkRay infer parameters for noisy input programs?
6.1. Real World Applications
First we show the applicability of ShrinkRay on 16 models from Thingiverse (thing). Our aim in choosing the models was to ensure that they are useful models that can be parametrized, i.e. they have some internal structure that can demonstrate ShrinkRay’s ability to recover it. For example, 3432939:nintendo-slot is a video game storage unit which has 12 triangular slots. 3097951:rasp-pie is a pin covering block for raspberry pies with 20 rows and 2 columns of pin covers. 3331008:med-slide is a supplement sorter that slides into a tablet tube. It has 7 slots for storing pills on a tube shaped base. The first column in Table 1 provides the item number for each model (for item number , the model can be found at https://www.thingiverse.com/thing:).
For 70% of the models, we found OpenSCAD implementations from Thingiverse because we specifically searched for parametrizable designs and OpenSCAD is one of the most popular parametric CAD tools used on Thingiverse. Most of these models already had some structure in them in the form of loops. We implemented a translator that can flatten these program into loop-free CSG. To evaluate ShrinkRay on these, we first flattened them using the translator, then ran ShrinkRay on the flat models; we compare the results with the human written models in Section 6.2. For the remaining 30% models, we simulated existing Mesh to CSG decompilers (inverse; csgnet; reincarnate) to get a flat input for ShrinkRay.
To run ShrinkRay, some models required minor preprocessing, e.g., to factor out some unsupported uses of features like Hull and Mirror. For 3244600:cnc-end-mill we had to tweak the input CSG to remove a non-critical Hull operation. A subexpression in 3044766:sander also used Hull, but to manually remove the hull, we would have to make non-trivial design changes. Instead, we replaced the Hull subexpression with an External keyword we added to LambdaCAD to encode unsupported features. We similarly preprocessed 1725308:soldering, which was implemented using Mirror. Even though ShrinkRay cannot reason about External, it is still useful for these examples. Both models have repetitive structure where the External expression appears several times. ShrinkRay successfully parameterizes over this repetition and significantly reduces the size of the model.
Table 1 summarizes the results obtained by running ShrinkRay on the flat input CSGs. The second and third columns give the size of the input CSG and output programs, respectively. On average, ShrinkRay leads to a 64% percent reduction in program size. Even though ShrinkRay has support for triply-nested loops, we found that in practice it is not common to use three nested loops for design. Our models only needed single or doubly-nested loops (shown in column n-l). ShrinkRay found functions and loops for 81% of the examples. For every example, the programs exposing internal structure were always within the top-5 models returned by ShrinkRay. Below top-5 does not imply that those programs had no simplifications—they had partial structure explored or smaller simplifications from syntactic rewrites. The AST depth of inputs is between 6 and 62 with a mean of 17.44 (column #i-d), and the output AST depth is reduced by 40.5% on average (column #o-d). The number of primitive shapes in the models was reduced by 65% on average (columns #i-p and #o-p). From our experiments, we also noticed that simple first and second degree polynomials can be sufficiently expressive for representing a variety of 3D models. Every model for which ShrinkRay found a closed-form function had at least one polynomial solution.
Smaller program does not imply parametrizability
We observed that small program size does not necessarily imply parametrizability. For example, the program with a single loop that ShrinkRay synthesized for 3452260:relay-box had lower rank (4) compared to other less parametrized variants. For 2921167:hc-bits and 3094201:dice, the parametrized programs generated by ShrinkRay had depth higher than the input. Using the parametrized model for these examples is still recommended because they make customization easier by exposed the structure of the model.
Cost function robustness
The default cost function we use is number of nodes in the AST. We also implemented another variant for cost function called reward-loops that assigns lower costs for programs with Mapi to evaluate the effect of cost function on ShrinkRay’s output. We ran all experiments with both cost functions. For 15 of the 16 benchmarks, ShrinkRay’s results are not significantly affected by the choice of cost function—the top-5 programs are the same using both. This shows that ShrinkRay output is not dependent on cost functions.
For one benchmark, 510849:wardrobe, when using size as the cost function ShrinkRay does not show any significant reduction in size (AST nodes decrease from 149 to 145), nor is its structure exposed. We then ran this benchmark with the reward-loops cost function. 510849:wardrobe in Table 1 shows the result: the size of the output program is in fact bigger than the input size (AST nodes increase from 149 to 185), but the trade-off is that some of the structure from the underlying design is exposed in the form of loops, making it more editable.
For two models, ShrinkRay returned the same flat CSG as the input—64847:sd-rack and 3333935:compose. For these, the flat CSGs did not have any repetitive structure that could be extracted using the algorithms in ShrinkRay. For all the remaining examples, ShrinkRay was able to synthesize loops and functions.
6.2. Comparison against Human-written Models
Our results indicate that ShrinkRay-generated programs are at least as good as human-written programs—for every model with loops, ShrinkRay was able to infer the same loop.
For 64847:sd-rack and 3333935:compose, the human-written input CSG was loop-free and the result generated by ShrinkRay was also loop-free because there was no repetitive structure for ShrinkRay to parameterize. On the other hand, for 3094201:dice (rendering in Figure 15), ShrinkRay was able to synthesize a loop even when the human-written model was flat. ShrinkRay found a nested-loop for the side with a 6 as shown in Figure 17.
6.3. Diversity of Solutions
As ShrinkRay supports multiple function solvers (trigonometric, polynomial) and loop inference, it can synthesize diverse programs. This is useful because different implementations of the same design may be preferred depending on what modifications one wants to do. An example is the hex cell generator (2921167:hc-bits) in Figure 15 which can be implemented using a nested loop or trigonometric functions. ShrinkRay synthesizes both these variants which are shown in Figure 18 and Figure 19. Consider a modification where the user wants to add another row/column of cells. For this, the nested loop implementation is preferred333The designer also needs to change the size of the base which is a single change at one location. because it only requires changing the loop bounds (Figure 18). The orientation and position of the cells are automatically updated. On the other hand, consider a modification for making a flower-like pattern by adding more hex cells. This modification is extremely difficult in a flat CSG and in the loop model, but trivial in the trigonometric model. The only change the user makes is in the number of hex cells, and the rotation angle (Figure 19). The initial model, the modification to add another column, and the modification to generate a flower pattern are visualized in Figure 15.
6.4. Handling Noisy Inputs
ShrinkRay is built to be resilient to noisy inputs. Mesh decompilation tools that generate flat CSGs from STL formats often have floating-point values and thus, rounding errors. To evaluate whether ShrinkRay can infer structure from noisy inputs, we ran it on a flat CSG that was synthesized by an existing mesh decompilation tool (reincarnate). The input model had three hexagonal prisms union-ed and subtracted from a base, each with nested affine transformations: a scale and a translation. The vectors to those transformations have noise from geometric computations involved in the decompilation process from the mesh. Figure 16 (L) shows the input program with 55 nodes and three prisms. ShrinkRay was able to synthesize a program, shown in Figure 16 (R), with 46 nodes with a loop and a function for nested affine transformations in 0.48 seconds. It found a closed form that encoded the first two hexagons. This result demonstrates that ShrinkRay’s function inference can handle noisy CSG inputs which makes it suitable for use on automatically decompiled CSGs.
This section provides observations we made during this work, including insights about the approach, limitations and future work.
CSG is a single trace
The flat CSG for a design can be viewed as a single trace of its corresponding LambdaCAD implementation. This paper’s technique takes this trace, and automatically infers the LambdaCAD program by exploiting internal repetition in the trace, such that when it is unrolled, the original trace is generated. An interesting property of this domain which makes our approach tractable is the fact that the traces are always bounded (CAD designs cannot have infinite loops), and the set of operations specific to CAD are narrow.
On the other hand, the following properties of this domain make our approach challenging. First, most real models when flat are hundreds of lines long which requires scalability. Second, designs often have floating point computations that can lead to rounding errors. Third, the approach should be able to synthesize multiple LambdaCAD programs depending on what edits the user wants to make.
Generality of approach
There are several domain specific components to each part of ShrinkRay like the rewrites based on geometric properties of affine transformations, and the function solvers that search for certain forms of functions that are more likely to be found in CAD. However, the underlying principle of using traditional syntactic rewrites with external tools for function and loop inference is general and can be applied to other domains.
Another interesting feature of the CAD domain is that after synthesizing a design in LambdaCAD, verifying its correctness is trivial. One can use a translation validation (transval; samet) style approach to compile the synthesized high-level CAD to a mesh and render it to compare with the mesh of the original CSG or use a more rigorous approach like Hausdorff distance.
Limitations and future work
While using internal repetition within a single trace, i.e. the flat CSG allows for a certain kind of parametrization as we saw in this paper, it has some limitations. Since this approach only relies on internal structure, it fails to identify relationships between parameters. In the gear example, even though ShrinkRay successfully determined that the tooth of the gear should be repeated 60 times using an arithmetic function for rotation, it cannot determine how other properties of the model such as its radius should change with the number of teeth. This is important in a gear system in order for the gears to mesh correctly.
ShrinkRay only infers design parameters for features that are repeatedly varied within a design. If a part appears only once in a single configuration, ShrinkRay cannot identify any structure because without more examples this task is impossible. Extending ShrinkRay to support a wider variety of parameter inference is an interesting direction for future work.
An important orthogonal challenge is to evaluate the usability of ShrinkRay from an HCI perspective. Even though automatically inferring parameters for CSG designs make them much more editable, end-users without any expertise in programming may still find it difficult to interact with any program. While this paper focused on the core programming language challenges in parametrizing designs, in the future, we would like to integrate ShrinkRay with more interactive design tools.
Finally, while ShrinkRay is robust to rounding error, its exact behavior is influenced by -bounds. In practice, we have not needed to modify the bound for any real examples and have found our results to be robust with respect to perturbations of . However, for larger and more complex models, it may be necessary to develop a more systematic approach for setting that balances fidelity to the input model against simple, editable parameterized outputs.
8. Related Work
E-graph based Deductive Program Synthesis
E-graphs have been used extensively in superoptimizers (denali; eqsat; aiken), and SMT solvers (z3; lean; simplify; rosette). The problem this paper tackles is that of discovering inherent structure in flat CSG-based CAD models. We use an E-graph based approach to apply rewrites to a CSG that exposes the underlying structure. One of the contributions of our work is identifying that this problem has two components: an uninterpreted component and an arithmetic component as described in previous sections. Our approach of using uninterpreted rewrites and arithmetic function solvers to modify the E-graph can be considered similar to Simplify (simplify) which uses an E-graph module for finding equivalent expressions containing uninterpreted functions, and a Simplex module that is used for arithmetic computations.
2D and 3D design synthesis
Nandi et al. (reincarnate) and Du et al. (inverse) have developed tools that can decompile low-level polygon meshes to CSGs. These tools use program synthesis together with domain specific computational geometric algorithms to discover structure in the meshes. CSGNet (csgnet)
uses machine learning to generate flat CSG programs for 2D and 3D shapes. Our contribution, ShrinkRay is different from these tools in that it is the first tool that can automatically infer parameters from CSGs to generate high-level CAD programs in a purely functional programming language.
Ellis et al.’s (latex) developed a tool that can automatically generate programs that correspond to hand-drawn images. They first use machine learning to detect primitives in the drawings and then use Sketch (sketch) to find loops and conditionals. However, their tool is only capable of finding programs of depth less than 3, whereas ShrinkRay was able to handle programs with depths 60 within minutes. Our technique is different from theirs in that they use Sketch to search the space of all programs within a given depth, based on a language grammar, a specification, and a cost, whereas we use a deductive synthesis technique where the specification is given as the initial CSG, and ShrinkRay constructs an E-graph and updates it using semantics preserving rewrites and external solvers.
In computer graphics and vision, symmetry detection (symm) in 3D shapes is a well studied topic. It can improve performance of geometry processing algorithms. The ability to detect folds and maps in 3D models is more general than symmetry detection because it can find patterns in models that have repetitive structure that is not symmetry. A simple example of this is union of cubes increasing in size. Schulz et al. (adrianagen)
presented an algorithm for optimizing parametric CAD models using interpolation methods. Their approach works for optimizing parameters, but does not automatically infer them.
Program Synthesis for End-Users
In the recent years, there has been an increasing focus on program synthesis for end-users. Chasins et al. (skipblocks) have developed a tool that uses programming by demonstration to automatically synthesize programs for web scraping. Wang et al. (scythe) have developed a tool that can synthesize SQL queries from input-output examples. Chugh et al. (chugh1)’s SKETCH-N-SKETCH is a tool that combines direct manipulation with programmatic manipulations for Scalable Vector Graphics (SVG) to detect programmatic updates based on direct manipulations to the SVG. To the best of our knowledge, ShrinkRay is the first tool that can automatically infer parameters from a flat CSG for 3D CAD models. Darulova et al. (evagen)
have used genetic algorithms for synthesizing fixed point programs for control applications.
Inferring Loops in Programs
There are several program synthesis tools that are capable of synthesizing recursive programs or programs with loops. Synquid (synquid) uses polymorphic refinement types to synthesize recursive functions in Haskell. Escher (escher) is a tool that can generate recursive programs from input-output examples. Myth (myth) uses types and input-output examples for generating higher-order functions such as maps and folds. Leon (leon) is a Scala-based tool that uses counter example guided inductive synthesis (CEGIS) and an SMT solver (smt) for synthesizing recursive programs. Our work is different from existing work in this space because the input to ShrinkRay is a single flat instantiation of the corresponding LambdaCAD program and scalability is crucial because the flat CSGs we target and often several hundreds of lines. Casper (metalift) automatically generates map-reduce programs from sequential Java. While Casper’s input is a program that already has loops and its output is a program with maps and folds, ShrinkRay’s inputs are completely flat, and do not contain any loops.
In this paper, we presented an approach for addressing the design parameter inference problem for CAD programs. Customizing flat CSG models can be tedious and error-prone, especially when the models have repetitive structure. We proposed a novel algorithm that uses E-graphs with syntactic rewrites and arithmetic solvers to infer functions and loops in such models, which makes them more editable by exposing their underlying structure. We implemented our technique as a tool in OCaml called, ShrinkRay, and evaluated it on 16 real world models we collected from Thingiverse. ShrinkRay was able to infer functions and loops for 81% of them and on average reduced program size by 64%, in under 5 minutes for each model.