基于Nelder-Mead算法的3D打印模型最優化放置

秦 爽，黃先鋒，張 帆，陳 偉，向東清

(1.武漢大學 測繪遙感信息工程國家重點實驗室，湖北 武漢 430079; 2.珠海賽納打印科技股份有限公司，廣東 珠海 519060)

0 引 言

3D打印是以三維模型文件為基礎，運用可粘合和可固化的離散材料(粉末、液體、絲等)為打印介質，通過分層打印、逐層堆疊累積的方式來制造物體的技術[1]。3D打印能快速而準確地將任意復雜的模型數據制造出實物，同時也帶來了如打印成本優化等新的研究問題[2]。一般用于3D打印的材料價格是遠遠高于傳統制造方式的，因而節省打印耗材成為降低打印成本的重要方法之一[3]。針對這一問題，許多學者通過優化3D打印模型的內部結構來減少打印模型耗材。例如，Wang等提出了一種基于“蒙皮-剛架”(skin-frame)的輕質結構來減少打印耗材[4]；Kindinger等提出基于泡沫、輕木等輕質結構來減少3D模型重量[5]；Lu等利用蜂窩結構思想提出一種打印模型內部掏空優化算法[6]；Chen利用蜂窩六邊形的網孔結構來填充內部挖空[7]。

目前，3D打印軟件在節材優化方面上仍十分有限，如果不能合理地設計出打印模型內部結構，在對物體的鏤空厚度和密度這些參數進行設定時仍然需要根據用戶的經驗，不合理的設計會導致打印出的模型不能滿足于實際生產應用，還浪費了昂貴的打印材料[8]。3D打印材料消耗除了模型耗材外，還包括打印支撐結構耗材。為了讓打印材料在有懸空的地方沉積，通常需要在模型有懸空部位的下方添加支撐材料[9-11]。因此，文中是在不改變模型原有內部結構的前提下，通過對打印模型最優化放置的研究來減少打印支撐耗材。

此外，與傳統的制造技術相比，3D打印技術已大大縮短了模型輸出時間，但是打印一個物體仍需花費不少的時間[2,12-13]。在打印過程中，還需考慮打印時間問題，通過縮短3D打印時間從而實現對產品對象的快速打印[2,14-15]。

文中針對打印耗材和打印時間兩個方面進行優化，利用打印模型的支撐結構耗材體積和打印時間這兩個參數以及各自所占的權重系數構造出目標函數，采用經典的Nelder-Mead算法，在不改變模型內部結構的前提下，計算出打印模型的最優擺放角度，以實現對打印模型的最優化放置，達到降低成本的目的。

1 模型支撐耗材體積計算

如圖1所示，支撐耗材體積(Vs)計算思路為，將模型的上頂面投影到打印平面的體積(Vp)減去模型實體體積(Vm)，即Vs=Vp-Vm，因此，可拆分為模型頂面投影體積計算和模型實體體積計算兩個部分。

圖1 模型耗材顯示圖

1.1 模型實體體積計算

文中分析的三維模型數據為三角網模型，由頂點和三角形構成，三角形的法向量滿足右手準則，即所有三角形面片的法向一致，均指向體外。

設三維模型中的任意一個三角形頂點為A(x1,y1,z1),B(x2,y2,z2)和C(x3,y3,z3)，如圖2所示，以坐標原點O(0,0,0)為頂點，以ΔABC為底的三棱錐的體積為：

如果ΔABC為順時針排序，根據右手準則，右手握拳方向為ΔABC的排序方向，大拇指指向為三角形法向的方向，那么原點O在ΔABC法向的正方向上，則VOABC為正數，反之VOABC為負數[10]。

圖2 模型體積計算

對任一給定三維模型數據，它的模型表面是由n個三角形面片組成，如果以坐標原點O為頂點，依次以這n個三角形為底可以構成n個三棱錐，那么該三維模型的體積計算公式為：

其中，Vi為第i個三角形與坐標原點構成的帶符號的體積，其正負符號根據坐標原點O和該三角形法向量的正負方向確定。

1.2 模型頂面投影體積計算

體積計算需要逐個單元進行分析，三維顯示引擎OpenGL提供了快速的幾何模型投影計算能力。利用OpenGL的成像機理和深度緩存機制來計算打印物體在正射投影下的體積。

1.2.1 模型變換矩陣的計算

假設模型變換矩陣為Mv，模型繞X軸、Y軸和Z軸旋轉的角度分別為DX、DY和DZ。為了使模型圍繞自身坐標軸進行旋轉，首先對模型進行平移變換，將模型移動到坐標原點，然后進行旋轉變換，最后又利用平移變換將模型移動到模型的中心點。由于縮放矩陣會改變模型的大小，因此在計算過程中不考慮縮放矩陣的影響，具體步驟為：

(1)將旋轉角度轉換為弧度：

將模型移到坐標原點的平移矩陣為T1，遍歷場景中模型所有的頂點坐標，得到在X軸、Y軸和Z軸方向上的最大值和最小值，假設分別為Maxx、Minx、Maxy、Miny、Maxz和Minz，并求出模型的中心點坐標(Xc,Yc，Zc)。滿足以下關系式：

Xc=(Maxx+Minx)/2

Yc=(Maxy+Miny)/2

Zc=(Maxz+Minz)/2

(2)模型繞X軸、Y軸和Z軸的旋轉矩陣分別為Rx、Ry和Rz：

(3)將模型移到物體的中心的平移矩陣為T2：

(4)模型變換矩陣Mv為：

Mv=T2×Rz×Ry×Rx×T1

通過模型變換矩陣和實物模型做相乘運算可以確定三維模型最終的大小、形狀和位置，從而可以計算在當前旋轉角度下的模型頂面投影體積。

1.2.2 模型頂面投影體積計算

根據計算出來的模型變換矩陣，可以得到模型在經過變換之后的坐標，從而可以計算出模型在X軸、Y軸和Z軸方向上的最大值和最小值，假設分別為Xmax、Xmin、Ymax、Ymin、Zmax和Zmin。

在OpenGL中提供了正射投影和透視投影這兩種不同的投影類型。正射投影的投影線互相平行，投影的結果與原來的物體大小相等，符合文中的需求，因此將投影方式設置為正射投影。根據正射投影可以得到打印模型所有的頂面區域，讀取系統計算的深度緩存信息得到視口范圍內的深度值。

將每一個像素的深度值與初始深度值進行比較，依據深度緩存原理，如果該像素深度值小于初始深度值，則說明該像素點是物體所在的像素點。然后利用gluUnProject函數將所有物體所在的像素點實現屏幕坐標向世界坐標的轉換，這樣每一個物體所在的像素點都對應一個世界坐標。

通過相鄰像素點的坐標值可以求出單個像素的邊長，計算其面積S，將打印模型頂面區域所在的像素點的Z坐標值減去Zmin，累加值記為Zsum，則物體在Z軸正射投影下的體積Vp可表示為：

Vp=S×Zsum

2 模型打印時間計算

文中提出了一種打印時間的計算方法。假設打印模型所需的時間為ht，模型的總層數為R，每一層的厚度為dmm，每層打印所花的時間為h，存在這樣的關系：

ht=R×h

R=(Zmax-Zmin)/d

設每一層的切片長(設定為沿X軸方向)為Lmm，寬(設定為沿Y軸方向)為Wmm，根據1.2.1節有：

L=Xmax-Xmin

W=Ymax-Ymin

噴頭長度為kmm，打印字車在X軸的運行速度為Vxm/s，打印字車在Y軸運行速度為Vym/s，打印機頭走過同一個圖像區域的次數為m，打印字車從打印結束點回到打印起始點所用耗時為S(S一般為常量)，則完成每層打印所需的步徑數E(向上取整)為：

E=W/(k/m)+3

每層打印耗時為：

可以看出上式中的L、W和R三個變量與模型的擺放有關。

3 基于Nelder-Mead的最優函數求解

通過計算物體在任意放置角度下的打印支撐耗材體積fv和打印時間ht，構造一個目標函數F，F=a×fv+b×ht，其中a和b為各自的權重系數，fv和ht的大小與模型的擺放有關，利用單純形算法求出F的最小值，得到模型繞X軸、Y軸和Z軸旋轉的最優放置角度。

3.1 Nelder-Mead算法

Nelder-Mead算法是一種求解多維函數極值的算法，由于該算法運用了單純形的概念，因此又稱單純形算法。一個n維單純形是指包含n+1個節點的凸多面體，例如，一維單純形是直線上的線段，二維單純形是平面中的三角形，三維單純形是三維空間中的四面體。

3.2 算法思路和流程

文中研究的是3D打印模型的最優化放置功能，最終需要解算出待打印繞X軸、Y軸和Z軸所旋轉的最佳角度，構造的目標函數有3個角度變量，為三維單純形，在變換過程中只改變頂點的位置和尺寸，幾何形狀和維度保持不變，始終保持一個4個點的點集，即為三維空間中的四面體。

具體的算法如下：

輸入：模型繞X軸、Y軸和Z軸旋轉的角度DX、DY和DZ以及打印支撐耗材體積和打印時間所占目標函數的權重系數a和b

輸出：在該權重系數下使得目標函數值最小的DX、DY和DZ

Step1：在進行每次迭代之前，分別計算4個點對應的函數值，并對各自的函數值進行排序，使其滿足:

f(x1)≤f(x2)≤f(x3)

Step2：找出目標函數最大值fh，次大值fs以及最小值fl，各自對應的點分別為xh、xs和xl，其中h=4，s=3，l=1。

Step3：計算重心點c,c為包含最好的3個點的多面體的中心，即除點xh外其他點的平均值:

Step4：對單純形進行變換操作，通過使用反射、擴張或收縮產生的新的點來嘗試替代最差的點xh，直到滿足收斂條件，得到新的單純形，從而得到最好的點。

圖3為具體的計算過程。

4 實驗結果

利用VS2013開發工具和OpenGL函數庫，通過VC++實現了所提出的優化算法，其中用戶界面基于Qt進行開發。實驗中每層切片的厚度d為0.028 mm,噴頭長度k為54 mm,采用4pass打印，即m為4，打印字車在X軸的運行速度Vx為0.6，Vy為0.1，s為1.5 s。圖4(a)為模型在初始狀態下的放置圖，在權重系數框中輸入0到1之間的實數，構造出關于打印模型支撐結構耗材體積和打印時間的帶有權重的目標函數。圖4(b)為打印時間權重為0、耗材權重為1得到的打印支撐耗材最優放置圖；圖4(c)為打印時間權重為1、耗材權重為0得到的打印時間最優的放置圖。

圖4 各種狀態下的模型放置圖

如表1和表2所示，在不改變模型內部結構的前提下，使用文中算法可以明顯減少打印支撐耗材體積，提高打印速度，從而達到降低成本的目的。

表1 心臟在各種擺放狀態下的打印成本

表2 血管在各種擺放狀態下的打印成本

5 結束語

針對目前3D打印材料費用昂貴、打印成本高的問題，提出了一種基于Nelder-Mead的優化算法。該算法計算出了模型在任意擺放角度下的支撐結構耗材體積和打印時間，通過不斷地迭代實現了對模型的最優放置，從而減少了打印支撐結構耗材、縮短了打印時間，達到了降低3D打印成本的目的。

該優化算法主要應用于軟材質實心打印材料，用于醫學手術模擬訓練和手動切割，因此，沒有考慮模型的內部結構優化。未來需要考慮內部支撐結構的優化，從而適應更多的打印需求。