礦山地表三維模型實時重建方法的研究

陳曉青,任鳳玉,張國建

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

1 問題提出

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

如何降低這些模型的復雜度，減少圖形系統需處理的多邊形數目，實現復雜虛擬環境的實時快速生成成為研究的關鍵。

本文通過數據簡化、分塊處理、閉合多邊形提取和閉合多邊形快速建立三角網等幾個步驟完成礦山大規模復雜虛擬地表模型的動態生成。

2 數據的簡化

地表模型主要采用高程數據通過規則格網模型或不規則三角網模型兩種方式來表現。

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

不規則三角網模型根據區域有限個點集將區域劃分為相連的大小各異、疏密不同的三角網，能用更少的空間和時間更精確地表示復雜的表面。特別當地形包含大量特征(如斷裂線、構造線)時，能更好地顧及這些特征，從而可以更精確合理地表達地表形態。由于其描述教率高，長期以來受到人們的普遍關注，但由于三角化過程本身的復雜性以及非規則網格拓撲關系的繁雜性，使得各種基于非規則網格模型的自動生成算法難以達到實時。

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

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

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

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

3 分塊處理

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

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

當地下開采時，由于地形長期不變化，模型可以預先處理，由于非規則網格模型數據量少，一般采用非規則網格模型，當然也可采用規則網格模型全網格直接繪制。

當采用露天開采時，隨著露天礦的生產，地形可能隨時發生變化。但由于露天境界外部分基本上是長期不變化的，這樣可以將露天礦山地表分成境界線以外和境界線以內兩部分分別處理。露天境界以外部分可以預處理，只對境界線以內部分進行實時構網，這樣大大減少了實時處理的數據量。由于露天礦地表采用分塊處理，就不能采用規則網格模型，只能采用非規則網格模型。

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

圖1 區域分塊

4 構建三角網

在簡化和分塊的基礎上，對需要三角化的部分實行三角網的構建。

要實現地表模型的實時顯示，就應設計好整個地表網格模型的點、線、面關系，避免復雜的三角化過程。三角化算法是影響實時顯示效率的關鍵。

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

本文運用分治法的原理，提出將區域劃分為閉合多邊形，再對閉合多邊形進行三角化，較好地解決了傳統算法在構建大數據量不規則三角網時的不足，提高構網速度。

4.1 區域分區

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

在提取閉合多邊形的過程中，經常會出現環形區域，也稱為空洞，如圖3所示的陰影部分，這給閉合多邊形描述增加困難。

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

圖2 待處理的區域地形 圖3 空洞現象

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

圖4 分區

4.2 閉合多邊形的提取

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

4.3 閉合多邊形三角網的構建

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

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

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

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

圖6 中值遞歸分治法實現閉合多邊形三角化

5 實例

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

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

6 結論

針對礦山開采的特點，本文算法在保證地形正確性的同時，提升了運算速度，能夠對大規模地表模型進行有效的實時重構。本文的建模結果已成功地應用到礦山虛擬現實技術的三維構模中。

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

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

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

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