STL實(shí)體的有限差分網(wǎng)格高效剖分算法

王躍平，薛 祥

(哈爾濱工業(yè)大學(xué)材料科學(xué)與工程學(xué)院，150001哈爾濱)

計(jì)算機(jī)數(shù)值模擬技術(shù)促進(jìn)了鑄造學(xué)科高速發(fā)展，為提高和確保鑄件質(zhì)量開創(chuàng)了新局面.目前，國際上在鑄造過程數(shù)值模擬領(lǐng)域都與網(wǎng)格剖分前處理技術(shù)密不可分［1］.精確合理的網(wǎng)格剖分是提高模擬精度、減少模擬時(shí)間的重要保障.

網(wǎng)格剖分模塊可接受的輸入數(shù)據(jù)一般為各種商品化造型平臺(tái)均支持的標(biāo)準(zhǔn)格式，其中STL(Stereo Lithography)格式［2-3］應(yīng)用最為廣泛.目前比較成熟的有限差分網(wǎng)格剖分算法有:切片法［4-5］、射線穿透法［6］、優(yōu)化分層算法［7］等.本文在已有算法以及實(shí)現(xiàn)非均勻網(wǎng)格剖分、消除平行面誤差等提高剖分精度的諸多研究［8-9］基礎(chǔ)上，研究了鑄造澆注系統(tǒng)有限差分網(wǎng)格高效精確剖分的算法，編制了程序并給出了網(wǎng)格剖分實(shí)例.

1 基于STL的有限差分網(wǎng)格剖分實(shí)現(xiàn)

該算法基于切片線掃描［10］原理進(jìn)行有限差分非均勻網(wǎng)格剖分.首先，讀取鑄造過程數(shù)值模擬對象:鑄件、鑄型、澆冒口、冷鐵等各STL文件作相應(yīng)分析，對各實(shí)體各方向的平行面以及最小、最大坐標(biāo)值排序后作為實(shí)體的剖分段邊界;然后，根據(jù)實(shí)體實(shí)際情況設(shè)置并自動(dòng)調(diào)整剖分步長;最后，對各STL實(shí)體的剖分段進(jìn)行網(wǎng)格剖分.

1.1STL文件讀取分析

STL文件格式將物體表面劃分成很多空間小三角形，用這些三角形小平面來逼近原CAD實(shí)體，每個(gè)三角形用一個(gè)從實(shí)體內(nèi)指向外部的單位矢量和3個(gè)頂點(diǎn)坐標(biāo)表示.STL文件有ASCII與Binary兩種格式，其中ASCII格式STL文件中含有“facet”關(guān)鍵字，而二進(jìn)制文件則不具有此關(guān)鍵字，所以“facet”關(guān)鍵字可以作為判斷文件格式的依據(jù)，從而采用相應(yīng)的讀入接口程序.本研究采用動(dòng)態(tài)鏈表存儲(chǔ)鑄件、鑄型、澆口等鑄造模擬對象的STL數(shù)據(jù)為

struct STLData

{int flag［3］;//三角形面片屬性標(biāo)識

float facetnormal［3］;//三角形面片的法向量float vertex［3］［3］;//三角形的3個(gè)頂點(diǎn)坐標(biāo)struct STLData*next;

}*Dhead［NoSTLs］;//各STL數(shù)據(jù)的指針數(shù)組

對STL數(shù)據(jù)進(jìn)行分析，用flag值作為小三角形面片屬性標(biāo)識:如果3個(gè)頂點(diǎn)Z方向的坐標(biāo)值均相等(zmax=zmid=zmin)，表明三角形為Z方向平行面，flag［2］=1;如果zmax＞zmid＞zmin，flag［2］=2;如果zmax=zmid＞zmin，flag［2］=3;如果zmax＞zmid=zmin，flag［2］=4.如果3個(gè)頂點(diǎn)Y方向坐標(biāo)值均相等，表明該三角形為Y方向平行面，flag［1］=1;如果3個(gè)頂點(diǎn)X方向坐標(biāo)值均相等，表明該三角形為X方向平行面，flag［0］=1.

從模擬對象的STLData動(dòng)態(tài)鏈表結(jié)構(gòu)中提取實(shí)體的X、Y、Z平行面坐標(biāo)以及最大、最小坐標(biāo)(Xmin、Xmax、Ymin、Ymax、Zmin、Zmax)分別按照X、Y、Z從小到大排序并剔除重復(fù)點(diǎn)后存儲(chǔ)在動(dòng)態(tài)鏈表中為

struct STLParalelPlane

{float PPlane;//平行面坐標(biāo)值

int No;//某方向剖分的網(wǎng)格起始編號

struct STLParalelPlane*next;

}*XPPhead［NoSTLs］，*YPPhead［NoSTLs］，*ZPPhead［NoSTLs］，*AssemXPPhead，*AssemYPPhead，*AssemZPPhead;//各STL模型平行面數(shù)據(jù)(包括邊界(Box［］)處退化成點(diǎn)或線的邊界)的指針數(shù)組，以及鑄造系統(tǒng)裝配體平行面數(shù)據(jù)的指針

為了使所有的鑄造模擬對象網(wǎng)格編號(i，j，k)統(tǒng)一，把鑄件、鑄型等各STL實(shí)體的平行面數(shù)據(jù)分別按照X、Y、Z從小到大再次排序，剔除重復(fù)點(diǎn)后存儲(chǔ)在平行面鏈表AssemXPPhead、AssemYPPhead、AssemZPPhead中.把PPlane作為剖分段的邊界與網(wǎng)格單元的邊界，能夠有效避免平行面處誤差，提高剖分精度;No通過程序自動(dòng)調(diào)整用戶設(shè)置的網(wǎng)格剖分步長確定.在處理平行面數(shù)據(jù)時(shí)，可能會(huì)遇到兩個(gè)PPlane非常接近的情況.經(jīng)分析認(rèn)為該問題是由于模擬對象的裝配體文件轉(zhuǎn)換成STL文件時(shí)的轉(zhuǎn)換精度和算法精度不高造成的.用戶可根據(jù)需要設(shè)置一誤差來解決.例如設(shè)誤差為0.01 mm，若兩平行面數(shù)據(jù)之差小于該值，則合并為一個(gè)平行面.

程序自動(dòng)調(diào)整剖分步長的基本原理為:設(shè)某剖分段的長度為Li=(PPlane)i+1-(PPlane)i，用戶設(shè)置的剖分步長為dl，如果Li/dl不為整數(shù)，即表明剖分段的邊界與網(wǎng)格單元邊界不重合，需要對分區(qū)內(nèi)的步長進(jìn)行自動(dòng)調(diào)整為

式中:f(x)為取x的四舍五入的函數(shù);dl'為自動(dòng)調(diào)整后的剖分步長.某方向上網(wǎng)格參數(shù)設(shè)置、調(diào)整的示例如圖1所示，設(shè)用戶設(shè)置的剖分步長均為dl=5 mm.

圖1 某方向上網(wǎng)格參數(shù)示意圖

網(wǎng)格剖分參數(shù)設(shè)置完成后，即可得各STL實(shí)體在Z、Y、X方向的起止網(wǎng)格編號(Nsz、Nez、Nsy、Ney、Nsx、Nex)及起始坐標(biāo)(zs、ys、xs)，然后按照Z、Y、X向的順序進(jìn)行剖分.

1.2Z方向切割實(shí)體

Z向切割平面z=zk切割實(shí)體，獲得一個(gè)或多個(gè)封閉輪廓線，用struct Section存儲(chǔ)這些線段為

struct Section

{double vertex0［2］;//線段第1個(gè)端點(diǎn)x、y坐標(biāo)

double vertex1［2］;//線段第2個(gè)端點(diǎn)x、y坐標(biāo)

double SignofNormaly;//線段所在三角形面片法向量的Y向分量:Normaly

struct Section*next;};

切割從第n個(gè)STL(n=1，2，3，…)的最小尺寸處z=zk=zs=ZPPhead［n］+dz［k］×0.5(k=Nsz)開始，之后用z=zk=zs+(dz［k］+dz［k+1］)×0.5(k=Nsz+1，Nsz+2，…，Nez-1)平面切割實(shí)體的三角形面片.在判斷三角形面片與切割平面z=zk是否相交時(shí)，先選擇非Z向平行面，即struct STLData中flag［2］≠1的三角形面片，再比較三角形3頂點(diǎn)Z坐標(biāo)值與zk值:若zmin≤zk≤zmax，則該面片與z=zk切割面相交，否則不相交.設(shè)三角形被切割棱邊的頂點(diǎn)坐標(biāo)為(x1，y1，z1)、(x2，y2，z2)，z=zk切割面與三角形棱邊的交點(diǎn)坐標(biāo)可以求得:

把三角形面片與Z向切割面交線的兩個(gè)端點(diǎn)數(shù)據(jù)存儲(chǔ)在vertex0、vertex1中，并把當(dāng)前三角形法向量的Y向分量賦給SignofNormaly.

1.3Y軸方向切割封閉輪廓線

Y向切割線y=yj切割z=zk面上封閉輪廓線，得到與一系列成對進(jìn)出的掃描線段.用struct Scanbeam記錄這些線段端點(diǎn)的x坐標(biāo)以及交點(diǎn)類型為

struct Scanbeam

{double vertexp;//Y掃描線與封閉輪廓線的線段交點(diǎn)的x坐標(biāo)

int flag;//y掃描線與封閉輪廓線的線段相交點(diǎn)類型

Y向切割從第n個(gè)STL實(shí)體(n=1，2，3，…)的最小尺寸處y=yj=ys=YPPhead［n］+dy［j］×0.5(j=Nsy)開始，之后用y=yj=ys+(dzy［j］+dy［j+1］)×0.5(j=Nsy+1，Nsy+2，…，Ney-1)掃描線切割z=zk面上的封閉輪廓線，得到一系列交點(diǎn)，交點(diǎn)坐標(biāo)可由式(1)求得.設(shè)struct Section中記錄線段的兩個(gè)端點(diǎn)的y坐標(biāo)分別為ymin、ymax，且ymin≤ymax，若ymin≤yj≤ymax，則該線段與y=yj掃描線相交，將交點(diǎn)類型賦給flag:1-與含有ymin的端點(diǎn)重合;0-交點(diǎn)在線段中間部分;-1-與含有ymax的端點(diǎn)重合;2-與線段重合.

將所得交點(diǎn)按x坐標(biāo)升序排序、處理奇異點(diǎn)、按奇偶配對，獲得成對進(jìn)出的掃描線段.

1.4X軸方向切割掃描線段

X向切割掃描線段，得到STL實(shí)體在掃描線段上的網(wǎng)格體心坐標(biāo)(xi，yj，zk).若x=xi在成對進(jìn)出的掃描線段上，則該網(wǎng)格為實(shí)體內(nèi)部的網(wǎng)格.根據(jù)多材質(zhì)系統(tǒng)網(wǎng)格剖分時(shí)材質(zhì)屬性賦值方法［11］，為材質(zhì)編號為默認(rèn)值(空氣，通常設(shè)為0)的當(dāng)前單元賦相應(yīng)的材質(zhì)編號值，保存網(wǎng)格信息，網(wǎng)格剖分基本完成.算法流程如圖2所示.

圖2 網(wǎng)格剖析分流程圖

2 網(wǎng)格剖分的關(guān)鍵點(diǎn)

2.1 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的使用

網(wǎng)格剖分程序運(yùn)行之前，并不能夠確切地知道各STL實(shí)體的三角形面片數(shù)量、需要?jiǎng)澐值钠史侄螖?shù)以及XYZ各方向的網(wǎng)格數(shù)等信息，這就給程序設(shè)計(jì)帶來了一些不便.在計(jì)算機(jī)內(nèi)存資源一定的情況下，本程序采用動(dòng)態(tài)鏈表和動(dòng)態(tài)數(shù)組［12］處理網(wǎng)格剖分相關(guān)數(shù)據(jù)，能夠較大限度地提高網(wǎng)格剖分?jǐn)?shù)量，增強(qiáng)了剖分程序的穩(wěn)定性和實(shí)用性.

2.2 奇異點(diǎn)處理

奇異點(diǎn)是指切割面或掃描線與STL實(shí)體相交的特殊交點(diǎn)，可分為:1)Z向切割STL實(shí)體時(shí)產(chǎn)生，如圖3(a)、(c)、(d)等3種情況;2)Y向掃描線與封閉輪廓線相交時(shí)產(chǎn)生，如圖4(b)、(c)等2種情況.

Z向切割奇異點(diǎn)處理為:圖3(a)中輪廓退化為點(diǎn)的情況，直接刪除;圖3(c)中輪廓退化成直線或兩點(diǎn)之間產(chǎn)生一條以上交線的情況，通過將切割面偏移一微小量消除;Z向平行面作為剖分段邊界，可以排除情況如圖3(d).通過上述處理，排除了封閉輪廓線退化成點(diǎn)或線的情況，避免了封閉輪廓線中出現(xiàn)重復(fù)線段的情況，保證了Z向切割面上的封閉輪廓線鏈表中記錄的線段均唯一且l＞0.這樣，程序更為簡單，且能夠有效地降低后續(xù)剖分的出錯(cuò)幾率.

圖3 切割平面與STL三角形面片相交情況

圖4 掃描線與封閉輪廓線交點(diǎn)情況

2.3 網(wǎng)格剖分對STL文件的容錯(cuò)處理

上述剖分算法原理簡單，在STL文件完好的前提下十分可靠，但可能因轉(zhuǎn)換精度以及其他算法精度的原因，STL格式文件常包含各種細(xì)小的錯(cuò)誤［13］，其中影響最大的是STL文件存在小孔洞.因此要保證程序的穩(wěn)定性，要么修復(fù)STL，要么對這些錯(cuò)誤進(jìn)行容錯(cuò)處理.本研究采用的是容錯(cuò)處理方法.其基本原理為:若某條掃描線穿過封閉環(huán)上的小孔洞造成交點(diǎn)不配對的情況時(shí)，則給出警告:1)提示用戶調(diào)整Y方向剖分步長，直到滿足配對條件為止;2)保留體心坐標(biāo)在該掃描線上的所有網(wǎng)格的原始材質(zhì)(空氣，材質(zhì)編號為0)，待網(wǎng)格剖分完成后，再對網(wǎng)格進(jìn)行過濾，糾正STL小孔洞造成的材質(zhì)不匹配的網(wǎng)格單元.其基本原理為:針對材質(zhì)編號為初始值0的網(wǎng)格單元，搜索并判斷其3個(gè)方向:X、Y、Z上6個(gè)相鄰網(wǎng)格單元的材質(zhì)，如果某一方向上的兩個(gè)相鄰單元材質(zhì)相同，則把該網(wǎng)格屬性重置為相鄰網(wǎng)格的材質(zhì)編號.原理示意圖如圖5所示.

圖5 糾正STL小孔洞導(dǎo)致網(wǎng)格材質(zhì)不匹配原理示意圖

3 有限差分網(wǎng)格剖分實(shí)例

應(yīng)用上述網(wǎng)格剖分算法編制了三維有限差分網(wǎng)格剖分程序.該程序能夠?qū)Ω鞣N復(fù)雜形狀的STL實(shí)體進(jìn)行網(wǎng)格剖分，剖分速度快、精度高、容錯(cuò)能力強(qiáng).圖6為剖分實(shí)例，該鑄造模擬對象包括鑄件、澆冒口等多個(gè)STL實(shí)體，其中，鑄件輪廓尺寸為740 mm×885 mm×488 mm.圖6(a)中的各實(shí)體主要由曲面組成，并且含有相對尺寸較小的倒圓、倒角、圓孔、凸臺(tái)等.若采用均勻網(wǎng)格，并且要保留盡可能多的幾何特征，就必須采用較小的剖分步長.這樣網(wǎng)格數(shù)量會(huì)驚人地龐大，從而導(dǎo)致后續(xù)模擬計(jì)算時(shí)間顯著增加.本算法會(huì)自動(dòng)在含有小幾何特征的剖分段內(nèi)采用較小的剖分步長，而其他剖分段內(nèi)采用較大的剖分步長，在不顯著增加網(wǎng)格數(shù)量的前提下進(jìn)行剖分，且不會(huì)出現(xiàn)小特征丟失或網(wǎng)格不連通的情況.網(wǎng)格剖分結(jié)果如圖6(b)所示，部分參數(shù)如圖6(c)所示.設(shè)輸入的最大空間步長為:Δx=10 mm，Δy=10 mm，Δz=9 mm，在Pentium(R)4 CPU 1.8 GHz，內(nèi)存512 MB的普通計(jì)算機(jī)上剖分耗時(shí)1.482 s，其中鑄件網(wǎng)格數(shù)為1 007 115個(gè).

4 結(jié)論

1)該算法能對多STL模擬對象進(jìn)行分區(qū)域非均勻剖分，程序能夠自動(dòng)調(diào)整剖分步長、有效消除平行面處誤差，提高剖分精度.

2)采用動(dòng)態(tài)鏈表和動(dòng)態(tài)數(shù)組處理數(shù)據(jù)、吸納了現(xiàn)有算法處理奇異點(diǎn)的長處并進(jìn)行改進(jìn)，剖分原理簡單，易于編程實(shí)現(xiàn)，在保證剖分精度的前提下，資源占用少，計(jì)算速度快.

3)程序在網(wǎng)格剖分完成后，通過網(wǎng)格材質(zhì)匹配對STL文件的進(jìn)行容錯(cuò)處理，能夠有效修復(fù)STL小孔洞造成的掃描線進(jìn)出點(diǎn)不配對的錯(cuò)誤，剖分結(jié)果精確、實(shí)用性強(qiáng).

［1］INOUE T，JU D Y.Analysis of solidification and viscoplastic stresses incorporating a moving boundary:an application to simulation of the casting process［J］.Journal of Thermal Stress，1992，15(1):109-128.

［2］ROSCOE L E.Sterolithography interface specification［M］.Valencia，CA:America-3D systems Inc，1988.

［3］侯華，毛紅奎，張國偉.鑄造過程的計(jì)算機(jī)模擬［M］.北京:國防工業(yè)出版社，2008:22-26.

［4］賈寶仟，柳百成.鑄造數(shù)值模擬中直角六面體網(wǎng)格自動(dòng)剖分技術(shù)［J］.熱加工工藝，1996，(6):27-29.

［5］邱宗文，孫國雄，劉永剛，等.基于STL的切片法有限差分網(wǎng)格剖分的研究［J］.特種鑄造技有色合金，2003，(6):28-30.

［6］周建興，劉瑞祥，陳立亮，等.基于STL的射線穿透法網(wǎng)格剖分的研究［J］.鑄造技術(shù)，2001，(1):15-17.

［7］徐宏，鐘雪友，程軍.鑄件三維有限差分網(wǎng)格自動(dòng)剖分技術(shù)［J］.鑄造，2000，49(12):903-907.

［8］HUANG S H，ZHANG L C，HAN M.An effective error-tolerance slicing algorithm for STL files［J］.The International Journal of Advanced Manufacturing Technology，2002，20(5):363-367.

［9］駱國建.鑄造過程計(jì)算機(jī)模擬前處理技術(shù)研究［D］.武漢:武漢理工大學(xué)，2010.

［10］梁英業(yè)，戴挺，趙建新，等.基于STL的切片線掃描法網(wǎng)格剖分技術(shù)［J］.鑄造，2005，54(10):1002-1005.

［11］關(guān)洋.鑄件充型凝固過程數(shù)值模擬前后處理技術(shù)研究［D］.沈陽:沈陽鑄造研究所，2004.

［12］陳鳳翔，李汪根.C++動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)與重用［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20(2):79-82.

［13］SZILVáSI-NAGY M，MáTYáSI G Y.Analysis of STL files［J］.Mathematical and Computer Modeling，2003，38(10):945-960.