低復雜度高度場的通視性研究及快速光照計算

李 華, 楊華民, 趙建平

(長春理工大學 計算機科學技術學院, 長春 130022)

0 引 言

高度場也稱2～1/2維表面, 在地理信息、 模擬仿真和3D游戲等方面有廣泛的應用。近些年, 高度場的實時高真實感繪制已成為計算機圖形學和虛擬現(xiàn)實研究重點之一。在交互可視化時, 高度場互見性的計算需要判斷每一點對場景內(nèi)其他所有點的可見性, 計算量大, 有局限性, 基于物理特性的可見性判斷更加復雜。在軍事、 通訊等方面高度場的通視性檢測及應用也非常廣泛。通過對高度場場景模型增加光照和陰影效果, 為視覺觀察提供了關鍵線索。如高大的建筑物或山峰離地面的高度和幾何關系等。

高度場正確的物理關系繪制和模擬, 主要依靠判斷場景點間的遮擋關系。在真實感渲染技術中, 可見性算法主要有兩方面應用： 幾何面的剔除和光照計算。前者用于加速渲染管線的計算效率, 后者用于確定場景表面點的亮度。一般情況下, 場景中任意一點都可作為光源影響其他場景點, 因此, 全局光照要考慮場景內(nèi)每一點接收所有光源的光照, 計算量相當巨大。在靜態(tài)幾何體光照計算中可通過預計算的方式預先確定可見面片, 以降低計算復雜性, 但對動態(tài)場景的幾何體的計算卻是個復雜問題。因為每幀畫面隨著相對位置發(fā)生變化, 可見性的判斷需要重新進行, 這大大增加了計算復雜性和成本。

1 高度場可見性

高度場可見性判別需計算來自各個方向上的頂點的遮擋關系。MAX[1]利用各方向的水平輪廓信息構造地平線地圖, 實現(xiàn)凸凹映射表面的硬陰影計算, 該算法已應用于靜態(tài)高度場的實時繪制中。近些年, 學者們提出了一些實時動態(tài)的高度場計算的方法, 通過采樣高度場在各個方向角上的頂點信息, 找到主要的遮蔽體, 進而獲得近似軟硬陰影[2,3]。對于一個尺寸為N×N的高度場地圖, 如果一個方位角方向的所有高度場點都被認為是接收點, 計算的時間復雜度將達到O(N3)。為降低計算復雜性, 對不同方向角以不同采樣分辨率采樣, 可以適應場景的不同復雜度, 但僅適合于近似計算軟陰影效果,而不能實現(xiàn)高分辨率的高度場場景計算。Ville等[4]提出沿方位角方向利用相鄰采樣點之間的一致性關系, 計算高度場在任何給定的方向上所有點的視界角, 可以把計算復雜性降為O(N2)。Dimitrov等[5]提出將陰影圖中的深度緩沖區(qū)信息作為高度場信息, 近似計算環(huán)境光遮蔽。由于深度緩沖區(qū)的信息是幾何可見性信息的子集, 所以, 這些方法只能通過抽樣計算局部近似遮擋關系, 這種近似計算, 適合于擴展到計算屏幕空間的環(huán)境光遮蔽的直接光照和間接光照計算。

低復雜度高度場由于其特殊的形式, 使可見點的數(shù)量相對于場景點的數(shù)量大大減少,Ville[6]研究了地形、 磚墻表面、 網(wǎng)格以及街區(qū)塊模型4種高度場圖(見圖1)在某個方向角的可見比例, 對于一個1 0242的高度場圖, 沿其中一個方向的可見度比例最大為5.6%, 最小為1.1%。足以計算半鏡面反射及自發(fā)光表面的光照效果。凸包樹的構建、 存儲和搜索效率較低, 確定一種簡化的可見點查找和存儲結構, 將能大大提高通視性判斷和光照計算效率。

a 地形 b 磚墻表面 c 網(wǎng)格 d 街區(qū)塊模型

2 凸包樹策略及轉化

圖2 掃描方向示意圖

場景剖面掃描可以用一棵樹的形式表述, 如圖3所示。該存儲結構記錄了高度場中每個場景點的方向可見點, 且水平高度角度最大的可見點在凸包樹中深度即該點的方向視界邊界。筆者依據(jù)該思想, 提出一個基于凸包樹搜索的可見性判別算法, 建立基于頂點的可見性二叉樹并進行線索化, 作為高度場的光照計算依據(jù), 當光源及視角位置變化時, 通過快速查找可見性樹表索引獲得遮擋信息。

2.1 線性掃描

圖3 高度場剖面圖

高度場數(shù)據(jù)是以網(wǎng)格形式給出的, 即對于N×N高度場中一點(x,y)為平面坐標,z為高度值, 該算法的輸入數(shù)據(jù)為頂點坐標和高度。觀察點或光源的位置任意, 因此, 需要對場景中每一點確定其可見范圍。沿著某一方向掃描高度場地圖, 能在線性的時間內(nèi)獲得水平高度角信息, 進而判斷可見片段。

由于高度場數(shù)據(jù)受到其特殊屬性的限制(見圖3), 掃描線將2.5維信息降解成1.5維切片。

圖4 方位角度接收點x的水平高度角

2.2 水平方位角計算

在3D場景內(nèi), 要確定表面一點P=(x,y,f(x,y))的可見范圍, 需要已知P點在各個方向上的水平高度角。φ方向上的參數(shù)化坐標值為(cosφ,sinφ), 其中φ∈[0,2π]。可見性被表示為P從地平線達到最大仰角, 叫φ方向水平高度角, 也稱為視界角[5]。設任一點p(x,f(x))φ方向的視界角為ω(x,φ), 在高度角小于ω的位置, 被遮擋而無法看到更遠處(見圖4)。

ω(x,φ)定義為

(1)

其中t表示沿著φ方向遠離x點的水平距離, 反正弦函數(shù)是單調(diào)函數(shù)。視界角ω如果為0, 表面本身沒有任何遮擋,ω大于π/2時被自身遮擋。

2.3 凸包遍歷樹

高度值相鄰的兩個點中, 只有當Pi+1的高度大于Pi時,Pi+1才可見。因此, 掃描遍歷所有t∈(0,∞)才是最有效的方法, 遍歷樹如圖5所示。

圖5 凸包樹

2.4 凸包樹搜索及可見性二叉樹

凸包樹搜索及流程如圖6所示。

圖6 凸包樹搜索流程圖

凸包樹型結構轉化成對應的可見性二叉樹及線索化, 可以提高搜索速度。該二叉樹以掃描起始頂點為根節(jié)點P0, 加入新的頂點P1, 計算新頂點P1的水平方向角β1, 加入新頂點P2, 連接頂點P2的水平方向角β2, 若β2>β1, 則更新當前最大水平方向角Max, 同時P2可見, 若β2<β1, 則P2對P0不可見。不可見以后若出現(xiàn)再次大于最大水平方向角的新頂點Pi, 則Pi對應片段為可見體。依次類推, 最終完成可見性二叉樹搜索。 從掃描起點, 每條掃描線對應一個二叉樹存儲表, 用來檢索可見頂點。由于通視性具有相互性, 所以為了便于反向掃描, 需將二叉樹先序線索化, 以便查找雙親節(jié)點。該結構實現(xiàn)了從場景點內(nèi)任一點觀察, 周圍高度場的可見性信息均可從可見性二叉樹進行查詢。

高度場的互見性應用范圍廣泛, 如, 通信節(jié)點或衛(wèi)星的覆蓋范圍及最佳位置判斷、 虛擬場景真實感繪制和3D場景的交互式應用等。為了驗證互見性判斷效果, 筆者模擬高度場的全局光照的計算, 忽略一次間接光照的可見性判斷, 實現(xiàn)高度場的光照效果繪制。

3 高度場光照及陰影計算

高度場數(shù)據(jù)圖的光照效果主要是自陰影和間接光照, 為快速計算可接受的模擬效果, 忽略間接光照的遮擋關系[7], 場景的直接光照通過渲染方程實現(xiàn)。場景內(nèi)一點P的光照強度L0的計算可表示為

(2)

在點光源情況下,

L0(p,ω)=fr(p,ω,p→L)Le(L,L→p)G(p,L)V(p,L)

(3)

若場景中任意兩點的可見性已知, 則問題的關鍵即可解決。筆者結合陰影圖實現(xiàn)動態(tài)低復雜度高度場的陰影計算和近似光照效果。高度場的數(shù)據(jù)存儲在N×N的二維數(shù)組中, 對于點X(x,y,z),N×N的二維數(shù)組確定位置(x,y), 其z值為高度值, 從光源視角位置計算光源到場景中每一點的深度, 根據(jù)交點坐標與各可見點確定光照可見點。高度場標量函數(shù)f(x)=f(x,y), 對于3D場景內(nèi)一點p(x,y,f(x,y))的軟陰影計算, 需要計算p點所有方向上可見點ρ, 最終p點的亮度由各可見點累加獲得

Lp=∑ρ

(4)

4 實驗效果

該實驗環(huán)境為處理器Intel(R)Xeon(R) CPU E5620@雙核2.40 GHz, 顯卡NVIDIA Quadro 4000。繪制的高度場模型如圖7所示, 場景幀率如表1所示。

a 圓錐1 b 圓錐2 c 圓錐3

d 山峰1 e 山峰2 f 山峰3

表1 場景幀率

5 結 語

筆者通過線性掃描并存儲方位角信息, 可以快速獲得可見高度場頂點, 運用在陰影圖中進行低分辨率采樣, 該實驗實現(xiàn)了近似高度場繪制的交互式幀率, 對動態(tài)場景和交互式應用提供了依據(jù)和保障。從表1可以看出, 在動態(tài)光源下, 高度場的繪制達到交互式幀率, 實現(xiàn)了對地復雜度高度場的可見性判斷, 并形成光照及陰影。

真實感繪制隨著GPU技術和并行編程的發(fā)展, 在今后的工作中將對線性掃描的并行化改進及基于CPU-GPU的異構編程將做進一步研究。

參考文獻：

[1]MAX N: Horizon Mapping: Shadows for Bump-Mappedsurfaces [J]. The Visual Computer, 1988, 4(2): 109-117.

[2]SNYDER J, NOWROUZEZAHRAI D. Fast Soft Shadows on Height Fields via Multi-Resolution Image Processing. Tech Rep MSR-TR-2008-77, Microsoft Corporation [EB/OL]. (2013-05-17). http:∥researh.microsoft.com/apps/pubs/default.aspx?id=70587.

[3]NOWROUZEZAHRAI D, SNYDER J. Fast Global Illumination on Dyna Height Fields [J]. Computer Graphics Forum: Eurographics Symposium on Rendering, 2009, 28(4): 1131-1139.

[4]VILLE TIMONEN, JANWESTERHOLM. Scalable Height Field Self-Shadowing [J]. Computer Graphics Forum, 2010, 29 (2): 723-731.

[5]DIMITROV R, BAVOIL L, SAINZ M. Horizon-Split Ambient Occlusion [C]∥SI3D’08: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games (2008). New York, NY, USA: ACM, 2008: 178-192.

[6]VILLE TIMONEN. Low-Complexity Intervisibility in Height Fields [C]∥Computer Graphics Forum (Volume 0) 2012, 36(2): 1-14.

[7]DACHSBACHER C, STAMMINGER M. Reflective Shadow Maps [C]∥Proceedings of the 2005 Symposium on Interactive 3D Graphics and Games. New York, NY, USA: ACM Press, 2005: 203-231.