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.
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.[Source/Images: MIT]
You May Also Like
3D Printing News Briefs, November 24, 2021: 3D Printing Steel, Glass, Skin Models, & More
In today’s 3D Printing News Briefs, we’re starting with a roundtable discussion on AM workforce development. Then we’re moving on to research, first about 3D printing a better steel, and...
ABCorp Adds Desktop Metal 3D Printing to its Boston Center of Excellence
American Banknote Corporation (ABCorp), one of the oldest manufacturing services providers in the United States, is announcing another expansion to its Center of Excellence in Boston. Back in May, ABCorp...
Nexa3D Reveals New 3D Printers, Executives, & Oqton Partnership at Formnext
As Formnext 2021 winds down in Frankfurt, Germany, we’re learning more about some of the announcements made during the event. We recently told you that Nexa3D, which specializes in developing...
Formnext 2021: First Day Impressions of Post-Lockdown 3D Printing
Formnext is back and we’ve headed once more to Frankfurt, the lovely city where you can see people smoking crack on the street at 19:00 while the financiers zoom by...
View our broad assortment of in house and third party products.