• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2012-02-15 06:38:14沈璐宋曉東鄧宇
    關(guān)鍵詞:三角網(wǎng)外接圓剖分

    沈璐 宋曉東 鄧宇

    (吉林建筑工程學(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.

    猜你喜歡
    三角網(wǎng)外接圓剖分
    基于重心剖分的間斷有限體積元方法
    歐拉不等式一個(gè)加強(qiáng)的再改進(jìn)
    將相等線(xiàn)段轉(zhuǎn)化為外接圓半徑解題
    二元樣條函數(shù)空間的維數(shù)研究進(jìn)展
    僅與邊有關(guān)的Euler不等式的加強(qiáng)
    針對(duì)路面建模的Delaunay三角網(wǎng)格分治算法
    一種實(shí)時(shí)的三角剖分算法
    復(fù)雜地電模型的非結(jié)構(gòu)多重網(wǎng)格剖分算法
    清華山維在地形圖等高線(xiàn)自動(dòng)生成中的應(yīng)用
    一道IMO試題的另解與探究
    孝义市| 台安县| 梁河县| 甘肃省| 南平市| 奈曼旗| 盐源县| 杨浦区| 台江县| 凤城市| 义马市| 石棉县| 舒兰市| 安阳县| 红原县| 寻甸| 杭锦旗| 吴堡县| 黎城县| 霍邱县| 夏津县| 浠水县| 新化县| 永春县| 桂东县| 衡阳县| 周口市| 莆田市| 南岸区| 中方县| 个旧市| 崇州市| 云梦县| 泰州市| 涿鹿县| 和政县| 临湘市| 佳木斯市| 邳州市| 子洲县| 绥宁县|