一個(gè)輸出恒定的三維地形多分辨率簡(jiǎn)化算法

1、一個(gè)輸出恒定的三維地形多分辨率簡(jiǎn)化算法 本文得到863計(jì)劃課題大型GIS測(cè)試與面向SIG的空間信息服務(wù)終端（SIST）2002AA131020資助陳斌1，董士海2，方裕1（1.北京大學(xué)遙感與地理信息系統(tǒng)研究所；2.北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京100871）摘要：本文提出了一種輸出恒定的基于視點(diǎn)的三維地形動(dòng)態(tài)多分辨率簡(jiǎn)化算法。該算法根據(jù)飛行漫游交互仿真的視點(diǎn)參數(shù)對(duì)三維地形數(shù)據(jù)進(jìn)行裁剪簡(jiǎn)化，并根據(jù)人眼視覺心理和顯示設(shè)備特性進(jìn)行多分辨率簡(jiǎn)化。其簡(jiǎn)化結(jié)果數(shù)據(jù)的數(shù)據(jù)量與三維地形總數(shù)據(jù)量和視點(diǎn)位置無關(guān)，從而實(shí)現(xiàn)恒定數(shù)據(jù)量輸出，并能夠通過參數(shù)來調(diào)節(jié)和評(píng)價(jià)簡(jiǎn)化的效果。由于實(shí)現(xiàn)了輸出質(zhì)量控制和數(shù)據(jù)量恒定，本文

2、的算法很適合應(yīng)用于基于網(wǎng)絡(luò)的大規(guī)模地形實(shí)時(shí)漫游系統(tǒng)。關(guān)鍵詞：三維地形，DEM，簡(jiǎn)化，多分辨率，GIS在基于網(wǎng)絡(luò)的大規(guī)模地形實(shí)時(shí)漫游系統(tǒng)中，如何盡可能減少在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量成為一個(gè)關(guān)鍵問題，本文提出了根據(jù)在客戶端仿真漫游過程中的姿態(tài)參數(shù)對(duì)大規(guī)模地形數(shù)據(jù)進(jìn)行動(dòng)態(tài)多分辨率簡(jiǎn)化的算法。本算法的目標(biāo)是：l 場(chǎng)景數(shù)據(jù)量受到控制并且盡可能恒定。即無論客戶端仿真姿態(tài)參數(shù)如何變化，為了繪制當(dāng)前場(chǎng)景需要，使從網(wǎng)絡(luò)傳輸?shù)娜S地形數(shù)據(jù)的數(shù)據(jù)量，能夠控制在網(wǎng)絡(luò)帶寬所允許的范圍，并且為了有效地進(jìn)行系統(tǒng)服務(wù)質(zhì)量控制，應(yīng)能夠防止出現(xiàn)數(shù)據(jù)量的大幅度變化，最好能夠保持恒定；l 可控的場(chǎng)景視覺效果。簡(jiǎn)化算法應(yīng)該可以控制控制視覺失

3、真，并有失真評(píng)價(jià)方法對(duì)失真的程度進(jìn)行評(píng)價(jià)；1 相關(guān)工作王宏武12提出了基于視點(diǎn)的動(dòng)態(tài)多分辨率地形模型VDDMT（View-Dependent Dynamic Multiresolution Terrain）以及地形的動(dòng)態(tài)簡(jiǎn)化算法，模型中采用了四叉樹結(jié)構(gòu)來容納經(jīng)過多分辨率預(yù)處理的地形數(shù)據(jù)，在地形動(dòng)態(tài)簡(jiǎn)化算法中按照結(jié)點(diǎn)評(píng)價(jià)函數(shù)的計(jì)算來為模型中不同區(qū)域選取不同分辨率的地形數(shù)據(jù)，并提供了誤差評(píng)價(jià)方法。但是算法需要對(duì)地形數(shù)據(jù)進(jìn)行預(yù)處理，四叉樹的結(jié)構(gòu)對(duì)于數(shù)據(jù)更新代價(jià)高昂，結(jié)點(diǎn)評(píng)價(jià)函數(shù)的計(jì)算也比較復(fù)雜。Lindstorm45的連續(xù)細(xì)節(jié)層次簡(jiǎn)化算法實(shí)現(xiàn)了對(duì)地形數(shù)據(jù)和高度場(chǎng)數(shù)據(jù)實(shí)時(shí)的連續(xù)細(xì)節(jié)層次簡(jiǎn)化，引入了屏幕

4、空間誤差評(píng)價(jià)的概念。但是算法仍將整個(gè)地形數(shù)據(jù)作為整體進(jìn)行處理，不適于大規(guī)模的三維地形數(shù)據(jù)；同時(shí)屏幕空間誤差用于衡量地形數(shù)據(jù)中頂點(diǎn)距離差，決定是否進(jìn)行簡(jiǎn)化，這樣不能保證簡(jiǎn)化后的模型數(shù)據(jù)量的恒定。陳斌3等提出的基于網(wǎng)絡(luò)的大規(guī)模地形數(shù)據(jù)實(shí)時(shí)漫游系統(tǒng)中，改進(jìn)了王宏武的動(dòng)態(tài)多分辨率算法，針對(duì)大規(guī)模地形數(shù)據(jù)，考慮實(shí)時(shí)性而采用視場(chǎng)模板來代替結(jié)點(diǎn)評(píng)價(jià)函數(shù)，這樣既對(duì)可視范圍進(jìn)行了裁剪，也顯著簡(jiǎn)化了多分辨率的計(jì)算。但是仍然采用了空間四叉樹來存儲(chǔ)地形數(shù)據(jù)，需要對(duì)地形數(shù)據(jù)進(jìn)行大量的預(yù)處理。2 漫游交互參數(shù)按照仿真效果的不同，地形漫游的交互方式分為飛行交互和行走交互兩種，其中飛行交互是將客戶端模擬為直升飛機(jī)的座艙，用戶

5、在機(jī)艙內(nèi)以第一人稱視角進(jìn)行飛行姿態(tài)的控制和地面觀察；而行走交互則是模擬人行走所進(jìn)行的觀察。大規(guī)模地形漫游的主要方式是飛行交互。圖 1飛行交互仿真示意圖圖 1是飛行交互仿真的示意圖，由圖看出，飛行的高度和視線俯角對(duì)可視范圍的影響最大。而可視范圍決定對(duì)應(yīng)空間范圍的地形數(shù)據(jù)量，可視范圍越大，則對(duì)應(yīng)的地形數(shù)據(jù)量越大。下面我們分析影響可視范圍大小的參數(shù)，以查明姿態(tài)參數(shù)和可視范圍大小之間的關(guān)系。影響可視范圍大小的姿態(tài)參數(shù)有4個(gè)，記為：l 視點(diǎn)高度he；l 豎直方向可視角大??；l 水平方向可視角大?。籰 視線的俯角；在海拔高度為0的水平面上可視范圍為一個(gè)梯形，其面積S為（公式經(jīng)過Mathematica 4.

6、0化簡(jiǎn)）：公式 1可視范圍面積公式在一般的飛行交互中，豎直可視角和水平可視角是確定的，而視線俯角和視點(diǎn)高度he是可以通過用戶交互改變的，所以在交互過程中，可視范圍的變化主要是由視線俯角和視點(diǎn)高度he來決定的。從公式 1我們可以看出，地面的可視范圍面積S與視點(diǎn)高度he的平方成正比?？梢姡w行交互高度的成倍上升將引起視野范圍覆蓋面積平方倍數(shù)的增加，同樣，需要傳遞給客戶端的地形數(shù)據(jù)量也將以平方倍數(shù)增加。從公式 1中我們難以看出視線俯角和可視范圍面積S的關(guān)系，不妨設(shè)=/3，=2/3，he=1，則公式 1化簡(jiǎn)如下：公式 2可視范圍S和視線俯角的關(guān)系（=/3，=2/3，he=1）可視范圍面積S（縱軸）和視

7、線俯角（橫軸）的關(guān)系如圖 2所示：圖 2可視范圍面積S（縱軸）和視線俯角（橫軸）的關(guān)系（=/3，=2/3，he=1）不難看出當(dāng)視線俯角接近/2時(shí)，可視范圍面積S迅速趨向無窮大，可視范圍所對(duì)應(yīng)的地形數(shù)據(jù)也以同樣的趨勢(shì)增加。3 帶失真的可視范圍控制裁剪客戶端仿真姿態(tài)參數(shù)中的豎直視角、水平視角限制了客戶端所可能觀察到的地面范圍，在海拔高度為零的水平面上，地面范圍的邊界是一個(gè)四棱錐和平面相交的梯形輪廓，如圖 3所示：圖 3豎直視角、水平視角和視線俯角形成的梯形可視范圍我們將梯形的短平行邊稱作近景界，記為av，將梯形的長(zhǎng)平行邊稱作遠(yuǎn)景界，記為bv。那么，如果地面是一個(gè)平面，在梯形范圍以外的地面都應(yīng)該排除

8、在可視范圍之外。公式 2可視范圍S和視線俯角的關(guān)系（=/3，=2/3，he=1）和圖 2可視范圍面積S（縱軸）和視線俯角（橫軸）的關(guān)系（=/3，=2/3，he=1）表明如果在飛行交互中視線俯角接近/2，則遠(yuǎn)景界bv將迅速遠(yuǎn)離視點(diǎn)，使得可視梯形范圍的面積迅速趨向無窮大。為了解決上述問題，我們?cè)谝肟梢暦秶д娴那疤嵯?，提出一種帶失真的豎直視角差裁剪算法，對(duì)可視范圍的面積進(jìn)行控制。這里的豎直視角差指一定的地面范圍經(jīng)過透視投影以后在視口的豎直方向上所占據(jù)的視角范圍。本算法的基本思路在于將遠(yuǎn)景界以內(nèi)視角差小于一定閾值的梯形地面范圍排除在可視范圍之外，以一定的失真度換取對(duì)可視范圍增大趨勢(shì)的控制。由于客戶

9、端用來顯示三維地形場(chǎng)景的光柵顯示設(shè)備其分辨率是有限的，地面范圍的投影尺寸如果小于一個(gè)像素的大小，這個(gè)范圍內(nèi)的地面將不會(huì)被顯示設(shè)備所表示。因此需要將遠(yuǎn)景界bv拉近，假設(shè)顯示設(shè)備垂直方向上的像素?cái)?shù)為p，由于垂直方向所有的像素所對(duì)應(yīng)的視角是豎直視角，那么垂直方向上的一個(gè)像素所對(duì)應(yīng)的視角是，我們可以安全地將遠(yuǎn)景界以內(nèi)視角差小于的部分排除在可視范圍之外，使得最終的顯示效果和沒有排除這些部分的顯示效果完全一樣；如果我們進(jìn)一步將視角差小于的部分排除在可視范圍之外，則最終顯示效果在遠(yuǎn)景界附近的失真將可以控制在n個(gè)像素之內(nèi)。我們將公式 1可視范圍面積公式中的豎直視角替換為，得到：公式 3豎直視角差裁剪后的可視范

10、圍面積公式可以證明，公式 3在區(qū)間內(nèi)有非負(fù)的最大最小值，這樣就解決了飛行交互中當(dāng)視線俯角接近/2的時(shí)候可視范圍趨向無窮大的問題。在豎直視角差裁剪算法中，n的取值對(duì)可視范圍的面積影響在接近/2的時(shí)候非常大，圖 4直觀地描繪了這種趨勢(shì)，圖中的10條曲線從上到下分別對(duì)應(yīng)=/3，=2/3，he=1，p=600，=/2，n=1到10，橫軸為視線俯角，縱軸為可視范圍面積S：圖 4像素誤差n對(duì)可視范圍面積的影響（橫軸為，縱軸為S）4 基于視點(diǎn)的多分辨率簡(jiǎn)化基于視角的裁剪可以將客戶端交互仿真可視范圍限制到一個(gè)具有近景界、遠(yuǎn)景界和側(cè)景界的有限面積的封閉區(qū)域，但由于可視范圍的面積隨著視點(diǎn)高度he增加以及隨著視線俯

11、角靠近/2而急劇增加的趨勢(shì)，如果不對(duì)地形數(shù)據(jù)進(jìn)行簡(jiǎn)化處理，對(duì)大規(guī)模地形的交互漫游仍然難以實(shí)現(xiàn)。這里我們就姿態(tài)參數(shù)中的視點(diǎn)高度he和視點(diǎn)提出一個(gè)地形數(shù)據(jù)的多分辨率簡(jiǎn)化方案。在交互過程中，可視范圍的面積雖然可以成平方倍數(shù)地增長(zhǎng)，但最終會(huì)在客戶端的光柵顯示設(shè)備上繪制出來，這樣，客戶端顯示設(shè)備的分辨率限制同樣可應(yīng)用到地形數(shù)據(jù)的簡(jiǎn)化方案中。假設(shè)客戶端光柵顯示設(shè)備垂直方向的分辨率是p個(gè)像素，縱橫比是r。單個(gè)像素能夠表達(dá)的有效三角面片數(shù)量為1。這樣，這個(gè)顯示設(shè)備所能夠表達(dá)的三角面片數(shù)量最多為，這些三角面片的數(shù)據(jù)采樣點(diǎn)個(gè)數(shù)最多為。也就是說，無論可視范圍多大，客戶端光柵顯示設(shè)備所能夠表達(dá)的有效地形數(shù)據(jù)點(diǎn)個(gè)數(shù)為，

12、問題是如何在可視范圍內(nèi)選取這些地形數(shù)據(jù)點(diǎn)。如圖 5所示，將豎直方向視角進(jìn)行p等分，相應(yīng)地將對(duì)應(yīng)于顯示設(shè)備垂直方向的近景界和遠(yuǎn)景界之間的距離分為p個(gè)部分，我們將靠近近景界的部分編號(hào)為1，依次遠(yuǎn)離的部分分別編號(hào)為2、3p。圖 5根據(jù)光柵顯示設(shè)備特性對(duì)可視范圍進(jìn)行劃分可以算出，第n個(gè)部分的寬度為：公式 4可視范圍劃分的寬度對(duì)每個(gè)部分的范圍在水平視角方向進(jìn)行等分，在每個(gè)等分部分的范圍內(nèi)，如果原始地形數(shù)據(jù)存在多于三個(gè)數(shù)據(jù)點(diǎn)，則可以簡(jiǎn)化為三個(gè)數(shù)據(jù)點(diǎn)。從公式 4中還可以看出，在p個(gè)劃分中，可視范圍中離視點(diǎn)越遠(yuǎn)y的劃分，寬度越大，面積也越大，但是都被統(tǒng)一簡(jiǎn)化為個(gè)數(shù)據(jù)點(diǎn)。根據(jù)人的視覺心理特征，人在觀察圖像，特別

13、是運(yùn)動(dòng)圖像的時(shí)候，在視覺中心附近的區(qū)域視覺敏感度最高，越遠(yuǎn)離視覺中心的區(qū)域視覺敏感度越低，如圖 6所示。圖 6視覺敏感度分區(qū)示意根據(jù)這個(gè)原理，我們?cè)谝朁c(diǎn)距離簡(jiǎn)化的基礎(chǔ)上進(jìn)一步對(duì)可視范圍內(nèi)的地形數(shù)據(jù)進(jìn)行簡(jiǎn)化。圖 5所劃分的p個(gè)部分分為如下幾類：1. 視覺中心區(qū)：以視線與地面的交點(diǎn)為中心，前后各個(gè)劃分部分，即劃分編號(hào)到，對(duì)應(yīng)客戶端顯示設(shè)備的中心三分之一的顯示區(qū)域；2. 前景區(qū)：從近景界開始的共個(gè)劃分，即劃分編號(hào)1到，對(duì)應(yīng)客戶端顯示設(shè)備的下三分之一的顯示區(qū)域；3. 中景區(qū)：從視覺中心區(qū)開始的共個(gè)劃分，即劃分編號(hào)到，對(duì)應(yīng)客戶端顯示設(shè)備中心偏上的六分之一處；4. 遠(yuǎn)景區(qū)：從中景區(qū)開始開始的共個(gè)劃分，即劃

14、分編號(hào)到p，對(duì)應(yīng)客戶端顯示設(shè)備最頂端的六分之一處；圖 7可視范圍的分區(qū)和客戶端顯示的對(duì)應(yīng)對(duì)于視覺敏感度高的視覺中心區(qū)，保持原有的數(shù)據(jù)簡(jiǎn)化不變；對(duì)于視覺敏感度一般的近景區(qū)和中景區(qū)，將數(shù)據(jù)在原有的簡(jiǎn)化基礎(chǔ)上再簡(jiǎn)化一倍；而對(duì)于視覺敏感度低的遠(yuǎn)景區(qū)，地形數(shù)據(jù)比中景區(qū)再簡(jiǎn)化一倍。這樣，能夠?qū)⒄麄€(gè)可視范圍的地形數(shù)據(jù)減少到：減少的幅度為一倍以上。為了進(jìn)一步簡(jiǎn)化可視范圍的地形數(shù)據(jù)，我們?cè)O(shè)定一個(gè)采樣步長(zhǎng)s，即對(duì)視覺中心區(qū)每個(gè)水平劃分的等分的采樣組合，當(dāng)s=1，對(duì)每個(gè)等分進(jìn)行采樣簡(jiǎn)化，情況同上面所述，當(dāng)采樣步長(zhǎng)s>1，則對(duì)s個(gè)等分進(jìn)行采樣簡(jiǎn)化，這樣地形數(shù)據(jù)的簡(jiǎn)化率進(jìn)一步降低到：圖 8采樣步長(zhǎng)進(jìn)一步簡(jiǎn)化地形數(shù)

15、據(jù)（橫軸為采樣步長(zhǎng)，縱軸為簡(jiǎn)化倍數(shù)）5 算法實(shí)現(xiàn)與評(píng)價(jià)我們實(shí)現(xiàn)了上述的基于視點(diǎn)的動(dòng)態(tài)多分辨率簡(jiǎn)化算法，測(cè)試數(shù)據(jù)采用美國(guó)1度DEM數(shù)據(jù)中GOLDFIELD1987和DEATH VALLEY1970兩塊，覆蓋的空間范圍是經(jīng)度跨度2度，緯度跨度2度，約38,000平方公里。DEM數(shù)據(jù)共2,400*2,400個(gè)采樣點(diǎn)，連成11,520,000個(gè)三角形。分別采用豎直象素誤差為1，采樣步長(zhǎng)為1、3進(jìn)行計(jì)算，算法生成的結(jié)果與初始場(chǎng)景的大小以及視點(diǎn)位置都沒有關(guān)系，只和豎直象素誤差以及采樣步長(zhǎng)相關(guān)。實(shí)際的測(cè)試結(jié)果如下，其中簡(jiǎn)化率為簡(jiǎn)化后的三角形個(gè)數(shù)與未簡(jiǎn)化個(gè)數(shù)的比值，場(chǎng)景繪制時(shí)間對(duì)應(yīng)的計(jì)算機(jī)配置為AMD Dur

16、on650+Geforce256：采樣步長(zhǎng)場(chǎng)景三角形個(gè)數(shù)簡(jiǎn)化率場(chǎng)景繪制時(shí)間1651,0025.65%0.27秒3109,1620.95%0.03秒圖 9 原場(chǎng)景明暗圖圖 10 采樣步長(zhǎng)為1的簡(jiǎn)化結(jié)果明暗圖（簡(jiǎn)化率5.65%）圖 11 采樣步長(zhǎng)為3的簡(jiǎn)化結(jié)果明暗圖（簡(jiǎn)化率0.95%）6 結(jié)論本文提出的基于視點(diǎn)的動(dòng)態(tài)多分辨率簡(jiǎn)化算法根據(jù)客戶端顯示設(shè)備分辨率特性和人眼視覺心理特性對(duì)地形數(shù)據(jù)進(jìn)行簡(jiǎn)化，實(shí)現(xiàn)了輸出結(jié)果數(shù)據(jù)量與源地形數(shù)據(jù)大小無關(guān)和視點(diǎn)位置無關(guān)的特性。算法設(shè)置了結(jié)果數(shù)據(jù)質(zhì)量調(diào)整參數(shù)，可以在選擇較低質(zhì)量數(shù)據(jù)的同時(shí)獲得數(shù)據(jù)量較小的簡(jiǎn)化數(shù)據(jù)。由于算法的輸出結(jié)果數(shù)據(jù)量恒定，輸出質(zhì)量可以控制，很適合應(yīng)

17、用于基于網(wǎng)絡(luò)的大規(guī)模地形實(shí)時(shí)漫游系統(tǒng)。7 參考文獻(xiàn)1 王宏武，面向數(shù)字地球的虛擬現(xiàn)實(shí)系統(tǒng)及若干問題研究，北京大學(xué)博士研究生學(xué)位論文，北京，1999年5月2 王宏武，董士海，一個(gè)與視點(diǎn)相關(guān)的動(dòng)態(tài)多分辨率地形模型，計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)2000年08期3 Chen Bin, MA Zhi-Gang, WANG Guo-Ping, DONG Shi-Hai，Network Based Realtime Flythrough on Massive Terrain Dataset，CAD/Graphics2001國(guó)際會(huì)議論文集第七屆計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)國(guó)際學(xué)術(shù)會(huì)議文集4 Peter Lindstr

18、om, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust, and Gregory Turner. Real-time, continuous level of detail rendering of height fields. In Holly Rushmeier, editor, Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, pages 109118. Addison Wesley, New Or

19、leans, Louisiana, August 1996. ISBN 0-201-94800-1.5 Peter Lindstrom. Out-of-core simplification of large polygonal models. In Kurt Akeley, editor, Proceedings of SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, pages 259262. ACM Press / ACM SIGGRAPH / Addison Wesley Longman, N

20、ew Orleans, Louisiana, July 2000. ISBN 1-58113-208-5.A 3D Terrain Multi-resolution Simplify Algorithm With Stable OutputCHEN Bin1, DONG Shi-Hai2, FANG Yu1(1.Institute of Remote Sensing and GIS, Peking Univ.; 2.School of Electronic Engineering and Computer Science, Peking Univ., Beijing 100871)Summary: This paper introduced a view p