李 釗，李建軍，李 冰，李 堅(jiān)，臧傳收

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

0 引言

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

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

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

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

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

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

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

2.1 壓縮紋理存儲(chǔ)的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

式中，f表示在v1時(shí)刻的幀頻率，于是下一視點(diǎn)v2的估計(jì)位置為:

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

4 結(jié)束語(yǔ)

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

[1]陸雁青.海量地形數(shù)據(jù)實(shí)時(shí)繪制的技術(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ì)算機(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。