大規模城市建筑物的一種混合LOD 實時繪制算法

陳鵬宇

（四川大學計算機學院，成都610065）

0 引言

當今時代，數字城市[1]成為城市發展研究的熱點，其基礎為計算機技術、大規模存儲技術等，通過寬帶網絡建聯，運用全球定位系統、地理信息系統、工程測量技術、仿真虛擬等技術，對城市進行多分辨率、多尺度、多時空和多種類的三維描述。大量、復雜的建筑物作為其主要地物，也是數字城市的重點研究對象之一，其自動生成的速度快慢、效果逼真與否，都將直接關系到數字城市的建設發展。目前，繪制大型城市建筑物場景，需要處理大量的數據，許多研究人員提出了各種各樣的方法，如GLOD 模型[2]、Out-of-Core[3-4]、Relief Map、Block Map 等基于圖像[5-6]的繪制技術，以上方法雖可實現大規模城市建筑物的繪制，但大都是在構建聚合體上工作的，容易產生視差誤差。

本文提出一種新的混合繪制方法，即基于點、基于線、基于splatting 多邊形等混合圖元的LOD 模型，根據視距，選擇不同類型、不同數量的點、線等簡單離散圖元構成LOD 的近似表示，從而提高繪制性能，保證LOD 模型與輸入模型視覺上的一致性，此方法適用于單個建筑，可提高視覺質量，并通過使用高對比度的簡化幾何圖形作為LOD 圖元減少內存使用，解決大規模城市建筑物三維場景可視化中常見的渲染數據復雜度過高，繪制速率較慢等問題。

1 算法概述

本文提出的大規模城市建筑物混合LOD 實時繪制算法的原理與流程如圖1 所示。該算法基于三維圖形學中透視投影原理設計，對輸入的三維建筑模型進行計算和分析，提取出基于點和基于線的三維模型表示。其中，點圖元通過抖動采樣[7]完成，并生成點圖元漸進LOD 模型序列；線圖元通過對輸入的幾何結構進行邊界線段分析提取，并采用顏色聚類算法進行分割，并生成線圖元漸進LOD 模型序列。而后根據輸入模型與視點的距離遠近，及其投影于屏幕空間的面積大小（可通過透視投影變換和視口變換計算），即將屏幕投影區域作為LOD 模型選擇器，確定無縫表示該建筑對象所需的點、線圖元數量，按照距離遠、面積小，選擇線圖元，距離逐漸縮小、面積增大，逐步添加點圖元的原則，從點、線圖元隊列中選擇對應的圖元。對于視距較近而點、線模型無法提供無縫覆蓋時，本文采用一種曲面細分算法，使用Splatting 多邊形進行填補。

本算法的優勢在于點和線段作為離散圖元，具有獨立的顏色屬性，可不通過紋理映射進行著色，在降低顯存消耗的同時均衡GPU 的負載，提高場景實時繪制的性能。

圖1 混合LOD實時繪制算法原理與流程

2 點線生成和排序

輸入三維建筑物模型將通過不同的方法轉換為一組點和線表示的LOD 模型。

2.1 點線生成

點圖元采樣的目的是生成基于點的三維模型表示，且采樣點需具有良好的視覺質量，具有點圖元分布均勻，可以避免鋸齒、采樣效率高等特性。本文采用抖動采樣，即將平面分成n×n 的網格，在每個網格中進行隨機采樣，使任意2 個同層級的采樣點處于不同的網格行或者列上，采樣點的顏色通過紋理映射直接獲得，每個采樣點對應的網格層級編號作為屬性保存并用于后續創建LOD 模型。

線模型的生成由兩個相鄰網格面之間的角度控制。若角度小于180°，則一個相鄰邊緣提取和表示為主要結構的輪廓，并使用較亮的顏色進行著色。另外，需注意如圖2 所示情況，一條完整邊緣線段上的顏色變化較為有序、明顯，先將紋理轉換到L*a*b 色域，使用三維歐氏距離計算出各像素點之間的視覺感知差異，分析幾何邊上的顏色著色梯度，對比相鄰像素的視覺差異，提取顏色聚類，將顏色聚類之間的分界點作為子線段的頂點，從而將完整的幾何邊分割為使用不同顏色著色的更為精確的子線條。

圖2

2.2 點線排序

點排序為輸入模型創建一個基于點的LOD 模型漸進序列，該序列的任意前綴都是一種簡化的基于點的模型LOD 表示，并且遞增的添加細節。在點采樣的過程中，為每一采樣點都被分配一個序號（層級值），根據序號對整個點集進行升序（本文采用堆排序）排序，在相同層級中，使用Fish-Yates 算法進行局部重排，從而為輸入模型生成所需的點LOD 模型。

線排序點排為輸入模型創建一個線的LOD 模型漸進序列，該序列中包含完整的幾何邊緣線段和按顏色聚類細分的子線段2 種不同的線段模型，且存儲于兩個不同序列中。首先，給每個完整線段分配一個序號（即唯一ID）；然后將被細分的線段按與完整線段的從屬關系構成集合，故細分線組與對應完整線組有相同序號。本文用長度作為排序鍵值，使用升序排序（本文使用堆排序）算法對細分線組和完整線組進行排序。同時，為避免重疊和Z-Fighting，本文采取的完整線和子線段的替換策略是：若一完整邊緣線段對應的任一細分線可見，則用細分線代替完整線；若一完整邊緣線段的細分線均不可見，則用完整線代替。

3 LOD選擇

點、線LOD 模型漸進序列提供了一種靈活的方法來繪制大規模城市場景模型。其所需點線數量，從預處理好的序列中進行選擇。我們的目標是選擇好的表示形式來繪制大規模城市建筑物模型，在使繪制圖元數量最小化的同時，保證視覺效果良好。本文使屏幕空間容錯因子ω=0，即使屏幕空間的像素點覆蓋錯誤率為0，以獲得最優的繪制輸出結果。

在給定透視投影下，設輸入模型T 由n 個三角形組成，T={t1,t2,…,tn}，其屏幕空間投影面積可以近似為：

設x 表示屏幕的分辨率。考慮到全視場θ 和在觀察方向從視點到模型d 的距離，單位投影面積和單位投影長度可計算為：

假設原始模型是由一個點集近似Sp={P1,P2,…,Pm}和一個線集Sl={L1,L2,…,Ln}繪制。點集有一個投影面積，線集有一個投影面積。為了獲得可靠的繪制輸出，特別是為了避免有間隙，我們需要：

3.1 線選擇

我們使用投影面積作為線的LOD 選擇器。當且僅當該組中最長的細分線可見（大于1 像素）時，才繪制該細分線組；否則，將繪制相應的完整線。我們首先從使用投影長度作為標準的細分線組的排序序列中選擇一個后綴，然后從完整線排序序列中繪制相應的前綴，以避免重疊。

假設輸入模型近似為一個線集Sl={L1,L2,…,Ln}，我們用li表示直線的長度。圖像平面上直線的長度可以近似為其中對應投影變換。則線集合所覆蓋的柵格區域為：

我們使用類似于式（3）的條件來決定是否全部選擇線圖元繪制。。如果條件為真，則只選擇線繪制模型。否則，我們計算需要由點覆蓋的投影面積來填補間隙。

3.2 點選擇

點填充線結構之間的空隙，并提供立面細節。我們首先繪制線條，然后計算覆蓋立面所需的點的數量。在我們的方法中，每個點都表示為一個點畫面（即，與像平面對齊的平面圓形單元）與大小。點的數量取決于三角形的近似投影面積與線的近似投影面積之間的差異，他們的計算方程是（1）和（4）。然后點的數量：

系數fp的值用于增加點密度，系數fp只用于點，因為線的長度不隨細分而變化。

3.3 splatting選擇

上述方法主要是針對中距離和遠距離的視距。如果距離較近，預計生成的實際點圖元數將小于所需點圖元數目np。在這種情況下，我們使用splatting 多邊形來填充點、線繪制區域之間的間隙。

本文使用Doo-Sabin 曲面細分算法[8]來獲得splatting 多邊形填補采樣點之間的縫隙和空洞。Doo-Sabin算法和基于點的模型繪制使用完全一致的繪制數據模型，如VBO 等，且完全在GPU 中進行處理，所以不會引入額外的數據，無需使用額外的紋理貼圖，可節省大量的顯存和內存空間。

Doo-Sabin 算法采用的是逼近型頂點分裂模式，算法過程如下：

（1）幾何規則：設Mk為一控制網格, Fk為網格中任意多邊形，記多邊形頂點為（0 ≤i ≤n），對應的細分后的多邊形為Fk+1，生成的新頂點為：

（2）算法實現：①根據公式（1）、（2）計算起始網格各面上新頂點位置，生成新頂點；②判斷原頂點在不在邊界上，若不在，為各原始頂點生成一個對應的新新V-面；否則不進行此操作；③判斷邊是不是邊界邊，若不是，為每條原始邊建立一個對應的新E-面；否則不進行此操作；④為各原始面建立對應的新F-面；⑤按照細分規則，重新進行連接；⑥計算各新產生的面和新產生的頂點的法向矢量；⑦一次迭代完成。

另外，經過Doo-Sabin 算法生成的splatting 多邊形使用點圖元的顏色進行著色，并使用混合技術與鄰近的幾何圖元進行顏色融合，以獲得更好的繪制效果。

3.4 混合表示

如圖3 所示，為離散圖元的LOD 數據結構組織與繪制混合過程。在選擇了表示形式并確定了每個圖元（點、線、splatting 多邊形）的數目之后，我們可以綜合他們的混合表示形式，通過排序序列生成簡化模型。

圖3

4 實驗結果與性能比較

4.1 實驗結果

本文對北京首都機場、上海虹橋機場2 個三維場景建筑物進行了算法測試。我們通過對比本文提出的算法與傳統GLOD 算法[9]生成圖像的視覺質量，給出了兩種算法的繪制性能結果。本實驗平臺為配置Intel Core i5-7500 處理器和NVIDIA GTX1080 顯卡的臺式計算機。實驗結果如圖4 所示。

圖4A1 北京首都機場（使用混合LOD算法）

圖4B1 北京首都機場（使用GLOD算法）

圖4A2 上海虹橋機場（使用混合LOD算法）

圖4B2 上海虹橋機場（使用GLOD算法）

圖4A1、A2中使用了離散點、線、splatting 多邊形組成的混合LOD 模型；圖4B1、B2為使用傳統LOD 算法生成的圖像。通過對比可知，兩種方法在人眼視覺可察中，生成的圖像無明顯差別。

4.2 性能比較

本文對北京首都機場、上海虹橋機場2 個場景建筑物的混合LOD 模型、GLOD 模型在相同的測試平臺上，通過輸出橫穿場景的漫游動畫并統計每一幀的平均繪制時間的方式進行性能對比，結果如表1 所示，可得出本文提出的混合LOD 算法是GLOD 算法速率的3 倍。

表1 繪制性能比較（每幀平均渲染時間，單位ms）

5 結語

本文提出一種新的LOD 方法來繪制大規模城市建筑物，主要思想是通過使用線、點和splatting 多邊形的混合方法來繪制，并使用了一種評價指標進行了對比。此方法實現了交互幀率，與傳統GLOD 方法保持視覺相似效果的同時，提高了約3 倍速率。但是此方法也有一些局限，本文提出的模型采樣和繪制方法，在處理某些具有特殊色彩和亮度的高頻特征時，可能會出現視覺精度損失，采用何種方法克服，是本文下一階段研究的重點。