基于三維表面模型的任意切割算法

摘 要：通過對(duì)三維表面模型進(jìn)行切割，人們可以方便地觀察物體的內(nèi)部結(jié)構(gòu)。針對(duì)三維表面模型，提出了一種任意切割算法。任意切割過程首先是交互生成切割曲線，生成切割面；然后通過切割面對(duì)表面模型進(jìn)行切割，在切割面上生成交線序列；再由交線序列與切割面邊界生成封閉的邊界輪廓，確定各邊界輪廓間的包含關(guān)系；最后對(duì)邊界輪廓包圍的截面區(qū)域進(jìn)行Delaunay三角剖分并著色，得到完整的剖面。實(shí)驗(yàn)結(jié)果證明了該算法的有效性和可行性。

關(guān)鍵詞：三維表面模型； 切割； 輪廓

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2008)09285003

Arbitrary cutting algorithm for 3D surface model

CHEN Xuegong， ZENG Jungang， LI Xiaoyong

(School of Information Science Engineering， Central South University， Changsha 410083， China）

Abstract:With cutting operation for 3D surface model， people can observe the internal structure of objects easily. This paper presented a new algorithm of arbitrary cutting operations of 3D surface model. The procedure of arbitrary cutting operation was to create cutting curve interactively at first， then created cut plane; the 3D model was cut by cutting planes， lists of edge in a cutting plane were established. With these lists and cutting plane’s borderlines， the boundary contours could be created， and their embracing relationship could be identified. The region enclosed by the contours was triangulated using Delaunay triangulation algorithm and filling color to these triangles at last. Complete profiles could be obtained. Experiments prove that the result of the algorithm is effective and available.

Key words：3D surface model; cutting; contours

0 引言

對(duì)三維表面模型進(jìn)行切割是三維可視化研究的一個(gè)基本應(yīng)用。通過切割，既可以詳細(xì)觀察了解具有復(fù)雜結(jié)構(gòu)物體內(nèi)各部分的相對(duì)位置、大小和形狀，同時(shí)，它也是構(gòu)造三維物體集合運(yùn)算的基礎(chǔ)。

研究者已經(jīng)提出了很多對(duì)三維物體進(jìn)行切割的方法。秦緒佳等人^[1]提出了采用平面及多面體對(duì)重構(gòu)模型進(jìn)行剖切的立體剪裁算法；陳俊智等人^[2]利用OpenGL中的附加裁剪面實(shí)現(xiàn)了平面切割。以上兩種方法只能實(shí)現(xiàn)平面的切割，且其切割平面只能平行于某一坐標(biāo)平面。為此，周翠英等人^[3]和郭圣文^[4]實(shí)現(xiàn)了對(duì)三維物體任意方向的平面切割，但不能以任意方式切割。花衛(wèi)華等人^[5]提出的算法可以用不規(guī)則三角網(wǎng)(TIN)切割三維物體，靈活性較強(qiáng)。該算法的基本操作是三角形與三角形求交和平面與三角形求交相比較，比較次數(shù)較多。 

根據(jù)實(shí)際應(yīng)用中對(duì)任意路徑切割的需求，本文提出了一種針對(duì)三維表面模型進(jìn)行任意交互切割的算法。本算法通過矩形切割面與表面模型的三角面片之間進(jìn)行求交運(yùn)算，得到切割面與表面模型的交線，并利用切割面的邊界，構(gòu)建實(shí)體的內(nèi)外側(cè)輪廓，實(shí)現(xiàn)對(duì)三維表面模型的任意切割。

1 基本定義

定義1^[6] 一個(gè)連通的、節(jié)點(diǎn)互連的實(shí)體表面TIN是一個(gè)有限的三角形序列。其滿足如下條件：

a)表面中的每一條邊至多被兩個(gè)三角形共用，或者說至多是兩個(gè)三角形的公共邊；

b)表面的頂點(diǎn)可以被任意多個(gè)三角形共享；

c)每一個(gè)三角形至少與其他三角形共享一個(gè)頂點(diǎn)；

d)如果三角形Ti的一個(gè)頂點(diǎn)同時(shí)被另一個(gè)三角形Tj共享，那么這個(gè)頂點(diǎn)也是三角形Tj的頂點(diǎn)；

e)三角形互不交疊。

定義2 對(duì)于任意實(shí)體表面TIN M與N，如果N上任意一點(diǎn)p在M所圍成的空間中，則稱M包含N，記為MN。對(duì)于M所圍成的空間ΩM與N所圍成的空間ΩN，如果ΩM與ΩN存在公共部分，則稱M與N相交，記為M∩N≠；反之則稱相離，記為M∩N=。

定義3 實(shí)體S=(OS，IS)。其中：OS表示實(shí)體的外側(cè)表面；IS表示實(shí)體的內(nèi)側(cè)表面，IS={ISi}，IS可為空集。OS，ISi均由實(shí)體表面TIN構(gòu)成，對(duì)任意的I(xiàn)Si，有ISiOS，且對(duì)于IS集合中任意兩個(gè)元素ISi與ISj，ISi∩ISj=。一個(gè)三維表面模型包含一個(gè)或者多個(gè)實(shí)體。

2 切割模型的構(gòu)建

切割模型的構(gòu)建過程如下：首先建立一個(gè)包含該三維表面的模型，且邊平行于坐標(biāo)軸的最小空間長(zhǎng)面體，稱此長(zhǎng)方體為包圍盒，然后用鼠標(biāo)交互地在包圍盒的一個(gè)面上畫一條任意折線，稱此折線為切割曲線，將切割曲線中每一條線段構(gòu)成一個(gè)矩形切割面。

包圍盒、切割面和切割曲線的關(guān)系如圖1所示。

3 算法的總體描述

3.1 三角面片的數(shù)據(jù)結(jié)構(gòu)

實(shí)體的基本幾何信息主要由實(shí)體表面的三角面片表達(dá)，每個(gè)三角面片元素含三角形的索引號(hào)、三個(gè)三角形頂點(diǎn)坐標(biāo)和與此三角面片相鄰的三個(gè)三角面片的索引號(hào)。三角面片數(shù)據(jù)結(jié)構(gòu)定義如下：

Class Triangle { 

long m_nTriID;

double m_point[3][3];

long m_adjacent[3];

};

3.2 算法的主要步驟

算法執(zhí)行以下主要步驟：

a)獲取切割面的數(shù)目qNum和實(shí)體數(shù)目sNum；

b)循環(huán)獲取單個(gè)切割面與單個(gè)實(shí)體的交線； 

c)將交線有序化，使交線構(gòu)成數(shù)條輪廓曲線；

d)組合輪廓線，生成實(shí)體的邊界輪廓；

e)檢測(cè)出實(shí)體的內(nèi)外側(cè)輪廓，得出實(shí)體在切割面上的區(qū)域，將區(qū)域進(jìn)行Delaunay三角剖分，得到實(shí)體的剖面。

4 關(guān)鍵步驟

根據(jù)三維表面模型的結(jié)構(gòu)，實(shí)體為模型的一個(gè)獨(dú)立的基本單元，三維表面模型的切割問題關(guān)鍵在于切割面對(duì)單個(gè)實(shí)體的切割。

41 單個(gè)實(shí)體與切割面交線的計(jì)算

將實(shí)體的一個(gè)表面TIN全部投影到與切割曲線所在的平面上，形成一組新的三角面片。判斷切割曲線與投影后的三角面片組是否存在交線，如果存在交線，則將交線映射回三維空間，得到三維線段。

41.1 三角面片的選取

設(shè)pipi+1為切割曲線的一條線段，Triangles是實(shí)體一個(gè)表面的三角面片數(shù)組。步驟如下：

a)從Triangles中逐一取出三角面片△ABCi，將△ABCi投影到平面P上，得到三角面片△A′B′C′i。

b)三角面片△A′B′C′i與線段pipi+1進(jìn)行求交運(yùn)算，相交將△ABCi相鄰的三個(gè)三角面片放入隊(duì)列；否則取下一個(gè)三角面片。

c)從隊(duì)列中取出三角面片，如果取出的三角面片沒有與線段pi pi+1進(jìn)行過求交運(yùn)算，則計(jì)算此三角面片與線段pi pi+1是否相交，相交則將此三角面片相鄰的三角面片放入隊(duì)列。如果已經(jīng)進(jìn)行過求交運(yùn)算，則繼續(xù)從隊(duì)列中取下一個(gè)三角面片，直到隊(duì)列為空，則Triangles所有與線段pi pi+1相交的三角面片已全部選出。

41.2 交線的生成

設(shè)△ABC是實(shí)體表面中任意一個(gè)三角面片，線段pipi+1是切割曲線中一線段。如果三角面片△ABC的法向量與切割曲線所在平面的法向量垂直，三角面片△ABC在投影面上成一條線段L。此時(shí)，只需判斷線段pipi+1是否與線段L相交，相交則記錄下二維的交點(diǎn)。如果三角面片△ABC的法向量與平面P的法向量不垂直。三角面片△ABC投影成一個(gè)三角形△A′B′C′。以下四種情況會(huì)有交線：

a)線段pipi+1的兩個(gè)端點(diǎn)pi，pi+1均在三角形△A′B′C′內(nèi)；

b)線段的兩個(gè)端點(diǎn)pi，pi+1都在三角形△A′B′C′外且線段pipi+1與三角形△A′B′C′至少有一條邊相交于非端點(diǎn)處；

c)線段pipi+1的兩個(gè)端點(diǎn)pi，pi+1，一個(gè)在三角形△A′B′C′中，另一個(gè)在三角形△A′B′C′外；

d)線段pipi+1與三角形△A′B′C′的一條邊部分重合或者完全重合。

得到線段pipi+1與三角形△A′B′C′相交的線段后，根據(jù)三角形△ABC所在平面的平面方程，將這些二維交點(diǎn)映射回三維，得到三維交線序列。

4.2 交線的有序化和邊界輪廓生成

由于對(duì)實(shí)體進(jìn)行切割后所得到的三維交線均是以無(wú)序形式存在，需要將交線有序化，使這些交線構(gòu)成一條或數(shù)條輪廓線。

如果一個(gè)表面只與一個(gè)切割面相交，交線有序化后將得到封閉的輪廓線；如果一個(gè)表面與多個(gè)切割面相交，交線有序化后則可能得到多條不封閉的輪廓線。封閉的輪廓線已經(jīng)構(gòu)成一個(gè)邊界輪廓，而不封閉輪廓線則需要相互組合才能構(gòu)成一個(gè)邊界輪廓。

如圖2所示，圖中陰影部分表示切割面切割一個(gè)實(shí)體后得到的剖面。實(shí)體的一個(gè)表面只與切割面Q2相交，因此得到封閉的輪廓曲線L3；而實(shí)體的外表面與三個(gè)切割面都相交，因此得到L1和L4兩條不封閉的輪廓線。

令集合P={p1，p2，…，pn}。其中：元素pi表示不封閉的輪廓線的起點(diǎn)或者終點(diǎn)；typei表示點(diǎn)pi所在輪廓線的類型。typei=1表示pi所在輪廓線的兩端點(diǎn)在切割面的同一條邊上；typei=2表示pi所在輪廓線的兩端點(diǎn)在切割面的兩條邊上。數(shù)組SCP存儲(chǔ)封閉輪廓線所構(gòu)成的邊界輪廓；數(shù)組NSCP存儲(chǔ)不封閉的輪廓線構(gòu)成的邊界輪廓。

獲取所有邊界輪廓的算法步驟如下：

a)將切割面的邊界線段按逆時(shí)針方向排序，將封閉的輪廓線存儲(chǔ)到SCP中，獲取所有不封閉輪廓線的首末點(diǎn)，并根據(jù)點(diǎn)在切割面邊界上的順序逆時(shí)針生成點(diǎn)列p1p2…pn，令i=0。

b)如果i=n，轉(zhuǎn)h)；否則，取點(diǎn)pi及pi所在輪廓線L。如果typei=2，轉(zhuǎn)d)。

c)獲得L的另一個(gè)端點(diǎn)pj，將端點(diǎn)的序號(hào)位于i和j之間的輪廓線加入到L中，令i=j+1，將L加入到NSCP數(shù)組中，轉(zhuǎn)b)。

d)獲得L的另一個(gè)端點(diǎn)pj，k=i+1。

e)如果typek=2，轉(zhuǎn)g)。

f)如果typek=1，將pk所在輪廓線加入L，令k=k+1，轉(zhuǎn)d)。 

g)令i=k。獲得pk所在輪廓線的另一個(gè)端點(diǎn)pe，將pk所在折線加入L中，將端點(diǎn)序號(hào)在e與k之間的輪廓線依次加入到L中，將L存儲(chǔ)到NSCP數(shù)組中，令i=k+1，轉(zhuǎn)b)。

h)輸出NSCP和SCP，結(jié)束。

以圖2為例，L3為封閉輪廓線，將L3存入SCP中，從p1點(diǎn)開始，type1=2，記錄下L1的另一個(gè)端點(diǎn)p8，獲得下一個(gè)點(diǎn)p2，type2=1。因此，將L2加入到L1中，取點(diǎn)p4，type4=2，將L4加入L1中，從L4另一端點(diǎn)p5開始，將點(diǎn)p6、p7所在輪廓線L5加入L1中，將L1存入NSCP中。因所有的點(diǎn)已經(jīng)加入數(shù)組中，程序結(jié)束。

4.3 單個(gè)實(shí)體內(nèi)外側(cè)邊界輪廓的檢出及三角化

得到邊界輪廓后，還必須確定輪廓間的相互包含關(guān)系，以檢測(cè)出切割面上實(shí)體的外側(cè)輪廓和內(nèi)側(cè)輪廓。在得出內(nèi)外側(cè)輪廓后，對(duì)內(nèi)外輪廓所圍成區(qū)域進(jìn)行三角剖分。目前，有多種優(yōu)秀的Delaunay三角化方法^[7，8]。本文采用文獻(xiàn)[8]提供的Delaunay三角剖分的方法。

根據(jù)實(shí)體的定義有以下結(jié)論：

a)由于實(shí)體是由外表面和可能存在的內(nèi)表面組成，即一個(gè)實(shí)體最多只有兩層表面，如果一個(gè)輪廓包含在另一個(gè)輪廓中，則此輪廓中不可能包含其他輪廓。

b)實(shí)體的表面之間只存在相離和包含關(guān)系，因此，任意的輪廓線之間也只能存在包含和相離關(guān)系。

由上述結(jié)論可知：判斷輪廓線間的包含關(guān)系只需檢測(cè)出SCP數(shù)組中包含在NSCP中的元素以及SCP數(shù)組元素之間的相互包含關(guān)系。

由于任意輪廓之間只能存在包含和相離關(guān)系，要判斷任意一個(gè)輪廓是否包含在其他輪廓中時(shí)，只需判斷此輪廓上任意一點(diǎn)是否在另一輪廓所圍成的多邊形區(qū)域中^[9]。

設(shè)Triangles為一三角形數(shù)組。存儲(chǔ)三角剖分后的三角形。

檢測(cè)輪廓間包含關(guān)系的步驟如下：

a)獲得NSCP的個(gè)數(shù)，如果數(shù)組NSCP的元素個(gè)數(shù)為0，轉(zhuǎn)c)。

b)取出NSCP中的第一個(gè)輪廓線poly，遍歷SCP，找出包含在poly中的輪廓，將poly和poly包含的輪廓所圍成的區(qū)域三角剖分，并將剖分得到的三角形存入Triangles中，將poly和包含在poly中的輪廓移除，轉(zhuǎn)a)。

c)如果SCP中輪廓個(gè)數(shù)為0，轉(zhuǎn)f)；否則，從SCP中取出一個(gè)輪廓s。

d)判斷SCP中其他輪廓是否包含在s中，如果s中包含有SCP中其他輪廓，則將s及s包含的輪廓所圍成的區(qū)域三角化，將剖分得到的三角形存入Triangles中，刪除s以及s所包含的輪廓；否則，判斷s是否為SCP中最后一個(gè)輪廓，如果不是，取SCP中下一個(gè)輪廓s，轉(zhuǎn)d)。

e)對(duì)SCP中的元素逐一進(jìn)行三角剖分，剖分得到的三角形存入Triangles。

f)結(jié)束。

5 實(shí)驗(yàn)結(jié)果

本算法在Visual C++7.0環(huán)境下用OpenGL實(shí)現(xiàn)。以某地區(qū)的地層模型為例，圖3(a)為定義多方向多切割面，(b)為多方向多切割面切割結(jié)果圖；圖4(a)為定義任意切割面圖，(b)為任意切割面切割結(jié)果圖。

6 結(jié)束語(yǔ)

本文針對(duì)三維表面模型，提出一種可進(jìn)行任意路徑切割的算法。本算法與現(xiàn)存算法相比具有以下特點(diǎn)：

a)本算法不僅實(shí)現(xiàn)了平面對(duì)表面模型的切割，而且能夠以任意切割路徑進(jìn)行切割，增強(qiáng)了算法的實(shí)用性和靈活性； 

b)將三維空間矩形與三角形求交，轉(zhuǎn)變成二維空間的線段與三角形求交，減少求交時(shí)的計(jì)算量；

c)在確定各邊界輪廓的相互包含關(guān)系時(shí)，本算法利用了實(shí)體的性質(zhì)，減少了輪廓間的比較次數(shù)。

當(dāng)三維表面模型的表面三角形個(gè)數(shù)及切割面?zhèn)€數(shù)非常多時(shí)，需要對(duì)每個(gè)切割面與表面的三角面片進(jìn)行求交運(yùn)算，以及求交后需要將大量無(wú)序的交線轉(zhuǎn)變成邊界輪廓，所需時(shí)間較長(zhǎng)。因此，如何快速地得到邊界輪廓，尚需進(jìn)一步探討。

參考文獻(xiàn)：

［1］秦緒佳，歐宗瑛，侯建華.醫(yī)學(xué)圖像三維重建模型的剖切與立體視窗剪裁［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14(3)：275279.

[2]陳俊智，侯克鵬.利用OpenGL對(duì)巖體三維模型進(jìn)行切剖面方法研究［J］.云南冶金，2005，34(1)：1215.

[3]周翠英，董立國(guó)，劉祚秋，等.OpenGL三維地層切割面的實(shí)現(xiàn)技術(shù)［J］.土木工程學(xué)報(bào)，

2006，39(2)：6165.

[4]郭圣文.利用鏈表對(duì)三維物體實(shí)現(xiàn)多平面剪切［J］.計(jì)算機(jī)應(yīng)用，2006，26(6)：5455.

[5]花衛(wèi)華，鄧偉萍，劉修國(guó)，等.一種改進(jìn)的不規(guī)則三角網(wǎng)格曲面剖切算法［J］. 地球科學(xué)—中國(guó)地質(zhì)大學(xué)學(xué)報(bào)，2006，31(5)：619623.

[6]盛業(yè)華，王永波，閭國(guó)年，等. 一種基于邊收縮的三維表面模型數(shù)據(jù)壓縮算法[J]. 中國(guó)圖象圖形學(xué)報(bào)，2007，12(1)：159163.

[7]張征宇，丁玉成，洪軍.STL模型分割截面的三角剖分算法［J］. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17(6)：12401245.

[8]曾薇，孟祥旭，楊承磊，等.平面多邊形域的快速約束Delaunay三角化［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2005，17(9)：19331940.

[9]王文成，吳恩華.判斷檢測(cè)點(diǎn)是否在多邊形或多面體內(nèi)的新方法［J］. 軟件學(xué)報(bào)， 2000，11(12)：16141619