塑料圣诞树和各种模型圣诞树已经够招人烦的了，现在又新来了一个 3D 打印圣诞树。先别着急，温哥华西门弗雷泽大学的一名计算机科学研究员 Richard Zhang 最近开发出了一种全新的打印算法。这种算法的意义，可能远比打印一棵圣诞树重要得多。

Zhang 解决了一个现实的问题：节省材料。打印一个带有凸出部分的物体（比如树枝），需要多余的材料来支持上方凸出的部分；当打印完成后，这些多余的材料就会被扔掉，变成垃圾。

针对这一问题，Zhang 的解决办法是使用锥形组件。不论是打印一个实际的物品，还是解决一道抽象的运算，我们都需要将其划分成一个个小部分。这样一来，再大再复杂的问题也可以通过迭代和递归来解决。用行话来说，这些小的单位被叫做基本几何体。

“将一个复杂的形状化为简单的基本何体，是最基本的几何问题之一，” Zhang 和团队在ACM Transaction on Graphics上发表的一篇论文中写道。“如果形状变得更加简单，那么计算和操作任务将会被更为高效的执行。”

_{Richard Zhang, 图片由西蒙弗雷泽大学提供。}

为了最大限度地减少组成物体所需的基本几何体的数量，物体的轮廓就要做些牺牲。Zhang 主张并证明，这些小金字塔的确是个解决之道。

至于其中的原因，Zhang 解释说是因为这些锥体是 2.5D 的。2.5D是个被应用于制造业（以及计算机绘图，不过含义有所不同）的概念，它描述的是一个没有凸出的物体；而锥形只有一个尖端，可以看做是一个 2D 平面到第三维度的投影，形状可比一颗椰子树什么的要简单多了。

既然如此，那我们干嘛不用这些小金字塔打印呢？答案是数学。这种将物体解构为一个个小锥形的计算，是个超级难题。在21世纪初，该问题被证明为 “NP 困难”。“NP 困难” 的问题，是真正意义上复杂且可怕的难题，其难度比大多我们认为复杂且可怕的难题还要大。看起来，我们还是别指这些望金字塔了。

Zhang 也没有找到锥体计算问题的的解答。他采取的是个折中的方法：虽然比完美方案要多浪费一些材料，但却给出一个切实可行的解答。“我们通过聚类自下而上的制作备用锥形零件，” Zhang 解释说。“聚类是建立在输入的形状中，两个基本几何体从属于同一个较大的锥体模块的这种可能性之上。算法优先处理较大的锥体模块，因为它们更可能达成体积最小的分解。通过聚类，我们逐渐完成体积更大的几何体。我们称之为 ‘单元’ 和 ‘块’。每个备用锥形零件都是由合并起来的 ‘块’ 组成的。”

如图所示：

不过即使有了新算法，在我们看来相当小的一个物件也需要花10分钟以上的时间进行计算。可想而知，打印一棵树出来将是个多大的工程。