Jan 4 2019
An innovative method that “reverse engineers” intricate 3D computer-aided design (CAD) models has been developed by MIT researchers. Through this technique, users can more easily customize the CAD models for 3D printing and manufacturing applications.
MIT researchers have devised a technique that “reverse engineers” complex 3D computer-aided design (CAD) models—breaking them down into the many individual shapes they are made of—to make them far easier for users to customize for manufacturing and 3D printing applications. (Image credit: MIT)
Almost all commercially available products begin as a CAD file or as a 2D/3D model with the design specifications of the product. Constructive solid geometry, or CSG, is one technique that is extensively utilized to represent current 3D models. In this method, many numbers of basic shapes, or “primitives,” with several modifiable parameters can be assembled in a variety of ways to produce one object. Once the compiled digital object is finalized, it is transformed to a mesh of 3D triangles that define the shape of the object. Such meshes are utilized as input for various applications, such as virtual simulation and 3D printing.
However, it is not easy to customize that mesh; for instance, in order to adjust the radius in one part of the object, the edges and vertices of each affected triangle have to be tweaked individually. Similarly, in the case of intricate models containing thousands of triangles, customization takes a long time and is rather daunting. Conventional methods for converting triangle meshes back into shapes do not work precisely on noisy, low-resolution files or scale well to intricate models.
MIT researchers presented a paper at the recent AMC SIGGRAPH Asia conference, describing a system that uses a method known as “program synthesis” through which CAD models can be broken down into their primitive shapes, like cuboids and spheres. Computer programs are automatically constructed by program synthesis depending on a series of instructions.
Principally, designers assemble separate shapes into a final object to construct CAD models; however, the researchers’ technique does the reverse by disassembling the CAD models into separate editable shapes. As input, the system considers a 3D triangle mesh and initially establishes the distinct shapes that make it up. The program synthesis technique crawls through the shapes, attempting to understand the way the shapes were assembled and put together into the final model. While doing so, the technique breaks down the mesh into a tree of nodes representing the primitive shapes and other nodes describing the steps for how those primitive shapes fit together. The ultimate shapes consist of editable parameters that can be tweaked by the users and re-uploaded to the mesh.
Foundational shapes
A dataset of 50 3D CAD models of variable complexity was constructed by the researchers. In experiments, the investigators showed that their system has the potential to reverse engineer CAD files containing around 100 primitive shapes. It takes approximately one minute to break down simpler models. According to the researchers, while run times can be rapid, the main benefit of the system is its potential to distill extremely intricate models into simple, foundational shapes.
At a high level, the problem is reverse engineering a triangle mesh into a simple tree. 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 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.
Tao Du, PhD Student, Computational Fabrication Group, Computer Science and Artificial Intelligence Laboratory, MIT
Du added that the process may prove handy in manufacturing or it may be useful when integrated with 3D printing software. This is particularly significant in the age of design sharing, where 3D-print models are uploaded to websites by novice 3D-printer users, enabling online communities to download and adjust. Usually, uploads are triangle meshes, since meshes are much more universally accepted across platforms when compared to the original CSG-based CAD files.
We have tons of mesh models, but comparatively few CAD files behind them. If users want to reproduce the design at home and customize it a little, then this technique could be useful.
Tao Du, PhD Student, Computational Fabrication Group, Computer Science and Artificial Intelligence Laboratory, MIT
Trees and triangles
Program synthesis can automatically detect candidate computer programs given mathematical specifications and a certain “grammar,” which means the structure it should work within, like trees. Program synthesis uses those limitations to work its way back and fill in the blanks to build an algorithm that meets those specifications, given fresh input. For instance, the method is applied for simple components of software engineering.
In the investigators’ work, CSG is the grammar and is denoted as trees. Each final node—that is without branching nodes—signifies a primitive shape with well-defined parameters, and intermediate nodes signify the basic ways the shapes unite and relate.
The investigators devised a technique that allows program synthesis to scan a whole 3D mesh and, in essence, think of each probable CSG tree it could generate as a novel candidate program.
After an input mesh is received by the system, a preprocessing step finds the potential locations, parameters, and orientations of all primitive shapes. This process produces a huge point cloud across the triangle mesh’s surface. From these points, a unique “primitive-detection” algorithm infers the dimensions for individual primitive shapes making up the mesh.
Subsequently, tons of points in the whole 3D space are sampled and flagged as either outside or inside the mesh. This helps in establishing the way the shapes relate or converge to each other. A simple example is a mesh containing a pair of spheres, A and B, combined together. If a single sampled point falls within sphere A, one within sphere B, and one at the intersection of the two (within both spheres A and B), it is most probably a union of both the shapes.
Considering this information, together with the primitive dimensions, the program synthesis technique can possibly produce a CGS tree. However, with regards to 3D meshes of even low complexity, program synthesis would need to sample an innumerable number of points. This would produce a large search space that is computationally not viable to handle. “Directly feeding all the samples will choke the program synthesizer,” Du stated.
To ensure the efficient operation of the system, the team developed a sampling technique that produces a number of tiny subsets of point samples across the 3D space, which makes it relatively easier for program synthesis to calculate. When these subsets are sampled, a fresh candidate “program,” or CGS tree, is created that can be considered as accurate. After various iterations—and utilizing methods to remove specific trees and points—the system lands on the exact CGS tree for individuals shapes, with accurate intermediate steps as well as final parameters. As the system computationally trails the intermediate steps back to the final object, edited shapes, if any, are fed back into the mesh.
At present, only four primitive shapes—cuboids, cylinders, spheres, and tori (donut shapes) can be handled by the system. Next, the investigators are planning to raise the complexity of CSG grammar to handle more modifiers and even more shapes beyond Boolean operators.