李 釗，李建軍，李 冰，李 堅，臧傳收

（1.第二炮兵駐石家莊地區(qū)軍事代表室，河北石家莊050081;2.第二炮兵士官學(xué)校，山東青州262500）

0 引言

紋理映射技術(shù)是當(dāng)前計算機(jī)圖形學(xué)中的一個熱點問題。然而由于紋理圖像數(shù)據(jù)量大，特別是對于大規(guī)模的地形數(shù)據(jù)模型，如果要求具有較高的真實感，內(nèi)存的需求量更是十分巨大。很多算法是采用一個單塊的地形紋理來進(jìn)行紋理映射，但是在越來越多的情況下紋理數(shù)據(jù)遠(yuǎn)遠(yuǎn)大于內(nèi)存容量，需要將紋理分塊處理后才能使用[1]。為了能在有限的資源下獲得較好的實時繪制效果，研究人員從地形的幾何多分辨率表示中得到啟示提出多分辨率紋理映射技術(shù)[2-4]。該文在總結(jié)已有算法的基礎(chǔ)上，提出了一種基于四叉樹結(jié)構(gòu)的海量數(shù)據(jù)紋理映射算法。有效地解決了大規(guī)模地形場景重建過程中的數(shù)據(jù)調(diào)度與海量數(shù)據(jù)的紋理映射問題。實驗結(jié)果證明了該算法的有效性。

1 基于四叉樹的多分辨率紋理分塊

為了能有效地實現(xiàn)大數(shù)據(jù)量紋理的實時調(diào)度，需要將紋理進(jìn)行分塊管理。一般情況下，紋理圖像分割得越細(xì)，紋理坐標(biāo)的計算量就越小，繪制速度就越快，然而這樣會大大增加內(nèi)存中的數(shù)據(jù)調(diào)度次數(shù)。該文使用四叉樹結(jié)構(gòu)來表示大規(guī)模數(shù)字地形的多分辨率紋理數(shù)據(jù)，每個結(jié)點用相同尺寸的紋理圖像表示，但不同分辨率結(jié)點的紋理精細(xì)程度不同。四叉樹結(jié)構(gòu)的根結(jié)點對應(yīng)覆蓋整個地形方形區(qū)域，它的4個子結(jié)點分別為根節(jié)點的四分之一地域，依次類推，每個子結(jié)點均按此方法產(chǎn)生4個子結(jié)點，直到原始紋理的最精細(xì)分辨率或滿足紋理劃分的要求為止。

多分辨率紋理映射的關(guān)鍵是如何選取與地形LOD相一致的紋理圖像的分辨率。一般來說，分辨率的選擇是與視點、地形塊的位置大小和紋理的原始分辨率相關(guān)的。根據(jù)文獻(xiàn)[4]中的誤差計算方法可以類似計算紋理映射誤差。與地形誤差不同的是，紋理誤差要考慮紋理結(jié)點的大小與圖像的分辨率級別，因此，紋理映射的誤差可表示成紋理的分辨率級別與距視點的距離的函數(shù)，可用下式表示:

式中，k為紋理圖像的分辨率級別;d為紋理分塊距視點的距離;w為紋理分塊的大小;l為地形數(shù)據(jù)點之間的行間距和列間距的幾何平均值，即λ的計算方法和文獻(xiàn)[4]中的一樣。

2 紋理調(diào)度算法

在大規(guī)模的實時繪制時，需要不斷地從硬盤到系統(tǒng)內(nèi)存再到紋理內(nèi)存調(diào)度紋理數(shù)據(jù)，如果用圖形庫的函數(shù)來實時建立多分辨率紋理則效率不高。該文的方法是預(yù)先建立紋理的各個層次細(xì)節(jié)，存儲在數(shù)據(jù)文件中，當(dāng)需要的時候?qū)Ω鱾€層次的紋理數(shù)據(jù)進(jìn)行讀取，然而使用多級紋理四叉樹一次調(diào)入的數(shù)據(jù)量太多時，就會造成幀間停頓時間過長，為了降低停頓時間，必須減少紋理數(shù)據(jù)的調(diào)入量。

2.1 壓縮紋理存儲的實現(xiàn)

在實際應(yīng)用中發(fā)現(xiàn)，在硬盤到系統(tǒng)內(nèi)存的傳輸這一過程可以使用算法對紋理數(shù)據(jù)進(jìn)行壓縮，再將其存儲在硬盤文件上。在使用時，用快速的解碼把紋理數(shù)據(jù)解壓到系統(tǒng)內(nèi)存中。由于紋理圖像相鄰的紋理象素之間具有某種連貫性，利用這種連貫性對紋理金字塔進(jìn)行壓縮可以有效地減少數(shù)據(jù)冗余，使得紋理的表示更為緊湊。該文使用類似文獻(xiàn)[5]中的圖像金字塔，進(jìn)行多層次的壓縮和存儲，來對紋理進(jìn)行有效地壓縮、調(diào)度及紋理反走樣。由于紋理數(shù)據(jù)需要在繪制時實時進(jìn)行解碼，對解碼的時間要求比較高，而矢量量化的方法僅需要建立索引表進(jìn)行數(shù)據(jù)檢索，效率非常高，因此可以采用矢量量化方法壓縮誤差圖像。用矢量量化編碼圖像是一種有損的壓縮技術(shù)，其關(guān)鍵是基于區(qū)域進(jìn)行碼本設(shè)計。這里使用LBG矢量量化算法對誤差圖像進(jìn)行壓縮編碼[6]。

在執(zhí)行圖像矢量量化的過程中，由于圖像各局部區(qū)域之間具有相似性，取一定大小的圖像子區(qū)域進(jìn)行矢量量化，這些圖像子區(qū)域區(qū)使用相同的編碼索引?；趫D像子區(qū)域進(jìn)行矢量量化，可以有效地對紋理圖像進(jìn)行壓縮。采用矢量化的壓縮方法，圖像解碼快速有效。對于層次多分辨率的紋理，當(dāng)需要導(dǎo)入高一層分辨率的紋理數(shù)據(jù)，可以通過使用粗糙一層的紋理數(shù)據(jù)，以及編碼索引號所指向的誤差圖像矢量量化后的顏色值就可以計算得出。在恢復(fù)每一層時，只需要從硬盤讀取碼本和編碼索引號的信息，數(shù)據(jù)量小，讀取非常快，這樣既可以節(jié)省存儲空間，又可以快速地恢復(fù)精細(xì)層紋理。

2.2 基于誤差控制的多分辨率紋理結(jié)構(gòu)

在實際繪制過程中，可以發(fā)現(xiàn)在一定誤差的控制下，越高分辨率的紋理圖像，在離視點越近的區(qū)域使用的較多，根據(jù)這一現(xiàn)象，在調(diào)入紋理數(shù)據(jù)時，只調(diào)入某一分辨率的在一定范圍內(nèi)的紋理數(shù)據(jù)即可滿足實時繪制的需要。因此，首先要根據(jù)多分辨率紋理計算的結(jié)果確定不同分辨率紋理的范圍，將在范圍內(nèi)的多分辨率紋理調(diào)入到內(nèi)存的多分辨率結(jié)構(gòu)中。該文在繪制時將每一層分辨率的紋理數(shù)據(jù)與預(yù)估的結(jié)果比較，將符合要求的紋理數(shù)據(jù)調(diào)入內(nèi)存結(jié)構(gòu)中，此時對于不同層次的紋理映射時會有2種情況:

①需繪制的紋理層次低于調(diào)入的紋理節(jié)點層次，此種情況可直接使用上一級紋理進(jìn)行紋理映射;

②需繪制的紋理層次高于調(diào)入的紋理節(jié)點層次，這種情況要復(fù)雜一些，因為調(diào)入的紋理不能完全覆蓋滿足紋理分辨率要求的一個多邊形，所以不能直接進(jìn)行紋理映射，解決的方法是利用己調(diào)入的紋理為繪制節(jié)點實時生成紋理圖像。

2.3 紋理內(nèi)存釋放算法

在進(jìn)行大規(guī)模的紋理調(diào)用時，當(dāng)紋理的緩沖空間達(dá)到一定限制時就需要釋放一部分紋理，通常的辦法是采用LRU算法。

假定當(dāng)前的視點位置為v1，前一幀視點位置為v0，下一幀視點位置為v2。由此可以估算出在視點v1處的運(yùn)動方向是（v1-v0）/‖v1-v0‖，運(yùn)動的速度為‖v1-v0‖/t，其中t是從視點v0運(yùn)動到視點v1所用的時間，所以在v1處視點的運(yùn)動矢量為:

式中，f表示在v1時刻的幀頻率，于是下一視點v2的估計位置為:

這里假設(shè)在3個視點處有相同的幀頻率，則在視點v2處的視錐體可以表示成由視點位置v2、視點方向d、視域張角w以及近截面fn和遠(yuǎn)截面ff的函數(shù)，即:

通常情況下，在實時飛行仿真過程中后面3個變量是不變的，只有視點的位置與方向在隨時間變化。在飛行仿真過程中，通常離視域范圍越遠(yuǎn)的紋理被釋放的可能性就越大，因此可以用紋理塊與視域的距離平均距離作為影響內(nèi)存釋放的一個因子，可以用下式計算:

式中，（qx，qy），（rx，ry）分別為紋理分塊與預(yù)測的下一視點處的視域體在平行于地面平面上投影的重心。

在進(jìn)行紋理調(diào)度時，首先計算內(nèi)存中紋理分塊到視域體的平均距離，然后，對平均距離超過一定閾值的內(nèi)存紋理分塊，使用改進(jìn)的LUR算法[1]，進(jìn)行內(nèi)存釋放。改進(jìn)的LUR策略的優(yōu)先級由下式給出:

式中，fq為紋理四叉樹結(jié)點最近一次調(diào)用的幀序號;l務(wù)紋理四叉樹結(jié)點的層數(shù)，p越小且距離視域平均距離越遠(yuǎn)的紋理結(jié)點的數(shù)據(jù)最先剔除。

3 實驗結(jié)果分析

該文對地形紋理的實時繪制進(jìn)行性能測試，使用的實驗數(shù)據(jù)是深圳地區(qū)的DEM數(shù)據(jù)，地形表面數(shù)據(jù)的大小為7169×4096個數(shù)據(jù)點，數(shù)據(jù)點的實際分辨率為10m，在硬盤中的文件總大小為112MB。對于地形紋理數(shù)據(jù)，這里使用的是該地區(qū)經(jīng)校正過的衛(wèi)星圖片，其大小為28672×16384，在硬盤中的文件大小約為1.34GB。

圖1是該算法實時幀速率與傳統(tǒng)算法的實時幀速率比較的結(jié)果圖。統(tǒng)計了一個給定飛行路線中500幀的數(shù)據(jù)。從圖中可以看出，算法的幀速率要明顯高于傳統(tǒng)方法的結(jié)果，這是因為該算法通過矢量量化圖像壓縮算法及根據(jù)紋理誤差范圍的數(shù)據(jù)調(diào)度算法，大大減少了實時仿真過程中的系統(tǒng)外存與內(nèi)存之間的數(shù)據(jù)調(diào)度量，同時基于視域的內(nèi)存釋放算法可以對紋理內(nèi)存進(jìn)行有效的管理，減少內(nèi)存中紋理數(shù)據(jù)在磁盤和緩沖區(qū)之間反復(fù)調(diào)度，提高了算法實時仿真的效率。

圖1 不同算法的幀速率比較

4 結(jié)束語

為實現(xiàn)實時的大規(guī)模地形的紋理映射，該文提出了一種新的基于四叉樹結(jié)構(gòu)的海量數(shù)據(jù)紋理映射算法。算法對多分辨率紋理數(shù)據(jù)進(jìn)行了基于金字塔結(jié)構(gòu)的數(shù)據(jù)壓縮存儲，提出了一種有效的紋理映射誤差的計算方法，提高了紋理映射的精度，并利用紋理映射誤差，減少了實時調(diào)度過程中紋理數(shù)據(jù)的數(shù)據(jù)量，同時優(yōu)化了內(nèi)存釋放算法，有效減少了紋理數(shù)據(jù)在磁盤和緩沖區(qū)之間的反復(fù)調(diào)度，從而解決了大規(guī)模地形場景重建過程中的數(shù)據(jù)調(diào)度與海量數(shù)據(jù)的紋理映射問題，在實際應(yīng)用中取得了比較滿意的效果。

[1]陸雁青.海量地形數(shù)據(jù)實時繪制的技術(shù)研究[D].浙江大學(xué)博士學(xué)位論文，2003.7.

[2]BLOW J.Terrain rendering at high levels of detail[C]//Proceedings of the Game Developers Conference 2000.California，2000:119-124.

[3]TANNER C，MIGAL C，JONES M.The clipmap:a virtual mipmap[C]//Cohen M.ed.，Proceedings of SIGGRAPH 1998.Orlando，florida.1998.New York:ACM Press，1998:415-422.

[4]黃超超，凌永順，呂相銀.地形紋理映射方法研究[J].計算機(jī)仿真，2005，22（1）:209-212.

[5]LINDSTROM P，PASCUCCIV.Terrain simplification simplified:a general framework for view-dependent out-ofcore visualization[J].IEEE Transactions on Visualization and Computer Graphics，2002，8（3）:239-25.

[6]BURT P J，ADELSON E.The laplacian pyramid as a compact image Code[J].IEEE Transactions on Communications，1983，COM-3l（4），532-540。