Obviously: A 3D-Printed Christmas Tree

Fake plastic Christmas trees and their mannequin version of holiday cheer are bad enough—at least outside of a legitimate bomb shelter environment—but now we have the 3D-printed version too. Said tree imposter comes courtesy of a computer science researcher at Vancouver's Simon Fraser University, Richard Zhang, who has developed a new printing algorithm with potential to go far deeper than the seasonal Xmas pitch.

In other words, Zhang is solving a real-life problem: saving waste. Printing an object with overhanging parts, like a tree branch, requires the deposition of extra material below to support the top part through the printing process. At the end, this material is cut away and trashed. The answer, according to Zhang, is in using pyramidal components.

Whether it's in printing a physical object or just plain abstract computation, solving a problem usually means breaking it down into smaller, more manageable components. And so big gnarly problems are decomposed using iteration or recursion. In fabrication, those small sub-units are called primitives.

"Decomposing a complex shape into simpler primitives is one of the most fundamental geometry problems," Zhang and his team write in a recent paper published in the ACM Transaction on Graphics. "The main motivation is that most computation and manipulation tasks can be more efficiently executed when the shapes are simple."

In order to reduce the number of primitive shapes needed for a given object, that object is often approximated. Zhang argues (and demonstrates) that pyramids offer an answer.

The reason, Zhang says, is that pyramids are 2.5D. Two-and-a-half dimensions is a concept used in machining (and computer graphics, with a different meaning) to describe an object with no overhangs. It only has a top, and can be viewed as a projection of 2D flatness into the third dimension. This is a whole lot simpler than, say, a palm tree.

So why isn't everything printed using pyramidal primitives? Math. The computations involved in decomposing things into pyramids are extremely difficult. In the early-00s, it was proven that the problem is what's known as NP-hard. NP-hard problems are the truly, horribly complex tasks beyond the difficulty of most every other problem that we consider to be truly, horribly complex. It seemed that pyramids were out for good.

Zhang didn't find out some double-top secret solution to the pyramidal primitive computation problem. He just decided that it was worth allowing a less perfect, slightly more wasteful solution to make the problem practically manageable. A compromise.

"We build the set of candidate pyramidal parts bottom-up via clustering," Zhang explains.

"The clustering is based on the likelihood that two primitives interior to the input shape belong to the same, large pyramidal part. Preference is given to larger pyramidal parts since they are more likely to contribute to minimum-sized decompositions. Through clustering, we progressively build larger and larger solid primitives, which we call cells and then blocks, with each candidate pyramidal part formed by merging blocks."

It looks like this:

Even fairly small objects can still take more than 10 minutes to compute, even with the new algorithm, so a full-size tree would be quite an undertaking. Computing a nice shiny Festivus pole, however, is still assured to take no time at all.