Nearly all commercial products start as a CAD file — a 2D or 3D model with the product’s design specifications. One method that’s widely used to represent today’s 3D models is constructive solid geometry (CSG), a technique where numerous basic shapes (primitives) with a few adjustable parameters can be assembled in various ways to form a single object. When finalized, the compiled digital object is converted to a mesh of 3D triangles that defines the object’s shape. These meshes are used as input for many applications, including 3D printing and virtual simulation.

The technique reverse-engineers complex 3D CAD models — breaking them down into the many individual shapes they’re made of — to customize for manufacturing and 3D printing applications. (Photo courtesy of the researchers)

Customizing that mesh is complex; for example, adjusting the radius in one portion of the object requires individually tweaking the vertices and edges of each affected triangle. With complex models comprising thousands of triangles, customization becomes time-consuming. Traditional techniques to convert triangle meshes back into shapes don’t scale well to complex models or work accurately on low-resolution, noisy files.

A system was developed that applies a technique called “program synthesis” to break down CAD models into their primitive shapes, such as spheres and cuboids. Program synthesis automatically constructs computer programs based on a set of instructions. Essentially, to build CAD models, designers assemble individual shapes into a final object — the new method does the reverse, disassembling the CAD models into individual shapes that can be edited. As input, the system takes a 3D triangle mesh and first determines the individual shapes that make it up. Program synthesis crawls through the shapes, trying to figure out how the shapes were put together and assembled into the final model.

In doing so, it breaks down the mesh into a tree of nodes that represents the primitive shapes and other nodes detailing the steps for how those shapes fit together. The final shapes contain editable parameters for users to tweak that can be re-uploaded to the mesh.

A dataset of 50 3D CAD models of varying complexity was built. In experiments, the system could reverse-engineer CAD files composed of up to 100 primitive shapes. Simpler models can be broken down in around a minute. While run times can be quick, the key advantage of the system is its ability to distill very complex models into simple, foundational shapes. The process could be useful in manufacturing or when combined with 3D printing software.

Program synthesis automatically finds candidate computer programs given a specific “grammar,” meaning the structure it must work within such as trees and mathematical specifications. Using those constraints, program synthesis works its way back and fills in the blanks to construct an algorithm that satisfies those specifications, given new input. The technique is used for simple components of software engineering. In the new system, the grammar is CSG, represented as trees. Each final node (with no branching nodes) represents a primitive shape with clearly defined parameters, and intermediate nodes represent basic ways the shapes converge and relate.

For more information, contact Abby Abazorius at This email address is being protected from spambots. You need JavaScript enabled to view it.; 617-253-2709.

Tech Briefs Magazine

This article first appeared in the May, 2019 issue of Tech Briefs Magazine.

Read more articles from the archives here.