基于三維表面模型的任意切割算法
2008-12-31 00:00:00陳學工曾俊鋼李小勇
計算機應用研究 2008年9期
摘 要：通過對三維表面模型進行切割，人們可以方便地觀察物體的內部結構。針對三維表面模型，提出了一種任意切割算法。任意切割過程首先是交互生成切割曲線，生成切割面；然后通過切割面對表面模型進行切割，在切割面上生成交線序列；再由交線序列與切割面邊界生成封閉的邊界輪廓，確定各邊界輪廓間的包含關系；最后對邊界輪廓包圍的截面區域進行Delaunay三角剖分并著色，得到完整的剖面。實驗結果證明了該算法的有效性和可行性。
關鍵詞：三維表面模型； 切割； 輪廓
中圖分類號：TP391.41 文獻標志碼：A
文章編號：10013695(2008)09285003
Arbitrary cutting algorithm for 3D surface model
CHEN Xuegong， ZENG Jungang， LI Xiaoyong
(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 引言
對三維表面模型進行切割是三維可視化研究的一個基本應用。通過切割，既可以詳細觀察了解具有復雜結構物體內各部分的相對位置、大小和形狀，同時，它也是構造三維物體集合運算的基礎。
研究者已經提出了很多對三維物體進行切割的方法。秦緒佳等人[1]提出了采用平面及多面體對重構模型進行剖切的立體剪裁算法；陳俊智等人[2]利用OpenGL中的附加裁剪面實現了平面切割。以上兩種方法只能實現平面的切割，且其切割平面只能平行于某一坐標平面。為此，周翠英等人[3]和郭圣文[4]實現了對三維物體任意方向的平面切割，但不能以任意方式切割。花衛華等人[5]提出的算法可以用不規則三角網(TIN)切割三維物體，靈活性較強。該算法的基本操作是三角形與三角形求交和平面與三角形求交相比較，比較次數較多。
根據實際應用中對任意路徑切割的需求，本文提出了一種針對三維表面模型進行任意交互切割的算法。本算法通過矩形切割面與表面模型的三角面片之間進行求交運算，得到切割面與表面模型的交線，并利用切割面的邊界，構建實體的內外側輪廓，實現對三維表面模型的任意切割。
1 基本定義
定義1[6] 一個連通的、節點互連的實體表面TIN是一個有限的三角形序列。其滿足如下條件：
a)表面中的每一條邊至多被兩個三角形共用，或者說至多是兩個三角形的公共邊；
b)表面的頂點可以被任意多個三角形共享；
c)每一個三角形至少與其他三角形共享一個頂點；
d)如果三角形Ti的一個頂點同時被另一個三角形Tj共享，那么這個頂點也是三角形Tj的頂點；
e)三角形互不交疊。
定義2 對于任意實體表面TIN M與N，如果N上任意一點p在M所圍成的空間中，則稱M包含N，記為MN。對于M所圍成的空間ΩM與N所圍成的空間ΩN，如果ΩM與ΩN存在公共部分，則稱M與N相交，記為M∩N≠；反之則稱相離，記為M∩N=。
定義3 實體S=(OS，IS)。其中：OS表示實體的外側表面；IS表示實體的內側表面，IS={ISi}，IS可為空集。OS，ISi均由實體表面TIN構成，對任意的ISi，有ISiOS，且對于IS集合中任意兩個元素ISi與ISj，ISi∩ISj=。一個三維表面模型包含一個或者多個實體。
2 切割模型的構建
切割模型的構建過程如下：首先建立一個包含該三維表面的模型，且邊平行于坐標軸的最小空間長面體，稱此長方體為包圍盒，然后用鼠標交互地在包圍盒的一個面上畫一條任意折線，稱此折線為切割曲線，將切割曲線中每一條線段構成一個矩形切割面。
包圍盒、切割面和切割曲線的關系如圖1所示。
3 算法的總體描述
3.1 三角面片的數據結構
實體的基本幾何信息主要由實體表面的三角面片表達，每個三角面片元素含三角形的索引號、三個三角形頂點坐標和與此三角面片相鄰的三個三角面片的索引號。三角面片數據結構定義如下：
Class Triangle {
long m_nTriID;
double m_point[3][3];
long m_adjacent[3];
};
3.2 算法的主要步驟
算法執行以下主要步驟：
a)獲取切割面的數目qNum和實體數目sNum；
b)循環獲取單個切割面與單個實體的交線；
c)將交線有序化，使交線構成數條輪廓曲線；
d)組合輪廓線，生成實體的邊界輪廓；
e)檢測出實體的內外側輪廓，得出實體在切割面上的區域，將區域進行Delaunay三角剖分，得到實體的剖面。
4 關鍵步驟
根據三維表面模型的結構，實體為模型的一個獨立的基本單元，三維表面模型的切割問題關鍵在于切割面對單個實體的切割。
41 單個實體與切割面交線的計算
將實體的一個表面TIN全部投影到與切割曲線所在的平面上，形成一組新的三角面片。判斷切割曲線與投影后的三角面片組是否存在交線，如果存在交線，則將交線映射回三維空間，得到三維線段。
41.1 三角面片的選取
設pipi+1為切割曲線的一條線段，Triangles是實體一個表面的三角面片數組。步驟如下：
a)從Triangles中逐一取出三角面片△ABCi，將△ABCi投影到平面P上，得到三角面片△A′B′C′i。
b)三角面片△A′B′C′i與線段pipi+1進行求交運算，相交將△ABCi相鄰的三個三角面片放入隊列；否則取下一個三角面片。
c)從隊列中取出三角面片，如果取出的三角面片沒有與線段pi pi+1進行過求交運算，則計算此三角面片與線段pi pi+1是否相交，相交則將此三角面片相鄰的三角面片放入隊列。如果已經進行過求交運算，則繼續從隊列中取下一個三角面片，直到隊列為空，則Triangles所有與線段pi pi+1相交的三角面片已全部選出。
41.2 交線的生成
設△ABC是實體表面中任意一個三角面片，線段pipi+1是切割曲線中一線段。如果三角面片△ABC的法向量與切割曲線所在平面的法向量垂直，三角面片△ABC在投影面上成一條線段L。此時，只需判斷線段pipi+1是否與線段L相交，相交則記錄下二維的交點。如果三角面片△ABC的法向量與平面P的法向量不垂直。三角面片△ABC投影成一個三角形△A′B′C′。以下四種情況會有交線：
a)線段pipi+1的兩個端點pi，pi+1均在三角形△A′B′C′內；
b)線段的兩個端點pi，pi+1都在三角形△A′B′C′外且線段pipi+1與三角形△A′B′C′至少有一條邊相交于非端點處；
c)線段pipi+1的兩個端點pi，pi+1，一個在三角形△A′B′C′中，另一個在三角形△A′B′C′外；
d)線段pipi+1與三角形△A′B′C′的一條邊部分重合或者完全重合。
得到線段pipi+1與三角形△A′B′C′相交的線段后，根據三角形△ABC所在平面的平面方程，將這些二維交點映射回三維，得到三維交線序列。
4.2 交線的有序化和邊界輪廓生成
由于對實體進行切割后所得到的三維交線均是以無序形式存在，需要將交線有序化，使這些交線構成一條或數條輪廓線。
如果一個表面只與一個切割面相交，交線有序化后將得到封閉的輪廓線；如果一個表面與多個切割面相交，交線有序化后則可能得到多條不封閉的輪廓線。封閉的輪廓線已經構成一個邊界輪廓，而不封閉輪廓線則需要相互組合才能構成一個邊界輪廓。
如圖2所示，圖中陰影部分表示切割面切割一個實體后得到的剖面。實體的一個表面只與切割面Q2相交，因此得到封閉的輪廓曲線L3；而實體的外表面與三個切割面都相交，因此得到L1和L4兩條不封閉的輪廓線。
令集合P={p1，p2，…，pn}。其中：元素pi表示不封閉的輪廓線的起點或者終點；typei表示點pi所在輪廓線的類型。typei=1表示pi所在輪廓線的兩端點在切割面的同一條邊上；typei=2表示pi所在輪廓線的兩端點在切割面的兩條邊上。數組SCP存儲封閉輪廓線所構成的邊界輪廓；數組NSCP存儲不封閉的輪廓線構成的邊界輪廓。
獲取所有邊界輪廓的算法步驟如下：
a)將切割面的邊界線段按逆時針方向排序，將封閉的輪廓線存儲到SCP中，獲取所有不封閉輪廓線的首末點，并根據點在切割面邊界上的順序逆時針生成點列p1p2…pn，令i=0。
b)如果i=n，轉h)；否則，取點pi及pi所在輪廓線L。如果typei=2，轉d)。
c)獲得L的另一個端點pj，將端點的序號位于i和j之間的輪廓線加入到L中，令i=j+1，將L加入到NSCP數組中，轉b)。
d)獲得L的另一個端點pj，k=i+1。
e)如果typek=2，轉g)。
f)如果typek=1，將pk所在輪廓線加入L，令k=k+1，轉d)。
g)令i=k。獲得pk所在輪廓線的另一個端點pe，將pk所在折線加入L中，將端點序號在e與k之間的輪廓線依次加入到L中，將L存儲到NSCP數組中，令i=k+1，轉b)。
h)輸出NSCP和SCP，結束。
以圖2為例，L3為封閉輪廓線，將L3存入SCP中，從p1點開始，type1=2，記錄下L1的另一個端點p8，獲得下一個點p2，type2=1。因此，將L2加入到L1中，取點p4，type4=2，將L4加入L1中，從L4另一端點p5開始，將點p6、p7所在輪廓線L5加入L1中，將L1存入NSCP中。因所有的點已經加入數組中，程序結束。
4.3 單個實體內外側邊界輪廓的檢出及三角化
得到邊界輪廓后，還必須確定輪廓間的相互包含關系，以檢測出切割面上實體的外側輪廓和內側輪廓。在得出內外側輪廓后，對內外輪廓所圍成區域進行三角剖分。目前，有多種優秀的Delaunay三角化方法[7，8]。本文采用文獻[8]提供的Delaunay三角剖分的方法。
根據實體的定義有以下結論：
a)由于實體是由外表面和可能存在的內表面組成，即一個實體最多只有兩層表面，如果一個輪廓包含在另一個輪廓中，則此輪廓中不可能包含其他輪廓。
b)實體的表面之間只存在相離和包含關系，因此，任意的輪廓線之間也只能存在包含和相離關系。
由上述結論可知：判斷輪廓線間的包含關系只需檢測出SCP數組中包含在NSCP中的元素以及SCP數組元素之間的相互包含關系。
由于任意輪廓之間只能存在包含和相離關系，要判斷任意一個輪廓是否包含在其他輪廓中時，只需判斷此輪廓上任意一點是否在另一輪廓所圍成的多邊形區域中[9]。
設Triangles為一三角形數組。存儲三角剖分后的三角形。
檢測輪廓間包含關系的步驟如下：
a)獲得NSCP的個數，如果數組NSCP的元素個數為0，轉c)。
b)取出NSCP中的第一個輪廓線poly，遍歷SCP，找出包含在poly中的輪廓，將poly和poly包含的輪廓所圍成的區域三角剖分，并將剖分得到的三角形存入Triangles中，將poly和包含在poly中的輪廓移除，轉a)。
c)如果SCP中輪廓個數為0，轉f)；否則，從SCP中取出一個輪廓s。
d)判斷SCP中其他輪廓是否包含在s中，如果s中包含有SCP中其他輪廓，則將s及s包含的輪廓所圍成的區域三角化，將剖分得到的三角形存入Triangles中，刪除s以及s所包含的輪廓；否則，判斷s是否為SCP中最后一個輪廓，如果不是，取SCP中下一個輪廓s，轉d)。
e)對SCP中的元素逐一進行三角剖分，剖分得到的三角形存入Triangles。
f)結束。
5 實驗結果
本算法在Visual C++7.0環境下用OpenGL實現。以某地區的地層模型為例，圖3(a)為定義多方向多切割面，(b)為多方向多切割面切割結果圖；圖4(a)為定義任意切割面圖，(b)為任意切割面切割結果圖。
6 結束語
本文針對三維表面模型，提出一種可進行任意路徑切割的算法。本算法與現存算法相比具有以下特點：
a)本算法不僅實現了平面對表面模型的切割，而且能夠以任意切割路徑進行切割，增強了算法的實用性和靈活性；
b)將三維空間矩形與三角形求交，轉變成二維空間的線段與三角形求交，減少求交時的計算量；
c)在確定各邊界輪廓的相互包含關系時，本算法利用了實體的性質，減少了輪廓間的比較次數。
當三維表面模型的表面三角形個數及切割面個數非常多時，需要對每個切割面與表面的三角面片進行求交運算，以及求交后需要將大量無序的交線轉變成邊界輪廓，所需時間較長。因此，如何快速地得到邊界輪廓，尚需進一步探討。
參考文獻：
［1］秦緒佳，歐宗瑛，侯建華.醫學圖像三維重建模型的剖切與立體視窗剪裁［J］.計算機輔助設計與圖形學學報，2002，14(3)：275279.
[2]陳俊智，侯克鵬.利用OpenGL對巖體三維模型進行切剖面方法研究［J］.云南冶金，2005，34(1)：1215.
[3]周翠英，董立國，劉祚秋，等.OpenGL三維地層切割面的實現技術［J］.土木工程學報，
2006，39(2)：6165.
[4]郭圣文.利用鏈表對三維物體實現多平面剪切［J］.計算機應用，2006，26(6)：5455.
[5]花衛華，鄧偉萍，劉修國，等.一種改進的不規則三角網格曲面剖切算法［J］. 地球科學—中國地質大學學報，2006，31(5)：619623.
[6]盛業華，王永波，閭國年，等. 一種基于邊收縮的三維表面模型數據壓縮算法[J]. 中國圖象圖形學報，2007，12(1)：159163.
[7]張征宇，丁玉成，洪軍.STL模型分割截面的三角剖分算法［J］. 計算機輔助設計與圖形學學報，2005，17(6)：12401245.
[8]曾薇，孟祥旭，楊承磊，等.平面多邊形域的快速約束Delaunay三角化［J］.計算機輔助設計與圖形學學報， 2005，17(9)：19331940.
[9]王文成，吳恩華.判斷檢測點是否在多邊形或多面體內的新方法［J］. 軟件學報， 2000，11(12)：16141619
