陳曉青,任鳳玉,張國建

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

1 問題提出

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

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

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

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

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

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

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

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

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

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

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

3 分塊處理

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

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

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

當(dāng)采用露天開采時(shí)，隨著露天礦的生產(chǎn)，地形可能隨時(shí)發(fā)生變化。但由于露天境界外部分基本上是長期不變化的，這樣可以將露天礦山地表分成境界線以外和境界線以內(nèi)兩部分分別處理。露天境界以外部分可以預(yù)處理，只對境界線以內(nèi)部分進(jìn)行實(shí)時(shí)構(gòu)網(wǎng)，這樣大大減少了實(shí)時(shí)處理的數(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)法單獨(dú)處理，本文不討論；采坑以外部分是在境界內(nèi)部分去除采坑后留下的部分，模型的實(shí)時(shí)處理實(shí)質(zhì)上只是對這部分進(jìn)行處理，如圖1所示。

圖1 區(qū)域分塊

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

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

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

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

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

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

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

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

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

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

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

圖4 分區(qū)

4.2 閉合多邊形的提取

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

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

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

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

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

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

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

5 實(shí)例

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

圖7 一個(gè)虛擬礦山實(shí)時(shí)場景

6 結(jié)論

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

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

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

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

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