張小青，吳坤華，黃 鶴

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

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

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

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

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

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

一、引 言

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

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

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

二、輪廓線生成算法

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

圖1 輪廓線生成算法流程

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

影響剖切算法效率的因素有兩個［2-4］：一個是模型中三角形的數(shù)量;另一個是剖切層數(shù)。為了提高算法效率，將模型中的三角面片進行預(yù)處理，即將模型中的三角形按照一定規(guī)則分成多個小組。本文是沿著Z軸方向剖切，即將模型中的三角形面片按其頂點坐標(biāo)Z值的大小進行排序，求出網(wǎng)格模型中的Z坐標(biāo)最小值Zmin和最大值Zmax，模型中的每個三角形面片被剖切的順序由該三角形的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，相鄰剖面之間的計算公式為

Zi+1=Zi+d (1)

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

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

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

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

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

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

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

3.輪廓線封閉處理

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

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

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

4.剖面面積計算

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

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

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

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

圖5 輪廓線封閉前

圖6 輪廓線封閉后

圖7 剖面面積計算

四、結(jié)束語

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

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

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

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

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

［5］ 張小青，朱光，侯妙樂，等.基于四面體的不規(guī)則表面文物體積計算［J］.測繪通報，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］.計算機工程與應(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)人，碩士，助教，主要研究方向為精密工程測量。