PaperlayerView exact revision on arXiv

Source-linked AI summary

ShapeMOD: Macro Operation Discovery for 3D Shape Programs

R. Kenny Jones, David Charatan, Paul Guerrero, Niloy J. Mitra, Daniel Ritchie

arXiv:2104.06392v3cs.GRcs.AIcs.CVcs.LG

TL;DR

Shape programs should be compact yet retain meaningful editing controls, but designing useful macros has been difficult and largely expert-driven. ShapeMOD automatically discovers macros across imperative shape-program collections, and its macros improve downstream task performance and editing efficiency.

  • Problem

    Useful macros could make shape programs compact while preserving meaningful editing controls, but authoring them has been difficult and largely restricted to domain experts.

    Source: §1 · p. 2

  • Method

    ShapeMOD discovers macros from collections of imperative, statement-based programs, seeking compact representations measured by function calls and free parameters.

    Source: §1 · p. 2

  • Results

    ShapeMOD’s discovered macros improve performance on shape generation, point-cloud program inference, and goal-directed editing, and can be useful across categories.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Compressed programs using discovered macros lead to better shape-generation and point-cloud inference results, while a user study found more efficient shape-program editing.

    Source: §7 · p. 12

    The proposed macro abstractions are currently relatively simple free-parameter refactorings; extensions to loops or conditionals could enable more complex macros.

    Source: §7 · p. 12

Abstract

from arXiv · show

A popular way to create detailed yet easily controllable 3D shapes is via procedural modeling, i.e. generating geometry using programs. Such programs consist of a series of instructions along with their associated parameter values. To fully realize the benefits of this representation, a shape program should be compact and only expose degrees of freedom that allow for meaningful manipulation of output geometry. One way to achieve this goal is to design higher-level macro operators that, when executed, expand into a series of commands from the base shape modeling language. However, manually authoring such macros, much like shape programs themselves, is difficult and largely restricted to domain experts. In this paper, we present ShapeMOD, an algorithm for automatically discovering macros that are useful across large datasets of 3D shape programs. ShapeMOD operates on shape programs expressed in an imperative, statement-based language. It is designed to discover macros that make programs more compact by minimizing the number of function calls and free parameters required to represent an input shape collection. We run ShapeMOD on multiple collections of programs expressed in a domain-specific language for 3D shape structures. We show that it automatically discovers a concise set of macros that abstract out common structural and parametric patterns that generalize over large shape collections. We also demonstrate that the macros found by ShapeMOD improve performance on downstream tasks including shape generative modeling and inferring programs from point clouds. Finally, we conduct a user study that indicates that ShapeMOD's discovered macros make interactive shape editing more efficient.

1 INTRODUCTION

Shape programs can be readable and editable, but useful high-level macros have traditionally required expert design. ShapeMOD automatically discovers macros for imperative shape-program languages, aiming to balance compactness with editable variation; its discovered macros improve performance across downstream tasks.

1 INTRODUCTION

  • A good shape program should be compact and high-level while retaining degrees of freedom for meaningful editing; macros expand into commands from the base language.Programs are also described as more readable and editable than other shape representations.Source: §1 · p. 2
  • The open challenge is to automate macro design, since manually authored macros are expert-designed and may not generalize to other modeling domains.Prior manually designed macros had helped with shape editing and generative modeling.Source: §1 · p. 2
  • ShapeMOD automatically discovers macros from collections of programs in imperative, statement-based languages with discrete and continuous parameters.It measures compactness by the number of function calls and free parameters needed to represent the collection.Source: §1 · p. 2
  • ShapeMOD seeks a middle ground: a small set of frequently used macros that covers program variation while retaining degrees of freedom for shape exploration.Using no macros leaves many free parameters, while a macro per shape would impede manipulation and learning to generate novel programs.Source: §1 · p. 2
  • ShapeMOD’s discovered macros improve performance on shape generation, program inference from point clouds, and goal-directed shape editing, and can generalize across categories.The evaluation uses collections of ShapeAssembly programs.Source: §1 · p. 2

2 BACKGROUND & RELATED WORK

Prior work addresses grammar induction, functional-program abstraction, single-program rewriting, shape abstraction, and shape generation or induction. ShapeMOD instead discovers abstractions across imperative programs with continuous-parameter relationships; the paper demonstrates it using ShapeAssembly.

2.1 Related Prior Work

  • Prior common-abstraction methods include grammar induction and functional-program systems, but the cited grammar approaches are context-free and EC/DreamCoder cannot discover relationships between continuous variables.ShapeMOD is presented as the first approach to discover such relationships across imperative programs.Source: §2.1 · p. 3
  • Single-program rewriting optimizes one program, whereas ShapeMOD discovers macros common to a collection of programs.Examples include Szalinski’s search for a compact CAD program and the Carpentry Compiler’s manufacturing-cost optimization.Source: §2.1 · p. 3
  • Shape abstraction work targets shape geometry, while ShapeMOD abstracts the procedural structures that generate geometry; related downstream areas include shape generation and program inference from sensor input.The paper reports improved novel-shape generation and point-cloud reconstruction when using macro-enhanced ShapeAssembly programs.Source: §2.1 · p. 3

2.2 Background: ShapeAssembly

  • ShapeAssembly is an imperative DSL for creating 3D shape structures by defining parts and attaching them; its base commands are Cuboid and attach, alongside existing macros.The described macros are squeeze, reflect, and translate; the language includes discrete and continuous parameters.Source: §2.2 · p. 3

3 MACRO OPERATOR DISCOVERY

ShapeMOD alternates macro proposals with program refactoring, seeking a compact library that removes extraneous degrees of freedom while retaining meaningful shape manipulation. Its objective balances library size, free parameters, and parameter error.

3.1 Overview

  • Alternating proposal and integration rounds let later macros use earlier macros, enabling discovery of increasingly complex operators.Proposal finds clusters and candidate macros; integration adds candidates when they improve the objective.Source: §3.1 · p. 4, Figure 3 · p. 5
  • ShapeMOD addresses real-valued parameters and imperative line-ordering challenges by clustering shared program structures and abstracting expressions across related shapes.This approach is intended to find parametric relationships that generalize beyond a single program.Source: §3.1 · p. 4

3.2 Initialization

  • The experiments initialize the library with five manually designed ShapeAssembly functions and derive programs and valid line orderings from PartNet structures.Each dataset entry pairs program lines with the orderings that reproduce the correct output geometry.Source: §3.2 · p. 4, §3.1 · p. 4

3.3 Objective Function

  • The objective minimizes a weighted combination of library size, free parameters in represented programs, and errors from using the refactored programs.Weights allow different parameter types and errors to count differently.Source: §3.3 · pp. 4–5

3.4 Finding the Best Program for a Given Library

  • A beam search finds the lowest-objective program by covering ordered program lines with library-function expansions that match discrete values exactly and continuous values within ε = 0.05.The search uses width 10; larger matching tolerances led to degenerate geometry.Source: §3.4 · p. 5

4 PROPOSAL PHASE

The proposal phase samples clusters of structurally matching programs, builds an abstracted program for each cluster, and turns reusable sequences into candidate macros. It generalizes candidates before passing them to integration.

4.1 Form a Program Cluster

  • Each proposal round samples structurally matching programs with the same commands and cuboid IDs, weighting matches by continuous-parameter distance to favor semantically consistent clusters.The procedure samples 20 programs for a cluster.Source: §4.1 · pp. 5–6

4.2 Find Abstracted Program for Cluster

  • For each cluster, the algorithm greedily builds a program with few free parameters that matches at least 70% of the next cluster lines.It chooses among library functions according to how many free parameters they constrain and retains parameter choices valid for at least the target share of programs.Source: §4.2 · p. 6

4.3 Proposing Candidate Macros

  • Candidate macros come from abstracted-program line sequences that simplify the covered lines by removing degrees of freedom.The algorithm records the originating cluster and covered lines for later frequency statistics.Source: §4.3 · p. 6

4.4 Generalizing Macros

  • To broaden candidates that may be overly specific or near-duplicates, ShapeMOD adds macros within two program edits that generalize each candidate.A generalizing macro can reproduce every output of the macro it generalizes; these relationships update coverage statistics for ranking.Source: §4.4 · pp. 6–7

5 INTEGRATION PHASE

The integration phase ranks candidate macros and tests whether adding them improves the library objective, while filtering program orderings that undermine macro discovery.

5.1 Ranking Candidate Macros

  • Candidates are ranked by occurrence percentage multiplied by weighted free-parameter gain over equivalent or generalizing functions already in the library.This heuristic prioritizes candidates without finding the best programs for the full dataset.Source: §5.1 · p. 7

5.2 Evaluating & Selecting Candidate Macros

  • The algorithm tests proposed library changes on a dataset subsample and keeps the version with lower objective value, with additional swaps to escape local minima.It may remove infrequently used functions, then test adding them back; after 20 candidate evaluations, it checks whether removing library functions helps.Source: §5.2 · p. 7

5 INTEGRATION PHASE

  • ShapeMOD improves objective f compared with No Macros on the dataset-compression evaluation.The table caption states that lower values are better for all compression metrics.Source: Table 1 · p. 8

5.3 Removing Bad Program Orders

  • After integration, ShapeMOD drops line orderings whose objective scores are significantly worse than the best ordering, improving later candidate rankings.The authors report that this filtering encouraged complex macro discovery, including the four-leg-base macro.Source: §5.3 · p. 8

6 RESULTS AND EVALUATION

The evaluation tests ShapeMOD on Chair, Table, and Storage programs, assessing compression and downstream generation, point-cloud inference, editing, and cross-category discovery.

6.1 Discovered Macros

  • 12 Chair macros remove 30% of program lines, 64% of discrete parameters, and 30% of continuous parameters, decreasing ShapeMOD’s objective by 37%.ShapeMOD compresses more than the baseline approach, especially for continuous parameters, while using half as many or fewer new macros.Source: §6.1 · p. 8

6.2 Generating 3D Shapes

  • ShapeMOD macros are best on % fool and Frechet Distance; complexity and validity generally improve, while simple baseline macros perform worse than no macros.The table compares the quality of programs sampled from learned generative models.Source: Table 2 · p. 10, §6.2 · p. 10

6.3 Inferring 3D Shape Structures

  • Point-cloud inference with ShapeMOD improves Chamfer distance and F-score by an average relative 11% across categories and always improves stability and rootedness.Macros help especially on Storage, the most structurally and geometrically heterogeneous category.Source: §6.3 · pp. 10–11, Table 3 · p. 11

6.4 Interactive Shape Editing

  • In a 38-participant, six-task user study, macro users reached targets faster on all tasks and rated most tasks slightly easier.Tasks covered Chair, Table, and Storage editing.Source: §6.4 · p. 12

6.5 Cross-category Macro Discovery

  • Cross-category libraries improve compression but slightly degrade novel-shape generation and program inference versus category-specific libraries; per-category discovery is slightly better for downstream tasks.The marginal performance gap also provides evidence that the discovered macros can generalize.Source: §6.5 · p. 12

7 CONCLUSION & FUTURE WORK

ShapeMOD discovers macros across shape-program datasets, yielding compressed programs that improve generative modeling, point-cloud program inference, and editing efficiency. Its current scope is bounded by simple parameter abstractions, integration cost, the need for a base DSL, and macros without semantic names; the method is general in principle to qualifying imperative languages.

7 CONCLUSION & FUTURE WORK

  • ShapeMOD discovers common abstractions across imperative programs with continuous-variable relationships, and its compressed programs improve shape generation and point-cloud program inference.The authors describe it as the first method to discover such abstractions and report a user study showing more efficient shape-program editing.Source: §7 · p. 12
  • Compressed programs also enable more efficient shape-program editing in the user study.This is a separate reported benefit alongside the improvements in generative modeling and point-cloud program inference.Source: §7 · p. 12
  • The current macro proposals use relatively simple free-parameter refactorings, such as replacing parameters with constants or expressions of other variables.The authors suggest that adding loops or conditional branches might enable more complex macros, including new symmetry groups.Source: §7 · p. 12
  • Optimal integration is intractable, and the greedy approximation can be slow on large program collections.Finding optimal programs P*(D, L) is the major computational bottleneck; neurally guided program search is proposed as a possible acceleration.Source: §7 · p. 12
  • ShapeMOD requires programs in a base DSL, and datasets readily convertible to that format are not widely available.The authors propose exploring discovery of a shape programming language from parts-per-shape data.Source: §7 · p. 12
  • Discovered macros lack semantic names, and some study participants found base ShapeAssembly functions easier to use despite editing more efficiently with macros.Assigning semantic names is identified as future work.Source: §7 · p. 12
  • Although demonstrated with ShapeAssembly, ShapeMOD is general in principle to imperative languages with the required parameter types.The authors note that shader programming may also be expressible in such a language.Source: §7 · p. 12

A MODIFIED SHAPEASSEMBLY GRAMMAR

The modified ShapeAssembly grammar interleaves attachments and symmetry operations with cuboid definitions, encouraging macros that mix operators. This ordering also lets non-Cuboid operators act on the last-defined cuboid, removing an index parameter from each such function.

A MODIFIED SHAPEASSEMBLY GRAMMAR

  • Interleaving attachments and symmetry commands with cuboid definitions permits macros to mix operators rather than consisting mostly of one command type.Each PBlock defines a Cuboid, attaches it to a previous cuboid or the bounding volume, and may apply a symmetry operation; non-Cuboid operators act on the last-defined cuboid, removing one cuboid-index parameter per function.Source: A MODIFIED SHAPEASSEMBLY GRAMMAR · p. 14

B BASELINE METHOD FOR MACRO OPERATOR DISCOVERY

The baseline discovers macros through a single pass over canonicalized program orders, promoting frequent function subsequences and parameter values to macros and constants. ShapeMOD’s discovered macros outperform this baseline on every task considered.

B BASELINE METHOD FOR MACRO OPERATOR DISCOVERY

  • The baseline records subsequences from one canonical order per program and turns subsequences appearing in over 10% of programs into macros.It converts parameters to constants when at least 90% of observed discrete values match, or continuous values fall within .05 of their mean.Source: B BASELINE METHOD FOR MACRO OPERATOR… · p. 14
  • ShapeMOD’s discovered macros outperform the baseline macros on every task considered.The baseline comparison uses ShapeMOD’s program-finding step to create programs with the baseline-discovered macros.Source: B BASELINE METHOD FOR MACRO OPERATOR… · pp. 14–15

C A NETWORK ARCHITECTURE FOR ANY LIBRARY

To model programs in any discovered library, the authors generalize a hierarchical sequence VAE whose original architecture assumed a fixed ShapeAssembly library. Its line representation and decoder adapt to the functions and parameters in each library.

C A NETWORK ARCHITECTURE FOR ANY LIBRARY

  • The authors generalize a hierarchical sequence VAE to generate programs using any library discovered by ShapeMOD.The encoder embeds hierarchical programs in a latent space, and the decoder maps latent codes back to hierarchical programs.Source: C A NETWORK ARCHITECTURE FOR ANY LIBRARY · p. 15
  • The generalized line tensor represents function type with |L| + 2 one-hot indices, including START and STOP tokens, and reserves parameter slots according to library L.Discrete-parameter slots depend on valid values and maximum free-parameter counts; continuous-parameter slots depend on each function’s continuous-parameter count.Source: C A NETWORK ARCHITECTURE FOR ANY LIBRARY · p. 15
  • The decoder uses a library-dependent function predictor plus parameter sub-networks for each function’s free discrete and continuous parameters.The function predictor has |L| + 2 outputs for library functions and START/STOP tokens.Source: C A NETWORK ARCHITECTURE FOR ANY LIBRARY · p. 15
  • The architecture uses three-layer MLP sub-networks and teacher-forced training with cross-entropy for discrete predictions and L1 loss for continuous predictions.Parameter subnetworks are invoked and tensor slots filled according to each predicted function type.Source: C A NETWORK ARCHITECTURE FOR ANY LIBRARY · p. 15

D SHAPEMOD CONVERGENCE PROPERTIES

The full ShapeMOD variant achieves the lowest objective value among the tested ablations, and the library improves over multiple algorithm rounds.

D SHAPEMOD CONVERGENCE PROPERTIES

  • The full ShapeMOD variant achieves the lowest objective function value among the tested ablation variants.The experiment measures how well each chair-program macro library compresses the dataset.Source: D SHAPEMOD CONVERGENCE PROPERTIES · p. 15
  • The discovered macro library improves through multiple rounds of the algorithm, as shown by the top three rows.Source: D SHAPEMOD CONVERGENCE PROPERTIES · p. 15
  • The ablation compares changes to parameter-similarity sampling, search, bad-order filtering, macro generalization, and macro-validity criteria.Variants replace or remove the corresponding algorithm component.Source: D SHAPEMOD CONVERGENCE PROPERTIES · p. 15

E SHAPE GENERATION QUALITATIVE COMPARISON

Qualitative generations with ShapeMOD macros are more plausible across shape collections, with a more pronounced difference for storage than for chairs and tables.

E SHAPE GENERATION QUALITATIVE COMPARISON

Loading 2104.06392v3…