海量數據紋理映射技術研究

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

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

0 引言

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

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

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

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

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

2 紋理調度算法

在大規模的實時繪制時，需要不斷地從硬盤到系統內存再到紋理內存調度紋理數據，如果用圖形庫的函數來實時建立多分辨率紋理則效率不高。該文的方法是預先建立紋理的各個層次細節，存儲在數據文件中，當需要的時候對各個層次的紋理數據進行讀取，然而使用多級紋理四叉樹一次調入的數據量太多時，就會造成幀間停頓時間過長，為了降低停頓時間，必須減少紋理數據的調入量。

2.1 壓縮紋理存儲的實現

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

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

2.2 基于誤差控制的多分辨率紋理結構

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

①需繪制的紋理層次低于調入的紋理節點層次，此種情況可直接使用上一級紋理進行紋理映射;

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

2.3 紋理內存釋放算法

在進行大規模的紋理調用時，當紋理的緩沖空間達到一定限制時就需要釋放一部分紋理，通常的辦法是采用LRU算法。

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

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

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

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

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

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

式中，fq為紋理四叉樹結點最近一次調用的幀序號;l務紋理四叉樹結點的層數，p越小且距離視域平均距離越遠的紋理結點的數據最先剔除。

3 實驗結果分析

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

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

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

4 結束語

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

[1]陸雁青.海量地形數據實時繪制的技術研究[D].浙江大學博士學位論文，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].計算機仿真，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。