Discovering Design Concepts for CAD Sketches

According to the two observations, we design an end-to-end sketch concept learning framework by self-supervised induction on sketch graphs. As shown in Fig. 2, the framework has two main steps before loss computation: a detection step that generates implicit representations of concepts making up the input sketch, and an explicit generation step that expands the implicit concepts into concrete structures on which self-supervision targets like reconstruction and modularity are applied.

Building on a state-of-the-art detection architecture [2], the detection module $D$ takes a sketch $S$ as input and detects the modular concepts within it, i.e. $\{\mathbf{q}_{i}\}=D(S,\{\overline{\mathbf{q}}_{i}\})$, where the concepts are represented implicitly as latent codes $\{\mathbf{q}_{i}\}$, and $\{\overline{\mathbf{q}}_{i}\}$ are a learnable set of concept instance queries. Notably, we apply vector quantization to the latent codes and obtain $\{\mathbf{q}^{\prime}_{i}=\min_{\mathbf{p}\in\mathbb{L}^{1}}{||\mathbf{p}-\mathbf{q}_{i}||_{2}}\}$, which ensures that each concept is selected from the common collection of learnable concepts $\mathbb{L}^{1}$ used for restructuring all sketches.

The explicit generation module is separated into two sub-steps, structure generation and parameter instantiation, which ensures that the modular concept structures are explicit and reused throughout different sketch instances. Specifically, the structure network takes each quantized concept code $\mathbf{q}^{\prime}_{i}$ and generates its explicit form $\mathbf{T}_{i}^{1}$ in terms of primitives and constraints of $\mathbb{L}^{0}$ types along with the composition operator $R_{\mathbf{T}_{i}^{1}}$. Subsequently, the parameter network instantiates the concept structure by assigning parameter values to each component of $\mathbf{T}_{i}^{1}$ conditioned on $\mathbf{q}_{i}$ and input sketch, to obtain $t^{1}_{i}$.

The composition operator $R_{S}$ for combining $\{t^{1}_{i}\}$ is generated from a special latent code $\mathbf{q}_{R}$ transformed by $D$ from a learnable token $\overline{\mathbf{q}}_{R}$ appended to $\{\overline{\mathbf{q}}_{i}\}$.

The entire model is trained end-to-end by reconstruction and modularity objectives. In particular, we design loss functions that measure differences between the generated and groundtruth sketch graphs, in terms of both per-element attributes and pairwise references. Given our explicit modeling of encapsulated structures of the learned concepts, we can further enhance the modularity of the generation by introducing a bias loss that encourages in-concept references.

Sketch encoding A raw sketch $S$ can be serialized into a sequence of $\mathbb{L}^{0}$ primitives and constraints. Previous works have adopted slightly different schemes to encode the sequence [6, 13, 18, 24, 25]. In this paper, we build on the previous works and take a simple strategy akin to [13, 25] for input sketch encoding. Specifically, we split each $\mathbb{L}^{0}$ typed instance $t^{0}$ into several tokens: type, parameter, and a list of references. For each of the token category, we use a specific embedding module. For example, parameters as scalars are quantized into finite bins before being embedded as vectors (see supplementary for the quantization details), and since there are at most five parameters for each primitive, we pack all parameter embeddings into a single code. On the other hand, each constraint reference as a primitive index is directly embedded as a code. Therefore, each token of a $\mathbb{L}^{0}$ typed instance is encoded as

where $t^{0}.x$ iterates over the split tokens (i.e., type, parameters, references), the type embedding is shared for all tokens of the instance, the position embedding counts the token index in the whole split-tokenized sequence of $S$, and parameter or reference embeddings are applied where applicable.

Concept detection We build the detection network as an encoder-decoder transformer following [2]. The transformer encoder operates on the sketch encoded sequence $[\mathbf{e}_{t_{i}^{0}\in S}]$ and produces the contextualized sequence $[\mathbf{e}^{\prime}_{t_{i}^{0}\in S}]$ through layers of self-attention and feed-forward. The transformer decoder takes a learnable set of concept queries $[\overline{\mathbf{q}}_{i}]$ of size $k_{qry}$ plus a special query $\overline{\mathbf{q}}_{R}$ for composition generation, and applies interleaved self-attention, cross-attention to $[\mathbf{e}^{\prime}_{t_{i}^{0}}]$ and feed-forward layers to obtain the implicit concept codes $[\mathbf{q}_{i}]$ and $\mathbf{q}_{R}$. The concept codes are further quantized into $[\mathbf{q}^{\prime}_{i}]$ by selecting concept prototypes from a library $\mathbf{L}^{1}$ implicitly encoding $\mathbb{L}^{1}$, before being expanded into explicit forms.

Concept structure expansion Given a library code $\mathbf{q}^{\prime}\in\mathbf{L}^{1}$ representing a type $\mathbf{T}^{1}\in\mathbb{L}^{1}$, through an MLP we expand its explicit structure as a collection of codes $[\mathbf{t}_{i}^{0}]$ representing the $\mathbb{L}^{0}$ type instances $[t_{i}^{0}]$ and a matrix representing the composition $R_{\mathbf{T}^{1}}$ of $[t_{i}^{0}]$ and arguments (cf. List 1).

We fix the maximum number of $\mathbb{L}^{0}$ type instances to $k_{L^{0}}$ (12 by default), and split the arguments into two groups, inward arguments and outward arguments, each of maximum number $k_{arg}$ (2 by default). Each type code $\mathbf{t}_{i}^{0}$ is decoded into discrete probabilities over $\mathbb{L}^{0}$ with an additional probability for null type $\phi$ to indicate the emptiness of this element (cf. Sec. 5.1), by $\textrm{dec}_{type}(\cdot)$ as the inverse of $\textrm{enc}_{type}(\cdot)$ in Sec. 4.1. An inward argument only points to a primitive inside the concept structure and originates from a constraint outside, and conversely an outward argument only points to primitives outside and originates from a constraint inside the concept (see inset for illustration); the split into two groups eases composition computation, as discussed below.

The composition operator $R_{\mathbf{T}^{1}}$ is implemented as an assignment matrix $\mathbf{R}_{\mathbf{T}^{1}}$ of shape $(2k_{L^{0}}{+}k_{arg})\times(k_{L^{0}}{+}k_{arg})$, where each row corresponds to a constraint reference or inward argument, and each column to a primitive or outward argument. The two-fold coefficient of constraint references comes from that any constraint we considered in the dataset [17] has at most two arguments. Each row is a discrete probability distribution such that $\sum_{j}{\mathbf{R}_{\mathbf{T}^{1}}[i,j]}=1$, with the maximum entry signifying that the $i$-th constraint/outward argument refers to the $j$-th primitive/inward argument. We compute $\mathbf{R}_{\mathbf{T}^{1}}$ by first mapping the concept code $\mathbf{q}^{\prime}$ to a matrix of logits in the shape of $\mathbf{R}_{\mathbf{T}^{1}}$, and then applying softmax transform for each row. Notably, we avoid the meaningless loops of an element referring back to itself, and inward arguments referring to outward arguments, by masking the diagonal blocks $\mathbf{R}_{\mathbf{T}^{1}}[2i{:}2i{+}2,i],i{\in}[k_{L^{0}}]$ and the argument block $\mathbf{R}_{\mathbf{T}^{1}}[2k_{L^{0}}{:},k_{L^{0}}{:}]$ by setting their logits to $-\infty$.

Cross-concept composition Aside from references inside a concept, references across concepts are generated to complete the whole sketch graph. We achieve cross-concept references by argument passing (see inset above for illustration). In particular, we implement the cross-concept composition operator $R_{S}$ as an assignment matrix $\mathbf{R}_{S}$ of shape $(k_{qry}{\cdot}k_{arg})\times(k_{qry}{\cdot}k_{arg})$ directly mapped from $\mathbf{q}_{R}$ through an MLP. Similar to the in-concept composition matrix, each row of the cross-concept matrix is a discrete distribution such that $\sum_{j}{\mathbf{R}_{S}[i,j]}=1$, with the maximum entry signifying that the $(i\bmod k_{arg})$-th outward argument of the $\lfloor i/k_{arg}\rfloor$-th concept instance refers to the $(j\bmod k_{arg})$-th inward argument of the $\lfloor j/k_{arg}\rfloor$-th concept instance.

The complete cross-concept reference is therefore the product of three transport matrices:

where $\mathbf{R}_{cref}[t_{i}^{1},t_{j}^{1}]$ is a block assignment matrix of shape $2k_{L^{0}}{\times}k_{L^{0}}$. Intuitively, $\mathbf{R}_{cref}[t_{i}^{1},t_{j}^{1}]$ specifies how constraints inside $t_{i}^{1}$ refers to primitives of $t_{j}^{1}$ throughout all possible paths crossing the arguments of two concepts.

Collectively, we denote the complete reference matrix for all pairs of generated $\mathbb{L}^{0}$ elements as $\mathbf{R}$ of shape $(2k_{qry}{\cdot}k_{L^{0}})\times(k_{qry}{\cdot}k_{L^{0}})$, which includes in-concept and cross-concept references.

Instantiating a concept structure requires assigning parameters to the components where applicable. Therefore, as shown in Fig. 2, the parameter generation network takes a concept structure $\mathbf{T}^{1}$ and its implicit instance encoding $\mathbf{q}$ as input, and produces the specific parameters for each $\mathbb{L}^{0}$ typed instances inside the concept. In addition, as the parameters of generated instances are directly related to the input parameters of the raw sketch $S$, we find it improves convergence and accuracy by allowing the parameter network to attend to the input tokens.

We implement the parameter network as a transformer decoder in a similar way as [2]. The instance code $\mathbf{q}$ is first expanded to $k_{L^{0}}$ tokens by a small MLP, which are summed with $[\mathbf{t}_{i}^{0}]$ token-wise to obtain the query codes. The parameter network then transforms the query codes through interleaved layers of self-attention, cross-attention to the contextualized input sequence $[\mathbf{e}^{\prime}_{t^{0}}]$, and feed-forward, before finally mapped to explicit parameters in the form of probabilities over quantized bins, through a decoding layer $\textrm{dec}_{param}(\cdot)$ that is inverse of $\textrm{enc}_{param}(\cdot)$ in Sec. 4.1.

As discussed in Sec. 4, an input sketch is restructured into a set of sketch concepts which are expanded into a graph of primitives and constraints; the generated sketch graph $\widetilde{S}$ is compared with the input sketch $S$ for reconstruction supervision.

The comparison of generated and target graphs requires a one-to-one correspondence between elements of the two graphs, on which the graph differences can be measured. However, it is nontrivial to find such a matching, because not only are there variable numbers of elements in the two graphs, but also both elements and references between elements must be taken into account for matching. To this end, we build a cost matrix that measures the difference for each pair of generated and target elements, in terms of their attributes and references, and apply linear assignment matching on the cost matrix [11, 8] to establish the optimal correspondence between two graphs.

Cost matrix construction To compare each pair of generated element and target element, we measure their type differences, and further use type casting to interpret the generated element as the target type, so that their parameters can be compared. To account for reference differences between the two elements, we compare the reference arrows by the differences of their pointed primitives.

Specifically, given the target graph $S$ of $k_{tgt}$ elements and the generated graph $\widetilde{S}$ of $k_{qry}{\cdot}k_{L^{0}}$ elements, we build the cost matrix $\mathbf{C}$ of shape $k_{tgt}\times(k_{qry}{\cdot}k_{L^{0}})$ in two steps. First, for a pair of target element $p$ and generated element $q$, we compare their type and parameter differences by cross-entropy. We denote the cost matrix in this stage as $\mathbf{C}_{ury}$, as it accounts for the element-wise unary distances between two graphs. Second, to measure the binary distances of references, for each target constraint element $p$ and its $r$-th referenced primitive $p.r$, its distance from the generated references of element $q$ is computed as (also illustrated by inset figure):

where $\mathbf{R}[2q+r,j]$ is the probability of $q$ taking $j$ as its $r$-th reference, as predicted by the composition operation (Sec. 4.2). Intuitively, the binary cost is a summation of unary costs weighted by predicted reference probabilities, where the unary costs measure how different a generated pointed primitive is from the target pointed primitive. The complete cost matrix is $\mathbf{C}=w_{ury}\mathbf{C}_{ury}+w_{bry}\mathbf{C}_{bry}$, with $w_{ury}=50,w_{bry}=1$; we give a larger weight to the unary costs because meaningful binary costs depend on reliable unary costs in the first place, as evident in Eq. (3).

Matching and reconstruction loss Given the cost matrix $\mathbf{C}$, we apply linear assignment to obtain a matching $\sigma:\widetilde{S}\rightarrow S{\cup}\{\phi\}$ between $\widetilde{S}$ and $S$. Note that the number of elements of these two graphs can be different, but we have chosen $k_{qry},k_{L^{0}}$ such that the generated elements always cover the target elements. Therefore, $\sigma(q)=p$ assigns a matched generation $q{\in}M{\subset}\widetilde{S}$ to a target $p{\in}S$, but assigns the rest unmatched generations $M^{\prime}=\widetilde{S}{\setminus}M$ to the empty target $\phi$, i.e. $\sigma(M^{\prime})=\phi$. The loss terms for matched generations are simply the corresponding cost terms $\mathbf{C}[\sigma(q),q],q\in M$; for unmatched generations, we supervise its type to be the empty type $\phi$ and neglect its parameters or references. We denote the average loss of all generated terms as $\mathcal{L}_{recon}$.

Besides matching cost, we also use an additional reference loss to encourage the generated references to be sharp (i.e., $\mathbf{R}$ being closer to binary). This loss complements the binary costs mentioned above by making sure that even if the generated primitives are similar, a generated constraint only refers to one primitive sharply.

We define the sharp reference loss as

where $p$ iterates over the target constraints $S_{c}$, $\sigma^{-1}(\cdot)$ is the inverse mapping from target element to generation, and we skip a term if $p.r$ does not exist for constraints with one reference.

Following [21, 16], we optimize the concept code quantization against library $\mathbf{L}^{1}$ with:

where $\textrm{sg}(\cdot)$ is the stop gradient operation. For training stability, we follow [16] and replace the first term with EMA updates of $\mathbf{q}^{\prime}\in\mathbf{L}^{1}$. Furthermore, we improve spare code usage by reviving unused code in $\mathbf{L}^{1}$ periodically [16] (please refer to supplementary for details).

We look for modular $\mathbb{L}^{1}$ concepts that have rich and meaningful encapsulated structures, rather than arbitrary groups of $\mathbb{L}^{0}$ elements that rely on cross-group references to recover the graph structures. This modularity can be enhanced by limiting the use of arguments for sketch concepts. Instead of allocating very few arguments as a hard constraint, we introduce a soft bias loss to encourage the restrictive use of arguments, which may still cover cases when more arguments are needed for accurate reconstruction. To be specific, we penalize the accumulated probability of elements pointing to outward arguments:

where again $p$ iterates over the target constraints $S_{c}$, $\sigma^{-1}(\cdot)$ is the inverse mapping from target element to generation, and $i+k_{L^{0}}$ slices the reference probabilities to outward arguments.

The training objective sums up losses of reconstruction, concept quantization and modularity bias:

where we empirically use weights $w_{recon}=1,w_{sharp}=20,w_{vq}=1,w_{bias}=25$ throughout all experiments unless otherwise specified in the ablation studies.

By training our model on the raw sketches with self-supervised induction losses, we obtain a result library of sketch concepts and a model for design intent parsing that interprets a given sketch into modular concepts and their combination. Indeed, we find the automatically discovered concepts capture natural design intents and modular structures. For example, through the restructured sketches and constraint graphs in Figs. 1 and 3, we find that our network decomposes sketches into modular structures like rectangles, line-arcs and parallel lines that align symmetrically, even though no such prior knowledge is applied during training except for concept modularity. Fig. 4 shows that a given concept can be used repetitively in different sketches, and structures with subtle differences in constraint relations can be detected and distinguished into different concepts of the library. Note that these subtle structural differences are subsumed in the input sketch graph, which makes them more difficult to detect. We refer to the supplementary for more examples of design intent parsing and instantiation of learned concepts, as well as quantitative analysis of the learned library.

Auto-completion is a critical feature of CAD modeling software for assisting designers. Given a partial sketch of primitives and their constraints, auto-completion aims at complementing them with the rest primitives and constraints to form regular and well-structured designs. Therefore, our concept detection and generation approach would naturally enhance the auto-completion task with better regularity. For training and evaluation, following previous work [18], we synthesize the partial input by removing a suffix of random length (up to $50\%$) from the sketch sequence, along with constraints that refer to the removed primitives, and make the model learn to generate the full sketches.

State-of-the-art methods [6, 13, 18, 24] formulate auto-completion through a combination of primitive and constraint generation models, both of which operate in an autoregressive fashion, with the constraint model conditioned on and referring (by pointers [23]) to the generated primitives. Since these works use diverse sketch encodings and have no publicly released code at submission time, for fair comparison, we implement the autoregressive baseline with our sketch encoding (Sec. 4.1).

Fig. 6 compares our method with autoregressive baseline under various primitive mask ratios: our method has superior primitive and constraint accuracy than the autoregressive baseline at almost all mask ratios. This difference confirms that since our method completes sketches concept-by-concept instead of primitive-by-primitive, more meaningful structures are likely to be generated. Our model also gains advantage by taking primitives and constraints together as input and generating primitives and constraints simultaneously, while in comparison the autoregressive baseline separates generation in two steps (primitives followed by constraints). Indeed, in practice CAD designers rarely finish all primitives first before supplementing the constraints, but rather apply constraints on partial primitives immediately whenever they form a design intent. Fig. 5 shows how our approach interprets the partial inputs and completes with modular concepts (see supplementary for more examples); in comparison, the autoregressive baseline does not provide such interpretable or regular completions.

To evaluate the impact of different loss terms of the induction objective (Sec. 5), we train several models in the absence of these losses respectively on the auto-encoding task. The results are shown in Table. 1. We see that removing the binary costs $\mathbf{C}_{bry}$ from reconstruction loss results in significant drop of constraint reconstruction, showing its necessity for constraint reference learning. Removing sharp reference loss $\mathcal{L}_{sharp}$ similarly fails constraint reference learning, although modularity enhancement bias loss makes all constraint references inside concepts. Removing the modularity enhancement bias loss $\mathcal{L}_{bias}$ only results in a slight drop in reconstruction quality but a significant drop in modularity, since without it cross-concept reference through arguments is more likely and therefore modularity suffers. We provide more ablation tests on hyper parameters like the numbers of concept queries $k_{qry}$ and arguments $k_{arg}$ in the supplementary.