陳曉青,任鳳玉,張國建

(1.遼寧科技大學(xué)，遼寧 鞍山 114044；2.東北大學(xué)，遼寧 沈陽 110004)

1 問題提出

虛擬現(xiàn)實技術(shù)是計算機圖形學(xué)領(lǐng)域中發(fā)展起來的一種模擬人在自然環(huán)境中視、聽、動等行為的人機交互技術(shù)，在實時仿真領(lǐng)域具有重要的應(yīng)用。礦山虛擬現(xiàn)實技術(shù)涉及大規(guī)模復(fù)雜虛擬地表模型的動態(tài)生成，現(xiàn)代高精度的掃描測繪手段為復(fù)雜物體基于多邊形網(wǎng)格表示的三維幾何建模提供了新的高效手段,但由于采樣精度高，由此建立起的三維模型的復(fù)雜程度遠遠超過了當(dāng)前計算機圖形工作站的實時處理能力。

如何降低這些模型的復(fù)雜度，減少圖形系統(tǒng)需處理的多邊形數(shù)目，實現(xiàn)復(fù)雜虛擬環(huán)境的實時快速生成成為研究的關(guān)鍵。

本文通過數(shù)據(jù)簡化、分塊處理、閉合多邊形提取和閉合多邊形快速建立三角網(wǎng)等幾個步驟完成礦山大規(guī)模復(fù)雜虛擬地表模型的動態(tài)生成。

2 數(shù)據(jù)的簡化

地表模型主要采用高程數(shù)據(jù)通過規(guī)則格網(wǎng)模型或不規(guī)則三角網(wǎng)模型兩種方式來表現(xiàn)。

規(guī)則格網(wǎng)將區(qū)域空間切分為規(guī)則的格網(wǎng)單元，每個格網(wǎng)單元對應(yīng)一個高程值。數(shù)學(xué)上可以表示為一個矩陣，在計算機實現(xiàn)中則是一個二維數(shù)組。算法比較簡單，其顯示速度取決于網(wǎng)格分辨率，降低分辨率可相應(yīng)加快速度，但規(guī)則格網(wǎng)本身對地貌的特征描述就比較弱，分辨率降低程度受到一定限制。在全分辨率下，對大規(guī)模數(shù)字地表模型可見網(wǎng)格直接繪制難達到實時的要求。

不規(guī)則三角網(wǎng)模型根據(jù)區(qū)域有限個點集將區(qū)域劃分為相連的大小各異、疏密不同的三角網(wǎng)，能用更少的空間和時間更精確地表示復(fù)雜的表面。特別當(dāng)?shù)匦伟罅刻卣?如斷裂線、構(gòu)造線)時，能更好地顧及這些特征，從而可以更精確合理地表達地表形態(tài)。由于其描述教率高，長期以來受到人們的普遍關(guān)注，但由于三角化過程本身的復(fù)雜性以及非規(guī)則網(wǎng)格拓撲關(guān)系的繁雜性，使得各種基于非規(guī)則網(wǎng)格模型的自動生成算法難以達到實時。

礦山圖紙主要采用等高線來描述高程，利用等高線矢量數(shù)據(jù)生成地表模型比較直接。

在地形數(shù)據(jù)量十分龐大時，數(shù)據(jù)量和要求的精度一直是一對不可調(diào)和的矛盾。在實際應(yīng)用中，特別是在普通PC機實驗環(huán)境下，為了達到更流暢的實時顯示目的，必須以犧牲地表顯示的精度為代價。

模型必須在不失真的情況下，先經(jīng)過一定簡化才能滿足要求。網(wǎng)格簡化算法的實質(zhì)就是減少模型的點和面，但又要逼近原始網(wǎng)格。

本文采用基于距離和拐點旋轉(zhuǎn)角閾值相結(jié)合的簡化方法，生成具有一定真實性的簡化地表模型，對原始等高線點刪除操作的原則為：①累計距離大于某一給定閾值，中間點刪除；②遇到拐點時，如果拐點處夾角大于某一給定閾值，該拐點保留。

3 分塊處理

地表模型數(shù)據(jù)往往由上萬甚至上百萬個數(shù)據(jù)組成，如果僅憑前一節(jié)描述的簡化算法，在正常條件下還是很難實現(xiàn)地表模型的實時生成的。

為此，根據(jù)礦山開采的特點，首先將模型數(shù)據(jù)劃分成塊，分別處理。

當(dāng)?shù)叵麻_采時，由于地形長期不變化，模型可以預(yù)先處理，由于非規(guī)則網(wǎng)格模型數(shù)據(jù)量少，一般采用非規(guī)則網(wǎng)格模型，當(dāng)然也可采用規(guī)則網(wǎng)格模型全網(wǎng)格直接繪制。

當(dāng)采用露天開采時，隨著露天礦的生產(chǎn)，地形可能隨時發(fā)生變化。但由于露天境界外部分基本上是長期不變化的，這樣可以將露天礦山地表分成境界線以外和境界線以內(nèi)兩部分分別處理。露天境界以外部分可以預(yù)處理，只對境界線以內(nèi)部分進行實時構(gòu)網(wǎng)，這樣大大減少了實時處理的數(shù)據(jù)量。由于露天礦地表采用分塊處理，就不能采用規(guī)則網(wǎng)格模型，只能采用非規(guī)則網(wǎng)格模型。

境界內(nèi)部分又可分為采坑以內(nèi)和采坑以外兩部分，由于采坑以內(nèi)部分地表已經(jīng)揭露，等高線需要刪除，采場內(nèi)部結(jié)構(gòu)采用特殊的臺階構(gòu)網(wǎng)法單獨處理，本文不討論；采坑以外部分是在境界內(nèi)部分去除采坑后留下的部分，模型的實時處理實質(zhì)上只是對這部分進行處理，如圖1所示。

圖1 區(qū)域分塊

4 構(gòu)建三角網(wǎng)

在簡化和分塊的基礎(chǔ)上，對需要三角化的部分實行三角網(wǎng)的構(gòu)建。

要實現(xiàn)地表模型的實時顯示，就應(yīng)設(shè)計好整個地表網(wǎng)格模型的點、線、面關(guān)系，避免復(fù)雜的三角化過程。三角化算法是影響實時顯示效率的關(guān)鍵。

目前在不規(guī)則三角網(wǎng)的各種算法中，大多數(shù)是通過三角形的邊來擴展新的三角形或在三角形內(nèi)插入新的點形成三角形，這需要根據(jù)很多點或三角形進行判斷，從而大大影響了構(gòu)網(wǎng)速度，不適合礦山大數(shù)據(jù)量的三角網(wǎng)實時生成。所有這些算法中，Delaunay三角網(wǎng)算法比較有代表，應(yīng)用也廣泛，其算法主要有區(qū)域生長法、逐點插入法和分治法三類，這三類方法各有特點。區(qū)域生長法思路簡單，易于編程，但在搜索“第三點”每次尋找最優(yōu)點時需要遍歷整個點集并比較，往往需要耗費大量的時間；逐點插入法是采用點插入的方式，實現(xiàn)較簡單，占用內(nèi)存較小，但在插入的過程中需要對邊界點和邊界邊進行判斷，在時間復(fù)雜度上太大，不適合實時生成；分治法綜合其它算法，采用遞歸分割區(qū)域進行處理，比較高效，但在合并網(wǎng)的過程中，空間復(fù)雜度太大。

本文運用分治法的原理，提出將區(qū)域劃分為閉合多邊形，再對閉合多邊形進行三角化，較好地解決了傳統(tǒng)算法在構(gòu)建大數(shù)據(jù)量不規(guī)則三角網(wǎng)時的不足，提高構(gòu)網(wǎng)速度。

4.1 區(qū)域分區(qū)

如圖2所示，要對該地表區(qū)域進行三角化。由圖可以看出，整個區(qū)域是由等高線與邊框線構(gòu)成的閉合多邊形區(qū)域組成的，只要能提取這些閉合多邊形，直接對各閉合多邊形進行三角化即可，這樣可以大大降低算法的復(fù)雜度，提高三角化速度。

在提取閉合多邊形的過程中，經(jīng)常會出現(xiàn)環(huán)形區(qū)域，也稱為空洞，如圖3所示的陰影部分，這給閉合多邊形描述增加困難。

為了消除空洞，只需在等高線某點處作豎線或橫線，把空洞割成兩份即可。這種處理同時也把整個區(qū)域劃分為若干條區(qū)，對每個區(qū)實行分治處理，可以大大減少每次三角化時頂點的分析比較次數(shù)。

圖2 待處理的區(qū)域地形 圖3 空洞現(xiàn)象

增加分割線，同時也增加了頂點數(shù)，因此，應(yīng)該盡量減少分割線數(shù)。具體做法是：先計算區(qū)域長軸方向，確定采用豎線或橫線進行分割。把每條等高線標(biāo)記“未處理”，對每條“未處理”的等高線在其起點處作分割線，再把該分割線穿過的等高線標(biāo)記“處理過”，這樣逐條等高線進行處理，直到每條都處理過。如圖4所示，采用了兩條豎線分割，將區(qū)域分為三個區(qū)。

圖4 分區(qū)

4.2 閉合多邊形的提取

本文采用多叉樹的方法提取閉合多邊形。首先計算等高線與邊框的交點，圖5(a)中1～12數(shù)字為交點，以這些交點為節(jié)點，構(gòu)造多叉樹。從根節(jié)點出發(fā)，通過樹的遍歷，逐個節(jié)點進行比較，遇到同一個交點，即構(gòu)成一個閉合圈，如圖5(b)中虛線構(gòu)成閉合多邊形。

4.3 閉合多邊形三角網(wǎng)的構(gòu)建

通過以上閉合多邊形的提取，我們可以對閉合多邊形進行三角化，算法如圖6所示。

取多邊形長軸方向(以X方向為例)的中值作豎線，如圖6中第1次的豎線交多邊形于1～4點。為了不增加額外的頂點，直接在多邊形上找離交點最近頂點代替1～4交點作為分割點，這種做法同時也保證了三角形間的無縫拼接問題。通過分割點兩兩的連線在多邊形的內(nèi)外來判斷兩兩是否作為分割線。如圖6中線段23在多邊形外，不可作為分割線，而線段12和34在多邊形內(nèi)，可以作為分割線，將多邊形分割為三部分。

采用遞歸法，分別對分割出的各多邊形再進行分治，直到該多邊形頂點數(shù)為3時，直接構(gòu)成三角形，終止遞歸。這樣完成整個多邊形的三角化。

圖5 多叉樹提取閉合多邊形

圖6 中值遞歸分治法實現(xiàn)閉合多邊形三角化

5 實例

通過以上方法的處理，建立起三角網(wǎng)，在OpenGL支持下，經(jīng)過模型生成與變換、視點變換、投影變換、紋理生成就可以生成真實感地形。圖7為一虛擬礦山地表模型的實例。

圖7 一個虛擬礦山實時場景

6 結(jié)論

針對礦山開采的特點，本文算法在保證地形正確性的同時，提升了運算速度，能夠?qū)Υ笠?guī)模地表模型進行有效的實時重構(gòu)。本文的建模結(jié)果已成功地應(yīng)用到礦山虛擬現(xiàn)實技術(shù)的三維構(gòu)模中。

[1] 謝傳節(jié),萬洪濤.基于四叉樹結(jié)構(gòu)的數(shù)字地表模型快速生成算法設(shè)計[J].中國圖象圖形學(xué)報,2002,7(4):394-399.

[2] 張凱選，潘夢清，方輝.利用等高線生成DEM方法的研究[J].測繪工程,2007,16(3):15-18.

[3] 翁巧琳,姜昱明.基于等高線的三角網(wǎng)建模及真實感地形重建[J].計算機仿真,2007,24(10):188-191.

[4] 劉學(xué)慧,吳恩華.基于圖象空間判據(jù)的地表模型加速繪制技術(shù)。軟件學(xué)報[J],1998,9(7):481-486.