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
New Data Report: 3D Printing Revenues Reached $2.12B in Q3 2020, Says SmarTech Analysis
Due to the COVID-19 pandemic, the global economy took a steep nose dive in 2020. This included the 3D printing market during the first half of the year, but our...
Dream M&As: 3D Printing Mergers and Acquisitions We’d Like to See in 2021
Inspired in part by the acquisition of EnvisionTEC by Desktop Metal and of Origin by Stratasys, we’ve been brainstorming about the newly hot 3D printing stocks and renewed interest from...
3D Printing Webinar and Virtual Event Roundup: January 17, 2021
We’ve got all kinds of virtual events and webinars to share with you this week, with topics ranging from 3D design and medical applications to simulation and more. Read on...
Desktop Metal (DM) Buys EnvisionTEC to Quickly Boost Revenues?
Wow. Publicly traded Desktop Metal (NYSE:DM) has just purchased EnvisionTEC for $300 million in stock and cash. For my part, I would have paid all my money to be a...
View our broad assortment of in house and third party products.