雪雕模型的離散處理及基本單元位置優(yōu)化

李建永，董緒斌，李來(lái)春，王立才，王開(kāi)寶，徐威震，王昊天，郭慶東

(1.北華大學(xué)機(jī)械工程學(xué)院，吉林 吉林 132021；2.北華大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，吉林 吉林 132021)

當(dāng)前，雪雕產(chǎn)業(yè)快速發(fā)展，雪雕的需求量與日俱增，傳統(tǒng)的制作方法已不能滿足冰雪旅游產(chǎn)業(yè)的需求，雪雕制作的機(jī)械化和智能化成為主要的發(fā)展趨勢(shì)，而利用操作難度低、效率高的智能化3D雪雕打印設(shè)備制作雪雕[1]取代傳統(tǒng)的制作工藝，可以提高制作效率，能夠適應(yīng)雪雕行業(yè)快速發(fā)展的需要.由于加工的高效性和靈活性，3D打印越來(lái)越多地被應(yīng)用到不同領(lǐng)域[2-7].智能化3D雪雕打印設(shè)備基于增材制造技術(shù)理念，以雪磚為基本單元，以傳統(tǒng)工程車輛為載體，在其上安裝一個(gè)關(guān)節(jié)機(jī)器人作為執(zhí)行單元.施工時(shí)，將提前預(yù)制好的雪磚依照雪雕的三維模型，通過(guò)執(zhí)行單元逐一擺放至指定坐標(biāo)位置，逐層疊放，實(shí)現(xiàn)大型雪雕的快速制作.雪磚逐層疊放形成雪雕是一個(gè)填充問(wèn)題[8]，屬于在規(guī)定約束下的空間填充，可分為規(guī)則填充和不規(guī)則填充兩類.對(duì)于前者，HALES[9]在1998年完成了Kepler猜想的證明；對(duì)于不規(guī)則填充，由于隨機(jī)填充與物質(zhì)結(jié)構(gòu)關(guān)系密切而被廣泛研究，并取得了很多成果[10].近年來(lái)，關(guān)于填充問(wèn)題的研究形成了3個(gè)主要方向，分別是自由裝填、覆蓋填充和填充，它們之間既有區(qū)別又有聯(lián)系，但追求的目標(biāo)一致，即研究獲得最大填充率的填充方法[11].顯而易見(jiàn)，對(duì)顆粒堆積填充問(wèn)題的研究具有理論意義和應(yīng)用價(jià)值[12].

在智能化3D雪雕打印設(shè)備逐層構(gòu)建雪雕時(shí)，打印系統(tǒng)的操作單元依據(jù)該層所在高度雪雕模型截面的二維輪廓擺放雪磚，因此，確定輪廓邊緣雪磚的坐標(biāo)信息尤為重要，這些坐標(biāo)信息通過(guò)對(duì)雪雕模型進(jìn)行數(shù)字化處理獲得；同時(shí)，雪磚擺放的具體位置決定雪雕與原模型的近似程度.本文探討雪雕三維模型的等高分層處理方法，將雪雕的三維模型轉(zhuǎn)化為二維輪廓，為雪雕3D打印的實(shí)施提供理論依據(jù)；討論雪磚在某一切面的位置優(yōu)化策略，以達(dá)到最大填充率，進(jìn)而獲得最優(yōu)復(fù)現(xiàn)雪雕三維模型；通過(guò)模擬試驗(yàn)，驗(yàn)證雪磚擺放策略的可行性及有效性.

1 雪雕模型的離散處理

通過(guò)MATLAB實(shí)現(xiàn)對(duì)STL格式雪雕模型文件的數(shù)字化離散處理，主要包括模型切分和坐標(biāo)點(diǎn)提取.等高分層算法實(shí)現(xiàn)對(duì)模型的切分，獲取二維輪廓信息；獲得輪廓內(nèi)雪磚中心點(diǎn)的坐標(biāo)信息，雪磚按此坐標(biāo)擺放，完成對(duì)二維輪廓的填充.

1.1 等高分層原理

由于實(shí)體雪雕是通過(guò)逐層累積完成的，因此，求出雪雕模型在每一層的邊界輪廓曲線至關(guān)重要.

模型的分層處理是指通過(guò)一系列相互平行的水平面(即切分平面)與模型相交，求得相交后的輪廓曲線.雪雕STL模型通過(guò)三角面片形式組成物體的三維形狀，對(duì)模型進(jìn)行切分就是求出切分平面和與其相交的三角面片的交線，交線相互連接即得到一定高度下模型的輪廓線.

智能化3D雪雕打印是以一定尺寸的雪磚為基本單元來(lái)填充輪廓，因此，其切分平面間距為等距，屬于等高分層[13-15].等高分層的算法思想是在固定的距離進(jìn)行一次模型切片處理[16]，通過(guò)求解其交線獲得模型的輪廓線.模型切分流程見(jiàn)圖1.

圖1模型切分流程Fig.1Model cutting process

1.2 雪雕模型截面輪廓獲取

通過(guò)計(jì)算某一分層高度下切平面和與其相交的三角形面片的交線獲得該分層高度下模型的輪廓線.圖2為切平面與某三角面片交線的示意圖.

圖2三角形面片與切平面相交Fig.2The triangular face piece intersects with the cutting plane

已知點(diǎn)A、B、C的空間坐標(biāo)分別為(x1，y1，z1)、(x2，y2，z2)、(x3，y3，z3)，設(shè)M點(diǎn)坐標(biāo)為(xm，ym，z0)，N點(diǎn)坐標(biāo)為(xn，yn，z0).通過(guò)空間直線參數(shù)方程可得M點(diǎn)坐標(biāo)為

(1)

N點(diǎn)坐標(biāo)為

(2)

通過(guò)式(1)、(2)可得到特定高度下切平面和所有與其相交三角面片的交線，即可獲得該切分高度下模型的輪廓曲線.

1.3 等高分層切片試驗(yàn)

根據(jù)等高分層算法，使用MATLAB平臺(tái)編程求解，對(duì)三維模型進(jìn)行切片試驗(yàn).將模型導(dǎo)入MATLAB并讀取數(shù)據(jù)信息，顯示所獲取的三角面片.將STL模型文件按照z軸方向進(jìn)行切分，切分高度可以設(shè)置為模型高度范圍內(nèi)的任意值.輪廓化算法實(shí)現(xiàn)：

第1步，讀取每個(gè)STL文件的三角面片信息，從而得到每個(gè)三角形面片的頂點(diǎn)坐標(biāo)與法向量，以及模型所含的三角形數(shù)量N，其中，n是N個(gè)三角形中的第n個(gè).

第2步，通過(guò)讀取模型STL文件得到的每個(gè)三角形面片頂點(diǎn)坐標(biāo)，求出模型z方向的最小值Zmin與最大值Zmax.

第3步，由人為給定的切片分層高度ΔZ和Zmin、Zmax得到切片高度向量Z=[Zmin+ΔZ，…，Zmin+kΔZ，…，Zmax-ΔZ]T.其中，Zmax-ΔZ=Zmin+KΔZ，K為該模型切片層數(shù)，k為K層切片中的第k個(gè).

第4步，逐層求得切平面與各三角形面片的交點(diǎn)，計(jì)算到第k層時(shí)Z0=Z(k)，遍歷每一個(gè)三角面片，如果該三角形z方向的最小值Zmin與最大值Zmax滿足Zmin

圖3球體模型切分結(jié)果Fig.3The results of the cut of sphere model

圖4小黃鴨模型切分結(jié)果Fig.4The result of the cut of little yellow duck model

通過(guò)球體和小鴨子的三維模型切分試驗(yàn)分析可知，該算法實(shí)現(xiàn)了對(duì)模型的切分，且可以根據(jù)需要設(shè)定分層高度，獲得雪雕模型各個(gè)高度切面所需的二維輪廓.

2 雪磚填充優(yōu)化策略

3D雪雕打印系統(tǒng)將雪磚逐層疊放制成雪雕，雪磚堆積后形成的整體輪廓即為雪雕外形，其過(guò)程借鑒了有限元思想，將模型離散后再裝配成整體.雪雕的外形與模型相似度越高，雪雕就越逼真.顯然，相似度與雪磚的尺寸有關(guān)，尺寸越小，相似度越高；圓柱體的雪磚要比立方體的雪磚能更好地逼近復(fù)雜輪廓，但考慮到工程實(shí)際，立方體雪磚是最好的選擇，容易制備也易擺放，且穩(wěn)定性好.本節(jié)主要探討立方體雪磚的擺放策略，以使雪雕與模型的相似程度更高，獲得最優(yōu)擺放策略.

2.1 相似度的基本概念

每一層雪磚擺放依據(jù)的是雪雕模型在該高度下的二維輪廓，并用雪磚填充該區(qū)域.前文提及的覆蓋方法是一種可覆蓋邊界的填充，填充對(duì)象之間可以相互重疊且與區(qū)域界也可以重疊，最后將目標(biāo)區(qū)域全部覆蓋，見(jiàn)圖5 a；用立方體雪磚填充雪雕二維輪廓所圍成的區(qū)域，其所形成的邊界就構(gòu)成雪雕輪廓，由圖5 b覆蓋后的輪廓可以看出，填充效果與雪雕原輪廓相比并不理想，原因是該覆蓋法需完全覆蓋二維輪廓，導(dǎo)致覆蓋后的輪廓與雪雕原輪廓誤差較大.為了提高雪雕與模型的相似度，應(yīng)減少誤差，使二者輪廓盡可能接近.

圖5覆蓋填充Fig.5Covering fill圖6改進(jìn)覆蓋Fig.6Improved covering fill

圖6為另外一種雪磚填充策略，與覆蓋法相比，最大區(qū)別是它不追求覆蓋邊界，而是使在輪廓邊緣處的雪磚凸出和凹進(jìn)輪廓的面積很小，減少了誤差，提高了相似程度.

依據(jù)以上所述，相似度為在雪雕的某一切面中所有的凸出和凹進(jìn)輪廓的誤差面積A，即

(3)

2.2 雪磚擺放位置優(yōu)化

綜上所述，在構(gòu)建雪雕過(guò)程中，如果要求雪雕與原模型逼近，就要使相似度高(即誤差面積A小).顯然，受到一些條件約束，誤差面積A不可能無(wú)限減小，受雪磚單元的制備成本及實(shí)際使用要求限制.比如，尺寸越大，雪雕制備的效率越高，但相似度不容易保證；尺寸越小，相似度越好，但效率低，且不易被執(zhí)行單元夾持.因此，雪磚的具體尺寸應(yīng)根據(jù)雪雕大小、工作效率等多實(shí)際工況確定.

在雪磚尺寸確定后，擺放位置對(duì)相似度起決定作用.這時(shí)，使相似度達(dá)到最大(誤差面積A最小)的問(wèn)題可被歸結(jié)為規(guī)劃問(wèn)題，問(wèn)題的目標(biāo)函數(shù)為誤差面積A，約束條件是雪磚之間的位置關(guān)系.數(shù)學(xué)規(guī)劃模型可表示為優(yōu)化問(wèn)題(P)，即

(4)

式中：xi、xj(i，j=1，2，…，n)為雪磚中心點(diǎn)在x-y平面內(nèi)的坐標(biāo)；a為立方體雪磚的邊長(zhǎng)；n為與二維輪廓相交的雪磚數(shù)量.

圖7誤差面積Fig.7Error area

由圖6可知，目標(biāo)函數(shù)誤差面積A的變量是雪磚中心點(diǎn)坐標(biāo)(xi，yi，zi)，當(dāng)層高固定時(shí)(即z固定)，變量就僅為x和y了，但x坐標(biāo)受式(4)中約束條件的限制，因此，誤差面積A僅是y坐標(biāo)的函數(shù)(圖7)：

(5)

綜上，優(yōu)化問(wèn)題P可歸結(jié)為在x坐標(biāo)及立方體雪磚邊長(zhǎng)的約束下獲得使誤差面積A最小的雪磚中心點(diǎn)yi(i=1，2，…，n)的坐標(biāo).

2.3 雪磚擺放位置優(yōu)化及模擬試驗(yàn)驗(yàn)證

根據(jù)優(yōu)化問(wèn)題P，使用MATLAB平臺(tái)進(jìn)行編程求解各層雪磚中心點(diǎn)最優(yōu)位置.通過(guò)之前的輪廓提取算法可以得到每層輪廓的點(diǎn)坐標(biāo)，從而得到該層x方向坐標(biāo)最小值xmin和最大值xmax，根據(jù)式(4)中的約束條件可以得到該層x方向最優(yōu)點(diǎn)坐標(biāo)向量

以及該層輪廓最優(yōu)點(diǎn)個(gè)數(shù)M，其中，xmax-L/2=xmin+(2m-1)L/2，m為該層輪廓中第m個(gè)最優(yōu)點(diǎn).所以，問(wèn)題轉(zhuǎn)化為求出該層y方向最優(yōu)點(diǎn)坐標(biāo)向量.對(duì)于第m個(gè)最優(yōu)點(diǎn)的y方向坐標(biāo)Yopt(m)，首先進(jìn)行隨機(jī)初始化使

ymin

然后搜索該層上屬于xmin+(m-1)L≤x≤xmin+mL的點(diǎn)，將式(5)中的面積表達(dá)式進(jìn)行離散化處理，表示為

其中：K+為此時(shí)該層輪廓等間隔插值后小于此時(shí)Yopt(m)的y方向坐標(biāo)點(diǎn)；K-為此時(shí)該層輪廓等間隔插值后大于此時(shí)Yopt(m)的y方向坐標(biāo)點(diǎn)，然后代入式(4)，運(yùn)用二分法迭代查找出最優(yōu)解Yopt(m).

為驗(yàn)證上述優(yōu)化算法，對(duì)球體進(jìn)行切分及雪磚堆積模擬試驗(yàn)，獲得模型邊界處雪磚中心的最優(yōu)位置.模型中，球體的半徑設(shè)置為1 000 mm，使用的立方體邊長(zhǎng)a=100 mm.球體模擬堆積見(jiàn)圖8.其中，圖8 a為按覆蓋方法填充球體，圖8 b為優(yōu)化yi(i=1，2，…，n)坐標(biāo)后填充球體.對(duì)比可以看出，雪磚依據(jù)最優(yōu)坐標(biāo)點(diǎn)堆積搭建球體，很好地?cái)M合了原模型.由此說(shuō)明，雪雕模型數(shù)據(jù)處理可行且有效，可為后續(xù)進(jìn)行智能化3D雪雕打印設(shè)備理論分析及采用雪磚進(jìn)行模型搭建提供參考.

圖8球體模擬堆積Fig.8Sphere simulation stacking

圖9不同尺寸雪磚模擬堆積Fig.9Simulated accumulation of snow bricks of different sizes

3 小黃鴨雪雕模擬驗(yàn)證

機(jī)器人模型搭建通過(guò)庫(kù)卡機(jī)器人試驗(yàn)平臺(tái)進(jìn)行物體抓取及擺放試驗(yàn).試驗(yàn)中的長(zhǎng)方體為木質(zhì)材料，規(guī)格為50mm×25mm×20mm.在庫(kù)卡機(jī)器人控制部分，通過(guò)離線編程將優(yōu)化算法生成的坐標(biāo)點(diǎn)編入機(jī)器人控制程序中，實(shí)現(xiàn)機(jī)器人自動(dòng)進(jìn)行模型的搭建.機(jī)器人搭建效果見(jiàn)圖10.

圖10機(jī)器人搭建效果Fig.10Construction effect of robot

使用機(jī)器人依次擺放木制長(zhǎng)方體完成小鴨子模型打印.該試驗(yàn)實(shí)現(xiàn)了機(jī)器人對(duì)木質(zhì)長(zhǎng)方體的抓取以及將其擺放到小鴨子模型的各個(gè)最優(yōu)坐標(biāo)點(diǎn)，完成模型搭建，整個(gè)模型的搭建效果較好.

4 小 結(jié)

本文研究了三維模型等高分層和雪磚位置優(yōu)化.對(duì)三維雪雕模型進(jìn)行數(shù)字離散處理，轉(zhuǎn)化為二維輪廓，以此為雪雕3D打印提供理論依據(jù)；進(jìn)行雪磚堆積位置優(yōu)化，以達(dá)到最大填充率，實(shí)現(xiàn)最大程度復(fù)現(xiàn)原模型；利用MATLAB實(shí)現(xiàn)對(duì)STL格式的模型文件的數(shù)字化處理，用等高切分算法實(shí)現(xiàn)模型的切分及優(yōu)化算法，提取雪磚坐標(biāo)點(diǎn)；通過(guò)仿真及機(jī)器人完成小鴨子模型打印，驗(yàn)證了模型處理和位置優(yōu)化方法的可行性及有效性.

本文在研究三維模型的等高分層和雪磚位置優(yōu)化時(shí)，默認(rèn)的雪磚為立方體，且尺寸一致.顯而易見(jiàn)，雪雕各部位復(fù)雜程度不一，形狀復(fù)雜的部位采用尺寸小的雪磚堆積，會(huì)使雪雕更逼近原模型，且不同形狀的雪磚會(huì)使雪雕獲得不同的效果，在以后的研究中，需在這方面進(jìn)行探討.