采用圖形加速的三角網(wǎng)格實時切分

陳志楊　倪棟梁

(浙江工業(yè)大學(xué)計算機學(xué)院　浙江 杭州 310000)

?

采用圖形加速的三角網(wǎng)格實時切分

陳志楊倪棟梁

(浙江工業(yè)大學(xué)計算機學(xué)院浙江 杭州 310000)

提出一種采用圖形加速的三角網(wǎng)格模型實時切分的方法。針對傳統(tǒng)的三角網(wǎng)格實時切分方法普遍效率不高的問題，提出利用OpenGL的拾取機制的快速、有效，將屏幕曲線映射到模型上，得到切分邊緣的三角面片。并利用網(wǎng)格的AIF(AdjacencyandIncidenceFramework)數(shù)據(jù)結(jié)構(gòu)和當(dāng)前圖像場景的視角矩陣優(yōu)化網(wǎng)格模型交線生成追蹤過程。然后將相交的三角面片重新三角化，構(gòu)建新的拓撲結(jié)構(gòu)。最后分離模型，實現(xiàn)模型的快速切分。實驗結(jié)果表明，該方法能夠快速有效地完成模型的實時切分。

屏幕曲線模型交線模型分離實時切分OpenGL追蹤過程

0　引　言

隨著逆向工程和掃描技術(shù)的應(yīng)用[1]，三角網(wǎng)格模型及其處理在牙科領(lǐng)域有突破性的應(yīng)用。能夠較容易地獲得口腔模型的掃描數(shù)據(jù)，但是由于很多牙科應(yīng)用是針對單個牙齒的，比如補牙，故從整個口腔模型中切割出單個牙齒數(shù)據(jù)(即單齒切分)，對網(wǎng)格算法的實時性和可操作性就有很高的要求。本文針對牙齒模型的單齒切分，研究開發(fā)了一套快速、實時的三角網(wǎng)格切分算法。

對于模型切割已有學(xué)者做過研究[2-7]，陳矛等人提出了一種基于改進的MC(marchingcubes)快速切割算法；趙新方等人提出了基于拓撲關(guān)系的剖切算法。這些算法都是以“刀面模型”對目標模型進行“一刀切”。而在牙科領(lǐng)域，單顆牙齒的切分需要根據(jù)牙齦與牙齒的邊界處的特征決定切分曲線，于是本文提出根據(jù)邊界特征做一系列連續(xù)的小平面，分別與目標模型求交，得到一系列分割點，再追蹤生成切分曲線。

對于三角網(wǎng)格的求交問題，有學(xué)者已做過研究[8-15]。周海在細分曲面造型技術(shù)研究中提出了基于三角形重心構(gòu)造包圍盒，然后通過包圍盒檢測的技術(shù)進行求交計算[12]，該方法求交效率不高，而且容易出現(xiàn)漏交現(xiàn)象；李寧等人在優(yōu)化的三角網(wǎng)格曲面求交算法中提出了層次包圍盒方法，以三角形與子包圍盒是否相交為依據(jù)確定三角形所屬的子包圍盒[13]，該方法雖然能解決漏交問題，但是更耗費時間，而且包圍盒的方法主要適用于兩張三角網(wǎng)格曲面求交的情況；蔣錢平等人提出了基于平均單元格的快速求交算法[14]；鄭軍紅等人提出了基于拓撲關(guān)系的交線快速生成方法[15]。

本文的研究目標是實現(xiàn)實時三角網(wǎng)格快速求交與切分算法?？紤]到之前的很多網(wǎng)格求交算法在求交的完整性、求交效率和實時性等方面的不足，本文通過OpenGL的拾取機制實現(xiàn)網(wǎng)格求交曲線的實時繪制，并根據(jù)OpenGL的場景視角實現(xiàn)快速求交計算[16，17]。在實時性和求交效率方面較其他方法在求交效率等方面有較大提升。本文提出的算法主要思路分為如下幾個步驟：(1) 繪制屏幕曲線；(2) 映射屏幕曲線到三角網(wǎng)格模型上，找到穿透三角面片；(3) 求交計算，追蹤生成交線；(4) 邊緣相交三角面片重新三角化；(5) 模型分離。在本方法中，利用OpenGL的拾取機制以及鼠標滑動時的場景的視角矩陣，可以有效提高穿透三角面片的檢測和求交計算的效率。

1　算法描述

本文的主要算法如下：(1) 開始切分時，根據(jù)當(dāng)前視角在需要切分的邊界處繪制屏幕曲線；(2) 將屏幕曲線實時地映射到三角網(wǎng)格模型上，得到一系列連續(xù)的穿透三角面片以及各三角面片上的穿透點，這里采用OpenGL的交互式拾取機制來完成，具體操作就是對屏幕曲線上的每一個點做一次拾取操作，得到對應(yīng)的穿透三角面片和穿透點；(3) 根據(jù)穿透點與對應(yīng)的穿透三角面片進行求交計算，得到邊界分割點；(4) 根據(jù)AIF快速搜索算法追蹤這些邊界分割點[18]，得到一條切分曲線；(5) 旋轉(zhuǎn)視角，重復(fù)上述操作，直到得到一條閉合的切分曲線；(6) 根據(jù)閉合的切分曲線將切分曲線上的三角形重新三角化[19]，建立新的拓撲關(guān)系[20]；(7) 根據(jù)新的拓撲關(guān)系，以閉合的切分曲線為邊界分離曲線兩側(cè)的三角形。

2　分割線的實時生成

考慮到單齒切分操作的便利性和實時性，本文允許采用交互式實時繪制的方法對網(wǎng)格進行切分。通過鼠標實時在屏幕上的運動，捕獲運動軌跡并實時得到運動軌跡和網(wǎng)格的交線。為此，本文通過如下三個步驟來實現(xiàn)：(1) 鼠標拖動，繪制屏幕曲線；(2) 穿透面片檢測；(3) 求交計算，交線追蹤生成。

2.1基于OpenGL的穿透交點快速生成及穿透三角面片檢測

通過鼠標拖動，在屏幕上獲得的曲線是一系列緊密的二維離散屏幕點，需要將這些點映射到三維空間網(wǎng)格模型上。點的映射過程通過當(dāng)前的場景視角來進行，即每一個點都有一條通過屏幕向里的射線，這條射線穿過模型中的三角面片，記錄該面片及射線與該面片的交點。這樣記錄每一個點的映射即可找到一系列的穿透面片及對應(yīng)穿透交點，這一系列的穿透三角面片即為切分曲線上的三角面片。這整個過程采用OpenGL的選擇機制來實現(xiàn)映射過程的加速。

在本文中，通過利用OpenGL的選擇機制，每個點都可以快速有效地找到映射的穿透三角面片，極大地簡化并加速了在海量三角面片中的檢測。對于屏幕曲線上的每個點通過OpenGL的反映射得到該點對應(yīng)的近截面和遠截面上的兩個點，這兩點之間的連線將穿過模型上的三角面片(如圖1所示)，該面片即為穿透面片，并記錄對應(yīng)穿透交點。當(dāng)模型是三維，就會出現(xiàn)連線穿過多個三角面片的情況，此時選取離近截面最近的穿透三角面片。

圖1　穿透三角面片檢測

上述過程可以為每一個屏幕點找到一個穿透三角面片，然而屏幕點的密集性必然會出現(xiàn)多個屏幕點映射后穿透同一個三角面片，如圖2左側(cè)圖形所示。經(jīng)過本文驗證，每個三角面片只需保留一個穿透交點就已足夠完成求交計算并保留求交曲線的特征。為方便計算，對于同一三角面片上的多個穿透點，本文選擇只保留第一個穿透點，如圖2右側(cè)圖所示。

圖2　多點穿透同一個三角面片只保留第一個點

2.2交線的追蹤生成

上述過程中得到一系列穿透三角面片及其穿透交點，根據(jù)這些信息，可以追蹤生成一條交線，步驟如下：

(1) 計算每個三角面片上對應(yīng)點的視角向量。在2.1節(jié)中提到過穿透面片檢測時會得到遠近截面上的兩個點，該兩點之間的向量即為視角向量：

a=(x0,y0,z0)

(1)

(2) 通過相鄰兩三角面片的對應(yīng)穿透點之間的方向向量(如圖3向量b所示)與其中一點的視角向量(如圖3向量a所示)做求交平面，兩三角面片之間存在一定的夾角，平面計算方法如下：

方向向量：

b=(x2-x1,y2-y1,z2-z1)

(2)

其中(x1,y1,z1)，(x2,y2,z2)為兩三角面片上各自保留的穿透點。

令：

bx=x2-x1

(3)

by=y2-y1

(4)

bz=z2-z1

(5)

則計算求交平面法向量為：

c=a×b

(6)

則：

cx=x0by-y0bx

(7)

cy=z0bx-x0bz

(8)

cz=y0bz-z0by

(9)

根據(jù)法向量即可求得求交平面：

cx(x-x2)+cy(y-y2)+cz(z-z2)=0

(10)

該平面將橫穿該兩相鄰三角面片。

圖3　方向向量與視角向量做平面

(3) 將步驟(2)中根據(jù)式(1)-式(10)所求的平面與圖3中兩三角面片的共邊求交，并記錄交點。

(4) 將一系列穿透三角面片及穿透交點分別做如上步驟，即可得到一系列的分割點，如圖4所示。

圖4　穿透面片經(jīng)求交計算得到的交點

(5) 將上述計算得到的一系列分割點按順序依次連接，即可在模型上得到一條求交曲線，如圖5所示。

圖5　模型上的求交曲線

2.3穿透面片不連續(xù)處理

前文已提到過屏幕曲線只是一系列離散的屏幕點，當(dāng)這些屏幕點映射到空間模型上時，很有可能會出現(xiàn)得到的一系列穿透三角面片并不是連續(xù)的，如圖6所示。圖中第四個離散點和第五個離散點中間有一個三角面片并沒有被選中，圖中用一個叉號標記該三角面片，該三角面片使整個穿透三角面片不連續(xù)，故將該三角面片稱為“被跳躍的三角形”。

圖6　穿透面片不連續(xù)

經(jīng)過本文研究發(fā)現(xiàn)，因為鼠標移動實時繪制的屏幕曲線是一系列十分密集的屏幕離散點，一般極少出現(xiàn)這種跳躍的情況，而一旦出現(xiàn)這種情況，那么必然是屏幕曲線十分靠近“被跳躍三角形”的一個內(nèi)角極小的頂點。這種情況下將該頂點作為斷裂處(即不連續(xù)處)的分割點，并且對于與“被跳躍的三角形”共頂點的碰撞三角面片只保留第一個和最后一個碰撞面片。例如對于圖7中第3、第4、第5和第6個穿透點對應(yīng)的三角面片與“被跳躍的三角形”是共頂點的。該情況下只保留第3個和第6個穿透點的三角面片，而忽略了第4個和第5個穿透點對應(yīng)的面片，并以該公共頂點作為其中一個分割點，依次連接各分割點，得到求交曲線如圖7所示。圖中三角面片邊上的交點為求交計算得到的一系列分割點。

圖7　穿透面片不連續(xù)的處理

3　基于交線的網(wǎng)格切分

本文基于第2節(jié)中得到的交線來進行網(wǎng)格模型的切分，網(wǎng)格切分主要分如下兩個步驟：(1) 切分邊緣的網(wǎng)格重新三角化；(2) 模型分離。

網(wǎng)格的重新三角化主要根據(jù)交線與三角面片的相交情況來進行，有以下幾種情況：(1) 最主要的情況是交線與三角形的兩個交點均在邊上，該情況只要對四邊形部分進行一條對角線的連接，并重新記錄拓撲結(jié)構(gòu)即可，如圖8所示；(2) 在特殊情況下或者對特殊情況處理后可能出現(xiàn)一個交點與三角形某一頂點重合，另一交點在該頂點對邊上，該情況三角形已分為兩個三角形，不需要添加新的連線，只需重新記錄拓撲結(jié)構(gòu)即可，如圖9所示；(3) 當(dāng)兩交點均在三角形頂點上時，即交線與邊重合，如圖10所示，此時不需要重新三角化，并保持原來的拓撲結(jié)構(gòu)即可。

圖8　兩交點都在邊上的情況

圖9　一交點在頂點上的情況

圖10　兩交點都在頂點上 (即交線與邊重合)

模型的分離主要根據(jù)上文中網(wǎng)格模型重新三角化時在切割邊緣部分建立的新的拓撲結(jié)構(gòu)及原先已存在的拓撲結(jié)構(gòu)來進行。本文以切分曲線為邊界，采用廣度優(yōu)先搜索遍歷算法來分離模型，主要算法描述如下：

圖11　模型分離流程圖

(1) 訪問切分邊界上任意一側(cè)的某一個三角形為起始三角形。

(2) 初始化一個隊列為僅包含起始三角形。

(3) 當(dāng)這個隊列為空時，跳到(4)，否則做以下工作：

① 從隊列中彈出隊首元素。

② 遍歷該隊首元素三角形的三條邊，做如下工作：

如果該邊不是邊界邊，則對該邊另一側(cè)的三角形w做如下工作：

如果w未被訪問，則：

? 訪問w；

? 將w壓入隊列。

③ 回到(3)。

(4) 將一系列訪問到的三角面片從模型中分離出來。分離算法流程如圖11所示。

4　實驗結(jié)果

本文在VC++環(huán)境下實現(xiàn)了采用圖形加速的牙齒三角網(wǎng)格模型的切分。結(jié)合OpenGL實現(xiàn)了三維顯示，如圖12、圖13所示。圖12中粗黑色曲線(牙齒與牙齦的交接處)為屏幕曲線映射并求交后得到的切分曲線，其中圖12(b)為切分曲線的區(qū)部放大圖。根據(jù)得到的切分曲線，將與切分曲線相交的三角面片重新三角化，并根據(jù)AIF快速搜索算法在切分邊緣建立新的三角網(wǎng)格拓撲結(jié)構(gòu)。最后根據(jù)廣度優(yōu)先遍歷算法，以切分曲線為邊界，分離流程如圖11所示，將需要的部分從模型中分離出來，如圖13所示為兩顆牙齒被切分下來后的情況，圖中被切分下來的牙齒進行了適當(dāng)?shù)奈灰啤?/p>

圖12　模型三維顯示

圖13　沿交線切分后的模型

5　結(jié)　語

本文提出的方法通過利用OpenGL的拾取機制和場景視角，簡化并加速了切分邊緣三角面片的檢測，實現(xiàn)了鼠標拖動過程中對三角網(wǎng)格模型的實時切分，有了更好的交互性，相比于其他方法提高了切分效率。

[1]LesPiegl.OnNURBS:ASurvey[J].IEEEComputerGraphics&Applications，1991,11(1):55-71.

[2] 陳矛,唐澤圣,唐龍.三維表面模型的快速切割算法[J].軟件學(xué)報,1998,9(9):661-664.

[3] 趙新方,周建中,李衷怡，等.三角網(wǎng)格剖切算法的研究[D].武漢:華中科技大學(xué)研究生院,1999.

[4] 花衛(wèi)華,鄧偉萍,劉修國，等.一種改進的不規(guī)則三角網(wǎng)格曲面切割算法[J].中國地質(zhì)大學(xué)報,2006,31(5):619-623.

[5] 劉青,姚莉秀.一種基于三角網(wǎng)格結(jié)構(gòu)的醫(yī)學(xué)虛擬切割算法[J].微型電腦應(yīng)用,2011，27(1): 50-54.

[6]BruynsC,SengerS,MenonA,etal.ASurveyofInteractiveMeshCuttingTechniquesandANewMethodforImplementingGeneralizedInteractiveMeshCuttingUsingVirtualTools[J].JournalofVisualizationandComputerAnimation，2002，13(1)：21-42.

[7]SotirisB,DieterP,TheodoridisY.RevisitingR-treeconstructionprinciples[C]//Proceedingsofthe6thEastEuropeanConferenceonAdvancesinDatabasesandInformationSystems,2002: 149-162.

[8]AhmedHElsheikh,MustafaElsheikh.Areliabletriangularmeshintersectionalgorithmanditsapplicationingeologicalmodeling[J].EngineeringwithComputers, 2014,30(1):143-157.

[9]DavidMcLaurin,DavidMarcum,MikeRemotigue,etal.Repairingunstructuredtriangularmeshintersections[J].InternationalJournalofNumericalMethodsinEngineering, 2013,93(10):266-275.

[10] 肖于,白潤才.基于包圍盒與空間分解互輔的三角網(wǎng)相交檢測方法[C]//2011InternationalConferenceonInformation,ServicesandManagementEngineering(ISME),2011:1500-1503.

[11] 孫殿柱,孫永偉,田中朝,等.三角網(wǎng)格曲面模型快速求交算法[J].北京工業(yè)大學(xué)學(xué)報,2012,38(8):1121-1124.

[12] 周海.細分曲面造型技術(shù)研究[D].南京:南京航空航天大學(xué)研究生院,2004.

[13] 李寧,田震,張立華,等.優(yōu)化的三角網(wǎng)格曲面求交算法[J].遼寧工程技術(shù)大學(xué)學(xué)報,2013,32(9): 1269-1273.

[14] 蔣錢平,唐平,袁春風(fēng).基于平均單元格的三角網(wǎng)格曲面快速求交算法[J].計算機工程,2008,34(21): 172-174.

[15] 鄭軍紅,陳志楊,葉修梓.基于拓撲關(guān)系的交線快速生成方法[J].計算機集成制造系統(tǒng),2003,9(12):1145-1149.

[16] 李一凡.基于OpenGL的三維建模系統(tǒng)[J].科教導(dǎo)刊，2014,1(1):139-140.

[17] 王新波,朱維杰.基于OpenGL與3DSMax的三維場景建模[J].電子科技,2012,25(1):103-104.

[18] 黃浩,楊杰.基于AIF的三角網(wǎng)格切割方法[J].上海交通大學(xué)學(xué)報,2008,42(4):564-568.

[19] 秦衡峰,王藝.任意平面/曲面域上的高質(zhì)量三角化網(wǎng)格生成[D].湘潭大學(xué),2012.

[20] 田中朝,孫殿柱.三角網(wǎng)格曲面重建及求交理論、方法研究[D].山東理工大學(xué),2008.

TRIANGULARMESHREAL-TIMECUTTINGUSINGGRAPHICSACCELERATION

ChenZhiyangNiDongliang

(Shool of Computer Science,Zhejiang University of Technology,Hangzhou 310000, Zhejiang, China)

Thepaperproposesamethodwhichusesgraphicsaccelerationtocuttriangularmeshinreal-time.Fortheproblemofgenerallyinefficientintraditionaltriangularmeshreal-timecuttingmethod,weproposetousethepicking-upmechanicsinOpenGLtomapthescreencurveontomodelfastandeffectively,andthroughtheuseofAIF(adjacencyandincidenceframework)datastructureandtheperspectivematrixofcurrentimagescenetooptimisethetrackingprocessofthegenerationofmeshmodelintersectinglines.Thenwere-triangulatetheintersectingtriangularfacets,andconstructthenewtopologystructure.Finally,wesplitthemodelandimplementthefastcuttingofmodel.Experimentalresultsshowthatthismethodcanaccomplishreal-timetriangularmeshmodelcuttingfastandeffectively.

ScreencurveModelintersectinglinesModelsplittingReal-timecuttingOpenGLTrackingprocess

2014-08-13。浙江省自然科學(xué)基金項目(Y1090597)。陳志楊，教授，主研領(lǐng)域：CAD，CAGD，幾何造型。倪棟梁，碩士生。

TP391

ADOI:10.3969/j.issn.1000-386x.2016.03.037