杜麗美

（長治學院 計算機系，山西 長治 046011）

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

杜麗美

（長治學院 計算機系，山西 長治 046011）

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

首個三角形；距離；夾角；異位法；迭代

1 引言

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

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

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

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

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

2 算法的提出

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

3 算法主要思想

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

因為文章只研究二維數(shù)據(jù)點，所以應選用合適的數(shù)組來存儲這些從物體表面提取到的數(shù)據(jù)點。這里采用結構體數(shù)組來存儲這些數(shù)據(jù)，相應的結構體數(shù)組的定義如下：

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

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

1.2 尋找首個三角形

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

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

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

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

1.3 采用異位法擴充三角形

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

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

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

1.4 迭代

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

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

4 試驗結果與分析

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

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

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

2 總結與展望

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

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

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

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

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

［5］謝伙生.計算Delaunay三角剖分的新算法［J］.福州大學學報(自然科學版).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］徐文鵬等.計算機圖形學［M］:第1版.機械工業(yè)出版社,2009.201-204.

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

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

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

（責任編輯 張劍妹）

TP391.41

A

1673-2015（2015）05-0031-04

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

2015—07—26

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