New algorithm a Christmas gift to 3-D printing -- and the environment

December 15, 2014

Just in time for Christmas, Simon Fraser University computing science professor Richard Zhang reveals how to print a 3D Christmas tree efficiently and with zero material waste, using the world's first algorithm for automatically decomposing a 3D object into what are called pyramidal parts.

A pyramidal part has a flat base with the remainder of the shape forming upwards over the base with no overhangs, much like a pyramid. A pyramidal shape is optimal for 3D printing because it incurs no material waste and saves print time.

The algorithm promises to become a big deal in the world of 3D printing, and also has applications for designing molds and for casting.

Zhang, a computer graphics expert specializing in geometric modeling and processing, developed the algorithm with PhD candidate Ruizhen Hu, an international student from Zhejiang University in China.

Their research paper, Approximate Pyramidal Shape Decomposition, was published this month in ACM Transaction on Graphics, the world's leading graphics journal. As well, Hu presented their research at a major graphics conference, SIGGRAPH Asia, this month in Shenzhen, China.

In 3D printing, the printer deposits melted plastic layer by layer in a bottom-up fashion. If the shape has an overhang, such as a tree branch, extra material has to be printed beneath it as support. This extra plastic is waste material and must be removed, which can be time consuming and difficult. And removing waste material that supports an object's hollow interior or tiny fragile parts, like the star atop a Christmas tree, can be almost impossible without causing breakage.

"Coming up with a practical algorithm to decompose 3D objects into the smallest possible number of pyramidal parts was quite a challenge," says Zhang.

"Importantly, it is impractical for most real-world objects to be broken into exactly pyramidal parts since this would result in too many parts," he says.

"Ruizhen came up with a really clever way of transforming the problem to obtain an effective solution."

The new algorithm partitions the object into a small number of nearly pyramidal parts that can be 3D-printed with little or no material waste.

These printed parts can then be glued together to form the finished object. The Christmas tree, for example, is divided in half for fabrication, and then glued together.

In molding and casting, the ideas are similar, says Zhang. "If the molded or cast parts are pyramidal, then removing the mold or cast after fabrication would not result in any breakage," he says.

In keeping with the Christmas theme, he suggests chocolatiers could use the algorithm to design chocolate molds for Christmas trees or reindeer.
-end-
The research is supported by NSERC and GRAND NCE funding. The first year of Ruizhen Hu's SFU visit was supported by the China Scholarship Council. The 3D printer was purchased for the GrUVi lab, through an NSERC Research, Tools and Instruments (RTI) grant.

As Canada's engaged university, SFU is defined by its dynamic integration of innovative education, cutting-edge research and far-reaching community engagement. SFU was founded almost 50 years ago with a mission to be a different kind of university--to bring an interdisciplinary approach to learning, embrace bold initiatives, and engage with communities near and far. Today, SFU is a leader amongst Canada's comprehensive research universities and is ranked one of the top universities in the world under 50 years of age. With campuses in British Columbia's three largest cities--Vancouver, Surrey and Burnaby--SFU has eight faculties, delivers almost 150 programs to over 30,000 students, and boasts more than 130,000 alumni in 130 countries around the world.

Simon Fraser University: Engaging Students. Engaging Research. Engaging Communities. Photos: http://at.sfu.ca/iMDjDh

Simon Fraser University

Related Algorithm Articles from Brightsurf:

CCNY & partners in quantum algorithm breakthrough
Researchers led by City College of New York physicist Pouyan Ghaemi report the development of a quantum algorithm with the potential to study a class of many-electron quantums system using quantum computers.

Machine learning algorithm could provide Soldiers feedback
A new machine learning algorithm, developed with Army funding, can isolate patterns in brain signals that relate to a specific behavior and then decode it, potentially providing Soldiers with behavioral-based feedback.

New algorithm predicts likelihood of acute kidney injury
In a recent study, a new algorithm outperformed the standard method for predicting which hospitalized patients will develop acute kidney injury.

New algorithm could unleash the power of quantum computers
A new algorithm that fast forwards simulations could bring greater use ability to current and near-term quantum computers, opening the way for applications to run past strict time limits that hamper many quantum calculations.

QUT algorithm could quash Twitter abuse of women
Online abuse targeting women, including threats of harm or sexual violence, has proliferated across all social media platforms but QUT researchers have developed a sophisticated statistical model to identify misogynistic content and help drum it out of the Twittersphere.

New learning algorithm should significantly expand the possible applications of AI
The e-prop learning method developed at Graz University of Technology forms the basis for drastically more energy-efficient hardware implementations of Artificial Intelligence.

Algorithm predicts risk for PTSD after traumatic injury
With high precision, a new algorithm predicts which patients treated for traumatic injuries in the emergency department will later develop posttraumatic stress disorder.

New algorithm uses artificial intelligence to help manage type 1 diabetes
Researchers and physicians at Oregon Health & Science University have designed a method to help people with type 1 diabetes better manage their glucose levels.

A new algorithm predicts the difficulty in fighting fire
The tool completes previous studies with new variables and could improve the ability to respond to forest fires.

New algorithm predicts optimal materials among all possible compounds
Skoltech researchers have offered a solution to the problem of searching for materials with required properties among all possible combinations of chemical elements.

Read More: Algorithm News and Algorithm Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.