陳志楊　倪棟梁

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

?

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

陳志楊倪棟梁

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

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

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

0　引　言

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

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

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

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

1　算法描述

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

2　分割線的實(shí)時(shí)生成

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

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

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

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

圖1　穿透三角面片檢測

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

圖2　多點(diǎn)穿透同一個三角面片只保留第一個點(diǎn)

2.2交線的追蹤生成

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

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

a=(x0,y0,z0)

(1)

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

方向向量：

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

(2)

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

令：

bx=x2-x1

(3)

by=y2-y1

(4)

bz=z2-z1

(5)

則計(jì)算求交平面法向量為：

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中兩三角面片的共邊求交，并記錄交點(diǎn)。

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

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

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

圖5　模型上的求交曲線

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

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

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

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

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

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

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

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

圖8　兩交點(diǎn)都在邊上的情況

圖9　一交點(diǎn)在頂點(diǎn)上的情況

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

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

圖11　模型分離流程圖

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

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

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

① 從隊(duì)列中彈出隊(duì)首元素。

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

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

如果w未被訪問，則：

? 訪問w；

? 將w壓入隊(duì)列。

③ 回到(3)。

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

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

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

圖12　模型三維顯示

圖13　沿交線切分后的模型

5　結(jié)　語

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

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

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

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

[4] 花衛(wèi)華,鄧偉萍,劉修國，等.一種改進(jìn)的不規(guī)則三角網(wǎng)格曲面切割算法[J].中國地質(zhì)大學(xué)報(bào),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é)報(bào),2012,38(8):1121-1124.

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

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

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

[15] 鄭軍紅,陳志楊,葉修梓.基于拓?fù)潢P(guān)系的交線快速生成方法[J].計(jì)算機(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é)報(bào),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é)基金項(xiàng)目(Y1090597)。陳志楊，教授，主研領(lǐng)域：CAD，CAGD，幾何造型。倪棟梁，碩士生。

TP391

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