VC環(huán)境下Delaunay三角剖分算法的設(shè)計(jì)及實(shí)現(xiàn)

沈璐 宋曉東 鄧宇

(吉林建筑工程學(xué)院基礎(chǔ)科學(xué)部，長(zhǎng)春130118)

在計(jì)算機(jī)視覺(jué)領(lǐng)域中，把由兩幅或多幅圖像恢復(fù)空間景物的三維幾何形狀的問(wèn)題稱(chēng)為三維重構(gòu).空間點(diǎn)的重構(gòu)通常采用三角剖分的方法來(lái)重建點(diǎn)與點(diǎn)之間的關(guān)系.三角剖分是指將有限平面點(diǎn)集內(nèi)的點(diǎn)，按一定的方式連接起來(lái)，成為互不交叉的三角形網(wǎng).B.Delaunay于1934年由Voronoi圖(簡(jiǎn)稱(chēng)V圖)演化出的比V圖更易于分析應(yīng)用的Delaunay三角網(wǎng).Delaunay三角網(wǎng)是最接近等角或等邊的最優(yōu)三角網(wǎng).

Visual C++是Microsoft公司推出的一種的Win 32程序開(kāi)發(fā)環(huán)境，它是面向?qū)ο蟮目梢暬删幊滔到y(tǒng).Visual C++開(kāi)發(fā)的程序具有運(yùn)行速度快、可移植能力強(qiáng)等特點(diǎn)，而且它還提供了豐富的位圖操作函數(shù)，對(duì)圖像處理提供了極大的方便［1-3］.本文在利用Visual C++的圖像基本處理的基礎(chǔ)上，結(jié)合MFC中的鏈表類(lèi)等數(shù)據(jù)結(jié)構(gòu)完成數(shù)據(jù)的Delaunay三角剖分.

1 Delaunay三角網(wǎng)的基本原理

Delaunay三角網(wǎng)的定義:它是一系列相連的但不重疊的三角形的集合，而且這些三角形的外接圓不包含這個(gè)區(qū)域內(nèi)的其他任何點(diǎn)［4］.Delaunay三角網(wǎng)的外邊界是一個(gè)凸多邊形，它由連接Voronoi圖中的凸集形成，通常稱(chēng)為凸殼.

Delaunay三角網(wǎng)絡(luò)由于具有空外接圓和最小內(nèi)角最大兩個(gè)性質(zhì)，被廣泛應(yīng)用于三維模型的重構(gòu)中.“空外接圓”是指任何一個(gè)三角形的外接圓均不包含其他數(shù)據(jù)點(diǎn)［5］.“最小內(nèi)角最大”即在所有可能的三角網(wǎng)中，Delaunay三角網(wǎng)中的三角形的最小內(nèi)角最大.這兩點(diǎn)保證了三角網(wǎng)最接近等角或等邊的最優(yōu)三角網(wǎng)，從而確保了準(zhǔn)確的重構(gòu)物體模型.而研究人員又在數(shù)學(xué)上證明了Delaunay三角網(wǎng)是二維平面三角網(wǎng)中唯一的、最優(yōu)的［6］.

2 算法實(shí)現(xiàn)

對(duì)空間點(diǎn)的三角剖分方法從數(shù)據(jù)點(diǎn)的結(jié)構(gòu)上一般可分為兩種:一種是直接對(duì)三維空間點(diǎn)進(jìn)行剖分;另一種是映射法.根據(jù)前面介紹，我們知道Delaunay三角網(wǎng)具有空外接圓和最小內(nèi)角最大兩個(gè)特點(diǎn)，如果直接對(duì)三維數(shù)據(jù)點(diǎn)剖分，雖然將點(diǎn)的空間位置考慮進(jìn)去了，但涉及到空間三角形的平面法向量及相應(yīng)外接圓的計(jì)算和球體問(wèn)題，這些運(yùn)算增加了算法程序的復(fù)雜度和不穩(wěn)定性.所以本文中的三角剖分還是選擇映射法，即將空間中的離散點(diǎn)向某一平面投影(本文采用的是向Z軸投影)，然后對(duì)投影得到的數(shù)據(jù)點(diǎn)進(jìn)行二維平面上的三角剖分，再在剖分的結(jié)果上加入第三維信息(本文中即是深度信息)，最后完成空間三維點(diǎn)的剖分.

2.1 數(shù)據(jù)結(jié)構(gòu)

為了方便對(duì)所剖分的點(diǎn)集和形成的三角形進(jìn)行管理，本文以Visual C++為平臺(tái)，利用鏈表和結(jié)構(gòu)體數(shù)組來(lái)實(shí)現(xiàn)數(shù)據(jù)點(diǎn)三角剖分.

2.2 逐點(diǎn)插入算法的實(shí)現(xiàn)

逐點(diǎn)插入法的主要步驟:

步驟1:凸殼的建立.本文采用超三角形作為Delaunay三角網(wǎng)的初始三角形.nvert為數(shù)據(jù)點(diǎn)個(gè)數(shù)，取Vertex［nvert+1］，Vertex［nvert+2］，Vertex［nvert+3］3點(diǎn)為初始三角形的3個(gè)頂點(diǎn).其與數(shù)據(jù)點(diǎn)中的x，y的最大值、最小值的關(guān)系如下:(當(dāng)前的三角形計(jì)數(shù)ntri為1)

步驟2:插入第一個(gè)頂點(diǎn).將點(diǎn)集內(nèi)的第一點(diǎn)插入到凸殼中，并將第一點(diǎn)與凸殼的頂點(diǎn)相連，即將各頂點(diǎn)與第一個(gè)頂點(diǎn)連線(xiàn)的頂點(diǎn)編號(hào)分別按照逆時(shí)針順序暫存入數(shù)組Edge［］［］中;

步驟3:生成三角網(wǎng).在已有的三角網(wǎng)中找出所有其外接圓包含新插入點(diǎn)P的三角形，將這些三角形連接成一個(gè)區(qū)域，刪除此區(qū)域中各個(gè)頂點(diǎn)在原三角網(wǎng)中的三角劃分，形成一個(gè)新的空腔，將P點(diǎn)與這個(gè)空腔中的所有頂點(diǎn)相連，生成新的三角形.在此過(guò)程中，如果出現(xiàn)Edge［1］［i］=Edge［2］［k］，Edge［2］［i］=Edge［1］［k］同時(shí)相等的情況，則刪除這兩個(gè)重復(fù)的邊;

步驟4:三角網(wǎng)優(yōu)化.應(yīng)用LOP局部?jī)?yōu)化算法，向外更新在此之前產(chǎn)生的三角形;

步驟5:重復(fù)步驟3和步驟4，直到所有的點(diǎn)遍歷完成;

步驟6:刪除超三角形頂點(diǎn);刪掉所有包含超三角形頂點(diǎn)的三角形.

2.3 逐點(diǎn)插入法實(shí)現(xiàn)過(guò)程中的問(wèn)題

(1)本文提出了一種生成Delaunay三角網(wǎng)的數(shù)據(jù)結(jié)構(gòu)，建立了兩個(gè)結(jié)構(gòu)體和結(jié)構(gòu)體數(shù)組，利用一個(gè)二維數(shù)組來(lái)暫時(shí)存儲(chǔ)空腔頂點(diǎn)的編號(hào);

(2)步驟3中，在插入點(diǎn)P的定位過(guò)程中，改變搜索順序，逆序和正序相結(jié)合，可降低對(duì)存儲(chǔ)變數(shù)據(jù)的數(shù)組的賦值次數(shù)，降低數(shù)據(jù)結(jié)構(gòu)的復(fù)雜度，只采用一個(gè)二維數(shù)組就可以滿(mǎn)足要求.如圖1所示，設(shè)在P點(diǎn)加入前，已經(jīng)形成5個(gè)三角形，并依次編號(hào)為1～5;在定位P點(diǎn)位置時(shí)，順次計(jì)算外接圓包含P點(diǎn)的三角形，譬如圖1中的2號(hào)三角形的外接圓包含P點(diǎn)，將三角形邊數(shù)據(jù)記錄在Edge［］［］中，繼續(xù)搜索，找出所有外接圓包含P點(diǎn)的三角形，搜索過(guò)程逆序進(jìn)行，遍歷所有的三角形，這樣的搜索過(guò)程可避免Edge［］［］中數(shù)據(jù)的混亂和不斷賦值;

圖1 點(diǎn)定位

(3)凸殼的選擇.由于本文主要是對(duì)插入法的搜索策略進(jìn)行改進(jìn)，而沒(méi)有選擇將分治算法和逐點(diǎn)插入法結(jié)合在一起的Delaunay三角網(wǎng)改進(jìn)策略，所以本文的凸殼選取的是超三角形;

(4)根據(jù)前面介紹我們知道Delaunay三角網(wǎng)是唯一確定的.因此，加入點(diǎn)的順序不會(huì)影響最終的網(wǎng)格形狀.在進(jìn)行步驟2之前，本文按照臨近點(diǎn)插入的原則，將所有數(shù)據(jù)重新排序，首先按數(shù)據(jù)點(diǎn)的x值的大小，劃分了n個(gè)區(qū)間，在每個(gè)區(qū)間中又重新把點(diǎn)按y值的由小到大重新排序，最后采用各區(qū)間輪流加點(diǎn)的辦法作為逐點(diǎn)插入的順序.由改進(jìn)之后的數(shù)據(jù)對(duì)比可知，數(shù)據(jù)點(diǎn)插入順序的改變對(duì)較少的數(shù)據(jù)量效果不是很明顯，而對(duì)于密集數(shù)據(jù)點(diǎn)效果較好.

3 結(jié)論

本文的三角剖分是基于雙目立體視覺(jué)來(lái)進(jìn)行的，其用戶(hù)操作界面利用Visual C++編寫(xiě)完成，剖分之后的三角網(wǎng)絡(luò)則直接繪制，如圖2～圖3所示.

圖2 用戶(hù)操作界面

圖3 三角剖分結(jié)果

雖然目前常用的、有效的三角剖分主要采用映射法來(lái)完成，此種方法在平面上可達(dá)到最優(yōu)剖分，然而，恢復(fù)到三維空間，卻未必仍是最優(yōu)的剖分，還可能會(huì)出現(xiàn)“尖三角形”問(wèn)題，影響曲面的重構(gòu)質(zhì)量.所以，如何既能把數(shù)據(jù)點(diǎn)的三維空間位置考慮進(jìn)去，又不必像直接三維剖分那樣處理龐大的數(shù)據(jù)量是今后發(fā)展的方向.

［1］楊淑瑩.VC++圖像處理程序處理(第二版)［M］.北京:清華大學(xué)出版社，2003:95-108.

［2］孫鑫，余安萍.VC++深入詳解［M］.北京:電子工業(yè)出版社，2006:4-10.

［3］章毓晉.圖像工程(下冊(cè).第二版)［M］.北京:清華大學(xué)出版社，2003:7-9，104-107.

［4］Lee D T，Schachter B J.Two Algorithms for Constructing a Delaunay Triangulation［J］.Computer and Information Sciences，1980，9(3):52-54.

［5］文偉，楊耀泉，于希寧.用Visual C++語(yǔ)言實(shí)現(xiàn)的Delaunay三角剖分算法［J］.華北電力大學(xué)學(xué)報(bào)，2000，27(4):54-58.

［6］高曉沨.2D-Delaunay三角網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)與遍歷［J］.天津理工大學(xué)學(xué)報(bào)，2006，22(2):66-69.