周圣川， 胡振彪， 馬純永， 陳　戈

(1.青島市勘察測繪研究院，山東 青島 266033; 2.海陸地理信息集成與應用國家與地方聯(lián)合工程研究中心，山東 青島 266033;

3.中國海洋大學信息科學與工程學院，山東 青島 266100)

?

海濱城市三維場景的混合圖元渲染方法*

周圣川1，2， 胡振彪1，2， 馬純永3， 陳戈3

(1.青島市勘察測繪研究院，山東 青島 266033; 2.海陸地理信息集成與應用國家與地方聯(lián)合工程研究中心，山東 青島 266033;

3.中國海洋大學信息科學與工程學院，山東 青島 266100)

摘要：本文提出一種適用于海陸一體場景的大規(guī)模城市三維可視化方法。使用多重抖動采樣和顏色聚類算法將城市三維模型轉換為由點、線等簡單圖元構成的層次細節(jié)模型，通過屏幕空間投影面積進行層次細節(jié)(Level-of-detail，LOD)模型的選擇，以較少數量的簡單圖元合成模型的近似表示，實現城市建筑的LOD渲染。實驗表明，該方法具有較高的真實感，可以大幅提高城市級大場景的渲染效率，并且與幾何LOD等方法相比，其性能受水體模型渲染的影響更小，更適用于海陸一體的海濱城市場景渲染。

關鍵詞：層次細節(jié)模型；混合渲染；海濱城市可視化；虛擬現實

盡管經歷了多年的研究和產業(yè)化應用，大規(guī)模城市三維場景的實時可視化渲染仍然是一個亟需解決的瓶頸問題。尤其是在海濱城市可視化方面，由于要同時進行水體和城市模型的渲染，數據和算法復雜度極高，因此難以實現交互式或者實時的大規(guī)模場景渲染。目前，在大規(guī)模城市三維可視化系統(tǒng)中廣泛采用和研究的技術主要有幾何LOD模型[1-2]、Out-of-Core[3-5]，以及Relief Map、Block Map等基于圖像的渲染[6-9]技術。以上方法雖然可以實現大規(guī)模城市三維場景的可視化，但是不可避免地會引入幾何形變、平行視差，以及可見性不完整等視覺精度上的損失。同時，上述方法也都使用了與水體渲染[10]相同的三角網格加紋理的數據模型，空間復雜度高，在疊加大規(guī)模水體渲染時，性能往往呈現非線性下降。

本文提出一種基于混合圖元的層次細節(jié)模型，將距離視點較遠的三維模型轉換為由點和直線等簡單離散圖元構成的LOD近似表示，以提高復雜城市模型的渲染性能。通過計算輸入模型的屏幕空間投影面積精確地選擇LOD模型中離散圖元的數量，在提高渲染性能的同時保證LOD模型與輸入模型視覺上的一致性,從而解決大規(guī)模城市三維場景可視化中常見的渲染數據復雜度過高，以及渲染視覺質量損失等問題。該方法在包含大規(guī)模水體的濱海城市場景中，受水體渲染的性能影響更小，更適用于海陸一體城市場景的渲染。

1混合LOD模型構建

本文基于人眼視覺對邊緣極度敏感的原理[11]提出一種混合圖元渲染方法。城市三維場景，尤其是現代城市場景，由大量的建筑組成，并且這些建筑和周邊環(huán)境之間有著較為明顯的邊界。建筑的邊界一般是由包含多種顏色的直線段構成。因此，傳統(tǒng)的LOD方法，通常會在原本應保持幾何連續(xù)性的模型邊界上產生不連續(xù)的噪聲圖元和鋸齒。另一方面，距離視點較遠的模型經過透視投影變換之后，一般在最終的渲染緩沖區(qū)中僅表示為少量的像素點。因為人眼的視覺對邊緣極度敏感，而直線段的三維渲染結果具有良好的抗鋸齒與反走樣性質，且線段、點等離散圖元在渲染過程中像素大小固定，不受投影變換影響，具有很好的著色填充性質。所以，在距離視點較遠時，三維模型可以使用極少量的點和直線段，甚至可以只使用直線段進行近似表示。點和直線段作為離散的圖元具有獨立的顏色屬性，可以不通過紋理映射進行著色，在降低顯存消耗的同時均衡GPU的負載，提高海陸一體場景的整體渲染性能。

1.1 點圖元采樣

點圖元采樣的目的是生成基于點的三維模型表示。點圖元是三維圖形學理論中最簡單的渲染圖元類型，因為其結構簡單，所以具有比常用的三角網格圖元更好的渲染性能。具有良好視覺質量的基于點的三維模型表示應該具有以下性質：(1)點圖元均勻地分布在模型表面；(2)采樣算法能夠將低頻失真轉為高頻特征，避免產生鋸齒等噪聲；(3)構成層次細節(jié)模型的采樣點子序列不應該違反性質(1)和(2)；(4)城市三維場景的數據量巨大，點模型的采樣應該具有較高的效率。

如圖1所示，本文使用多重抖動采樣生成具有上述特征的點模型。首先在多邊形上進行多分辨率的網格劃分，然后進行采樣。采樣的過程遵循N-rooks條件，即：隨機在網格中進行采樣點選擇，任意2個同層級的采樣點處于不同的網格行或者列上。采樣點的顏色通過紋理映射獲得，每個采樣點對應的網格層級編號作為屬性保存并用于創(chuàng)建層次細節(jié)模型。

圖1　多重抖動點圖元采樣

1.2 線圖元采樣

單一的基于點的模型一般不適用于表示城市建筑等具有大量低頻幾何結構以及明顯的幾何邊界的三維模型，所以本文引入了點、線等多種圖元混合的三維模型表示方法。

線模型的構建以多邊形之間的夾角進行判斷。如果2個鄰接多邊形之間的角度不為180°，那么鄰接的邊即被提取出進行采樣，作為建筑模型的邊界。提取出的直線使用在直線上出現次數最多的顏色進行著色。

圖2　基于顏色聚類的線模型采樣

此外，需要注意的一種情況是在一條幾何邊上可能出現如圖2所示的顏色變化。此時，本文通過分析幾何邊上的顏色著色梯度，提取顏色變化的關鍵點，將完整的幾何邊細分為使用不同顏色著色的子線條。

首先，使用如下公式將紋理由RBG色域轉換到L×a×b色域：

X=0.412 453×R+0.357 580×G+0.180 423×B，

Y=0.212 671×R+0.715 160×G+0.072 169×B，

Z=0.019 334×R+0.119 193×G+0.950 227×B，

L*=116×f(Y/YN)-16，

a*=500×[f(X/XN)-f(Y/YN)]，

b*=200×[f(Y/YN)-f(Z/ZN)]，

其中：

在L×a×b色域中，像素點之間的視覺感知差異與色彩值成正相關，可以通過三維歐氏距離計算得出。本文首先使用一個一維的高斯濾波器對幾何邊上的所有像素點進行平滑濾波處理，過濾紋理圖像中的高頻噪聲信號；然后，使用一維卷積核[-1,0,1]在幾何邊上進行逐像素的濾波，通過對比相鄰像素的視覺差異提取顏色聚類。如圖2所示，經過以上操作，顏色聚類之間的分界點，也就是子線段的頂點，對應卷積操作后像素值序列中的極大值點。通過上述操作可以將提取出的三維對象幾何邊界按照著色變化分割成更為精確的子線段。

2混合LOD模型構建

2.1 點圖元排序

本文通過對點序列重新排序，生成一個支持漸進層次細節(jié)變換的點序列。該序列的任意前綴子序列都是原始模型的一個層次細節(jié)模型。這樣，就可以通過三維模型的投影面積，在LOD選擇階段生成不同視距下的三維模型多分辨率表示。

如前文所述，對于使用多重抖動采樣方法生成的點云三維模型，在進行采樣時每一個點樣本都被賦予了層級索引值，使采樣生成的點序列具有了漸近層次細節(jié)特征。本文進一步地對采樣的結果按照層級索引值的升序進行排序，使最終的點序列中任意長度的前綴子序列都構成一個三維模型的層次細節(jié)表示。為了保證同一層級采樣點分布的均勻性，對具有相同層級索引值的采樣點使用洗牌算法進行了局部重排列。

2.2 線圖元排序

類似的，對線模型進行重排序的目的是生成一個支持多分辨率層次細節(jié)變換的線序列。在線模型的生成過程中，產生了2種不同的線段模型——完整的幾何邊緣線段和按照顏色聚類細分的子線段。線段模型可以用于加強模型的幾何邊緣，消除點渲染結果中的鋸齒等噪聲，同時減少渲染的點圖元數量。完整的幾何邊緣線段可以直接在模型距離視點較遠時作為層次細節(jié)模型使用；在模型距離視點較近時，使用精確著色的分割線段逐漸替換完整的幾何邊緣線段可以明顯地改善圖像質量，實現混合圖元表示的反走樣。構建基于線的連續(xù)層次細節(jié)模型就是創(chuàng)建一種用于存儲線段模型的LOD數據結構，該數據結構可以實現連續(xù)地、動態(tài)地使用分割子線段替換對應的完整幾何邊緣線段，實現基于線的LOD模型選擇和切換。

本文將完整的幾何邊緣線段與分割子線段分別存儲于2個順序結構中，其中每一個完整線段分配一個唯一的索引ID并使用順序隊列存儲；所有的分割線段按照其從屬關系構成集合，每一個線段集合和其對應的完整線段具有相同的ID，并使用如圖3所示的線性表結構進行存儲。為了避免深度值沖突(Z-Fighting)造成的渲染圖形閃爍，本文采取的替換策略是，對于任意一個完整線段，其對應的分割線段集合中有任一子線段可見，則將該完整線段設為不可見，對應的所有分割子線段設為可見；當一個完整線段的所有分割子線段均不見時，使用完整的幾何線段進行渲染，所有的分割子線段不進行渲染處理。

圖3　線模型數據結構

為了實現動態(tài)的層次細節(jié)模型切換，對每一個分割線段集合，本文提取其中最長的子分割線段的長度作為排序的鍵值；然后，使用排序算法按照升序對存儲分割線段集合的順序表進行排序；在排序后，通過索引ID對存儲完整線段的順序表進行重排列，使每一個完整線段和其對應的分割線段集合在順序表中的索引ID一致，即具有相同的線性表下標值或索引值。通過上述重排列算法，在可視化過程中如果從完整線段順序表中提取了一個前綴子序列進行渲染，可以在分割子線段集合順序表中選擇對應的后綴序列進行渲染，從而在實現渲染精度動態(tài)變化的同時避免分割子線段和完整線段之間的重疊。

假設一個三維模型可以由N條完整邊緣線段近似表示，則本文中構建的基于線的層次細節(jié)模型中包含了i,i∈[0,N]個細節(jié)層次；其中，第級的層次細節(jié)模型由完整線段順序表中的前N-i條幾何邊緣線段，和子分割線段集合順序表中的后i個集合元素中的所有子分割線段構成。

本文構建的LOD數據結構可以直接編譯成OpenGL中的頂點緩沖區(qū)對象或者頂點數組對象，所以LOD模型的選擇和渲染都可以通過1～2個OpenGL渲染函數調用完成，具有極高的效率。

3混合LOD模型渲染

通過對點、線圖元的采樣和排列組織，本文構建了基于點、線圖元的連續(xù)層次細節(jié)數據模型。上述模型提供了極具伸縮性的LOD性質與數據存儲結構，可以用于實時LOD模型渲染。在渲染過程中，通過自適應地確定需要的點和線圖元數量，從預處理好的點、線序列中選擇相應的子序列構成輸入模型的層次細節(jié)表示，進行高性能的可視化輸出。

3.1 線圖元渲染

線模型可以生成平滑的模型輪廓，并在模型距離視點較遠時實現無縫渲染。對于分割線段集合元素，當其中最長的子分割直線段可見，也就是投影面積大于1個像素時進行渲染，否則使用對應的完整直線段進行渲染。本文中線段的渲染寬度都設置為1像素，所以線段的投影面積可以使用線段的投影長度近似表示。

假設三維模型的近似表示由直線段集合L構成，集合中線段L的長度為li，線段所覆蓋的模型投影面積可以通過如下公式求解：

則說明線模型能夠完整覆蓋模型的表面，構成無縫的模型近似表示；反之，需要在線段之間增加點圖元，填充未被直線覆蓋的區(qū)域。

3.2 點圖元渲染

點模型可以在近距離渲染時填充線段之間的空隙并提供模型表面的著色細節(jié)。具體方法是在線模型渲染后，計算完全覆蓋模型表面所需要的點數量，從點模型的存儲序列中選取對應的前綴子序列傳入渲染管線。

在求出無縫渲染所需的點數量后，從經過預處理和重排序的點序列中選取前np個點進行渲染就可以得到無縫的三維模型層次細節(jié)表示。

3.3 曲面細分渲染

當視點距離渲染對象較遠時，點和線段組成的混合渲染模型可以取得較好的空間覆蓋效果。但是，由于點的空間覆蓋能力有限，實際存在的采樣點數量可能小于渲染所需的點數量np。此時，本文使用曲面細分算法填補采樣點之間的縫隙和空洞。

如圖4所示，本文使用與法線方向垂直的正方形作為曲面細分的結果，擴大點圖元的空間覆蓋范圍。給出相機垂直方向方向向量U，點圖元法線N，點圖元坐標Pi，點圖元采樣密度s，則水平方向和垂直方向的曲面細分方向向量可以分別表示為：H=U×N和V=H×N。

曲面細分向量Tij∈{0，1}，j∈{0，1}則可以通過如下方法計算得出：

Tij=Pi+(2i-1)·H/|H|·s+(2j-1)·V/|V|·s。

此外，經過曲面細分生成的多邊形使用點圖元的顏色進行著色，并且使用混合技術(Alpha-blending)與臨近的幾何圖元進行顏色融合以獲得更好的渲染視覺效果。

圖4　基于點的曲面細分填充

3.4 圖元混合策略

在進行渲染圖元的選擇后，每一種離散渲染圖元(點、線、Splatting多邊形)的數量已經確定，本文提出一種混合渲染模型，從離散圖元的序列中提取層次細節(jié)模型并進行混合，合成輸入模型的混合層次細節(jié)表示。

圖5　混合渲染策略

如圖5所示為離散渲染圖元的層次細節(jié)數據結構組織與渲染數據混合過程。本文首先根據投影面積選擇子分割線段集合序列的一個后綴子序列進行渲染；然后，從完整線段序列中選擇未被分割子線段集合替換的前綴序列進行線模型的渲染。

假設經過采樣的離散點圖元序列的第個LOD層級中包含了ni個采樣點。如果在離散點序列中存在2個相鄰的采樣層級r和r+1，滿足如下關系：

則本文選擇離散點序列中的前np個點進行渲染。否則整個離散點圖元序列被傳入曲面細分引擎，以著色多邊形的形式進行渲染輸出。在渲染過程中，混合圖元使用FXAA(Fast Approximate Anti-aliasing)方法進行反走樣，去除其中的高頻噪聲信號。

圖6　渲染結果

4實驗結果與討論

本文使用總數據量為52 GB的包含海陸模型的青島市城市三維場景對算法進行測試。實驗平臺為配置Intel Core I7-3740處理器，NVidia Quadra K2000顯卡，4 GB內存的圖形工作站。處理后的三維場景總共包含72.6 M的直線段和1.7 G的采樣點。

圖6a所示為使用混合LOD模型進行城市三維場景渲染的結果。圖6b中使用了動態(tài)范圍無關算法[13]比較了混合LOD模型與原始模型的視覺差異。其中，具有明顯差異的像素點使用紅色標識，具有細微差異的像素點使用綠色標識，視覺等價的像素點用灰色標識?？梢钥闯?，混合LOD模型的視覺效果與原始模型基本一致，只有6%～7%的像素點呈現明顯差異。這種差異在大規(guī)模城市場景的渲染結果中是難以被察覺的。

使用本文算法可以實現完整城市級大場景的可視化，通過視錐裁剪后的渲染幀速約為每秒65～70幀(見圖6c)。圖6d所示為使用本文方法進行海濱城市三維場景渲染的結果，其中使用本文方法進行渲染的平均幀速為122 fps，使用純三角網格渲染方法的平均幀速為15 fps。

圖7　渲染圖元數量

/ms

圖7中所示為不同視距下混合LOD模型渲染的圖元數量?？梢钥闯?，點圖元的數量與線圖元和多邊形圖元相比，以更快的速度收斂。這表明距離視點較遠的渲染對象大多數是單純地通過線圖元進行表示的。雖然城市建筑多彩多樣，但是對于距離視點較遠的對象，其絕大多數細節(jié)經過透視投影后難以被觀察到，通過直線表示的模型提供了清晰的輪廓和主體著色，經過實驗驗證(見圖6b)與原始模型無明顯差異，是一種較為有效的簡化模型表示方法。此外，只有非常少的渲染對象以Splatting多邊形的形式進行渲染，這與本文基于屏幕空間投影面積進行層次細節(jié)模型選擇和渲染的原理吻合。

近年來，海洋水體可視化算法[10]普遍較為依賴片元著色器的計算能力，本文提出的渲染模型通過避免在LOD模型中使用紋理貼圖降低渲染流水線中的片元著色器負載，從而提高海陸一體場景的整體渲染效率。為了評估本文算法的性能，本文在圖6c的大場景中隨機選取了3個數據量約為2GB的濱海城市場景進行實驗。將混合LOD模型、幾何LOD模型[13]與原始模型在相同的測試平臺上通過輸出橫穿場景的漫游動畫并統(tǒng)計每一幀的平均渲染時間的方式進行性能對比。實驗結果如表1所示，本文提出的混合LOD算法與原始模型相比可以獲得約10倍的性能提升，與幾何LOD方法相比可以獲得約4倍的性能提升。在加入海水水體渲染后，使用原始模型與幾何LOD模型都出現了70至90%的性能下降；而使用混合LOD模型的渲染系統(tǒng)性能只出現了輕微的下降，橫向比較中，海水水體的渲染時間也有明顯減少。結果表明，本文算法具有更高的加速比，與海洋可視化算法結合的渲染性能較高，適用于海陸一體的海濱城市場景渲染。

5結語

本文提出了一種適用于海陸一體城市場景的LOD渲染方法。構建了由點、線等簡單圖元組成的三維模型近似表示，并基于屏幕空間投影面積進行了動態(tài)的LOD選擇，實現了混合模型渲染輸出。該方法構建的模型數據量小，具有較高的真實感，可以實現城市級三維場景的渲染，與基于三角網格與紋理貼圖的渲染方法相比性能有明顯的提高，且更適用于海陸一體城市場景的渲染，在“數字青島”等海濱城市仿真與相關的地理信息系統(tǒng)應用項目中取得了良好的實用效果。

本文提出的模型采樣和渲染方法在處理某些具有特殊色彩和亮度的高頻特征時可能會出現視覺精度損失，如何通過漸進藍噪聲采樣等方法改善采樣點的均勻和隨機分布將是本文下一階段的研究重點。

參考文獻：

[1]Hoppe H. Progressive meshes [C].//Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. New York: ACM, 1996: 99-108.

[2]Sander P V, Snyder J, Gortler S J, et al. Texture mapping progressive meshes [C].//Proceedings of the 28th annual conference on Computer graphics and interactive techniques. New York: ACM, 2001: 409-16.

[3]Peng C, Cao Y. A gpu-based approach for massive model rendering with frame-to-frame coherence[J]. Computer Graphics Forum, 2012, 31(2): 393-402.

[4]Yoon S E, Salomon B, Gayle R, et al. Quick-vdr: Out-of-core view-dependent rendering of gigantic models[J]. IEEE Transactions on Visualization and Computer Graphics, 2005, 11(4): 369-382.

[5]Gobbetti E, Marton F. Far voxels: A multi-resolution framework for interactive rendering of huge complex 3d models on commodity graphics platforms[J]. ACM Transactions on Graphics, 2005, 24(3): 878-885.

[6]劉波， 王章野， 王麗英，等. 大規(guī)模城市場景的高效建模及其實時繪制[J]. 計算機輔助設計與圖形學學報， 2008， 20(9)： 1153-1162.

Liu B, Wang Z Y, Wang L Y, et al. Efficient modeling and real-time rendering of large-scale urban scenes[J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(9):1153-1162(in Chinese).

[7]馬純永， 陳勇， 韓永，等. 虛擬城市仿真中一種基于GPU的繪制加速算法[J]. 中國海洋大學學報(自然科學版)， 2010, 40(7): 141-144.

Ma C Y, Chen G, Han Y, et al. A GPU-based rendering accleration algorithm from urban simulation[J]. Periodical of Ocean University of China: Nature Science Edition, 2010,40(7),141-144(in Chinese).

[8]Cignoni P, Di Benedetto M, Ganovelli F, et al. Ray-casted blockmaps for large urban models visualization[J]. Computer Graphics Forum, 2007, 26(3): 405-13.

[9]Andujar C, Brunet P, Chica A, et al. Visualization of large-scale urban models through multi-level relief imposters[J]. Computer Graphics Forum, 2010, 29(8): 2456-2468.

[10]李文慶. VV-Ocean海洋環(huán)境仿真與海洋數據動態(tài)可視化系統(tǒng)的研究與實現[D].青島： 中國海洋大學, 2011.

Li W. Research and implementation of VV-Ocean System on Marine Environment Simulation and Data Visualization[D]. Qingdao: Ocean University of China, 2011(in Chinese).

[11]Burr D C, Morrone M C, Spinelli D. Evidence for edge and bar detectors in human vision[J]. Vision Research, 1989, 29(4): 419-431.

[12]Luebke D P. Level of Detail for 3d Graphpics[M]. Burlington: USA Morgan Kaufmann Pub, 2003.

[13]Aydin T, Cadik M, Myszkowski K, et al. Video quality assessment for computer graphics applications[J]. ACM Transactions on Graphics, 2010, 29(6): 161-173.

責任編輯陳呈超

A Hybrid Rendering Approach for 3D Seaside Urban Scenes Visualization

ZHOU Sheng-Chuan1，2， HU Zhen-Biao1，2， MA Chun-Yong3， CHEN Ge3

(1.Qingdao Geotechnical Investigation & Surveying Research Institute， Qingdao 266033， China; 2.National & Local Joint Engineering Reseach Center for Sea-land Geographics Information Integration and Application， Qingdao 266033, China; 3.College of Information Science and Engineering, Ocean University of China， Qingdao 266100, China)

Abstract:A novel hybrid level-of-detail algorithm for large-scale seaside urban scenes rendering is introduced. We combine point, line, and splat-based rendering to synthesize large-scale urban city images. Points and lines are extracted through multi-jittered sampling and color-clustering, and encoded in a data structure that allows for automatically LOD selection. A screen-space projected area is used as the LOD selector. The algorithm selects lines for long distance views, uses points for midum-distance views, and introduces splatting for close-ups. Architecture models are then represented by few lines and points and provide high realistic rendering results. The experiment shows our approach is significantly faster than the textured models for rendering large-scale urban scenes, and is more suitable for seaside urban scenes visualization. The quality of the results is indistinguishable from the original as confirmed by algorithmic metrics.

Key words:level-of-detail； hybrid rendering； seaside city visualization； virtual reality

中圖法分類號：TP391.9

文獻標志碼：A

文章編號：1672-5174(2016)01-138-07

作者簡介：周圣川(1986-)，男，博士，高級工程師，主要研究方向為過程式建模、大規(guī)模數據可視化。E-mail：zhoushengchuan@qq.com

收稿日期：2014-03-04；

修訂日期：2014-12-10

*基金項目：中央高校青年教師科研專項基金項目(201213019)

DOI：10.1644/j.cnki.hdxb.20140054

引用格式：周圣川， 胡振彪， 馬純永， 等. 海濱城市三維場景的混合圖元渲染方法[J].中國海洋大學學報(自然科學版)，2016,46(1)：138-144.

ZHOU Sheng-Chuan，HU Zhen-Biao，MA Chun-Yong ，et al. A hybrid rendering approach for 3D seaside urban scenes visualization[J]. Periodical of Ocean University of China, 2016, 46(1): 138-144.

Supported by Research Funds for the Youth Teacher of Central University(201213019)