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]
Subscribe to Our Email Newsletter
Stay up-to-date on all the latest news from the 3D printing industry and receive information and offers from third party vendors.
You May Also Like
Anisoprint Unveils New Office At Shanghai 3D Printing Center
Shanghai’s newest 3D printing hub, the Additive Manufacturing Technology Center (AMTC), is rapidly growing, increasingly attracting businesses to its innovation-driven environment. One of its latest additions is Anisoprint, a Luxembourg...
3D Printing News Briefs, March 22, 2023: Carbon Sequestration, 3D Printed Bird Drones, & More
In 3D Printing News Briefs today, Meltio is expanding its worldwide partner network, and 3D Systems introduced its VSP Connect portal. Oregon State University and Sandia National Laboratories received a...
3D Printing News Briefs, February 18, 2023: Post-Processing, Footwear, & More
First up in today’s 3D Printing News Briefs, Wohlers Associates has published a specialty report on post-processing, and AON3D has launched a line of filaments. On to business, Lithoz and...
Europe’s Largest Private Biomethane Deal to Drive Arkema’s Sustainable 3D Printing Materials
French energy company Engie (EPA: ENGI) announced it would supply 300 gigawatt hours (GWh) of renewable biomethane per year to local chemical company Arkema (EPA: AKE) for the next decade....
Upload your 3D Models and get them printed quickly and efficiently.