基于OpenGL生成TI N的程序研究

■閔盛彪 寇攀

（四川省林業(yè)科學(xué)研究院 四川 成都610081）

基于OpenGL生成TI N的程序研究

■閔盛彪 寇攀

（四川省林業(yè)科學(xué)研究院 四川 成都610081）

TIN可以用來實(shí)現(xiàn)復(fù)雜物體表面的逼近以及地形起伏變化的模擬，在三維可視化和地理信息系統(tǒng)中得到了廣泛的應(yīng)用。本文主要介紹了TIN、TIN的生成算法以及離散點(diǎn)凸包的生成，同時(shí)以VC++6.0為平臺(tái)，調(diào)用OpenGL庫(kù)函數(shù)實(shí)現(xiàn)了TIN網(wǎng)的繪制和TIN形成區(qū)域的繪制，最后通過導(dǎo)入不同的實(shí)驗(yàn)數(shù)據(jù)以驗(yàn)證本文所述方法的可行性。

TIN；凸包；VC++6.0；OpenGL；地形模擬

0 引言

在現(xiàn)實(shí)世界里，地球表面呈現(xiàn)出的是一種不規(guī)則連續(xù)變化的曲面，為此我們?cè)趯?duì)地球表面進(jìn)行模擬時(shí)，只能利用一系列的微小曲面，通過逼近的方法來實(shí)現(xiàn)仿真顯示。利用數(shù)字高程模型（DEM）對(duì)地球表面地形做數(shù)字描述和模擬可以很好的解決從現(xiàn)實(shí)物體到計(jì)算機(jī)的模數(shù)轉(zhuǎn)化，因此在測(cè)繪工程，三維可視化，虛擬現(xiàn)實(shí)等領(lǐng)域中得到了廣泛的應(yīng)用。DEM有三種主要的表示模型：規(guī)則格網(wǎng)模型，等高線模型和不規(guī)則三角網(wǎng)。規(guī)則網(wǎng)格模型GRID，只適用于地形平坦的地方，存在大量的數(shù)據(jù)冗余，且在不改變網(wǎng)格大小的情況下很難表達(dá)復(fù)雜多變的地物。而不規(guī)則三角網(wǎng)TIN在減少數(shù)據(jù)冗余的同時(shí)能夠根據(jù)地形起伏變化來改變采樣點(diǎn)的密度和位置，使得表面建模更為方便靈活。利用TIN不但便于空間分析中的計(jì)算，而且還能按地形特征點(diǎn)如山脊，山谷線，地形變化線等來表示數(shù)字高程等特征，與GRID相比，更能表現(xiàn)地形細(xì)節(jié)[1]。

VC是一門功能強(qiáng)大易于理解和掌握的計(jì)算及編程語(yǔ)言，而OpenGL是一個(gè)定義了跨語(yǔ)言、跨平臺(tái)的編程接口的規(guī)格，是一個(gè)專業(yè)的圖形程序接口，其多功能且便于調(diào)用的底層圖形庫(kù)是整個(gè)技術(shù)的主要支撐。本文主要介紹的就是利用三角網(wǎng)生成算法生成TIN并調(diào)用OpenGL庫(kù)函數(shù)在VC6.0環(huán)境下的實(shí)現(xiàn)繪制的過程。

1 TIN生成算法及其特點(diǎn)

1.1 Delaunay三角網(wǎng)法則

一個(gè)任意的三角剖分并非是理想的三角剖分，利用隨機(jī)分布的離散高程采樣點(diǎn)建立連續(xù)覆蓋整個(gè)區(qū)域的TIN的技術(shù)關(guān)鍵就是確定哪三個(gè)點(diǎn)可以構(gòu)成一個(gè)最佳三角形，并使得每個(gè)離散采樣點(diǎn)均為三角形的頂點(diǎn)。通常構(gòu)建的三角網(wǎng)并沒有考慮到地性線（山脊線、山谷線）的框架作用，而一些地區(qū)存在大面積水域等內(nèi)部不需要構(gòu)網(wǎng)的區(qū)域，因此要對(duì)三角網(wǎng)的構(gòu)建進(jìn)行約束。Delaunay三角形具有良好的特性，利用它可以在垂直投影的地面點(diǎn)中根據(jù)實(shí)際情況構(gòu)造最佳三角形，該方法應(yīng)當(dāng)滿足如下的法則：Delaunay三角網(wǎng)為相互鄰接且互不重疊的三角形的集合，每一個(gè)三角形的外接圓內(nèi)不包含其他點(diǎn)。Delaunay三角網(wǎng)由對(duì)應(yīng)Voronoi多邊形的點(diǎn)連接而成。Delaunay三角形有三個(gè)相鄰點(diǎn)連接而成，這三個(gè)相鄰頂點(diǎn)對(duì)應(yīng)的Voronoi多邊形有一個(gè)公共的頂點(diǎn)，此頂點(diǎn)是Delaunay三角形外接圓的圓心。

根據(jù)Delaunay三角網(wǎng)的實(shí)現(xiàn)過程的不同，可以分為逐點(diǎn)插入法、分治算法、凸包算法、三角網(wǎng)生長(zhǎng)算法等。本文主要討論了三角網(wǎng)生長(zhǎng)算法，并用該算法實(shí)現(xiàn)TIN的繪制。

1.2 三角網(wǎng)生長(zhǎng)算法

三角網(wǎng)生長(zhǎng)算法的基本思路是：首先找出離散點(diǎn)集中相距最短的兩點(diǎn)，連線成為TIN的初始基線；然后按D-TIN的判斷方法找出包含此基線的Delaunay三角形的第三個(gè)端點(diǎn)，該端點(diǎn)應(yīng)該位于基線的右側(cè)；連接新點(diǎn)與原來的兩點(diǎn)形成兩條新邊；再按D-TIN的判斷方法找出包含此兩邊的另外兩個(gè)Delaunay三角形的第3端點(diǎn)；依此循環(huán)處理所有的新生成的邊，直到所有的離散點(diǎn)均為D-TIN的端點(diǎn)。例如在離散數(shù)據(jù)中任意選擇一點(diǎn)A作為第一個(gè)三角形的第一個(gè)端點(diǎn)，然后尋找距離其最近的一點(diǎn)B作為第二個(gè)頂點(diǎn)，對(duì)AB附近的點(diǎn)C計(jì)算其余弦值，如果最小則C為第三個(gè)頂點(diǎn)。尋找C點(diǎn)關(guān)于AB異側(cè)的點(diǎn)，在所有的備選點(diǎn)中，按照角度最大原則選擇一點(diǎn)D作為AB邊上新生成三角形的第三個(gè)頂點(diǎn)。同理對(duì)所有的三角形進(jìn)行擴(kuò)展，直到所有的點(diǎn)被添入到不規(guī)則三角網(wǎng)中。

2 離散點(diǎn)的凸包生成

2.1 最小二維凸包

最小凸包計(jì)算在地理信息系統(tǒng)中有著廣泛的應(yīng)用，如進(jìn)行區(qū)域裁剪，獲得數(shù)字地面模型等空間分析模型的有效計(jì)算區(qū)域等。在本次程序設(shè)計(jì)中，生成離散點(diǎn)的凸包主要是為了繪制出TIN的區(qū)域邊界。在給定平面上的一個(gè)點(diǎn)集中找出一個(gè)最小點(diǎn)集順次連結(jié)形成一個(gè)凸多邊形，使得點(diǎn)集中的點(diǎn)皆在此多邊形內(nèi)或此多邊形上，這個(gè)凸多邊形就是給定點(diǎn)集的最小二維凸包。

2.2 卷包裹算法

經(jīng)過長(zhǎng)期的研究，計(jì)算機(jī)科學(xué)家們推出了一系列的凸包生成算法，比較著名的有Graham掃描算法、快速凸包算法以及卷包裹算法等。在此我們探究通過卷包裹算法，來實(shí)現(xiàn)最小二維凸包的尋找。

卷包裹算法是凸包問題的最直觀的一種解法，它是Chand和Kapur于1970年提出的，其基本思想如下：首先過y坐標(biāo)最小的點(diǎn)p1，畫一水平直線AB，顯然該點(diǎn)是凸包的一個(gè)頂點(diǎn)。然后AB繞p1按逆時(shí)針方向旋轉(zhuǎn)，碰到S中的第二個(gè)點(diǎn)p2時(shí)，直線AB改繞p2按逆時(shí)針方向旋轉(zhuǎn)而在p1與p2之間留下一條線段，該線段為凸包的一條邊。繼續(xù)旋轉(zhuǎn)下去，最后直線AB旋轉(zhuǎn)360°回到p1，便得到所要求的凸包。直線AB繞點(diǎn)pi的旋轉(zhuǎn)是通過如下方法實(shí)現(xiàn)的：首先連接pi與非凸頂點(diǎn)pj得到線段pipj，然后求這些線段與AB與pipj的夾角，組成最小夾角的另一端點(diǎn)pi+1即凸包頂點(diǎn)。

3 TIN的程序設(shè)計(jì)及實(shí)現(xiàn)

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

在程序?qū)崿F(xiàn)TIN的繪制過程中，首先要針對(duì)不規(guī)則三角網(wǎng)自身的特點(diǎn)進(jìn)行數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，在此主要的數(shù)據(jù)結(jié)構(gòu)有記錄離散數(shù)據(jù)的點(diǎn)數(shù)據(jù)結(jié)構(gòu)，記錄邊信息的線數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)三角形的三角形數(shù)據(jù)結(jié)構(gòu)，以及在凸包形成過程中所使用到的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)等。

（1）離散點(diǎn)數(shù)據(jù)結(jié)構(gòu)。程序中使用vectorT1數(shù)組，用來記錄離散數(shù)據(jù)的坐標(biāo)信息，通過數(shù)組自身帶有的部分函數(shù)來實(shí)現(xiàn)對(duì)數(shù)據(jù)的操作。

（2）線數(shù)據(jù)結(jié)構(gòu)。主要記錄三角形邊兩端點(diǎn)的坐標(biāo)信息，用數(shù)組vectorT2記錄形成的三角形邊，數(shù)據(jù)結(jié)構(gòu)如下：

struct Line//儲(chǔ)存直線的兩個(gè)端點(diǎn)

（3）三角形數(shù)據(jù)結(jié)構(gòu)。vectorT3存儲(chǔ)了所有生產(chǎn)的三角形的頂點(diǎn)，頂點(diǎn)的高程以及相關(guān)邊的信息，具體的數(shù)據(jù)結(jié)構(gòu)為：

（4）在所有離散點(diǎn)的凸包的形成過程中，根據(jù)算法的要求不但要記錄位于凸包線上點(diǎn)的坐標(biāo)而且還要記錄該點(diǎn)與下點(diǎn)連線與旋轉(zhuǎn)線的夾角，使用數(shù)組vectorpoints對(duì)凸包點(diǎn)做記錄，其數(shù)據(jù)結(jié)構(gòu)如下：

3.2 程序的實(shí)現(xiàn)

3.2.1 數(shù)據(jù)的讀取和顯示

考慮到在實(shí)際中用來構(gòu)成TIN的離散點(diǎn)數(shù)據(jù)量比較大，因此在該程序中數(shù)據(jù)是以*.TXT文件的形式存儲(chǔ)于硬盤上，當(dāng)程序運(yùn)行時(shí)，通過調(diào)用CstdioFile類構(gòu)建的對(duì)象，對(duì)文件進(jìn)行操作，并通過函數(shù)WriteString()逐行將數(shù)據(jù)讀取到內(nèi)存中。在狀態(tài)欄中分別顯示了讀取點(diǎn)的個(gè)數(shù)以及在構(gòu)網(wǎng)之后形成三角形的個(gè)數(shù)，該功能可以通過構(gòu)建CstatusBar類對(duì)象來實(shí)現(xiàn)。

3.2.2 TIN的繪制

根據(jù)算法，TIN的生成可以分為這樣幾步，首先確定基線從右邊開始找點(diǎn)，然后調(diào)用函數(shù)GetThirdPoint(CPoint p1,CPoint p2)找到第三個(gè)點(diǎn)形成三角形，并將其存儲(chǔ)到數(shù)組vectorT3中，其頂點(diǎn)和邊分別存儲(chǔ)到數(shù)組vectorT1和數(shù)組vectorT2中，如此遞歸，直到生成所有的三角形。最后從T3中讀出三角形的頂點(diǎn)坐標(biāo)，調(diào)用OpenGL畫線函數(shù)，繪制出三角網(wǎng)。以下就是繪制TIN的部分代碼：

3.2.3 繪制離散點(diǎn)的凸包

根據(jù)卷包裹算法，在求離散數(shù)據(jù)凸包上點(diǎn)的時(shí)候需要用數(shù)據(jù)結(jié)構(gòu)Node來記錄當(dāng)前點(diǎn)坐標(biāo)以及與下點(diǎn)連線同旋轉(zhuǎn)線之間的夾角。首先找到Y(jié)值最大的一個(gè)凸包極點(diǎn)做基點(diǎn)，然后求出所有點(diǎn)與旋轉(zhuǎn)線之間的夾角，快速排序找出夾角小的那一個(gè)點(diǎn)作為凸包點(diǎn)，最后轉(zhuǎn)到下一個(gè)點(diǎn)，以該點(diǎn)為基點(diǎn)，重復(fù)尋找，直到形成一個(gè)封閉的凸多邊形。部分代碼如下：

3.2.4 程序演示

本實(shí)驗(yàn)中，以一個(gè)存有1000個(gè)離散點(diǎn)的文件為例，先打開文件導(dǎo)入數(shù)據(jù)，點(diǎn)擊按鈕生成TIN，再點(diǎn)擊按鈕繪制出TIN的生成區(qū)域，在文檔視圖的狀態(tài)欄里，可以看到當(dāng)前點(diǎn)的個(gè)數(shù)以及生成三角形的數(shù)量。經(jīng)過驗(yàn)證，發(fā)現(xiàn)生成的TIN網(wǎng)滿足最大最小化原則，符合實(shí)際應(yīng)用的要求，生成結(jié)果可以圖片的形式導(dǎo)出，如下圖所示程序研究效果。

TU195[文獻(xiàn)碼]A

1000-405X（2016）-12-240-3