STL模型的分區(qū)域面片刪除簡(jiǎn)化方法

李日華,周惠群,劉 歡

(西北工業(yè)大學(xué)現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,陜西西安710072)

快速成形(rapid prototyping,RP)技術(shù)是20世紀(jì)80年代末期發(fā)展起來(lái)的一項(xiàng)采用材料精確離散/堆積成形原理的新型制造方法,它需要由三維CAD模型切片求出每層的截面輪廓。

由于不同的CAD制造系統(tǒng)對(duì)實(shí)體的內(nèi)部表達(dá)方式各不相同,直接對(duì)原CAD實(shí)體模型進(jìn)行切片的方法在通用性上存在著很大缺陷,因此,目前廣泛采用ST L文件在CAD和RP系統(tǒng)間進(jìn)行數(shù)據(jù)交換[1]。

STL格式用于將三維模型近似成小三角形平面的組合,是后續(xù)數(shù)據(jù)處理的依據(jù)。如何減少數(shù)據(jù)運(yùn)算量和存儲(chǔ)量也是RP領(lǐng)域的研究熱點(diǎn)之一。目前,最普遍采用的簡(jiǎn)化策略為幾何元素刪除法,其他還包括頂點(diǎn)刪除法、三角形折疊法、迭代收縮法[2-3]等。Schroeder[4]提出的頂點(diǎn)刪除法思想是判斷每個(gè)頂點(diǎn)類型,根據(jù)不同類型選擇不同判斷依據(jù);若滿足設(shè)定的條件則將頂點(diǎn)刪除,再對(duì)形成的空洞三角化。本文先將模型劃分為一個(gè)個(gè)子區(qū)域,若某個(gè)子區(qū)域較平坦,則將其用更少的三角形面片進(jìn)行重新劃分,以減少模型中面片的數(shù)量,通過(guò)多輪簡(jiǎn)化以達(dá)到要求。

1 STL文件的子區(qū)域劃分

1.1 STL文件間拓?fù)潢P(guān)系和毗鄰表的建立

STL的每個(gè)三角形網(wǎng)格由它的3個(gè)頂點(diǎn)及單位法矢構(gòu)成[5]。為了在整體STL文件中劃分出一個(gè)較小的子區(qū)域,需知道每個(gè)面片與哪幾個(gè)面片相鄰,即建立面片之間的毗鄰信息。

在一個(gè)沒(méi)有錯(cuò)誤的ST L文件中,每個(gè)面片應(yīng)有3條邊及3個(gè)相鄰面片,兩個(gè)共享一條邊的面片可稱為一對(duì)毗鄰面片;不會(huì)有超過(guò)兩個(gè)面片共享一邊。

記某個(gè)面片的 3個(gè)頂點(diǎn)為 v1、v2、v3;用 Eij表示連接頂點(diǎn)vi和vj的邊,其毗鄰資料由一對(duì)數(shù)字(m,n)表示,m為毗鄰面片的號(hào)碼,n為毗鄰面片中邊的號(hào)碼。n=0表示毗鄰面片的邊 E23,n=1表示毗鄰面片的邊 E13,n=2表示毗鄰面片的邊E12(圖1)。

圖1 面片1的毗鄰面片

面片1中,E12與面片18的E12重合;E23與面片3的E23重合;E13與面片7的 E13重合。面片1的毗鄰信息見表1。

表1 面片1的毗鄰表

在對(duì)整個(gè)STL文件的遍歷過(guò)后,就可建立起全部面片的毗鄰信息表,即可精確查找到任意一個(gè)面片的毗鄰面片,并知道二者之間的共用邊及共用頂點(diǎn)。

1.2 子區(qū)域劃分方法

本文將子區(qū)域定義為:由某個(gè)面片及所有與這個(gè)面片有公共頂點(diǎn)的面片所組成的集合(圖2)。

圖2 采樣面片及其確定的子區(qū)域

子區(qū)域是本文對(duì)STL文件進(jìn)行簡(jiǎn)化的基本單位,基于毗鄰信息表可得出某個(gè)面片所確定的子區(qū)域的查找方法。

由采樣三角形(記為面片 i)的 E12邊開始,找到其毗鄰面片 j并對(duì)其進(jìn)行標(biāo)記。由STL文件的共頂點(diǎn)原則(一個(gè)小三角形平面的頂點(diǎn)不能落在相鄰的任何一個(gè)三角形的邊上)可知,在j的3個(gè)毗鄰面片中必有另一個(gè)面片包含了頂點(diǎn)v2,找出這個(gè)面片并對(duì)其標(biāo)記后,查找該面片的3個(gè)毗鄰面片,其中一個(gè)就是面片 j,另外的兩個(gè)中必有一個(gè)(記為 k)包含了頂點(diǎn) v2。這又分為兩種情況:一種是僅包含v2;另一種是包含了 v2及 v3(圖3)。若是前者,可繼續(xù)在k的3個(gè)毗鄰面片中查找包含v2的面片并標(biāo)記;若是后者,則說(shuō)明k就是i中E23的毗鄰三角形,接下來(lái)在k的毗鄰面中查找包含v3的面片。

圖3 新查找到的面片 k

這樣,在繞著采樣面片查找完畢后即可標(biāo)記出所有與其共頂點(diǎn)的面片,即確定了一個(gè)子區(qū)域。

1.3 平坦子區(qū)域的判斷

某個(gè)子區(qū)域中,所有相鄰面片法向量夾角的方差可反映出這個(gè)區(qū)域里STL模型表面曲率變化的大小?？山o定一個(gè)參數(shù)ε,當(dāng)方差小于ε時(shí),即認(rèn)為該子區(qū)域平坦,可簡(jiǎn)化;當(dāng)方差大于ε時(shí),則保留此區(qū)域。

網(wǎng)格的單位法矢可由三角形的v1、v2、v3的連接順序按右手規(guī)則確定。若頂點(diǎn)的坐標(biāo)值為 xi、yi、zi(i=1,2,3),則該網(wǎng)格的單位法矢可由下式計(jì)算[5]:

式中:i、j、k分別為沿 x、y、z 軸的單位矢量;N1=y1(z2-z3)+y2(z3-z1)+y3(z1-z2);N2=z1(x2-x3)+z2(x3-x1)+z3(x1-x2);N3=z1(y2-y3)+x2(y3-y1)+x3(y1-y2)。

由兩個(gè)相鄰面片的法矢即可算出它們的法向量夾角:

法向量夾角的方差為:

式中:E為期望,即平均值的符號(hào);Eθ為子區(qū)域中相鄰面片法向量夾角的平均值。該方差可反映出這個(gè)區(qū)域是否平坦。如果Dθ≤ε,即對(duì)這個(gè)區(qū)域標(biāo)記為平坦[3]。

2 基于面片刪除的子區(qū)域簡(jiǎn)化方法

2.1 面片刪除及重新三角化

刪除平坦區(qū)域內(nèi)部所有的面片,并對(duì)其重新進(jìn)行三角化。新生成的面片的邊必須至少有一條為區(qū)域的輪廓邊,這樣重新進(jìn)行三角化后,面片的數(shù)量會(huì)有所減少(圖4)。

圖4 子區(qū)域的簡(jiǎn)化方式

然而,在某個(gè)頂點(diǎn)周圍連續(xù)出現(xiàn)多個(gè)狹長(zhǎng)面片之后,區(qū)域輪廓可能變得非常復(fù)雜(圖5)。

圖5 復(fù)雜的輪廓

對(duì)復(fù)雜的輪廓進(jìn)行三角化分為兩個(gè)步驟:首先將其劃分為 y-單調(diào)多邊形,再對(duì)y-單調(diào)多邊形進(jìn)行三角化。需要指出的是區(qū)域輪廓嚴(yán)格上來(lái)說(shuō)不是一個(gè)平面多邊形,而是一組封閉的空間折線。但由于區(qū)域較平坦,本文的算法并不會(huì)受到影響。

2.1.1 子區(qū)域輪廓的y-單調(diào)塊劃分

如果對(duì)于任意一條垂直于直線 l的直線l′,多邊形與 l′的交都是連通的,則該多邊形為關(guān)于直線l單調(diào)的多邊形(圖6)。

圖6 關(guān)于 l單調(diào)的多邊形

設(shè)想,沿著一個(gè)普通區(qū)域輪廓p的左邊界或右邊界,從最高頂點(diǎn)走向最低頂點(diǎn)。在某些頂點(diǎn)處行進(jìn)方向可能會(huì)從向下轉(zhuǎn)為向上或從向上轉(zhuǎn)為向下,這些頂點(diǎn)稱為拐點(diǎn)。拐點(diǎn)可分為4類:起始頂點(diǎn)處的內(nèi)角小于π,且其相鄰兩個(gè)頂點(diǎn)高度都比它低;分裂頂點(diǎn)處的內(nèi)角大于 π,且其相鄰兩個(gè)頂點(diǎn)高度都比它低;匯合頂點(diǎn)處的內(nèi)角大于π,且其相鄰兩個(gè)頂點(diǎn)高度都比它高;終止頂點(diǎn)處的內(nèi)角小于π,且其相鄰兩個(gè)頂點(diǎn)高度都比它高。其余的頂點(diǎn)稱為普通頂點(diǎn)(圖7)。

圖7 5種頂點(diǎn)

很明顯,如果一個(gè)多邊形里沒(méi)有匯合頂點(diǎn)和分裂頂點(diǎn),它就是y-單調(diào)的。為了消除這兩類頂點(diǎn),需在每個(gè)分裂頂點(diǎn)處向上連一條對(duì)角線,在每個(gè)匯合頂點(diǎn)處向下連一條對(duì)角線,且這些對(duì)角線兩兩不相交。

考慮ej與ek之間、位于 vi上方的那些頂點(diǎn)。若這些頂點(diǎn)中存在一個(gè)最低的,那就將它和vi連接起來(lái)組成一條對(duì)角線將vi消除,見圖8a;如果不存在一個(gè)最低的,或 ej與ek間沒(méi)有頂點(diǎn),則將 vi與ej或ek的上端點(diǎn)連接,見圖 8b和圖 8c。這個(gè)與 vi連接的頂點(diǎn)叫做ej的助手——helper(ej),其定義是:helper(ej)是在當(dāng)前掃描線上方、通過(guò)一條完全落在p內(nèi)部的水平線段與ej相連的頂點(diǎn)中高度最低的那個(gè)頂點(diǎn)。至此可知,把分裂頂點(diǎn)與它左側(cè)那條邊的助手相連即可將其消除。

圖8 分裂頂點(diǎn)的消除

如果將輪廓 p上下顛倒就會(huì)發(fā)現(xiàn)分裂頂點(diǎn)和匯合頂點(diǎn)發(fā)生了互換。因此,處理分裂頂點(diǎn)的思路也可用來(lái)處理匯合頂點(diǎn)。只需把某個(gè)匯合頂點(diǎn)vi與它左右兩側(cè)的邊ej與ek之間、當(dāng)前掃描線下方位置最高的那個(gè)頂點(diǎn)連接起來(lái)即可。雖然在掃描線剛觸及vi時(shí)還不知道哪個(gè)是位于其下方位置最高的頂點(diǎn),但至少已知vi是ej的新助手。圖 9a中,掃描線向下進(jìn)行到vm時(shí)發(fā)現(xiàn)它變成了ej的新助手,那么就在 vm和vi之間連一條對(duì)角線,消除了匯合頂點(diǎn)vi。因此,更換某條邊的助手時(shí),要檢查被替換下的助手是否為一個(gè)匯合頂點(diǎn)。如果是,就在新、老助手之間連一條對(duì)角線。第二種可能見圖9b,掃描線越過(guò) vi后,ej的助手不再發(fā)生變化,就把vi和ej的下端點(diǎn)連接起來(lái),也可將分裂頂點(diǎn)vi消除。

圖9 匯合頂點(diǎn)的處理

2.1.2 y-單調(diào)塊的三角劃分

對(duì)某個(gè)y-單調(diào)塊p而言,可從最高頂點(diǎn)開始同時(shí)沿著其左、右兩條邊界走向最低頂點(diǎn),通過(guò)引入對(duì)角線完成三角剖分。

按照y-坐標(biāo)遞減的順序依次處理各個(gè)頂點(diǎn)。當(dāng)兩個(gè)頂點(diǎn)y-坐標(biāo)相等時(shí),優(yōu)先處理靠左的頂點(diǎn)。用一個(gè)棧s作為輔助數(shù)據(jù)結(jié)構(gòu)。一開始棧s為空,在算法運(yùn)行過(guò)程中,它存放 p中已被發(fā)現(xiàn),卻依然可生出更多對(duì)角線的頂點(diǎn)。在處理新頂點(diǎn)的時(shí)候,應(yīng)盡可能在這個(gè)頂點(diǎn)與棧中的各頂點(diǎn)之間引入對(duì)角線,這些對(duì)角線會(huì)從p中分離出若干三角形。尚未從原多邊形中分離出的頂點(diǎn)都散落在 p中尚未被三角剖分的部分與已處理過(guò)的部分之間的邊界上。這些頂點(diǎn)中位置最低的那個(gè)就位于棧頂;高度次低的那個(gè)頂點(diǎn)位于次棧頂。在已被發(fā)現(xiàn)的那些頂點(diǎn)之上,p中還有一些尚未剖分的部分,這些部分的形狀像一個(gè)金字塔。這個(gè)金字塔的一側(cè)邊界由 p的某條邊獨(dú)立界定,而另一側(cè)邊界上所有的頂點(diǎn),除了最高處的那一個(gè)之外,其對(duì)應(yīng)的內(nèi)角都不小于180°(圖10),這樣的頂點(diǎn)稱為凹頂點(diǎn)。

圖10 已經(jīng)三角剖分和未三角剖分的部分

在處理下一個(gè)頂點(diǎn) vi時(shí),分為兩種情況:vj與棧中的凹頂點(diǎn)不在同側(cè)(圖11a),或位于同側(cè)(圖11b和圖11c)。

圖11 接受處理的下一頂點(diǎn)的3種情況

可由 vj出發(fā)與當(dāng)前棧中除了最后一個(gè)頂點(diǎn)之外的每個(gè)頂點(diǎn)連一條對(duì)角線。所有這些頂點(diǎn)連同棧中最后一個(gè)頂點(diǎn)一起從棧中彈出。此后在vj之上,原多邊形中尚未三角剖分的部分將由剛剛生成的、連接 vj與棧頂頂點(diǎn)的那條對(duì)角線界定。該頂點(diǎn)及vj仍然屬于多邊形中尚待三角剖分的部分,要將它們重新壓回棧中。

當(dāng)vj與凹頂點(diǎn)同側(cè)時(shí),可按照如下方法處理:首先從棧中彈出一個(gè)通過(guò) p的一條邊與vj連接的頂點(diǎn),然后依次從棧中彈出各頂點(diǎn),并將其與 vj連接,不斷重復(fù)這個(gè)過(guò)程。當(dāng)遇到一個(gè)無(wú)法與vj相連的頂點(diǎn)后,就重新將被彈出的前一頂點(diǎn)壓入。完成上述操作后將vj重新壓入棧中。

對(duì)y-單調(diào)多邊形完成三角化的算法如下:

算法:TriangulationP

輸入:一個(gè)y-單調(diào)多邊形p

輸出:p的三角剖分

(1)將 p所有頂點(diǎn)按照y-坐標(biāo)排成一個(gè)遞減序列。若多個(gè)頂點(diǎn) y-坐標(biāo)相同,則 x-坐標(biāo)較小的在前。令排序后的序列為 u1,u2,……un

(2)初始化一個(gè)空棧 s,壓入 u1、u2

(3)for(j←3 to n-1)

(4)do if(uj處于與s棧頂定點(diǎn)對(duì)面一側(cè))

(5)then彈出s中所有頂點(diǎn)

(6)對(duì)彈出的(除最后一個(gè)之外的)每個(gè)頂點(diǎn)在uj與該頂點(diǎn)生成一條對(duì)角線

(7)將和uj壓入s

(8)else彈出s的棧頂

(9)不斷檢查當(dāng)前棧頂處的頂點(diǎn):只要它與uj的連線完全落在p內(nèi)部,就彈出該頂點(diǎn)。把這些連線作為對(duì)角線儲(chǔ)存。將最后彈出的頂點(diǎn)壓回s中

(10)將 uj壓入s中

(11)將un與棧中除第一個(gè)和最后一個(gè)之外的每個(gè)頂點(diǎn)連成對(duì)角線。

2.2 子區(qū)域簡(jiǎn)化示例

以圖5中的子區(qū)域輪廓為例,它含有一個(gè)分裂頂點(diǎn)和一個(gè)匯合頂點(diǎn)需要消除(圖12a)。

圖12 分裂頂點(diǎn)與匯合頂點(diǎn)的消除

按照本文的算法,分別對(duì)這兩個(gè)頂點(diǎn)予以消除(圖12b)。對(duì)劃分出的y-單調(diào)塊進(jìn)行三角劃分,通過(guò)對(duì)比可看出面片數(shù)量由14個(gè)減少為8個(gè)(圖13)。

3 結(jié)語(yǔ)

本文采用將區(qū)域內(nèi)的面片刪除后進(jìn)行重新三角劃分的方法,分區(qū)域?qū)TL模型進(jìn)行簡(jiǎn)化?；诿嫫呐彵碚业讲蓸尤切未_定的子區(qū)域后,以相鄰面片之間法矢量夾角的方差為標(biāo)準(zhǔn)判斷子區(qū)域是否平坦。保留了ST L模型表面較重要的、反映其細(xì)節(jié)或形狀特征的區(qū)域,最大限度保留了模型視覺(jué)特征。通過(guò)控制簡(jiǎn)化循環(huán)次數(shù)、方差閾值來(lái)得到不同精度的簡(jiǎn)化模型。

圖13 簡(jiǎn)化結(jié)果

[1]蔡小康.智能化的快速成形切片算法[J].中國(guó)機(jī)械工程,1997,8(5):49-51.

[2]余羅兼.反求工程中三角網(wǎng)格模型簡(jiǎn)化若干方法的研究[J].機(jī)電技術(shù),2009(2):9-11.

[3]馬淑梅,朱少斌,李愛(ài)平.采用頂點(diǎn)刪除的STL模型分簇簡(jiǎn)化方法[J].現(xiàn)代制造工程,2012(1):79-83.

[4]Schroeder W J,Zarge J A,Lorensen W E.Decimation of triangle meshes[J].ACM Siggraph ComputerGraphics,1992,26(2):65-70.

[5]謝存禧,李仲陽(yáng),成曉陽(yáng).STL文件毗鄰關(guān)系的建立與切片算法研究[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2000,28(3):33-38.