張小青，吳坤華，黃 鶴

(1.福建水利電力職業(yè)技術(shù)學(xué)院水利工程系，福建永安366000;2.福建水利電力職業(yè)技術(shù)學(xué)院電氣工程系，福建永安366000;3.北京建筑工程學(xué)院測(cè)繪與城市空間信息學(xué)院，北京100044;4.現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，北京100044)

基于三角網(wǎng)格模型的剖面輪廓信息提取

張小青1，吳坤華2，黃 鶴3，4

(1.福建水利電力職業(yè)技術(shù)學(xué)院水利工程系，福建永安366000;2.福建水利電力職業(yè)技術(shù)學(xué)院電氣工程系，福建永安366000;3.北京建筑工程學(xué)院測(cè)繪與城市空間信息學(xué)院，北京100044;4.現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，北京100044)

為獲得三角網(wǎng)格模型的剖面輪廓信息，提出分層切片和鄰接排序算法。首先將模型中的三角形面片在剖切方向上分組;然后計(jì)算每一組三角形和剖切平面的交線，并按鄰接順序?qū)⒔痪€按首尾順序連接;最后對(duì)每一層非封閉的輪廓線進(jìn)行封閉處理，并計(jì)算剖面面積。試驗(yàn)結(jié)果表明，該算法高效簡(jiǎn)單，能夠有效地獲得封閉的剖面輪廓環(huán)。

三角網(wǎng)格模型;網(wǎng)格剖切;分層切片;鄰接順序;輪廓信息

一、引 言

三維模型中的三角網(wǎng)格模型具有許多良好的幾何特性，它能夠用多個(gè)面片逼近復(fù)雜形體的表面，而且容易處理，因此三角網(wǎng)格模型被廣泛應(yīng)用于計(jì)算機(jī)圖形學(xué)、機(jī)械仿真、科學(xué)計(jì)算可視化等領(lǐng)域［1］。剖面輪廓線是三維模型的一個(gè)重要特征，它代表模型在某一位置處的大致輪廓和幾何形狀，并體現(xiàn)三維模型的基本外觀。如在文物三維展示和虛擬修復(fù)中，往往需要觀察其各個(gè)部位的截面特征，為達(dá)到既不損壞文物、又能夠觀察文物的截面形狀和大小的目的，可采用對(duì)三維模型進(jìn)行剖切處理的方法實(shí)現(xiàn)文物剖面輪廓信息的提取。

目前常用的剖面輪廓線提取算法主要分兩類［2-4］：一類是先建立網(wǎng)格模型中的頂點(diǎn)、邊和三角面片的鄰接拓?fù)潢P(guān)系，再計(jì)算網(wǎng)格模型與剖切平面的交點(diǎn)，此類算法的優(yōu)點(diǎn)是交點(diǎn)是有序的，但建立網(wǎng)格模型的完整的相鄰?fù)負(fù)潢P(guān)系比較費(fèi)時(shí);另一類算法是根據(jù)網(wǎng)格模型中三角形的幾何特征，預(yù)先將三角形按特定法則進(jìn)行排序和分組，并在每組中建立模型的點(diǎn)、邊和三角形面片的鄰接拓?fù)潢P(guān)系，再用平面對(duì)組中的三角形進(jìn)行剖切處理。后一類算法只需比較每個(gè)小組中的三角形和剖切平面的位置關(guān)系，而在每個(gè)小組中建立網(wǎng)格模型中的頂點(diǎn)、邊和三角形之間的相鄰?fù)負(fù)潢P(guān)系，減少了三角形面片和切割平面空間位置關(guān)系的判斷次數(shù)，簡(jiǎn)化了網(wǎng)格模型拓?fù)潢P(guān)系的構(gòu)建工作。

本文采用OBJ格式的三維模型數(shù)據(jù)，利用分層切片和鄰接排序算法，獲得了三角網(wǎng)格模型的剖面輪廓信息，并對(duì)其處理結(jié)果進(jìn)行了分析。

二、輪廓線生成算法

本文的剖切算法可歸納為讀取模型數(shù)據(jù)，即先提取模型中的三角形頂點(diǎn)信息，將三角形在剖切方向上分組;然后在每一組中，比較三角形和剖切平面的空間位置關(guān)系，如果三角形和剖切平面相交，則將交線添加到交線組合中;最后對(duì)交線排序并進(jìn)行封閉處理，獲得封閉的輪廓線。算法流程如圖1所示。

圖1 輪廓線生成算法流程

1.模型中的三角形面片分組

影響剖切算法效率的因素有兩個(gè)［2-4］：一個(gè)是模型中三角形的數(shù)量;另一個(gè)是剖切層數(shù)。為了提高算法效率，將模型中的三角面片進(jìn)行預(yù)處理，即將模型中的三角形按照一定規(guī)則分成多個(gè)小組。本文是沿著Z軸方向剖切，即將模型中的三角形面片按其頂點(diǎn)坐標(biāo)Z值的大小進(jìn)行排序，求出網(wǎng)格模型中的Z坐標(biāo)最小值Zmin和最大值Zmax，模型中的每個(gè)三角形面片被剖切的順序由該三角形的Z坐標(biāo)最小值Zmin確定。假設(shè)剖切間距為d，Zi表示第i層剖切平面的高度，則第一層剖面的Z坐標(biāo)為Z1，其值為模型中Z坐標(biāo)最小值Zmin與剖切間距為d之和，第i層剖面高度的Z坐標(biāo)為Zi，第i+1層剖面的Z坐標(biāo)為Zi+1，相鄰剖面之間的計(jì)算公式為

Zi+1=Zi+d (1)

模型中三角形分組算法原理為：設(shè)Zi-1為第i-1層剖切平面的高度，Zi(i=1，2，…，n)為第i層剖切平面的高度，則存放在第i層剖切輪廓上的三角形面片由如下關(guān)系確定：當(dāng)某個(gè)三角形的 Zmin和Zmax滿足公式：Zi-1≤Zmin＜Zi，而且Zmax≥Zi，則該三角形被分在第i個(gè)小組。

2.判斷三角形面片與剖切平面的位置關(guān)系

由于網(wǎng)格模型是由許多三角形構(gòu)成的，因此模型與剖切平面的相交問(wèn)題，可轉(zhuǎn)化為模型中的三角形與剖切平面的相交問(wèn)題。圖2表示了網(wǎng)格模型與平面的相交情況，粗的多邊形線段表示相交線，將這3條相交線段順序連接，從而構(gòu)成剖面輪廓多邊形。

圖2 平面剖切網(wǎng)格模型

模型中的三角形和剖切平面是否有交點(diǎn)，可以通過(guò)計(jì)算三角形的每個(gè)頂點(diǎn)與平面的有符號(hào)距離，通過(guò)3個(gè)頂點(diǎn)的有符號(hào)距離，對(duì)剖切平面和模型中的三角形的位置關(guān)系進(jìn)行判斷。三角形與剖切平面的空間位置關(guān)系，采用以下原則來(lái)進(jìn)行判斷［6］：假設(shè)剖切平面方程為ax+by+cz+d=0，模型中的三角形的頂點(diǎn)P(X，Y，Z)到平面的有向距離為D，其值可表示為

根據(jù)D值符號(hào)相同或不相同的情況，可確定三角形和平面的空間位置關(guān)系，包括5種情況，如圖3所示，除了圖3(a)中的三角形和平面沒(méi)有交點(diǎn)，圖3中(b)～(e)均存在交點(diǎn)。

圖3 三角形和平面的相交情況

3.輪廓線封閉處理

獲得交線組合后，再對(duì)交線進(jìn)行排序構(gòu)建封閉輪廓環(huán)，先從交線組合中，任意取出一條交線，并將這條交線添加到一個(gè)新交線組合中，每條交線都有頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。從這條交線的尾節(jié)點(diǎn)開始，尋找下一條交線上離這個(gè)尾節(jié)點(diǎn)距離最近的點(diǎn)，稱滿足要求的交線為相關(guān)線。由于這些交線都是同一層剖面上的交線，所以它們具有相同的Z坐標(biāo)，判斷兩點(diǎn)的距離公式為

式中，(xz，yz)是取出的第一條交線的尾節(jié)點(diǎn)坐標(biāo)。如果找到的最近點(diǎn)是相關(guān)線的頭節(jié)點(diǎn)，那么把這條交線添加到上述新交線組合中，并將這條相關(guān)線添加到前一條交線的后面;如果找到的最近點(diǎn)是相關(guān)線的尾節(jié)點(diǎn)，則將這相關(guān)線的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)順序改變，同樣將這條已更改頭節(jié)點(diǎn)和尾節(jié)點(diǎn)順序的交線添加到上述新交線組合中。繼續(xù)上述算法，直至這層剖面的交線都添加到上述新交線組合中。

將交線排完順序后，要檢查每一組交線是否封閉。如果輪廓線不封閉［7］，則要進(jìn)行封閉處理，在排完序的交線組合中，查找其尾節(jié)點(diǎn)是斷開的(即有斷點(diǎn))某條交線，若找到這樣的交線，稱之為斷開線。首先計(jì)算該斷開線的斷點(diǎn)與其他交線(如果有多條斷開線)的斷點(diǎn)之間的距離，并將這些距離值進(jìn)行比較，找到最小距離的那條斷線，這個(gè)最小距離值以D1表示，這條交線稱為相關(guān)線;然后計(jì)算該斷開線的終點(diǎn)與輪廓線中的起始線的起點(diǎn)之間的距離，令這個(gè)距離值為D2。輪廓線中的起始線是這樣的一條交線，即輪廓線是以這條交線的尾節(jié)點(diǎn)開始，并以這條交線的頭結(jié)點(diǎn)結(jié)束。如果距離值D1小于距離值D2，則在斷開線的尾節(jié)點(diǎn)和相關(guān)線的頭節(jié)點(diǎn)之間生成一條線;反之，則在斷開線和輪廓線的起始線之間生成一條線，令生成的那條線為輪廓線的起始線。繼續(xù)檢查是否有斷開線，若有，則繼續(xù)上述算法。最終得到一條正確封閉的輪廓線，并檢查輪廓線不相互交錯(cuò)以及不通過(guò)原來(lái)的線條。

4.剖面面積計(jì)算

將每一層剖面輪廓線進(jìn)行首尾排序之后，形成完整封閉的輪廓環(huán)，每一層輪廓環(huán)可構(gòu)成簡(jiǎn)單多邊形，對(duì)于由頂點(diǎn)A1、A2、…、An構(gòu)成的簡(jiǎn)單多邊形，令頂點(diǎn)Ai的坐標(biāo)為(xi，yi，zi)(i=0，1，…，n)，由于該剖切方向是沿著Z軸，每一層的輪廓線具有相同的Z坐標(biāo)，其面積計(jì)算公式為［8］

三、試驗(yàn)結(jié)果與分析

本文采用的兔子網(wǎng)格模型如圖4所示，本文算法是在VC#2008環(huán)境下，調(diào)用OpenGL函數(shù)庫(kù)編程實(shí)現(xiàn)模型的顯示，將網(wǎng)格模型沿坐標(biāo)軸Z軸方向剖切了11層，獲得每一層剖面輪廓線，進(jìn)行排序構(gòu)建首尾相連的輪廓線，并將未封閉的輪廓線進(jìn)行封閉處理。如圖5所示，提取的是第8層剖面輪廓線，輪廓線中間有斷開，將其進(jìn)行封閉處理之后，如圖6所示。得到封閉的剖面輪廓線。剖面輪廓線能很好地表達(dá)模型的幾何形狀，圖7為第8層剖面面積計(jì)算結(jié)果。

圖4 兔子網(wǎng)格模型

圖5 輪廓線封閉前

圖6 輪廓線封閉后

圖7 剖面面積計(jì)算

四、結(jié)束語(yǔ)

本文提出的剖切算法能對(duì)一些復(fù)雜或有拓?fù)溴e(cuò)誤的模型有很好的適用性。由于將模型中的三角形在剖切方向上進(jìn)行了分組，減少了遍歷與剖切平面相交的三角形的次數(shù)，能夠很好地提高算法效率。利用交線的首尾節(jié)點(diǎn)拓?fù)潢P(guān)系對(duì)交線進(jìn)行排序，而不需要對(duì)模型建立復(fù)雜的拓?fù)溧徑雨P(guān)系，利用最近距離法將輪廓線進(jìn)行封閉處理，從而得到完整封閉的輪廓線。在計(jì)算機(jī)圖形學(xué)、機(jī)械仿真和文物三維展示等領(lǐng)域，往往需要觀察模型的內(nèi)部或截面構(gòu)造，這就需要通過(guò)剖切算法來(lái)提取剖面輪廓特征，輪廓線能夠很好地表現(xiàn)三維模型的剖面特征，因此，剖切算法具有重要的應(yīng)用價(jià)值。

［1］ 張瑞，駱巖林，周明全，等.文物數(shù)字化的關(guān)鍵技術(shù)［J］.北京師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，43 (2)：150-153.

［2］ 王靜亞，方亮，郝敬賓.STL模型特征面片自適應(yīng)分層算法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(6)：2361-2364.

［3］ 潘海鵬，周天瑞，朱根松，等.STL模型切片輪廓數(shù)據(jù)的生成算法研究［J］.中國(guó)機(jī)械工程，2007，18(17)：2076-2079.

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

［5］ 張小青，朱光，侯妙樂(lè)，等.基于四面體的不規(guī)則表面文物體積計(jì)算［J］.測(cè)繪通報(bào)，2011(10)：50-52.

［6］ VATANI M，RAHIMI A R，BRAZANDEH F，et al.An Enhanced SlicingAlgorithm UsingNearestDistance Analysis for Layer Manufacturing［J］.World Academy of Science， Engineering and Technology， 2009，49：721-726.

［7］ TOPCU O，TASCIOGˇLU Y，üNVER H ?.A Method for Slicing CAD Models in Binary STL Format∥6th International Advanced Technologies Symposium(IATS’11).Elazigˇ，Turkey：［s.n.］，2011.

［8］ 王泉德.任意三角網(wǎng)格模型體積的快速精確計(jì)算方法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(18)：32-34.

Extraction of Section Contour Information Based on Triangular Meshes

ZHANG Xiaoqing，WU Kunhua，HUANG He

0494-0911(2012)09-0026-03

P23

B

2012-04-25

張小青(1980—)，女，江西東鄉(xiāng)人，碩士，助教，主要研究方向?yàn)榫芄こ虦y(cè)量。