李 培， 張仁俊

（蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅蘭州 730070）

0 引言

數(shù)字博物館是將文物和歷史場(chǎng)景通過(guò)三維建模，利用虛擬現(xiàn)實(shí)技術(shù)在計(jì)算機(jī)網(wǎng)絡(luò)上進(jìn)行展示，并實(shí)現(xiàn)瀏覽者與文物、瀏覽者與瀏覽者之間的交互，是傳統(tǒng)展示方法與先進(jìn)計(jì)算機(jī)虛擬技術(shù)的結(jié)合。

虛擬視景的實(shí)時(shí)程度，從一定意義上決定了虛擬現(xiàn)實(shí)的真實(shí)程度。也就是說(shuō)，為了達(dá)到較好的真實(shí)感，虛擬視景要求圖形的生成速度達(dá)到實(shí)時(shí)，因此，要確保復(fù)雜虛擬場(chǎng)景的實(shí)時(shí)性，即圖形的顯示速度。

本文提出了一種適合博物館虛擬場(chǎng)景實(shí)時(shí)顯示的管理機(jī)制，并提出了一種改進(jìn)的基于時(shí)間估計(jì)和對(duì)象重要性的實(shí)時(shí)LOD選擇算法，大大降低了場(chǎng)景的復(fù)雜度，提高了場(chǎng)景載入的實(shí)時(shí)性。

1 限時(shí)自適應(yīng)LOD技術(shù)

1.1 LOD細(xì)節(jié)層次技術(shù)

LOD(level of detail)細(xì)節(jié)層次技術(shù)[1]，它是指對(duì)于同一個(gè)場(chǎng)景或場(chǎng)景中的物體使用一組具有不同細(xì)節(jié)程度的模型對(duì)象，不同細(xì)節(jié)程度模型的多邊形復(fù)雜度也不一樣，細(xì)節(jié)程度越高模型對(duì)象所包含的多邊形的數(shù)量也越多[2]。在實(shí)時(shí)渲染和繪制時(shí)，瀏覽器會(huì)根據(jù)用戶的視點(diǎn)離該物體的遠(yuǎn)近自動(dòng)顯示相應(yīng)的模型。

博物館場(chǎng)景模型的實(shí)時(shí)繪制中，如果要做到畫(huà)面的連續(xù)性，一秒之內(nèi)至少需要繪制25幀的數(shù)據(jù)，那么對(duì)于每一幀來(lái)說(shuō)就只有0．04 s的限定時(shí)間，如果某一幀場(chǎng)景需要繪制的對(duì)象太多或者太復(fù)雜，那么繪制時(shí)間就會(huì)超過(guò)0．04 s，這樣就會(huì)產(chǎn)生停頓現(xiàn)象，產(chǎn)生延遲，進(jìn)而影響用戶使用的滿意度[4]。所以在限時(shí)自適應(yīng)LOD的機(jī)制中，為了保證在限定的時(shí)間內(nèi)將數(shù)據(jù)繪制完，就會(huì)出現(xiàn)降低繪制對(duì)象LOD級(jí)別的情況，如本來(lái)需要的是最精細(xì)的LOD級(jí)別就會(huì)被替換成一般精細(xì)或者模糊的LOD級(jí)別。這樣做就是為了在速度和效果之間尋求一個(gè)平衡，能夠讓用戶滿意。

1.2 博物館場(chǎng)景模型限時(shí)自適應(yīng)機(jī)制

本文針對(duì)博物館場(chǎng)景模型的特點(diǎn)，將博物館場(chǎng)景模型劃分為6大功能模塊，分別是：最優(yōu)化繪制方案選擇模塊、繪制模塊、時(shí)間估計(jì)模塊、重要性估計(jì)模塊、數(shù)據(jù)調(diào)度管理模塊和性能檢測(cè)模塊。圖1為博物館場(chǎng)景模型自適應(yīng)LOD機(jī)制流程圖。

圖1 博物館場(chǎng)景模型自適應(yīng)機(jī)制流程圖

各模塊的主要功能如下：

數(shù)據(jù)調(diào)度管理模塊：根據(jù)當(dāng)前的博物館場(chǎng)景參數(shù)調(diào)入當(dāng)前視域范圍內(nèi)的模型數(shù)據(jù)。

時(shí)間估計(jì)模塊：主要包含數(shù)據(jù)裝載時(shí)間估計(jì)、繪制時(shí)間估計(jì)等功能，用于為最優(yōu)化繪制方案選擇模塊提供參考。

重要性估計(jì)模塊：計(jì)算調(diào)入場(chǎng)景中的每個(gè)模型的相對(duì)重要性程度，并把它作為在繪制時(shí)間不能滿足以最高細(xì)節(jié)繪制時(shí)選擇合適LOD級(jí)別的參考。

最優(yōu)化繪制方案選擇模塊：此模塊根據(jù)場(chǎng)景繪制的總時(shí)間和各個(gè)模型的繪制時(shí)間估計(jì)重要性計(jì)算的結(jié)果，在控制總繪制時(shí)間小于繪制時(shí)間預(yù)算的前提下，為每個(gè)模型選擇合適的LOD級(jí)別，以提供盡可能好的繪制效果。

繪制模塊：將確定需要繪制的模型數(shù)據(jù)進(jìn)行重組并進(jìn)行分類繪制。

性能檢測(cè)工具模塊：此模塊在每幀收集各項(xiàng)監(jiān)測(cè)數(shù)據(jù)，為時(shí)間估計(jì)模塊提供分析數(shù)據(jù)集。

2 基于時(shí)間估計(jì)和對(duì)象重要性的實(shí)時(shí)LOD選擇

在博物館場(chǎng)景模型的實(shí)時(shí)繪制過(guò)程中，為了提高實(shí)時(shí)性，方法之一我們必須對(duì)所要顯示的模型進(jìn)行不同LOD級(jí)別的選擇，而選擇哪個(gè)層次的模型則是由繪制該對(duì)象所需要的時(shí)間和對(duì)象的重要性來(lái)一起決定的[6]。在不同繪制時(shí)間和重要性的選擇下，做到繪制速度和顯示效果的最佳配置。

2.1 繪制時(shí)間估計(jì)

目前針對(duì)幾何對(duì)象繪制時(shí)間估計(jì)的研究大多數(shù)都是針對(duì)不含紋理的幾何模型。典型的有Funkhouser和Wimmer所作的研究[7]。Funkhouser：將繪制一個(gè)幾何模型的時(shí)間表達(dá)為一個(gè)包含頂點(diǎn)個(gè)數(shù)、三角形個(gè)數(shù)以及實(shí)際繪制的像素個(gè)數(shù)等3個(gè)因素的線性表達(dá)式，根據(jù)具體的實(shí)驗(yàn)?zāi)Ｐ蜏y(cè)試得出相應(yīng)表達(dá)式的系數(shù)；Wimme：指出Funkhouse的公式只是給出了繪制一個(gè)對(duì)象的時(shí)間下限，真實(shí)的繪制時(shí)間趨向于頂點(diǎn)轉(zhuǎn)換和柵格化的和，決定幾何傳輸時(shí)間的是真正轉(zhuǎn)換的頂點(diǎn)數(shù)量而不是僅僅所有頂點(diǎn)或多邊形的數(shù)量，因此，他提出了一個(gè)改進(jìn)公式，以轉(zhuǎn)換的頂點(diǎn)數(shù)及實(shí)際繪制的像素個(gè)數(shù)兩個(gè)因素的線性表達(dá)作為時(shí)間估計(jì)函數(shù)。由于此兩類方法都沒(méi)有考慮紋理數(shù)據(jù)傳輸所耗費(fèi)的時(shí)間，所以對(duì)于包含紋理對(duì)象的場(chǎng)景內(nèi)容不具備參考性和應(yīng)用性。

隨著人們對(duì)文物以及場(chǎng)景真實(shí)感期望的提高，紋理的使用率在博物館景模型的顯示中所占的比例越來(lái)越大。由于紋理數(shù)據(jù)分辨率的不斷提高，在三維顯示過(guò)程中，其數(shù)據(jù)轉(zhuǎn)換的時(shí)間以及在顯卡內(nèi)部的數(shù)據(jù)調(diào)度時(shí)間成為不可忽略的部分，嚴(yán)重時(shí)可以引起繪制流程的明顯停頓。所以要對(duì)博物館場(chǎng)景模型的繪制時(shí)間做出準(zhǔn)確的估計(jì)，就必須將紋理的顯示時(shí)間一起考慮進(jìn)去。

由于繪制整個(gè)場(chǎng)景的時(shí)間可以認(rèn)為是各個(gè)對(duì)象繪制時(shí)間的總和，因此可以對(duì)每個(gè)對(duì)象的繪制時(shí)間進(jìn)行考慮。本文將紋理量作為繪制時(shí)間時(shí)考慮的一個(gè)因素，認(rèn)為每個(gè)對(duì)象的繪制時(shí)間可以用如下公式表達(dá)：

其中，v_number表示當(dāng)前模型需要繪制頂點(diǎn)的個(gè)數(shù)；p_number表示該模型在屏幕上投影的像素?cái)?shù)；t_size表示在繪制此模型時(shí)所需要的紋理量；系數(shù)c1，c2，c3，c4則是表示不同的硬件和軟件環(huán)境。

2.2 對(duì)象重要性

在博物館場(chǎng)景模型繪制過(guò)程中，由于受時(shí)間限制不可能將所有的模型都按照最高細(xì)節(jié)層次進(jìn)行繪制，因此就需要對(duì)各個(gè)對(duì)象的繪制層次作出適當(dāng)?shù)倪x擇，這也是博物館場(chǎng)景模型限時(shí)自適應(yīng)LOD算法的核心問(wèn)題，如何在給定的時(shí)間預(yù)算內(nèi)，選擇合適的層次模型以達(dá)到最佳的可視效果。

在LOD管理中最重要的問(wèn)題是不同分辨率之間模型的切換。本文中用來(lái)決定LOD細(xì)節(jié)層次的因素主要有距離、偏心率、速度和投影大小等[8]。

距離(distance)：用距離來(lái)決定LOD的選擇是最簡(jiǎn)單直接的一種方法。當(dāng)視點(diǎn)與物體之間的距離在一定范圍內(nèi)時(shí)將采用高分辨率的LOD模型，當(dāng)視點(diǎn)與物體之間的距離在我們?cè)O(shè)定的范圍之外時(shí)采用低分辨率的模型。這里的距離既可以是視點(diǎn)與物體中心點(diǎn)之間的距離，也可以是視點(diǎn)與某一個(gè)指定的點(diǎn)之間的距離?；诰嚯x的LOD簡(jiǎn)單而且高效，只需要很少的條件表達(dá)式就可以確定一個(gè)距離是否超過(guò)了我們所設(shè)定的距離的閾值。但也存在明顯的缺陷：選擇物體內(nèi)的任意點(diǎn)來(lái)進(jìn)行所有的距離計(jì)算將產(chǎn)生不可避免的誤差；由于到視點(diǎn)的真實(shí)距離可能會(huì)根據(jù)方向而發(fā)生變化，這樣會(huì)導(dǎo)致明顯的視覺(jué)跳躍。因此，單一的距離并不能完全說(shuō)明對(duì)象的重要性。

偏心率(eccentricity)：偏心率是利用視點(diǎn)對(duì)超出視域中心區(qū)域的對(duì)象的感知能力遞減的特性來(lái)選擇LOD。視網(wǎng)膜的中心用來(lái)在固定的面積內(nèi)搜索高細(xì)節(jié)層次模型，而視網(wǎng)膜的邊緣被用來(lái)選擇下一個(gè)固定點(diǎn)的位置。據(jù)此可以將顯示區(qū)域分為兩個(gè)部分：一個(gè)是中間的高細(xì)節(jié)區(qū)域，對(duì)應(yīng)于視點(diǎn)可視域的中心位置；另一個(gè)是四周邊緣的簡(jiǎn)單細(xì)節(jié)區(qū)域，對(duì)應(yīng)于可視域的邊緣位置。經(jīng)驗(yàn)顯示減少周?chē)鷧^(qū)域的視覺(jué)復(fù)雜度并不會(huì)顯著影響視覺(jué)搜索任務(wù)的完成。這種邊緣遞減策略需要得到用戶當(dāng)前視線的方向，跟蹤頭部或眼睛的移動(dòng)，或者假設(shè)用戶一直注視著屏幕顯示區(qū)域的中心，所以也有一定的局限性。

速度(speed)：基于速度的LOD是指根據(jù)對(duì)象相對(duì)于視點(diǎn)的運(yùn)動(dòng)角速度來(lái)選擇LOD層次?？焖僖苿?dòng)穿過(guò)屏幕的對(duì)象表現(xiàn)出運(yùn)動(dòng)模糊，它們僅能在一個(gè)很短的時(shí)間內(nèi)被看到，用戶可能看不清楚它們，可以用較低分辨率的細(xì)節(jié)層次來(lái)表示，所以它可以作為判斷對(duì)象重要性的依據(jù)之一。

投影大小(area)：基于投影大小的方法利用一個(gè)物體投影到屏幕的大小來(lái)建立LOD的細(xì)節(jié)層次，它可以避免一些基于距離LOD的問(wèn)題，因?yàn)橥队按笮?duì)顯示分辨率、對(duì)象縮放或視角等的變化不是很敏感。而且，基于投影大小的LOD選擇使用整個(gè)對(duì)象而不是用戶選擇的一個(gè)任意點(diǎn)來(lái)進(jìn)行計(jì)算，因此比基于距離的LOD技術(shù)更準(zhǔn)確，更具有一般性。但是，基于投影大小的計(jì)算代價(jià)也要相對(duì)高一些，并且此方法不具有旋轉(zhuǎn)的不變性，即：當(dāng)一個(gè)很薄的對(duì)象旋轉(zhuǎn)時(shí)，其在屏幕上的投影大小會(huì)發(fā)生劇烈的變化，從而導(dǎo)致LOD的不穩(wěn)定或波動(dòng)。

本文根據(jù)以上4個(gè)因素來(lái)判斷對(duì)象的重要性，每個(gè)重要性因子都定義為0～1之間的數(shù)字，對(duì)象的重要性用這4個(gè)重要性因子的乘積來(lái)表示，表達(dá)式如下：

3 算法流程

在繪制時(shí)間受限的情況下，為了保證繪制時(shí)間不超出預(yù)算，并提供盡可能好的圖像質(zhì)量，因此需要合適的場(chǎng)景繪制選擇算法，以決定每個(gè)對(duì)象以何種LOD級(jí)別進(jìn)行繪制。在參考和對(duì)比已有相關(guān)算法的基礎(chǔ)上，本文根據(jù)博物館場(chǎng)景模型的繪制特點(diǎn)提出了一種基于繪制時(shí)間估計(jì)和對(duì)象重要性的LOD選擇方法。

在每幀進(jìn)行繪制前，首先對(duì)本幀要繪制的對(duì)象的LOD級(jí)別進(jìn)行選擇，首先計(jì)算本幀所有對(duì)象在現(xiàn)有LOD級(jí)別上的總的繪制時(shí)間，若開(kāi)始計(jì)算的時(shí)間超過(guò)了限定的時(shí)間，則按照對(duì)象重要性由小到大的排列，依次降低當(dāng)前對(duì)象的LOD級(jí)別，直到總的繪制時(shí)間在限定時(shí)間以內(nèi)，直到繪制結(jié)束；若小于限定時(shí)間，則根據(jù)對(duì)象重要性的大小在不超過(guò)限定時(shí)間的基礎(chǔ)上增加對(duì)象的LOD級(jí)別，直到繪制結(jié)束。整個(gè)過(guò)程的循環(huán)步驟如下：

步驟1：計(jì)算當(dāng)前幀中所有對(duì)象的LOD級(jí)別繪制的總的繪制時(shí)間；

步驟2：如果計(jì)算的總時(shí)間小于限定時(shí)間，則執(zhí)行步驟3，否則執(zhí)行步驟5 ；

步驟3：將各個(gè)對(duì)象按照重要性大小順序進(jìn)行排列，按順序?qū)γ總€(gè)對(duì)象執(zhí)行步驟4，完成后結(jié)束繪制；

步驟4：當(dāng)對(duì)象的當(dāng)前LOD級(jí)別低于最佳級(jí)別時(shí)，增加此對(duì)象的LOD級(jí)別后在不會(huì)超出限定的繪制時(shí)間要求內(nèi)，則逐級(jí)增加此對(duì)象的LOD級(jí)別；

步驟5：將各個(gè)對(duì)象按照重要性大小反向排列，按順序?qū)γ總€(gè)對(duì)象執(zhí)行步驟6,完成后結(jié)束繪制。

步驟6：當(dāng)對(duì)象的當(dāng)前LOD級(jí)別高于最低級(jí)別限制時(shí)，降低此對(duì)象的LOD級(jí)別，直到總的繪制時(shí)間小于限定時(shí)間。

圖2為限時(shí)繪制的步驟示意圖。

圖2 限時(shí)繪制的步驟示意圖

4 實(shí)驗(yàn)結(jié)果和性能分析

在固定視角情況下，人眼對(duì)25幀以上的顯示速度已經(jīng)沒(méi)有察覺(jué)(如電視、電影)，但是對(duì)于快速變換的視角而言，顯示速度一般要求在30幀以上。所以，評(píng)價(jià)顯示性能不僅要看顯示的圖像質(zhì)量，也要看顯示的速度。幀數(shù)(fps)就是衡量顯示速度的指標(biāo)。實(shí)驗(yàn)中得出以下數(shù)據(jù)（見(jiàn)表1），在較高的LOD層次上，漸進(jìn)網(wǎng)格的算法速度比較快，對(duì)于60000多個(gè)面片的模型，幀數(shù)都能在50幀以上。隨著層次的增加，幀數(shù)越高，說(shuō)明三角形的查找速度仍然是比較快的?？紤]到查找線性表要消耗一部分時(shí)間，從較高的層次突進(jìn)到較低層次，顯示速度會(huì)暫時(shí)出現(xiàn)一些下降，但由于該算法中三角形在線性表中是順序排列的，所以速度的下降不是很明顯，對(duì)于實(shí)時(shí)顯示而言算法效率是比較高的。

另外，對(duì)于原來(lái)的未采用該算法的模型顯示速度來(lái)說(shuō)，盡管顯示速度上與采用該算法的模型沒(méi)有太大的區(qū)別，甚至在某些層次顯示速度還略高一些，但是這些模型所占用的存貯量是很大的（見(jiàn)表2），尤其在簡(jiǎn)化層次多的時(shí)候，采用增加空間復(fù)雜度來(lái)減少時(shí)間復(fù)雜度的方法，這對(duì)于存儲(chǔ)空間來(lái)講是很大的浪費(fèi)。那么在顯示速度差不多的情況下，漸進(jìn)網(wǎng)格可以減少存儲(chǔ)量，可以在時(shí)間和空間上達(dá)到一個(gè)平衡。

表1 LOD漸進(jìn)網(wǎng)格不同層次的顯示速度

表2 不同層次的三角形面片數(shù)量

圖3表明隨著模型與攝像機(jī)之間的距離的變化，漸進(jìn)網(wǎng)格用了不同分辨率的網(wǎng)格，較遠(yuǎn)距離使用的網(wǎng)格數(shù)目是130，而距離最近的網(wǎng)格數(shù)目是8040，但是從視覺(jué)角度上不太能察覺(jué)模型的明顯變化。

圖3 LOD漸進(jìn)網(wǎng)格的實(shí)驗(yàn)顯示

5 結(jié)論

在博物館場(chǎng)景模型在線實(shí)時(shí)可視化方法中，本文提出了一種限時(shí)自適應(yīng)LOD方法，分析了其中嚴(yán)重影響繪制幀率的數(shù)據(jù)裝載和繪制工作量的因素，并從數(shù)據(jù)量的角度對(duì)繪制時(shí)間進(jìn)行分析，將每個(gè)對(duì)象的繪制時(shí)間預(yù)先估計(jì)，根據(jù)對(duì)象的重要性來(lái)選擇幀內(nèi)每個(gè)對(duì)象的LOD級(jí)別。在對(duì)對(duì)象的繪制時(shí)間進(jìn)行估計(jì)時(shí)，將紋理數(shù)據(jù)一起考慮，更加符合實(shí)時(shí)漫游的現(xiàn)實(shí)情況。

[1] 祝清魯．大規(guī)模場(chǎng)景中LOD的技術(shù)研究與應(yīng)用[D]．北京:北京郵電大學(xué),2009．

[2] 羅丹．?dāng)?shù)字城市模型自適應(yīng)相關(guān)LOD技術(shù)研究[D]．武漢:華中師范大學(xué),2009．

[3] 沙從術(shù)．LOD 技術(shù)在三維地形圖實(shí)時(shí)可視化中的應(yīng)用研究[J]．價(jià)值工程,2011,22(1):154-155．

[4] J．Airey,J．Rohlfetc．Towards Image Realism with Interactive Update Rates in Complex Virtual Buliding Environments[J]．Computer Graphics,ACM,1990,24(2):41-50．

[5] 朱濤．虛擬現(xiàn)實(shí)中場(chǎng)景建模技術(shù)的研究及應(yīng)用[D]．武漢:武漢理工大學(xué),2010．

[6] Rossignac J．,Bowel P． Multi-resolution 3D approximation for rendering complex seenes[A]． Proeeedings of the 20th Conference Modeling in Computer GraPhic [C]．Berlin,1993:453-465．

[7] 郭陽(yáng)明,翟正軍．虛擬場(chǎng)景生成中的LOD技術(shù)綜述[J]．計(jì)算機(jī)仿真,2005,22(12):180-183．

[8] 崔鐳．虛擬現(xiàn)實(shí)中LOD技術(shù)的研究[D]．西安:西安電子科技大學(xué),2008．