肖 坤，楊曦曄

（95685部隊，云南昆明650500）

基于OpenGL和離散點的三維建?？梢暬接?/p>

肖 坤，楊曦曄

（95685部隊，云南昆明650500）

OpenGL是當今使用最廣泛的三維底層圖形庫。本文以GPS原始三維觀測離散點為數(shù)據基礎，通過讀取存儲離散點的文本文件，運用生長算法對空間散亂點進行Delaunay三角剖分，將離散點群數(shù)據有效地轉化為三維模型數(shù)據。通過OPenGL技術實現(xiàn)了其三維可視化效果，實現(xiàn)放大、縮小、漫游、旋轉等功能。在此基礎之上疊加該區(qū)域的遙感影像圖像，效果逼真，加之實測數(shù)據使其精度更加精確。

OpenGL；離散點；生長算法；三維可視化

0 引 言

隨著計算機科學技術的發(fā)展，事物和景觀的三維可視化表現(xiàn)已成為發(fā)展的趨勢。三維建?？梢暬悄M人類雙眼處理物體的方式。往往容易獲取物體、景觀和地形等的一些離散點信息，而很難把它們在計算機中再次重新真實的表現(xiàn)或者模擬重建出來。Delaunay三角網結構良好，數(shù)據結構簡單，數(shù)據冗余度小，可以適應各種分布密度的數(shù)據[1］。因此對這些散亂的三維點進行三角剖分，用許多的小三角形組成的表面近似物體表面。這樣就相當于給散亂的三維點集搭起一個立體的網狀骨架模型。能更加真實的表現(xiàn)物體的結構特征。Delaunay三角剖分采用生長算法，為了使算法的效率更快點，在尋找弧段對應的擴展最佳點時候，可以提前用弧段和第三點判斷弧段另一側的點，然后就從這些點中去尋找擴展三角形所需要的最佳點。OpenGL是一個跨編程語言、跨平臺的專業(yè)圖形編程接口，是最為廣泛接納的2D/3D圖形API[2］。采用OpenGL技術進行三維的表達顯示。疊加遙感影像圖片增加其真實感?？焖贅嫿ǔ稣鎸嵉娜S地形場景模型。本文對于計算機三維仿真、三維模擬、三維分析、虛擬現(xiàn)實和數(shù)值模擬等具有一定的參考和借鑒意義。

1 三角網生長算法簡介

三角網生長算法的基本流程，如圖1所示。

圖1 生長法構建Delaunay三角網 （a）形成第一個三角形；（b）擴展生成第二個和第三個三角形

1）在所有離散數(shù)據點中取任意一點1（一般從離散點群幾何中心附近開始），尋找距離此點1最近的點2，相連后作為初始基線1－2；

2）在初始基線右邊運用Delaunay法則搜尋第三點3，形成第一個Delaunay三角形；

3）并以此三角形的兩條新邊（2－3，3－1）作為新的初始基線；

4）重復步驟2）和3）直至所有離散數(shù)據點處理完畢為止。

該算法主要的工作是在大量數(shù)據點中搜尋給定基線符合要求的鄰域點。一種比較簡單的搜索方法是通過計算三角形外接圓的圓心和半徑完成對鄰域點的搜索。使用外接圓的搜索方法限定了基線的待選鄰域點，因而降低了用于搜尋Delaunay三角網的計算時間。

2 改進算法

三角剖分必須滿足以下準則和特性：

1）空圓特性：Delaunay三角網的唯一性，在三角網的任意一個三角的外接圓內都不存在其他點。

2）最大化最小角特性：在相鄰的三角形構成的凸多邊形的對角線，在交換后，六個內角的最小角不再增大（也就是每個三角形的最小內角盡可能最大化）[3］。

針對該算法在尋找第三點時運算量較大。這個算法的實現(xiàn)中，為了使生成的三角形彼此間不交叉，而且新生成的三角形中不存在其余的離散點，此時采取的是尋找對應弧段的最佳點。在尋找弧段對應的擴展最佳點時候，可以提前用弧段和第三點判斷弧段另一側的點，然后就從這些點中去尋找擴展三角形所需要的最佳點。

3 離散點的三維可視化系統(tǒng)構建

3.1 離散點的讀取

三維離散點存儲成文本文件形式是目前的通用形式，它具有很好的跨平臺性。通過讀取文件file的形式將其讀入此系統(tǒng)中，并利用OpenGL三維圖形包將三維點群繪制。本系統(tǒng)利用GPS在某山區(qū)采集的三維離散點群進行實驗。

3.2 散點的三維剖分和基本功能實現(xiàn)

為了實現(xiàn)Delaunay三角剖分和所需要的功能，并且記錄下結果數(shù)據，需要定義如下的結構體：

針對該算法的核心程序需要定義如下函數(shù)進行實現(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）//判定新生成的三角形的唯一性

運用三角網遞歸生長算法的定義和本文中對算法進行的改進構建Delaunay三角網。對構網過程中生成的每個三角形投影面積、周長、三角形出現(xiàn)的順序及凸包的面積數(shù)據存儲于文本文件txt.如圖2所示，對于生長算法構網的過程研究具有詳細的指導意義。對于構建的三維Delaunay三角網如圖3所示。

圖2 存儲數(shù)據的文本

三維可視化模型已經初步建立，通過OpenGL函數(shù)包中定義的平移矩陣、旋轉矩陣和縮放矩陣，可以方便的對三維模型進行放大、縮小、漫游、旋轉等功能的交互式操作。使三維模型更加具有真實感和操作性。將離散點群數(shù)據有效的轉化為三維模型數(shù)據。

圖3 三維Delaunay三角網 （a）三角網俯視圖；（b）三角網側視圖

圖4 效果圖

4 三維地形可視化系統(tǒng)構建

三維場景基礎就是地形數(shù)據，它是建筑物、小品的載體，可以表達地物特征與地貌特征。通過上述算法已經建立基本的地形模型，再在表面疊加遙感影像數(shù)據，使其真實感大大增強。既保證了地形數(shù)據在細節(jié)上的精確性，又保證了效果上的真實感。圖4為效果圖。

5 結束語

追求虛擬現(xiàn)實是未來計算機發(fā)展的必然趨勢，三維重建首當其沖[4］。本文以最為常見的三維離散點群為數(shù)據基礎，利用Delaunay三角網的結構良好、數(shù)據冗余度小、適應各種分布密度的數(shù)據等一系列優(yōu)點[5］。采用目前最為流行的三維重建工具OPenGL對構建的三維模型進行繪制。開發(fā)出一套三維地形場景的快速和精確構建系統(tǒng)，并及時記錄點計算和三角網構建過程中的數(shù)據，對于地形離散點的三維可視化研究具有一定的指導和參考意義。對于離散點群的三維仿真、三維模擬、三維分析、虛擬現(xiàn)實和數(shù)值模擬等具有一定的參考價值。

[1]童 慶，張敬誼，陳 誠，等.高分辨率圖像特征提取和VG重構技術研究[J］.計算機應用與軟件，2013，30（7）：116－118.

[2]李東陽.基于虛擬現(xiàn)實技術的虛擬農場的研究和實現(xiàn)[J］.微計算機信息，2012（10）：7.

[3]劉學軍，龔健雅.約束數(shù)據域的Delaunay三角剖分與修改算法[J］.測繪學報，2001，30（1）：82－88.

[4]李國超，劉 爽，張延超，等.VC環(huán)境下基于OpenGL與3DS的三維場景重建[J］.電腦知識與技術，2010，6（35）：10131－10133

[5]代 莉，陳春華，聶 焱.在AutoCAD環(huán)境下不規(guī)則三角網構建及等高線生成[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

金川公司－蘭州交通大學預研基金（編號：JCYY2013015）

聯(lián)系人：肖坤E－mail：xk5035＠163.com