在Dapper框架中,还存在着一个重要的算法设计问题:我们应该使用什么基本图元来进行模型的分解与排列?将模型分解成任意形状的部件可能可以减少部件的数量,但是排列的问题将会变得更加复杂。另一方面,形状规则方正的矩形(或三维空间中的长方体)非常易于排列,但却可能导致过多的分解部件。方法选择使用近似金字塔属性块(或简称金字塔块)作为分解与排列问题中的基本图元,将其扩展应用到DAP问题当中。金字塔块是具有单面平坦底面的类似地形的二维或三维形状,金字塔块包括但不仅限于矩形,定义更加广泛,并且有助于产生少数块的分解结果。金字塔块不仅仅有利于排列(底面平坦,易于对接测试),因其在逐层累积形式的打印过程中无需支撑材料还有利于打印。最后,金字塔块在水平和垂直的切割操作下产生的块也均为金字塔块,即金字塔块的自包含性。在Dapper中,我们从一个仅有少量金字塔块的初始化分解开始,通过对体素化后的块进行轴对齐的切割操作,优化搜索最优的DAP解。
对接测试操作构成了候选操作集合,我们为每一个候选操作所生成的部分解计算一个局部优先级函数来反映其导向一个好的DAP完整解的可能性;然后再用一个全局目标函数为搜索中遇到的DAP完整解进行最终的打分。基于局部优先级函数,我们引入了集束搜索来搜索求解,集束的宽度控制着搜索树自上而下扩展搜索的宽度,并在全局目标函数界限的帮助下实现深度剪枝搜索。