一種解決全球地形繪制抖動問題的方法

引 言

抖動問題是像星球仿真、物理計(jì)算仿真、大規(guī)模軍事仿真系統(tǒng)等大型虛擬環(huán)境中一個非常棘手的問題[1]。它會導(dǎo)致繪制場景時，出現(xiàn)物體一部分被莫名其妙地裁剪掉，三角網(wǎng)格破碎，紋理錯亂等錯誤現(xiàn)象。全球地形環(huán)境是一個典型的大規(guī)模虛擬環(huán)境，也會遇到抖動問題。特別是在繪制米級高分辨率地面時，抖動問題特別明顯，嚴(yán)重削弱地形的繪制效果[2]。

抖動問題是由于浮點(diǎn)數(shù)舍入誤差過大所造成的[3]。目前解決全球地形環(huán)境中抖動問題的方法有兩種：多局部坐標(biāo)系統(tǒng)方法和動態(tài)局部坐標(biāo)系統(tǒng)方法。多局部坐標(biāo)系統(tǒng)方法為每個地形塊都建立一個局部坐標(biāo)系統(tǒng)，每塊的地形頂點(diǎn)都在自己的局部坐標(biāo)系統(tǒng)中繪制，從而減小頂點(diǎn)的浮點(diǎn)數(shù)誤差，避免抖動現(xiàn)象的出現(xiàn)[2,3]。然而這種方法會破壞全球統(tǒng)一的地理坐標(biāo)系統(tǒng)，而且還會帶來多坐標(biāo)系統(tǒng)導(dǎo)致的各種問題[4,5]。動態(tài)局部坐標(biāo)系統(tǒng)方法只需建立一個動態(tài)的局部坐標(biāo)系統(tǒng)，該坐標(biāo)系統(tǒng)的原點(diǎn)隨著視點(diǎn)變化而變化，場景中所有物體都在這個局部坐標(biāo)系統(tǒng)中定義[1,5,6,8,9]。由于場景中物體一般都離視點(diǎn)不遠(yuǎn)(如果太遠(yuǎn)，會被視錐體裁減掉)，所以物體坐標(biāo)的浮點(diǎn)數(shù)誤差一般不大，因此避免抖動現(xiàn)象的出現(xiàn)。然而目前的動態(tài)局部坐標(biāo)系統(tǒng)方法都有各自的問題。微軟 Flight Simulator[5]采用動態(tài)局部坐標(biāo)系統(tǒng)進(jìn)行反抖動，但并沒有介紹如何設(shè)置局部坐標(biāo)系統(tǒng)的原點(diǎn)，只是定期地更新原點(diǎn)。如果視點(diǎn)移動速度很快，地形塊遠(yuǎn)離上次更新的原點(diǎn)，同樣會出現(xiàn)抖動現(xiàn)象。GeoVRML[6]使用GeoOrigin 設(shè)置原點(diǎn)建立動態(tài)局部坐標(biāo)系統(tǒng)，但不能阻止用戶錯誤地設(shè)置原點(diǎn)，例如設(shè)置原點(diǎn)遠(yuǎn)離視點(diǎn)，仍然會導(dǎo)致抖動現(xiàn)象[1]。另外它對自由導(dǎo)航?jīng)]有做任何處理，也會出現(xiàn)嚴(yán)重的抖動問題[1]。雖然基于GeoVRML 的 TerraVision[7]對自由導(dǎo)航采用周期地將原點(diǎn)歸位于視點(diǎn)，仍會遇到微軟Flight Simulator 中視點(diǎn)移動過快時出現(xiàn)的問題。Java3D[8]雖然可以使用場景(locale)坐標(biāo)系統(tǒng)作為動態(tài)局部坐標(biāo)系統(tǒng)，也會遇到和GeoVRML 一樣的問題。 O'Neil [9]，Throne[1]和Lambers[10]以視點(diǎn)為原點(diǎn)建立動態(tài)局部坐標(biāo)系統(tǒng)，但是視點(diǎn)卻不是全球地形環(huán)境中動態(tài)局部坐標(biāo)系統(tǒng)原點(diǎn)的最佳選擇。

本文在目前動態(tài)局部坐標(biāo)系統(tǒng)方法的基礎(chǔ)上，提出一種新的更適合全球地形環(huán)境的反抖動方法。這種方法選擇視點(diǎn)在球面上的投影點(diǎn)代替視點(diǎn)作為局部坐標(biāo)系統(tǒng)的原點(diǎn)。該方法既能避免多局部坐標(biāo)系統(tǒng)方法帶來的各種問題，又能保證在任何情況下都不會出現(xiàn)抖動現(xiàn)象，同時比以視點(diǎn)為原點(diǎn)的動態(tài)局部坐標(biāo)系統(tǒng)方法有更好地反抖動效果。

1 全球地形數(shù)據(jù)組織

為了平衡全球海量地形的渲染質(zhì)量和速度，一般采用面向全球的多分辨率金字塔模型來組織地形[11]。這種技術(shù)把全球地形按經(jīng)緯度分成不同的層和塊，如圖1 所示。全球地形數(shù)據(jù)在預(yù)處理階段分成小塊的地形數(shù)據(jù)塊存儲起來。無論地形塊結(jié)構(gòu)是規(guī)則網(wǎng)格還是不規(guī)則三角網(wǎng)，都使用保存在文件中的對應(yīng)地形數(shù)據(jù)塊來構(gòu)建地形網(wǎng)格。所有地形塊的地形網(wǎng)格連在一起，就構(gòu)成全球地形網(wǎng)格。當(dāng)視點(diǎn)移動時，需要將已經(jīng)不在視錐體內(nèi)的地形塊從內(nèi)存中卸載，并用新的地形塊替換。當(dāng)視點(diǎn)向地球靠近時，使用精細(xì)的地形塊替換粗糙的地形塊。相反地，當(dāng)視點(diǎn)離開地球時，使用粗糙的地形塊替換精細(xì)的地形塊。

2 浮點(diǎn)數(shù)舍入誤差與抖動問題的成因

舍入誤差是量化誤差的一種形式[12]，是運(yùn)算得到的近似值和精確值之間的差值。當(dāng)使用有限位數(shù)的浮點(diǎn)數(shù)(理論上存在無限位數(shù)的浮點(diǎn)數(shù))來表示實(shí)數(shù)的時候，就會產(chǎn)生浮點(diǎn)數(shù)舍入誤差。由于舍入誤差的存在，所以計(jì)算機(jī)系統(tǒng)并不能精確表達(dá)所有實(shí)數(shù)。例如十進(jìn)制實(shí)數(shù) 0.25 能被計(jì)算機(jī)系統(tǒng)精確表達(dá)，即(0.25)10 = (0.01)2 ，此時不存在舍入誤差;但是實(shí)數(shù) 0.1 就不能被計(jì) 算機(jī)系統(tǒng)精 確表達(dá)，即(0.1)10 = (0.000110011...)2 ，此時存在舍入誤差。假定浮點(diǎn)數(shù)x 的舍入誤差為?x ，有效數(shù)字位數(shù)為t，則浮點(diǎn)數(shù)的舍入誤差可以通過公式(1)計(jì)算出來[12]：