MIT CSAIL Program Breaks Complex CAD Models Down Into Simpler Shapes for Easier 3D Printing

At the ACM SIGGRAPH Asia conference, a group of MIT researchers presented a paper describing their development of a system that applies what’s called program synthesis, which constructs computer programs automatically based on instructions, to break complex 3D meshes models down into primitive shapes, such as cubes and spheres. Essentially, the method is used to reverse engineer the models, so they are easier to customize and modify for 3D printing.

Most commercial products begin life as a CAD file, and often, a method called constructive solid geometry (CSG), where several primitive shapes are put together in a variety of ways to form one object, is used to represent 3D models. Once the digital object is complete, it’s then converted into a mesh made up of 3D triangles that further define its shape, render it or print it. But it’s not easy to customize these meshes for a variety of reasons.

“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,” explained Tao Du, a PhD student in the Computational Fabrication group of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL). “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.”

Designers often build CAD models by putting individual shapes together into a final object. The team’s method goes the opposite way, disassembling the meshes into individual shapes that are easier to edit. First, their system determines the shapes that make up a 3D triangle mesh, using program synthesis to determine just how the shapes were assembled into the resulting model. This actually breaks the mesh down into what MIT calls “a tree of nodes” that is representative of the primitive shapes; additional nodes explain how the shapes all fit together. The resulting shapes have parameters that can be edited by users and later re-uploaded to the mesh.

L: the original mesh. R: results from the pipeline using 10, 20, 40, and 57 surface primitives. As the number of primitives increases, the result converges to the input mesh.

To test their work, the team built a dataset of 50 3D CAD models, in various levels of complexity, and showed how their system was able to reverse engineer CAD files made of up to 100 primitives. Not only can the system break down simpler models in about a minute, but it can also break down complex models into more simple shapes.

Du said that the process can be helpful when combined with 3D printing software, which is good news for amateurs who upload 3D models to websites so others can download and modify them, as most uploads are mainly triangle meshes.

“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,” Du said.

Program synthesis will automatically find candidate computer programs with a certain grammar (the structure it works within), like trees; the research team’s grammar is CSG, and each final node, without any branches, is representative of a primitive shape with clear parameters. Using the specific grammar, and mathematical specifications, the program works backward to build an algorithm by filling in the blanks.

The team’s program synthesis can scan an entire 3D mesh, thinking of each CSG tree it could potentially create as a brand new candidate program. The possible orientations, parameters, and locations of all the primitives are detected once the system receives an input mesh, and a massive point cloud is created across the surface. The dimensions of each shape that makes up the mesh are then inferred from these points by a special algorithm. Then, the researchers sample points across the entire 3D space, flagging them as inside or outside the mesh to show how the shapes relate to each other.

Technically, program synthesis could be used to create a full CSG tree, but even less complex 3D meshes would need to have tens of thousands of points sampled, which would be “computationally impractical.”

Du said, “Directly feeding all the samples will choke the program synthesizer.”

That’s why the team created a sampling method that more efficiently creates multiple small subsets of point samples; then, a new candidate program, or CSG tree, is created from sampling these subsets. After multiple iterations, and getting rid of several trees and points, the system arrives at the correct tree for each shape. Then, any edited shapes go back into the mesh while the system follows the steps backward to arrive at the final object.

Right now, the team’s system only works with cuboids, cylinders, spheres, and tori (donut shapes), but they plan on increasing the CSG grammar’s complexity so more shapes can be handled. Could this be used to automatically turn any mesh into a more adaptable CAD file? Could this “computationally impractical” problem be solved through a cloud based solution? CSAIL’s development has interesting possible implications for raising the adaptability and usability of many of the models that populate our 3D printing world.

Discuss this research and other 3D printing topics at 3DPrintBoard.com or share your thoughts in the Facebook comments below.