MIT technique ‘reverse engineers’ complex 3D CAD models
The researchers used “program synthesis” – a process by which computer programs are generated from descriptions of their intended behavior – to break down CAD models into their primitive shapes, such as spheres and cuboids. Their technique, say the researchers, promises to make it far easier for users to customize CAD models for manufacturing and 3D-printing applications.
Currently, many of today’s 3D models are created using constructive solid geometry (CSG), where numerous basic shapes – or “primitives” – with a few adjustable parameters can be assembled in various ways to form a single object. When finalized, the compiled digital object is then 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. Customizing that mesh, however, say the researchers, is no easy task.
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 daunting and time consuming, say the researchers. Traditional techniques to convert triangle meshes back into shapes don’t scale well to complex models or work accurately on low-resolution, noisy files.
Reversing the process that builds CAD models, the researchers’ method disassembles 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 represent 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.
“At a high level, the problem is reverse engineering a triangle mesh into a simple tree,” says Tao Du, a PhD student in the Computational Fabrication group of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL). “Ideally, if you want to customize an object, it would be best to have access to the original shapes – what their dimensions are and how they’re combined.”
“But,” says Du, “once you combine everything into a triangle mesh, you have nothing but a list of triangles to work with, and that information is lost. Once we recover the metadata, it’s easier for other people to modify designs.”
In their work, the researchers built a dataset of 50 3D CAD models of varying complexity. In experiments, they demonstrated that their 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 researchers say.
The process could be useful in manufacturing or when combined with 3D printing software, says Du. This is especially important in the age of design sharing, where amateur 3D-printer users upload 3D-print models to websites for online communities to download and modify. Uploads are mostly triangle meshes, because meshes are far more universally accepted across platforms than the original CSG-based CAD files.
“We have tons of mesh models, but comparatively few CAD files behind them,” Du says. “If users want to reproduce the design at home and customize it a little, then this technique could be useful.”
Currently, the system handles four primitive shapes – spheres, cylinders, cuboids, and tori (donut shapes). Looking ahead, the researchers hope to increase the complexity of CSG “grammar” to handle far more shapes and more modifiers outside just Boolean operators.
For more, see “InverseCSG: Automatic Conversion of 3D Models to CSG Trees (PDF).