3D打印物体的稳定平衡优化

吴芬芬 刘利刚

(中国科学技术大学数学科学学院 合肥 230026) (lgliu@mail.ustc.edu.cn)

3D打印物体的稳定平衡优化

吴芬芬 刘利刚

(中国科学技术大学数学科学学院 合肥 230026) (lgliu@mail.ustc.edu.cn)

3D打印日渐流行，赋予大众创造物体的能力.首先通过计算机中3D建模软件构造3D数字模型，再借助3D打印加以制造.虚拟环境中无物理规则的特点使得模型千姿百态，但是通过3D打印之后发现物体无法平衡站立.首次提出3D打印物体的稳定平衡优化问题，针对这一问题，研究不倒翁的原理，提出稳定平衡优化算法，使得物体达到稳定平衡.具体做法为先将物体体素化，迭代式从水平、垂直方向进行逐体素的挖空，选取最佳的挖空方式；对于个别极端例子，再通过对底部小范围内的修改来达到稳定平衡.逐体素的启发式挖空策略避免了挖空可能出现的悬浮、自相交等问题；底部局部小范围的修改也保证了物体的形状基本不变,该方法的可行性通过多个例子的成功优化得到证明.

稳定平衡；优化；3D打印；体素化；不倒翁

不倒翁自古以来就受到广大老百姓的喜爱，尤其是儿童爱不释手的玩具.常见的不倒翁上身由空壳组成，下底由填满固体的半圆球，具有上轻下重的特点.不倒翁在受到外力时倾倒，当撤去外力时，不倒翁自行恢复到初始位置，这种性质在物理中称之为稳定平衡(stable equilibrium).稳定平衡原理在人们的生活中有着广泛的应用，带给了人们更多的乐趣与便利，如不倒翁娃娃(如图1(a)所示)，不倒翁牙刷(如图1(b)所示)、不倒翁沙袋(如图1(c)所示)、平衡鸟等.

Fig. 1 Stable equilibrium objects图1 利用稳定平衡原理的物体(来源网络)

近几年，3D打印技术快速发展，引起了人们对该科技的关注.3D打印是增材制造技术(additive manufacturing, AM)的俗称，它依据CAD设计数据(3D数字模型)，采用离散材料(液体、粉末、丝、片、板块等)逐层累加制造物体的技术[1].这种增材制造方式相对于传统的减材制造有着得天独厚的优势：减少材料的浪费、可制造非常复杂的物体、大大缩小制作周期、设计空间无限等.

3D打印被称为是第3次工业革命的导火线.它给人们带来机遇的同时也带来了挑战，针对于3D打印的问题层出不穷.这引发了科研前沿学者们的关注和研究[2-3]，将问题一一攻破.Wang等人[4]提出一种基于“蒙皮-钢架”(skin-frame)的轻质结构大大节约了3D打印材料的使用，节省了时间和成本；针对于强度问题，Stava等人[5]提出自动检测脆弱部分，使用内部挖空、局部加厚、加支撑这3种方法对物体进行修改；Vanek等人[6]提出自动生成树状支撑结构的方式，解决沉积熔融式(FDM)3D打印机不可避免的悬空部分打印失败问题；由于3D打印机尺寸的限制，无法一次性打印大于设备本身尺寸的物体，Luo等人[7]考虑可组装性、可打印性、结构稳定性、美观性提出了自动切割分别打印最后拼装组合的策略.

在计算机中，3D数字模型无需遵守物理规律，比如重力、摩擦力等，但若要3D打印，违反物理规则的物体就不能在现实世界中得到相同的效果.实际制造的需求使得如何让计算中的3D虚拟物体打印出来之后平衡也成为计算机图形学研究领域学者们关注的问题.Prévost等人[8]提出了交互调整修改模型的方式达到物体平衡的目的，他们采取的策略分为2步：1)通过模型内部的挖空调整质心位置；2)在保证模型整体形态的基础上对模型进行局部的微小变形.Musialski等人[9]采取对模型外表面进行偏移得到内表面从而挖空物体内部的方法，结果表明该方式能有更大的拓展和延伸;Yamanaka等人[10]通过改变物体的密度分布和内部结构来达到平衡的目的.

物体静止时保持稳定状态的平衡称之为静力平衡.文献[8-10]研究更多的是物体保持静力平衡.如果物体受到外界轻微的扰动，物体即刻失去平衡，效果很不理想.Bächer等人[11]改进Prévost等人[8]的方法不仅达到静力平衡，还将物体做成动态平衡的物体，即旋转陀螺.本文第1次提出物体的稳定平衡优化问题，深入研究不倒翁的原理[12-13]，针对底面与水平接触面只有1个接触点的物体，将原本不能保持平衡的3D打印物体变成稳定平衡的物体.将模型内部挖空使得物体的质心在接触点的正上方，同时将质心的高度降到尽量低，让物体达到平衡的同时还能稳定；对于极端例子，再通过修改物体底部一定范围内的形状实现稳定平衡.

1 力学分析

1.1 静力平衡

根据牛顿力学，物体在几个力的作用下处于静止或者匀速直线运动状态叫作平衡状态.当物体放在水平面上时，物体受到的重力G以及水平面对它垂直向上的支持力N等大反向共线，物体所受合力为零，故保持平衡，如图2(a)左图所示.当物体换个方向放置，物体是否也能保持平衡？如图2(a)右图所示，由于支持力的受力点为接触面，重力和支持力不共线，故此时二力不能相互抵消，物体不平衡.

Fig. 2 Analysis of the principle of stable equilibrium图2 物体稳定平衡原理分析

那物体在什么情况下能保持平衡呢？如上所述，当重力的方向与支持力的方向一致时，二力能相互抵消，即物体达到平衡.物体受的重力集中于质量中心(center of mass)，简称质心.物体与地面的接触点所形成的凸包，称之为支撑多边形(support polygon).根据力矩平衡，若物体在某个姿势下保持平衡(无人为外力下)，物体的质心在重力方向上的投影必须要落在支撑多边形内.如图3中白色多边形就是该物体的支撑多边形，物体上的白色圆点表示质心，白色多边形中的黑色圆点表示质心在重力方向上的投影，可见落在支撑多边形，故物体能保持平衡.本文针对的是与地面只有1个接触点的物体，故该物体的质心必须落在地面接触点的正上方，如图2(a)左图所示.

Fig. 3 Projection of center of mass falls within the polygon图3 物体质心投影落在支撑多边形内

1.2 稳定平衡

那稳定平衡的物体是怎么样的？当物体受到外力F时，物体偏离初始位置；当撤去外力F时，物体又自行恢复到初始位置.稳定平衡的严格定义为，处于平衡状态的物体，当受到外界的扰动而偏离平衡位置时，外力或外力矩促使物体回到原平衡位置[14].如图2(a)所示的物体发生倾斜时，重力和支持力的合力矩驱使物体恢复初始位置，而图2(b)所示则相反，力矩使得物体更加偏移初始位置.这是稳定平衡的本质.

从能量角度考虑，势能低的物体比较稳定，物体一定会向着势能低的状态变化.在图2(a)中，物体质心较低，当物体倾斜时质心被抬高，造成势能增加，所以物体具有回复初始位置的趋势，这也是不倒翁的原理；而在图2(b)中，物体质心较高，当物体倾斜时质心下降，造成势能减少，此时物体更加稳定，具有继续倾斜的趋势.

2 稳定平衡优化

给定1个3D数字模型，目标是通过对该模型进行适当的调整变形，使得模型3D打印出来之后能稳定平衡.通过挖空模型内部优化质量分布以调整质心位置，同时允许网格变形.将物体进行体素化，并将每个体素标记为1或0(1代表保留，0代表挖空)，最终得到1个二值向量表示物体内部的挖空情况.若此时物体还不能达到稳定平衡，再对物体外表面底面局部范围内进行形状的微小修改.

2.1 数学建模

输入1个三角网格M表示待平衡的模型，输出2个三角网格MO和MI定义已稳定平衡物体的内、外表面.MO表示初始网格M变形后的效果，而MI代表内部空缺部分形成的边界.给出物体最低点c*和倾斜角度θ，c*为物体放置时与水平面接触的那点，确定物体的放置方向.Cone(θ)表示以初始质心c0在截平面的投影点为顶点，顶角为2θ，平行于重力方向的圆锥；p(θ)为Cone(θ)与物体外表面MO相交的所有点,如图4所示.

根据1.2节分析，若要物体在外力作用下摆动θ角度，撤去外力之后仍能恢复在初始位置，需要满足质心高度随着倾斜角度的增加而增加的条件.如图5所示，当物体平衡放置时，当前质心c离最低点c*的高度为h0，当物体摆动θ角度后，由于最低点的变化质心此时为h1，则有h0

(1)

则有：

(2)

其中，h(θ)表示物体摆动θ角度后质心的高度，具体的表达式为h(θ)=(p(θ)-c)·n(p(θ)).

Fig. 4 Definition of stable angle and other notations concerned图4 稳定平衡角度定义及相关符号说明

Fig. 5 Analysis of the principle of stable equilibrium图5 稳定平衡原理分析

考虑物体的稳定性和保型性，建立数学模型：

(3)

其中，EM(MO)是保型项，即衡量外表面MO和输入网格M的偏差；ECOM(MI,MO)测量质心离理想位置的差距：

ECOM(MI,MO)=λ1‖(c(MI,MO)-c*)⊥g‖2+

(4)

其中，向量g是重力方向(‖g‖=1)，αg表示向量α在重力方向上的投影.权重λ1≫λ2，μ用于平衡2个目标函数.

其中,F是MO和MI所有三角面的集合，f=(i,j,k)是1个三角面，v是顶点的坐标，*表示按分量逐个乘积.

g(vi,vj,vk)=vi*vj+vi*vk+

vj*vk+vi*vi+vj*vj+vk*vk.

2.2 挖空算法

为了更加直观地感受挖空物体内部对物体质心带来的影响，将物体内部用体素来表示，即体素化物体[15].体素的表达避免了挖空内部可能产生的悬空、自交等情况.赋予每个体素1个二值变量αi(0表示挖空，1表示保留)，所有体素的值构成1个向量α.挖空之后，物体内部轮廓由体素的边界组成，如图6所示:

Fig. 6 The sectional view after carving图6 挖空后物体的截面图

首先设置初值α0为所有的体素都保留，即α0=(1,1,…,1).为了避免将物体挖空到很薄，将预留tmin的壁厚，即离物体外表面MO距离tmin是不被挖空的.tmin由用户根据物体的材料属性输入.

此处采用快速启发式的挖空算法来近似最优的体素挖空.首先，从物体的平衡性考虑，给定物体的当前质心c0=c(α0)，假设有1个截平面经过最低点c*并且垂直于(c0-c*)⊥g，如图7所示.若想将质心c0调整至c*的正上方，需挖空截平面包含c0的一侧，反之质心会更加偏离c*.将体素依照距离截平面的远近降序排列：

(5)

其中，ri为第i个体素的中心.距离为负数的体素直接忽略.为方便说明，将能量函数ECOM(MI,MO)分成2项：

(6)

(7)

Fig. 7 A heuristic carving strategy图7 启发式挖空策略

挖空的具体算法如下：

算法1. 挖空算法 Carving Algorithm.

输入：物体的三角网格表示M、放置时的最低点c*、最小壁厚tmin、阈值τ，ζ；

输出：挖空后内部形成的内表面网格MI.

Step1. 在最小壁厚tmin的限制下，将物体体素化；

Step2. 计算每个体素的di，并将体素降序排列；

Step3. 逐体素挖空(用向量α表示)，直到ECOM不再减少为止；

DO

{

跳出本次循环；

END IF

END WHILE

跳出本次循环；

END IF

END WHILE

} WHILEECOM不再减少为止

Step4. 根据α计算出物体内表面网格MI.

该启发式算法避免了挖空之后悬空部分的存在.另外，每次挖空之后要更新能量值，逐体素挖空的方法使质心的计算更加有效，只要增加新三角面对应的值减去覆盖的三角面对应的值即可.

2.3 形状修改

若挖空还不能让物体达到θ角度范围内的稳定平衡，由于稳定平衡与底部形状相关性最大，而且底部的形变对物体整体形状视觉上的影响最小，允许物体底部微小范围内进行修改.为了将问题简单化，规定物体外表面形状的改变由点的移动来描述，并且顶点只在它的法线方向移动.此时有:

(8)

其中,ξ(p)为顶点的移动距离.

2.4 稳定平衡优化算法

结合式(3)(4)(8)可将能量函数具体化为

(9)

目标函数式(9)相当复杂：它有1个描述体素挖空状态的离散变量α以及1个表达物体底面形状修改的距离ξ(p).本文采取迭代优化的方法进行稳定平衡优化，如图8所示:

Fig. 8 Flow chart of optimization algorithm图8 优化算法流程图

稳定平衡优化算法具体如下：

算法2. 优化算法(optimization algorithm).

输入：物体的三角网格表示M、放置时的最低点c*、最小壁厚tmin、倾斜角度θ、阈值τ，ζ；

输出：挖空后内部形成的内表面网格MI、形变之后的外表面MO.

Step1. 固定外表面网格MO,即固定ξ(p)，利用算法1寻找物体内部最优的质量分布即α；

Step2. 在内表面网格MI不变的情况下,即固定α，寻找最优的外表面网格变形ξ(p)；

Step3. 计算式(9)中目标函数的值;

Step4. 重复上述步骤，更新α和ξ(p)，直到目标函数式(9)不再减少.

3 实验结果

本文方法能让物体在原本不能静止放置的方位平衡放置，并且在小范围的摆动内仍不倒.本文测试了多个例子验证了该方法的可行性.

我们通过1个二维拉伸物体的例子来具体说明

本文的方法.如图9所示，1个蘑菇形状的截面图(如图9(a)所示)，图9(e)所示“+”表示物体初始的质心,“○”表示迭代过程中的质心位置变化.由第1节可知，物体的质心不在物体与水平面唯一接触点的正上方，故该物体不平衡.首先对物体的外表面进行偏移并且体素化，设置tmin=0.04，以免挖空之后的壁厚过薄.第1步，对物体进行挖空，设置挖空分辨率为25，ζ=0.01，τ=0.03，挖空情况如图9(a)～(d)所示,质心的变化如图9(e)所示.此时物体已达到平衡.

Fig. 9 The process of iteratively carving and change of center of mass图9 物体迭代挖空优化过程以及质心变化

第2步我们通过修改底部形状来实现θ=10°范围内的稳定平衡.经过优化计算，修改后的形状如图10所示.对于算法2，在实际操作中，只要1次迭代就能达到很好的效果.

Fig. 10 The result of modifying图10 底面修改结果

通过FDM 3D打印机将物体进行打印制造.由于FDM的特点，物体内部挖空后形成的悬空部分会出现不好的效果.庆幸的是，我们不能看到内部的构造，打印产生的瑕疵可被隐藏.对打印材料的部分悬挂可能会对物体的质量分布产生影响，因为影响太小忽略不计.

图11(a)显示的是该测试例子打印实物在受到外力之后自我摆动的效果(视频截图)，图11(b)是倒立不倒翁物体在稳定平衡过程中的视频截图，可发现本来很难平衡的2个物体经过本文方法之后变得像不倒翁一样分别在倾斜角度θ=10°和θ=15°内仍能回到初始位置.

Fig. 11 The object reached stable equilibrium (video screenshot)图11 已稳定平衡的物体(视频截图)

由于针对与水平面只有1个接触点的物体，质心在水平方向上的容差很低.这导致了一些极端的物体是无法通过挖空来达到平衡，有些不能达到稳定平衡.如图12所示的物体均能倒立，至于稳定平衡只能做到很小角度内的.实际操作中，物体被触碰的角度往往会超过这个角度范围.同一个物体通过不同挖空可停留在不同的姿势，如图13所示.

Fig. 12 Balanced objects (static photo)图12 平衡物体(静态照片)

Fig. 13 Same objects with different gesture (static photo)图13 同一物体不同放置姿势(静态照片)

4 结束语

本文只针对采用同种材料进行物体质量分布的调整，多材料的填充可以让更多的物体达到平衡状态.由于目前3D打印技术的局限，我们将这项工作列为未来规划.对于3D打印制造物体时内部出现的悬空问题，可以通过将物体一分为二分别打印再粘合的方法来解决.不过这又会带来新的问题：物体表面会显得不美观，因此本文没有采取这种方法.

对于多组件物体的稳定平衡优化，分为2种情况考虑：

1) 相对简单的静态多组件物体，即组件之间不考虑相对运动.此种情况下，可将多组件物体等同于1个组件物体来考虑，但由于成为组件的边缘部分不可被挖空，在挖空中需要考虑.具体的做法如下：对多组件进行求并运算，得到2.1节中的最初输入M，同时记录原多个组件的外表面；结合给定的最小壁厚tmin，将表示物体挖空情况的向量α0做出一些标记，将组件的边缘标记为不可挖空；在优化过程中不挖空组件的边缘部分，将挖空结果和原多组件求交运算即可得到每个组件的挖空结果，从而达到整个静态多组件的稳定平衡状态.

2) 动态多组件物体，由于物体在挖空的过程中，由于重心不断变化而引起物体的形态变化，从而再次引起重心变化.该过程涉及力学、时间变化，本文很难用类似的算法给出很好的方案去优化此类物体.但该问题必定是个有趣且值得考虑的问题，我们将其列为又一项未来工作.

本文实现了如何将待打印的模型变成可稳定平衡的物体.本文的方法结合了平衡的能量函数和保持物体大部分外表面不变的保型措施，也避免了直接在物体底部加上1个底座这样直接的做法.介绍了一个启发式的体素挖空算法，让物体达到平衡的同时最稳定；然后通过不倒翁的原理对底面进行变形使得物体达到最佳的稳定状态.通过多个测试例子，验证了本文方法的有效性.

[1]Wu Huaiyu. 3D Printing: 3D Creation via Intelligent Digitization[M]. Beijing: Publishing House of Electronics Industry, 2014 (in Chinese)(吴怀宇. 3D打印：三维智能数字化创造[M]. 北京: 电子工业出版社, 2014)

[2]Liu Ligang, Xu Wenpeng, Wang Weiming, et al. Survey on geometric computing in 3D printing [J]. Chinese Journal of Computers, 2015, 38(6): 1243-1267 (in Chinese)(刘利刚, 徐文鹏, 王伟明, 等. 3D打印中的几何计算研究进展 [J]. 计算机学报, 2015, 38(6): 1243-1267)

[3]Hu Ruizhen, Huang Hui. Recent progress in 3D printing inspired fabrication optimization [J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(6): 961-967 (in Chinese)(胡瑞珍, 黄惠. 3D打印启发下的模型实例化优化研究综述 [J]. 计算机辅助设计与图形学学报, 2015, 27(6): 961-967)

[4]Wang Weiming, Wang Tuanfen Y, Yang Zhouwang, et al. Cost-effective printing of 3D objects with skin-frame structures [J]. ACM Trans on Graphics, 2013, 32(6): Article No 177

[5]Stava O, Vanek J, Benes B, et al. Stress relief: Improving structural strength of 3D printable objects [J]. ACM Trans on Graphics, 2012, 31(4): Article No 48

[6]Vanek J, Galicia J A G, Benes B. Clever support: Efficient support structure generation for digital fabrication [J]. Computer Graphics Forum, 2014, 33(5): 117-125

[7]Luo Linjie, Baran I, Rusinkiewicz S, et al. Chopper: Partitioning models into 3D-printable parts [J]. ACM Trans on Graphics, 2012, 31(6): Article No 129

[8]Prévost R, Whiting E, Lefebvre S, et al. Make it stand: Balancing shapes for 3D fabrication[J]. ACM Trans on Graphics, 2013, 32(4): Article No 81

[9]Przemyslaw M, Thomas A, Michael B, et al. Reduced-order shape optimization using offset surfaces[J]. ACM Trans on Graphics, 2015, 34(4): Article No 81

[10]Yamanaka D, Suzuki H, Ohtake Y. Density aware shape modeling to control mass properties of 3D printed objects[C]Proc of SIGGRAPH Asia 2014 Technical Briefs. New York: ACM, 2014: 7-10

[11]Bächer M, Whiting E, Bickel B, et al. Spin-it: Optimizing moment of inertia for spinnable objects [J]. ACM Trans on Graphics, 2014, 33(4): Article No 96

[12]Liu Yanzhu. Tumbler, turn-over tortoise and Gomboc [J]. Mechanics in Engineering, 2010, 32(2): 147-149 (in Chinese)(刘延柱. 不倒翁、乌龟翻身和冈布茨[J]. 力学和实践, 2010, 32(2): 147-149)

[13]Cao Chunmei, Zhang Xiaohong. Mechanics analysis of tumbler [J]. Physics and Engineering, 2002, 12(1): 10-11 (in Chinese)(曹春梅, 张晓宏. 不倒翁的力学分析[J]. 物理与工程, 2002, 12(1): 10-11)

[14]Fan Qinshan, Guo Guanglin. Engineering Mechanics 2[M]. Beijing: Higher Education Press, 2011 (in Chinese)(范钦珊, 郭光林. 工程力学2[M]. 北京: 高等教育出版社, 2011)

[15]Wu Xiaojun, Liu Weijun, Wang Tianran, et al. Modified polygonal mesh voxelization based on Euclidean distance measurement [J]. Journal of Computer-Aided Design & Computer Graphics, 2004,16(4): 592-597 (in Chinese)(吴晓军, 刘伟军, 王天然, 等. 改进的基于欧氏距离测度网格模型体素化算法 [J]. 计算机辅助设计与图形学学报, 2004,16(4): 592-597)

Wu Fenfen, born in 1992. Master. Her main research interests include computer graphics, geometric processing and modelling.

Liu Ligang, born in 1975. Professor and PhD supervisor in the University of Science and Technology of China. His main research interests include geometric processing, computer graphics, and image processing.

Stable Equilibrium Optimization for 3D Printed Objects

Wu Fenfen and Liu Ligang

(SchoolofMathematicalSciences,UniversityofScienceandTechnologyofChina,Hefei230026)

3D printing is increasingly popular, giving the public the ability to create objects. First of all, a 3D digital model is constructed by 3D modeling software, and then manufactured via 3D printer. Virtual environment with no physical rules makes the model stand with diverse gesture, but failed in the real world. We put forward the stable equilibrium optimization problem for 3D printed object for the first time. To solve this problem, we propose a stable equilibrium optimization algorithm based on the principle of the tumbler, which can make the object achieve stable equilibrium. Specifically, we voxelize the object iteratively from horizontal and vertical direction voxel by voxel until obtaining the best carving result, measured by an equation; for some exceptions, we continue to modify the bottom within an acceptable small range to achieve stable equilibrium. This novel heuristic carving strategy avoids possible problems such as suspension, self-intersection, etc. Modification of the bottom part within the small range also ensures that the shape of the object is basically unchanged. The feasibility of the proposed method is demonstrated by several examples of successful optimization. The limitation is that multiple material is not considered in this paper for the complexity of operation, which is to be explored in the future.

stable equilibrium; optimization; 3D printing; voxelization; tumbler

2015-10-13；

2016-04-19

国家自然科学基金项目(61672482,11626253);中国科学院“百人计划”项目 This work was supported by the National Natural Science Foundation of China (61672482, 11626253) and the Hundred Talents Program of Chinese Academy of Sciences

刘利刚(lgliu@ustc.edu.cn)

TP391.41