一種新的三角網(wǎng)格劃分算法研究

杜麗美

（長治學(xué)院 計(jì)算機(jī)系，山西 長治 046011）

一種新的三角網(wǎng)格劃分算法研究

杜麗美

（長治學(xué)院 計(jì)算機(jī)系，山西 長治 046011）

基于三角網(wǎng)格劃分在三維重建中的重要性，提出了一種新的三角網(wǎng)格劃分算法。算法的主要思想是：首先使用最近的點(diǎn)構(gòu)造出首個(gè)三角形；然后以首個(gè)三角形為基礎(chǔ)，采用異位法尋找新的頂點(diǎn)構(gòu)造出新的三角形，直到滿足結(jié)束條件時(shí)停止尋找。

首個(gè)三角形；距離；夾角；異位法；迭代

1 引言

三維物體重建技術(shù)是計(jì)算機(jī)動(dòng)畫、計(jì)算機(jī)視覺、醫(yī)學(xué)圖像處理等方面的核心技術(shù)。目前為止進(jìn)行三維重建的方法主要有兩種：第一種是直接用相應(yīng)的軟件來重建現(xiàn)實(shí)生活中物體，對應(yīng)的軟件有3DMAX、AutoCAD、Maya等，此種方法較為簡單，其關(guān)鍵是對相應(yīng)的軟件的熟練程度；第二種方法相對復(fù)雜，需要一定的數(shù)學(xué)基礎(chǔ)和編程能力。下面主要介紹使用此種方法進(jìn)行三維重建的過程。

首先從真實(shí)物體表面獲取相應(yīng)的離散數(shù)據(jù)點(diǎn)，這些數(shù)據(jù)點(diǎn)的獲取可以借助相應(yīng)的儀器設(shè)備來進(jìn)行。只要借助這些設(shè)備在真實(shí)物體表面掃一圈，相應(yīng)的三維數(shù)據(jù)點(diǎn)就可以讀入計(jì)算機(jī)存儲設(shè)備中。

接著將這批數(shù)據(jù)點(diǎn)在計(jì)算機(jī)中進(jìn)行處理。處理即將得到的這批數(shù)據(jù)點(diǎn)進(jìn)行歸一化處理，使得整體數(shù)據(jù)可以顯示在計(jì)算機(jī)屏幕的指定位置上。

最關(guān)鍵的技術(shù)是使用什么樣的算法對這批數(shù)據(jù)點(diǎn)進(jìn)行三角網(wǎng)格的劃分。進(jìn)行三角網(wǎng)格劃分的目的是重建出與真實(shí)物體表面一樣的虛擬物體，因此三角網(wǎng)格劃分算法選取的好壞直接影響物體的重建效果。

最后使用OpenGL函數(shù)對三角網(wǎng)格模型進(jìn)行光照、材質(zhì)、紋理、霧化等效果的設(shè)置，從而虛擬出真實(shí)物體。

2 算法的提出

文章主要針對二維平面上的散亂數(shù)據(jù)點(diǎn)來研究相應(yīng)的三角網(wǎng)格劃分算法。到目前為止已經(jīng)有許多研究提出了各種三角網(wǎng)格劃分算法，最常見的有區(qū)域生長算法、分治算法、細(xì)分算法等，這些算法[1-4]各有各的優(yōu)缺點(diǎn)。算法類似區(qū)域生長算法，但和區(qū)域生長算法又有些不同，其中首個(gè)三角形的選取采取就近原則（即取決于數(shù)據(jù)點(diǎn)在相應(yīng)數(shù)組中的存儲順序），以首個(gè)三角形為基礎(chǔ)向外擴(kuò)展其它三角形的過程中采用異位尋找法。

3 算法主要思想

1.1 數(shù)據(jù)的存儲

因?yàn)槲恼轮谎芯慷S數(shù)據(jù)點(diǎn)，所以應(yīng)選用合適的數(shù)組來存儲這些從物體表面提取到的數(shù)據(jù)點(diǎn)。這里采用結(jié)構(gòu)體數(shù)組來存儲這些數(shù)據(jù)，相應(yīng)的結(jié)構(gòu)體數(shù)組的定義如下：

在此數(shù)組結(jié)構(gòu)的定義中主要定義了每一個(gè)數(shù)據(jù)點(diǎn)（x，y）的坐標(biāo)信息，并將此數(shù)組定義為Vertex [N]，其中N為已知給定的常數(shù)，表明此數(shù)組的長度為N（N即表示所有數(shù)據(jù)點(diǎn)的數(shù)目）。當(dāng)找到三角形時(shí)，對三角形的三個(gè)頂點(diǎn)采用鏈表的形式存儲，這樣做的好處是可以動(dòng)態(tài)分配存儲空間，其對應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：

此結(jié)構(gòu)中的num表示構(gòu)造出的三角形的編號也可以理解為構(gòu)造出的三角形的數(shù)目，V1[2]、V2 [2]、V3[2]表示第num個(gè)三角形的三個(gè)頂點(diǎn)坐標(biāo)，*T_before為指向第num-1個(gè)三角形的指針，*T_after為指向第num+1個(gè)三角形的指針。

1.2 尋找首個(gè)三角形

從離散點(diǎn)數(shù)組Vertex[N]中取出第一個(gè)二維數(shù)據(jù)點(diǎn)（Vertex[1].x，Vertex[1].y），將此點(diǎn)作為首個(gè)三角形的第一個(gè)頂點(diǎn)，并將此頂點(diǎn)在數(shù)組Vertex[N]中的位置標(biāo)記為flag1，因?yàn)檫@里選取的是Vertex[N]中的第一個(gè)點(diǎn)，所以這里flag1=1。然后在剩下的N-1個(gè)點(diǎn)中尋找與flag1這點(diǎn)距離最近的點(diǎn)，式（3.1）為兩點(diǎn)的距離公式（其中i=2，3....N），若第m個(gè)點(diǎn)Vertex [m]與flag1最近，則標(biāo)記flag2=m，表明首個(gè)三角形的第二個(gè)頂點(diǎn)已找到。

接下來尋找首個(gè)三角形的第三個(gè)頂點(diǎn)，主要在剩下的N-2個(gè)點(diǎn)中尋找（除去第1個(gè)和第m個(gè)點(diǎn)）。主要思想是：先使用公式（3.2）求出flag1與flag2的中點(diǎn)坐標(biāo)Mid（mx，my），然后在這N-2個(gè)點(diǎn)中找到與Mid距離最近的點(diǎn)，具體公式為（3.3）所示，其中j=2，3…N且j≠m。假若第n個(gè)點(diǎn)Vertex[n]與Mid最近，則標(biāo)記flag3=n，表明首個(gè)三角形的第三個(gè)頂點(diǎn)已找到。

Figure 3-1 looking for the first triangle圖3-1 首個(gè)三角形的尋找

到此為止首個(gè)三角形的三個(gè)頂點(diǎn)全部找到，標(biāo)號分別為flag1、flag2和flag3，最后將這三個(gè)點(diǎn)依次存入數(shù)組triangle[1].V1、triangle[1].V2、triangle[1].V3中，并將num的值記為1，表明所找到的為第一個(gè)三角形。如圖3-1中的（a）為數(shù)組Vertex[N]中的N個(gè)數(shù)據(jù)點(diǎn)，圖中的1、2、3…N表示數(shù)據(jù)點(diǎn)在數(shù)組Vertex[N]中的存儲位置，（b）為采用本小節(jié)的方法找到的第一個(gè)三角形。

1.3 采用異位法擴(kuò)充三角形

首個(gè)三角形已經(jīng)找到，記為△1?，F(xiàn)在以△1的三條邊為基礎(chǔ)向外擴(kuò)展出新的三角形[5-6]，為方便描述，還是借助圖3-1(b)為基礎(chǔ)來進(jìn)行，并將首個(gè)三角形的三個(gè)頂點(diǎn)記為a、b和c，如圖3-2(a)所示?？傮w思想為：先以△1的一條邊ab所在直線為基礎(chǔ)，尋找處在c點(diǎn)異側(cè)的那些點(diǎn)c1、c2、c3…，如圖3-2（b）所示；然后計(jì)算∠acib的大小（其中i=1，2，3…），如圖3-2（c）所示，在c1、c2、c3…中找到一點(diǎn)c'使得∠ac'b最大，c'即為將要擴(kuò)展的點(diǎn)，因此第二個(gè)三角形△2已找到，△2的三個(gè)頂點(diǎn)為a、b和c'；將這三個(gè)點(diǎn)存入數(shù)組triangle[2].V1、triangle[2].V2、triangle [2].V3中，并且num+1；接下來采用同樣的辦法找到邊ac所對的點(diǎn)b'，以及邊bc所對的點(diǎn)a'，如圖3-2（d）所示，分別將△3和△4存入triangle[3]和triangle[4]中，相應(yīng)的num+1。

Figure 3-2 Looking for the first triangle圖3-2 異位法擴(kuò)充過程

以尋找c'為例，下面介紹判斷點(diǎn)c與點(diǎn)c'處在直線ab異側(cè)的方法。設(shè)a點(diǎn)坐標(biāo)（x1，y1），b點(diǎn)坐標(biāo)（x2，y2），則直線ab所在的方程為式（3.4）所示。若c與c'處在直線ab的異側(cè)，則將c與c'的坐標(biāo)代入式（3.4）的左邊后所得結(jié)果應(yīng)該異號，若c與c'處在直線ab同側(cè)，則代入式（3.4）的左邊后所得結(jié)果應(yīng)該同號。設(shè)c點(diǎn)坐標(biāo)（cx，cy），c'點(diǎn)坐標(biāo)（cx'，cy'），則將c點(diǎn)坐標(biāo)代入式（3.4）左邊所得結(jié)果k1如式（3.5）所示，將c'點(diǎn)坐標(biāo)代入式（3.4）左邊所得結(jié)果k2如式（3.6）所示；接下來計(jì)算∠ac'b的大小，所用公式為（3.7）。

1.4 迭代

上一小節(jié)是以首個(gè)三角形的三邊為基礎(chǔ)向外擴(kuò)展出了三個(gè)新的三角形△2、△3和△4，接下來再以△2的三邊為基礎(chǔ)向外擴(kuò)展三角形。同樣△3和△4的邊也采用同樣的方法向外擴(kuò)充，總體來說就是反復(fù)的使用3.3小節(jié)的方法來逐步擴(kuò)充，但是在擴(kuò)充過程中難免會遇到新擴(kuò)充出來的三角形其實(shí)就是以前已經(jīng)存在的三角形的情況，所以每擴(kuò)充一個(gè)新的三角形都要檢查一下這個(gè)新三角形的三邊是否和以前已經(jīng)存在的三角形的三邊一樣。若一樣，則去掉新擴(kuò)充出來的這個(gè)三角形；若不一樣，則保留此新三角形，并將三個(gè)頂點(diǎn)存入數(shù)組triangle中，三角形數(shù)目num加1。

結(jié)束條件：當(dāng)以新生成的三角形的邊再向外擴(kuò)充時(shí)，所擴(kuò)充出來的三角形全部都是已經(jīng)存在的三角形且不存在單個(gè)的離散數(shù)據(jù)點(diǎn)時(shí)，停止擴(kuò)充。到此已將給定的數(shù)組Vertex[N]中的全部數(shù)據(jù)點(diǎn)進(jìn)行了三角網(wǎng)格劃分。

4 試驗(yàn)結(jié)果與分析

根據(jù)文章算法，在windowsXP系統(tǒng)下使用VC6. 0進(jìn)行編程證明了本算法的有效性。程序中窗體視點(diǎn)的定位以及點(diǎn)與點(diǎn)之間的連線借助OpenGL中的函數(shù)來完成[7]。圖4-1中的（a）（b）（c）（d）（e）是采用文章所提出的算法分別對50、100、200、500、1000個(gè)數(shù)據(jù)點(diǎn)進(jìn)行三角網(wǎng)格劃分的結(jié)果，其中每張圖中的數(shù)據(jù)點(diǎn)的橫縱坐標(biāo)都在0到150之間隨機(jī)取值，所以生成的三角網(wǎng)的大小也在150*150的區(qū)域內(nèi)，從圖中可以看出，利用本算法可以很有效地對二維平面上的離散數(shù)據(jù)點(diǎn)進(jìn)行三角網(wǎng)的劃分。表4-1是對圖4-1中的五種結(jié)果的分析，所分析的內(nèi)容包括離散數(shù)據(jù)點(diǎn)數(shù)目、生成的三角網(wǎng)格的三角形數(shù)目以及運(yùn)行時(shí)間。

Figure 4-1 Triangulation division using different data points圖4-1 不同的數(shù)據(jù)點(diǎn)的三角網(wǎng)劃分結(jié)果

Table4-1 Triangulations of index parameters表4-1生成的三角網(wǎng)的各指標(biāo)參數(shù)

2 總結(jié)與展望

文章提出了一種新的三角網(wǎng)格劃分算法，該算法的優(yōu)點(diǎn)在于最終劃分的三角網(wǎng)中的三角形大多數(shù)都是銳角三角形，只有很少一部分是鈍角三角形。原因是文章在采用異位法擴(kuò)充三角形時(shí)，對于點(diǎn)的選取采取夾角最大的原則。另外本算法雖是針對二維平面上的離散點(diǎn)進(jìn)行的三角網(wǎng)格劃分，但是對于三維空間[8-10]中具有平滑的凸曲面形態(tài)的離散點(diǎn)同樣適用，只需將滿足這種條件的三維離散點(diǎn)投影到二維平面上，再利用本算法進(jìn)行三角網(wǎng)格的劃分即可?？梢姳舅惴ㄊ怯幸欢ǖ膬?yōu)越性的，但是本文所提算法也有其自身的缺陷，對于三維空間中的復(fù)雜多變的離散數(shù)據(jù)點(diǎn)的三角網(wǎng)格劃分還無法實(shí)現(xiàn)，這是今后有待解決的問題。

［1］謝增廣.平面點(diǎn)集Delaunay三角剖分的分治算法［J］.計(jì)算機(jī)工程與設(shè)計(jì).2012,33(07):2652-2658.

［2］吳晶,姚琪.平面任意區(qū)域的Delaunay三角剖分及其加密［J］.水利科技與經(jīng)濟(jì).2006,12(02): 132-133.

［3］全紅艷,張?zhí)镂?基于區(qū)域生長的網(wǎng)格模型分割技術(shù)［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2006,7 (7):2100-2106.

［4］宋曉宇,戚爰偉等.基于最大外接圓的約束Delaunay三角剖分算法［J］.沈陽建筑大學(xué)學(xué)報(bào)(自然科學(xué)版).2008,24(06):1094-1098.

［5］謝伙生.計(jì)算Delaunay三角剖分的新算法［J］.福州大學(xué)學(xué)報(bào)(自然科學(xué)版).2000,28(05):13-17.

［6］Tsai V J D.Delaunay Triangulations in TIN Creation:anOverviewandaLinear-time Algorithm［J］.Int.J.of GIS,1993,7(6):501-524.

［7］徐文鵬等.計(jì)算機(jī)圖形學(xué)［M］:第1版.機(jī)械工業(yè)出版社,2009.201-204.

［8］施逸飛等.改進(jìn)的三角網(wǎng)格表面近似測地線算法［J］.計(jì)算機(jī)工程.2014,40(11):225-228.

［9］王宏志.離散數(shù)據(jù)點(diǎn)集的3D三角劃分算法研究［J］.工具技術(shù).2008,42(04):85-89.

［10］熊英,胡于進(jìn)等.基于映射法和Delaunay方法的曲面三角網(wǎng)格劃分算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).2002,14(01):56-60.

（責(zé)任編輯 張劍妹）

TP391.41

A

1673-2015（2015）05-0031-04

長治學(xué)院校級科研課題(201419)。

2015—07—26

杜麗美（1983—）女，山西大同人，講師，碩士，主要從事計(jì)算機(jī)圖形學(xué)與圖像處理研究。