基于OpenGL和離散點的三維建?？梢暬接?/h1>
2015-02-08 03:40:20楊曦曄
全球定位系統(tǒng) 2015年1期
肖 坤，楊曦曄
（95685部隊，云南昆明650500）
基于OpenGL和離散點的三維建?？梢暬接?/p>
肖 坤，楊曦曄
（95685部隊，云南昆明650500）
OpenGL是當(dāng)今使用最廣泛的三維底層圖形庫。本文以GPS原始三維觀測離散點為數(shù)據(jù)基礎(chǔ)，通過讀取存儲離散點的文本文件，運用生長算法對空間散亂點進(jìn)行Delaunay三角剖分，將離散點群數(shù)據(jù)有效地轉(zhuǎn)化為三維模型數(shù)據(jù)。通過OPenGL技術(shù)實現(xiàn)了其三維可視化效果，實現(xiàn)放大、縮小、漫游、旋轉(zhuǎn)等功能。在此基礎(chǔ)之上疊加該區(qū)域的遙感影像圖像，效果逼真，加之實測數(shù)據(jù)使其精度更加精確。
OpenGL；離散點；生長算法；三維可視化
0 引 言
隨著計算機(jī)科學(xué)技術(shù)的發(fā)展，事物和景觀的三維可視化表現(xiàn)已成為發(fā)展的趨勢。三維建模可視化是模擬人類雙眼處理物體的方式。往往容易獲取物體、景觀和地形等的一些離散點信息，而很難把它們在計算機(jī)中再次重新真實的表現(xiàn)或者模擬重建出來。Delaunay三角網(wǎng)結(jié)構(gòu)良好，數(shù)據(jù)結(jié)構(gòu)簡單，數(shù)據(jù)冗余度小，可以適應(yīng)各種分布密度的數(shù)據(jù)[1］。因此對這些散亂的三維點進(jìn)行三角剖分，用許多的小三角形組成的表面近似物體表面。這樣就相當(dāng)于給散亂的三維點集搭起一個立體的網(wǎng)狀骨架模型。能更加真實的表現(xiàn)物體的結(jié)構(gòu)特征。Delaunay三角剖分采用生長算法，為了使算法的效率更快點，在尋找弧段對應(yīng)的擴(kuò)展最佳點時候，可以提前用弧段和第三點判斷弧段另一側(cè)的點，然后就從這些點中去尋找擴(kuò)展三角形所需要的最佳點。OpenGL是一個跨編程語言、跨平臺的專業(yè)圖形編程接口，是最為廣泛接納的2D/3D圖形API[2］。采用OpenGL技術(shù)進(jìn)行三維的表達(dá)顯示。疊加遙感影像圖片增加其真實感。快速構(gòu)建出真實的三維地形場景模型。本文對于計算機(jī)三維仿真、三維模擬、三維分析、虛擬現(xiàn)實和數(shù)值模擬等具有一定的參考和借鑒意義。
1 三角網(wǎng)生長算法簡介
三角網(wǎng)生長算法的基本流程，如圖1所示。
圖1 生長法構(gòu)建Delaunay三角網(wǎng) （a）形成第一個三角形；（b）擴(kuò)展生成第二個和第三個三角形
1）在所有離散數(shù)據(jù)點中取任意一點1（一般從離散點群幾何中心附近開始），尋找距離此點1最近的點2，相連后作為初始基線1－2；
2）在初始基線右邊運用Delaunay法則搜尋第三點3，形成第一個Delaunay三角形；
3）并以此三角形的兩條新邊（2－3，3－1）作為新的初始基線；
4）重復(fù)步驟2）和3）直至所有離散數(shù)據(jù)點處理完畢為止。
該算法主要的工作是在大量數(shù)據(jù)點中搜尋給定基線符合要求的鄰域點。一種比較簡單的搜索方法是通過計算三角形外接圓的圓心和半徑完成對鄰域點的搜索。使用外接圓的搜索方法限定了基線的待選鄰域點，因而降低了用于搜尋Delaunay三角網(wǎng)的計算時間。
2 改進(jìn)算法
三角剖分必須滿足以下準(zhǔn)則和特性：
1）空圓特性：Delaunay三角網(wǎng)的唯一性，在三角網(wǎng)的任意一個三角的外接圓內(nèi)都不存在其他點。
2）最大化最小角特性：在相鄰的三角形構(gòu)成的凸多邊形的對角線，在交換后，六個內(nèi)角的最小角不再增大（也就是每個三角形的最小內(nèi)角盡可能最大化）[3］。
針對該算法在尋找第三點時運算量較大。這個算法的實現(xiàn)中，為了使生成的三角形彼此間不交叉，而且新生成的三角形中不存在其余的離散點，此時采取的是尋找對應(yīng)弧段的最佳點。在尋找弧段對應(yīng)的擴(kuò)展最佳點時候，可以提前用弧段和第三點判斷弧段另一側(cè)的點，然后就從這些點中去尋找擴(kuò)展三角形所需要的最佳點。
3 離散點的三維可視化系統(tǒng)構(gòu)建
3.1 離散點的讀取
三維離散點存儲成文本文件形式是目前的通用形式，它具有很好的跨平臺性。通過讀取文件file的形式將其讀入此系統(tǒng)中，并利用OpenGL三維圖形包將三維點群繪制。本系統(tǒng)利用GPS在某山區(qū)采集的三維離散點群進(jìn)行實驗。
3.2 散點的三維剖分和基本功能實現(xiàn)
為了實現(xiàn)Delaunay三角剖分和所需要的功能，并且記錄下結(jié)果數(shù)據(jù)，需要定義如下的結(jié)構(gòu)體：
針對該算法的核心程序需要定義如下函數(shù)進(jìn)行實現(xiàn)：
Void Nearpoint（Trianglepoint＊ypoint，Trianglepoint＊all，int n）//尋找距離起始點距離最近點
Void jiline（Trianglepoint p1，Trianglepoint p2，Trianglepoint p3，Trianglepoint＊all，int n，int＊m）
//計算基線方程，判斷符合條件的點
Int findfirst（Trianglepoint p1，Trianglepoint p2，Trianglepoint＊all，int n）
//找到原始三角形的第三點的編號
bool judgeTriangle（Trianglepoint p1，Trianglepoint p2，Trianglepoint p3，Trianglepoint＊all，int n）//判定三角形的合法性
bool judgeTritrue（Triangle＊all，Triangle kuozhan，int m）//判定新生成的三角形的唯一性
運用三角網(wǎng)遞歸生長算法的定義和本文中對算法進(jìn)行的改進(jìn)構(gòu)建Delaunay三角網(wǎng)。對構(gòu)網(wǎng)過程中生成的每個三角形投影面積、周長、三角形出現(xiàn)的順序及凸包的面積數(shù)據(jù)存儲于文本文件txt.如圖2所示，對于生長算法構(gòu)網(wǎng)的過程研究具有詳細(xì)的指導(dǎo)意義。對于構(gòu)建的三維Delaunay三角網(wǎng)如圖3所示。
圖2 存儲數(shù)據(jù)的文本
三維可視化模型已經(jīng)初步建立，通過OpenGL函數(shù)包中定義的平移矩陣、旋轉(zhuǎn)矩陣和縮放矩陣，可以方便的對三維模型進(jìn)行放大、縮小、漫游、旋轉(zhuǎn)等功能的交互式操作。使三維模型更加具有真實感和操作性。將離散點群數(shù)據(jù)有效的轉(zhuǎn)化為三維模型數(shù)據(jù)。
圖3 三維Delaunay三角網(wǎng) （a）三角網(wǎng)俯視圖；（b）三角網(wǎng)側(cè)視圖
圖4 效果圖
4 三維地形可視化系統(tǒng)構(gòu)建
三維場景基礎(chǔ)就是地形數(shù)據(jù)，它是建筑物、小品的載體，可以表達(dá)地物特征與地貌特征。通過上述算法已經(jīng)建立基本的地形模型，再在表面疊加遙感影像數(shù)據(jù)，使其真實感大大增強(qiáng)。既保證了地形數(shù)據(jù)在細(xì)節(jié)上的精確性，又保證了效果上的真實感。圖4為效果圖。
5 結(jié)束語
追求虛擬現(xiàn)實是未來計算機(jī)發(fā)展的必然趨勢，三維重建首當(dāng)其沖[4］。本文以最為常見的三維離散點群為數(shù)據(jù)基礎(chǔ)，利用Delaunay三角網(wǎng)的結(jié)構(gòu)良好、數(shù)據(jù)冗余度小、適應(yīng)各種分布密度的數(shù)據(jù)等一系列優(yōu)點[5］。采用目前最為流行的三維重建工具OPenGL對構(gòu)建的三維模型進(jìn)行繪制。開發(fā)出一套三維地形場景的快速和精確構(gòu)建系統(tǒng)，并及時記錄點計算和三角網(wǎng)構(gòu)建過程中的數(shù)據(jù)，對于地形離散點的三維可視化研究具有一定的指導(dǎo)和參考意義。對于離散點群的三維仿真、三維模擬、三維分析、虛擬現(xiàn)實和數(shù)值模擬等具有一定的參考價值。
[1]童 慶，張敬誼，陳 誠，等.高分辨率圖像特征提取和VG重構(gòu)技術(shù)研究[J］.計算機(jī)應(yīng)用與軟件，2013，30（7）：116－118.
[2]李東陽.基于虛擬現(xiàn)實技術(shù)的虛擬農(nóng)場的研究和實現(xiàn)[J］.微計算機(jī)信息，2012（10）：7.
[3]劉學(xué)軍，龔健雅.約束數(shù)據(jù)域的Delaunay三角剖分與修改算法[J］.測繪學(xué)報，2001，30（1）：82－88.
[4]李國超，劉 爽，張延超，等.VC環(huán)境下基于OpenGL與3DS的三維場景重建[J］.電腦知識與技術(shù)，2010，6（35）：10131－10133
[5]代 莉，陳春華，聶 焱.在AutoCAD環(huán)境下不規(guī)則三角網(wǎng)構(gòu)建及等高線生成[J］.地理空間信息，2011，9（2）：40－42.
Discussion on 3D Visualization Modeling Based on OPenGL and Discrete Points
XIAO Kun，YANG Xiye
（Unit 95685，Kunming650500，China）
OpenGL is one of the most widely used 3Dgraphic library of low－level.In this paper，three dimensional discrete points is the data base，by reading the stored discrete points of the text file，use the growth algorithm for scattered points by Delaunay triangulation.The triangulation of each triangle generated projection area，perimeter and the sequence of records.And the calculation of the discrete points in the future process of triangulation complete convex hullarea and number of boundary points，Through the 3Dvisualization of OPenGL technology to achieve the effect，to realize the function such as amplification，narrow，roaming and rotation.And images in the area of remote sensing image，the effect is clear，and the measured data to make it more accurate precision.
OpenGL；discrete points；growth algorithm；3Dvisualization
TP319
A
1008－9268（2015）01－0094－04
10.13442/j.gnss.1008－9268.2015.01.022
肖 坤（1987－），男，碩士，助理工程師，主要從事GIS三維可視化研究。
楊曦曄（1986－），男，助理工程師，主要從事GIS三維可視化工作或研究。
2014－11－10
金川公司－蘭州交通大學(xué)預(yù)研基金（編號：JCYY2013015）
聯(lián)系人：肖坤E－mail：xk5035＠163.com
猜你喜歡
一種航天測控冗余跟蹤弧段處理方法上海航天(2024年1期)2024-03-08 02:52:28 基于改進(jìn)弧段切點弦的多橢圓檢測電子設(shè)計工程(2022年24期)2022-12-23 12:03:28 面向工業(yè)復(fù)雜場景的合作靶標(biāo)橢圓特征快速魯棒檢測光學(xué)精密工程(2021年8期)2021-10-04 11:46:28 基于重心剖分的間斷有限體積元方法南京大學(xué)學(xué)報(數(shù)學(xué)半年刊)(2020年1期)2020-03-19 02:24:48 二元樣條函數(shù)空間的維數(shù)研究進(jìn)展赤峰學(xué)院學(xué)報·自然科學(xué)版(2018年9期)2018-10-18 07:15:52 針對路面建模的Delaunay三角網(wǎng)格分治算法智能計算機(jī)與應(yīng)用(2017年2期)2017-05-04 00:45:34 一種實時的三角剖分算法池州學(xué)院學(xué)報(2015年3期)2016-01-05 01:13:07 復(fù)雜地電模型的非結(jié)構(gòu)多重網(wǎng)格剖分算法地震地質(zhì)(2015年3期)2015-12-25 03:29:42 淺談如何將多段線中的弧線段折線化四川建筑(2015年4期)2015-06-24 14:08:40 清華山維在地形圖等高線自動生成中的應(yīng)用長江工程職業(yè)技術(shù)學(xué)院學(xué)報(2014年4期)2014-11-30 02:41:40
肖 坤，楊曦曄
（95685部隊，云南昆明650500）
基于OpenGL和離散點的三維建?？梢暬接?/p>
肖 坤，楊曦曄
（95685部隊，云南昆明650500）
OpenGL是當(dāng)今使用最廣泛的三維底層圖形庫。本文以GPS原始三維觀測離散點為數(shù)據(jù)基礎(chǔ)，通過讀取存儲離散點的文本文件，運用生長算法對空間散亂點進(jìn)行Delaunay三角剖分，將離散點群數(shù)據(jù)有效地轉(zhuǎn)化為三維模型數(shù)據(jù)。通過OPenGL技術(shù)實現(xiàn)了其三維可視化效果，實現(xiàn)放大、縮小、漫游、旋轉(zhuǎn)等功能。在此基礎(chǔ)之上疊加該區(qū)域的遙感影像圖像，效果逼真，加之實測數(shù)據(jù)使其精度更加精確。
OpenGL；離散點；生長算法；三維可視化
0 引 言
隨著計算機(jī)科學(xué)技術(shù)的發(fā)展，事物和景觀的三維可視化表現(xiàn)已成為發(fā)展的趨勢。三維建模可視化是模擬人類雙眼處理物體的方式。往往容易獲取物體、景觀和地形等的一些離散點信息，而很難把它們在計算機(jī)中再次重新真實的表現(xiàn)或者模擬重建出來。Delaunay三角網(wǎng)結(jié)構(gòu)良好，數(shù)據(jù)結(jié)構(gòu)簡單，數(shù)據(jù)冗余度小，可以適應(yīng)各種分布密度的數(shù)據(jù)[1］。因此對這些散亂的三維點進(jìn)行三角剖分，用許多的小三角形組成的表面近似物體表面。這樣就相當(dāng)于給散亂的三維點集搭起一個立體的網(wǎng)狀骨架模型。能更加真實的表現(xiàn)物體的結(jié)構(gòu)特征。Delaunay三角剖分采用生長算法，為了使算法的效率更快點，在尋找弧段對應(yīng)的擴(kuò)展最佳點時候，可以提前用弧段和第三點判斷弧段另一側(cè)的點，然后就從這些點中去尋找擴(kuò)展三角形所需要的最佳點。OpenGL是一個跨編程語言、跨平臺的專業(yè)圖形編程接口，是最為廣泛接納的2D/3D圖形API[2］。采用OpenGL技術(shù)進(jìn)行三維的表達(dá)顯示。疊加遙感影像圖片增加其真實感。快速構(gòu)建出真實的三維地形場景模型。本文對于計算機(jī)三維仿真、三維模擬、三維分析、虛擬現(xiàn)實和數(shù)值模擬等具有一定的參考和借鑒意義。
1 三角網(wǎng)生長算法簡介
三角網(wǎng)生長算法的基本流程，如圖1所示。
圖1 生長法構(gòu)建Delaunay三角網(wǎng) （a）形成第一個三角形；（b）擴(kuò)展生成第二個和第三個三角形
1）在所有離散數(shù)據(jù)點中取任意一點1（一般從離散點群幾何中心附近開始），尋找距離此點1最近的點2，相連后作為初始基線1－2；
2）在初始基線右邊運用Delaunay法則搜尋第三點3，形成第一個Delaunay三角形；
3）并以此三角形的兩條新邊（2－3，3－1）作為新的初始基線；
4）重復(fù)步驟2）和3）直至所有離散數(shù)據(jù)點處理完畢為止。
該算法主要的工作是在大量數(shù)據(jù)點中搜尋給定基線符合要求的鄰域點。一種比較簡單的搜索方法是通過計算三角形外接圓的圓心和半徑完成對鄰域點的搜索。使用外接圓的搜索方法限定了基線的待選鄰域點，因而降低了用于搜尋Delaunay三角網(wǎng)的計算時間。
2 改進(jìn)算法
三角剖分必須滿足以下準(zhǔn)則和特性：
1）空圓特性：Delaunay三角網(wǎng)的唯一性，在三角網(wǎng)的任意一個三角的外接圓內(nèi)都不存在其他點。
2）最大化最小角特性：在相鄰的三角形構(gòu)成的凸多邊形的對角線，在交換后，六個內(nèi)角的最小角不再增大（也就是每個三角形的最小內(nèi)角盡可能最大化）[3］。
針對該算法在尋找第三點時運算量較大。這個算法的實現(xiàn)中，為了使生成的三角形彼此間不交叉，而且新生成的三角形中不存在其余的離散點，此時采取的是尋找對應(yīng)弧段的最佳點。在尋找弧段對應(yīng)的擴(kuò)展最佳點時候，可以提前用弧段和第三點判斷弧段另一側(cè)的點，然后就從這些點中去尋找擴(kuò)展三角形所需要的最佳點。
3 離散點的三維可視化系統(tǒng)構(gòu)建
3.1 離散點的讀取
三維離散點存儲成文本文件形式是目前的通用形式，它具有很好的跨平臺性。通過讀取文件file的形式將其讀入此系統(tǒng)中，并利用OpenGL三維圖形包將三維點群繪制。本系統(tǒng)利用GPS在某山區(qū)采集的三維離散點群進(jìn)行實驗。
3.2 散點的三維剖分和基本功能實現(xiàn)
為了實現(xiàn)Delaunay三角剖分和所需要的功能，并且記錄下結(jié)果數(shù)據(jù)，需要定義如下的結(jié)構(gòu)體：
針對該算法的核心程序需要定義如下函數(shù)進(jìn)行實現(xiàn)：
Void Nearpoint（Trianglepoint＊ypoint，Trianglepoint＊all，int n）//尋找距離起始點距離最近點
Void jiline（Trianglepoint p1，Trianglepoint p2，Trianglepoint p3，Trianglepoint＊all，int n，int＊m）
//計算基線方程，判斷符合條件的點
Int findfirst（Trianglepoint p1，Trianglepoint p2，Trianglepoint＊all，int n）
//找到原始三角形的第三點的編號
bool judgeTriangle（Trianglepoint p1，Trianglepoint p2，Trianglepoint p3，Trianglepoint＊all，int n）//判定三角形的合法性
bool judgeTritrue（Triangle＊all，Triangle kuozhan，int m）//判定新生成的三角形的唯一性
運用三角網(wǎng)遞歸生長算法的定義和本文中對算法進(jìn)行的改進(jìn)構(gòu)建Delaunay三角網(wǎng)。對構(gòu)網(wǎng)過程中生成的每個三角形投影面積、周長、三角形出現(xiàn)的順序及凸包的面積數(shù)據(jù)存儲于文本文件txt.如圖2所示，對于生長算法構(gòu)網(wǎng)的過程研究具有詳細(xì)的指導(dǎo)意義。對于構(gòu)建的三維Delaunay三角網(wǎng)如圖3所示。
圖2 存儲數(shù)據(jù)的文本
三維可視化模型已經(jīng)初步建立，通過OpenGL函數(shù)包中定義的平移矩陣、旋轉(zhuǎn)矩陣和縮放矩陣，可以方便的對三維模型進(jìn)行放大、縮小、漫游、旋轉(zhuǎn)等功能的交互式操作。使三維模型更加具有真實感和操作性。將離散點群數(shù)據(jù)有效的轉(zhuǎn)化為三維模型數(shù)據(jù)。
圖3 三維Delaunay三角網(wǎng) （a）三角網(wǎng)俯視圖；（b）三角網(wǎng)側(cè)視圖
圖4 效果圖
4 三維地形可視化系統(tǒng)構(gòu)建
三維場景基礎(chǔ)就是地形數(shù)據(jù)，它是建筑物、小品的載體，可以表達(dá)地物特征與地貌特征。通過上述算法已經(jīng)建立基本的地形模型，再在表面疊加遙感影像數(shù)據(jù)，使其真實感大大增強(qiáng)。既保證了地形數(shù)據(jù)在細(xì)節(jié)上的精確性，又保證了效果上的真實感。圖4為效果圖。
5 結(jié)束語
追求虛擬現(xiàn)實是未來計算機(jī)發(fā)展的必然趨勢，三維重建首當(dāng)其沖[4］。本文以最為常見的三維離散點群為數(shù)據(jù)基礎(chǔ)，利用Delaunay三角網(wǎng)的結(jié)構(gòu)良好、數(shù)據(jù)冗余度小、適應(yīng)各種分布密度的數(shù)據(jù)等一系列優(yōu)點[5］。采用目前最為流行的三維重建工具OPenGL對構(gòu)建的三維模型進(jìn)行繪制。開發(fā)出一套三維地形場景的快速和精確構(gòu)建系統(tǒng)，并及時記錄點計算和三角網(wǎng)構(gòu)建過程中的數(shù)據(jù)，對于地形離散點的三維可視化研究具有一定的指導(dǎo)和參考意義。對于離散點群的三維仿真、三維模擬、三維分析、虛擬現(xiàn)實和數(shù)值模擬等具有一定的參考價值。
[1]童 慶，張敬誼，陳 誠，等.高分辨率圖像特征提取和VG重構(gòu)技術(shù)研究[J］.計算機(jī)應(yīng)用與軟件，2013，30（7）：116－118.
[2]李東陽.基于虛擬現(xiàn)實技術(shù)的虛擬農(nóng)場的研究和實現(xiàn)[J］.微計算機(jī)信息，2012（10）：7.
[3]劉學(xué)軍，龔健雅.約束數(shù)據(jù)域的Delaunay三角剖分與修改算法[J］.測繪學(xué)報，2001，30（1）：82－88.
[4]李國超，劉 爽，張延超，等.VC環(huán)境下基于OpenGL與3DS的三維場景重建[J］.電腦知識與技術(shù)，2010，6（35）：10131－10133
[5]代 莉，陳春華，聶 焱.在AutoCAD環(huán)境下不規(guī)則三角網(wǎng)構(gòu)建及等高線生成[J］.地理空間信息，2011，9（2）：40－42.
Discussion on 3D Visualization Modeling Based on OPenGL and Discrete Points
XIAO Kun，YANG Xiye
（Unit 95685，Kunming650500，China）
OpenGL is one of the most widely used 3Dgraphic library of low－level.In this paper，three dimensional discrete points is the data base，by reading the stored discrete points of the text file，use the growth algorithm for scattered points by Delaunay triangulation.The triangulation of each triangle generated projection area，perimeter and the sequence of records.And the calculation of the discrete points in the future process of triangulation complete convex hullarea and number of boundary points，Through the 3Dvisualization of OPenGL technology to achieve the effect，to realize the function such as amplification，narrow，roaming and rotation.And images in the area of remote sensing image，the effect is clear，and the measured data to make it more accurate precision.
OpenGL；discrete points；growth algorithm；3Dvisualization
TP319
A
1008－9268（2015）01－0094－04
10.13442/j.gnss.1008－9268.2015.01.022
肖 坤（1987－），男，碩士，助理工程師，主要從事GIS三維可視化研究。
楊曦曄（1986－），男，助理工程師，主要從事GIS三維可視化工作或研究。
2014－11－10
金川公司－蘭州交通大學(xué)預(yù)研基金（編號：JCYY2013015）
聯(lián)系人：肖坤E－mail：xk5035＠163.com
猜你喜歡
上海航天(2024年1期)2024-03-08 02:52:28
電子設(shè)計工程(2022年24期)2022-12-23 12:03:28
光學(xué)精密工程(2021年8期)2021-10-04 11:46:28
南京大學(xué)學(xué)報(數(shù)學(xué)半年刊)(2020年1期)2020-03-19 02:24:48
赤峰學(xué)院學(xué)報·自然科學(xué)版(2018年9期)2018-10-18 07:15:52
智能計算機(jī)與應(yīng)用(2017年2期)2017-05-04 00:45:34
池州學(xué)院學(xué)報(2015年3期)2016-01-05 01:13:07
地震地質(zhì)(2015年3期)2015-12-25 03:29:42
四川建筑(2015年4期)2015-06-24 14:08:40
長江工程職業(yè)技術(shù)學(xué)院學(xué)報(2014年4期)2014-11-30 02:41:40
