基于自適應二叉樹的場景視錐體裁剪算法①

牛 鵬, 廉東本, 蘇 謨

1(中國科學院大學,北京 100049)

2(中國科學院 沈陽計算技術研究所,沈陽 110168)

隨著計算機硬件與虛擬現實技術的發展,應用于場景的模型的數據規模呈指數級增長,場景的結構也更加復雜. 盡管圖形渲染已經在硬件方面得到了很好地支持,卻仍不能解決場景在圖形實時渲染方面的問題,還需對相關的裁剪算法進行分析研究. 所以,在克服傳統場景組織方式弊端的基礎上,能夠有效地減少繪制對象,降低模型復雜度,提升裁剪和場景渲染的效率,就成為本文研究所關注的內容.

在三維場景中,模型作為基本的組成單位,一般是以點線面的存儲結構的,這種點線面的數據結構適用幾何建模,但不能體現場景中的空間分布情況. 比較有效的方法是對場景進行空間分割. 并用樹結構進行組織,這樣可以把空間無序的場景模型變成一棵空間有序的層次樹. 對層次樹的操作也就等同于對整個場景的操作.

本文提出了采用自適應二叉樹空間分割算法負責場景的組織管理,在可見性判斷方面,采用了一種基于包圍球和包圍盒的層次化的視錐體裁剪算法,在充分發揮自適應二叉樹空間分割算法的優勢的基礎上,該視錐體裁剪算法有效地降低了場景模型的復雜度,提高了裁剪的精確度,提升了三維場景的繪制效率.

1 場景組織及視錐體裁剪算法

針對傳統二叉樹(BSP)[1]存在的問題,本文采用自適應二叉樹算法(Adaptive Binary Tree,ABT)進行場景的組織管理,其較強的自適應性,適合剖分任何類型的場景. 與傳統的八叉樹[2]相比,ABT提供了“多態”的優點,在某種意義上是幾何模型和空間劃分的抽象,而不限于固定的形狀. 它主要用在復雜3D場景下的視錐體裁剪. 而八叉樹由于其嚴格的空間結構,增加了可見性計算的開銷. 這可以通過使用松散的八叉樹來緩解,但是仍然有很多限制,特別是八叉樹并不能保證網格數據的唯一性(這在現代3D硬件上是非常重要的),此外,八叉樹不如自適應二叉樹那樣平滑地適應于幾何體的分割. 基本上,為了中等或復雜場景的通用渲染,ABT比八叉樹更有效率. 在視錐體裁剪方面,對場景樹中的節點的采用層次化裁剪的方式來剔除模型中冗余的數據,降低三維模型的復雜度,提高后續的渲染效率.

1.1 場景組織

1.1.1 自適應二叉樹的建立

ABT算法基于場景的幾何體對空間進行分割. 分割平面由一個考慮了多種不同參數(分割面的數量和位置等)的評分系統決定,使得到的分割平面更適合特定類型的場景的模型劃分. ABT建立的具體算法的執行流程如圖1所示.

在創建過程中,首先,將與坐標軸對齊且覆蓋整個場景的包圍盒作為根節點(在創建節點的過程中,每個節點中都要存放一個包圍盒和包含該包圍盒的一個包圍球,用來進行后續的裁剪和碰撞檢測). 然后,開始執行一個遞歸剖分函數,該遞歸剖分函數的功能就是將當前的包圍盒用一個垂直于三個主坐標軸之一的分割面分開,作為當前節點的兩個子節點. 然后分別對兩個子節點繼續進行細分,直到節點中的面的數量達到預定閾值或樹的深度上限.

1.1.2 最佳分割面的獲取準則

求解最佳分割平面是ABT創建過程中最重要的部分,其目的是對當前包圍盒中的幾何體進行有效地分割,使得建立的場景樹更有利于后續的裁剪和渲染.在文獻[3]描述了求解有效分割面的標準.

圖1 自適應二叉樹的構建流程圖

標準1. 最優空間定位

該標準側重于分割當前節點包圍盒最長坐標軸的分割平面.

f1(pos)=max(split_x_axis,split_y_axis,split_z_axis)

標準 2. 子節點體積

該標準側重于將當前節點分割成對等體積子節點的分割平面.

f2(pos)=abs(volume_child1-volume_child2)

標準 3. 面的數量

該標準側重于將當前幾何體表面均勻地分布到所有葉子節點上的分割平面.

f3(pos)=abs(numfaces_child1-numfaces_child)

標準 4. 被分割的面的數量

計算幾何體被分割平面分割的面的數量. 被分割平面分割的面越多,該分割平面越不適合作為分割面.

f4(pos)=total_number_of_split_faces

上面所有函數必須最小化,才能找到最優的剖分平面. 另外,每個函數都有一個權重因子,根據場景類型的特點,靈活的設置權重因子,權重因子分布取決于場景策略的選擇,從而保證算法更可控、有效. 最終可獲取可行平面時必須最小化的方程：

1.1.3 獲取最佳空間分割面的步驟

步驟1. 采用隨機采樣方法,確定用于分割的候選面數據集.

步驟2. 采用評分函數對候選面數據集中的每個候選面進行評分,分數最高者則為最佳分割面.

步驟3. 采用最佳分割面對節點進行分割.

1.2 基于自適應二叉樹的視錐體裁剪算法

三維場景規模越來越大,能夠有效地減少繪制對象,降低模型復雜度,是三維渲染引擎中實現復雜場景快速繪制的關鍵所在. 可見性判斷是一種很有效的方法,可見性裁剪算法[4,5]常常分為3類： 視錐體裁剪、背面裁剪和遮擋裁剪. 本文主要研究在自適應二叉樹的場景組織的基礎上采用基于包圍球[6]和包圍盒[7]的層次化的裁剪方式進行視域剔除. 在既定的場景中,采用ABT算法來組織場景元素,面片在在葉子節點中分布的更加均勻,樹的深度達到最佳,形成了一棵高效平衡的二叉樹,基于此優勢,在該數據結構上進行視錐體裁剪,會大大的提高裁剪的效率.

1.2.1 算法描述

該算法的原理是首先利用ABT算法對場景中的對象進行組織,構建起自適應二叉樹,自適應二叉樹中的每個節點都包含了一個包圍球和包圍盒(軸對齊包圍盒),然后在視錐裁剪方面,采用遞歸的方式對樹中的節點進行裁剪處理,首先,判斷節點的包圍球是否在視錐體內,如果包圍球位于視錐體內,那么就說明該節點分支下的所有子節點均是可見的,所以可直接送入渲染管道進行繪制. 如果包圍球位于視錐體之外,則說明該節點及分支下的子節點均不可見,則可以直接停止對該分支上的節點的可見性判斷,從而節省了CPU的周期開銷. 當包圍球與視錐體相交時,就開始判斷視錐體與包圍球中的軸對齊包圍盒的位置關系,如果包圍盒位于視錐體內,同樣將該節點及其分支節點直接送入渲染管道進行繪制. 如果包圍盒位于視錐體外,則停止對該節點及其分支子節點的可見性判斷. 如果包圍盒與視錐體相交,則繼續遍歷其子節點,然后對其子節點同樣進行基于包圍球和包圍盒的可見性判斷. 該算法的執行流程圖如圖2所示.

圖2 基于包圍球和包圍盒的視錐體算法執行流程圖

1.2.2 確定包圍球、包圍盒與視錐體的位置關系

確定包圍球是位于視錐體內、視錐體外還是與視錐體相交實際上是一個非常簡單的過程,需要做的是計算球體中心到視錐體的6個平面的距離. 如果距離的絕對值小于球體的半徑,那么球體與平面相交. 在相交不成立的情況下,如果距離大于0,那么球體位于平面的前側(也可能在視錐體內). 如果小于0,那么球體位于視錐體背面,絕對在視錐體之外. 判斷包圍球與視錐體位置關系的流程圖如圖3所示.

確定視錐體與包圍盒的位置狀態,用以下方式來完成該操作,首先,用三個最小值和三個最大值來定義包圍盒,然后將該包圍盒的8個頂點與視錐體進行比較. 如果所有的點在視錐體內,那么說明這個包圍盒位于視錐體內,如果包圍盒至少有一個頂點(但不是全部)不在視錐體內,則說明包圍盒與視錐體相交. 如果包圍盒所有的點都在特定的視錐體平面的背面. 那么這個包圍盒位于視錐體的外面,是不可見的. 考慮到,視錐體完全包含在包圍盒內的情況. 在這種情況下,這些點都不在視錐體內,但包圍盒仍然被視為可見的. 判定算法的執行流程圖如圖4所示.

圖3 包圍球與視錐體位置關系的判斷的流程圖

圖4 包圍盒與視錐體位置關系的判斷的流程圖

2 實驗結果及分析

本實驗的硬件配置： CPU Intel Core(TM)i3-4160 3.6GHz,四核處理器,內存為 4 GB,顯卡類型為NVIDIA GeForce GT610,顯存大小為1 GB. 軟件環境：Windows 7旗艦版64位操作系統,OpenGL4.3版本,VS2015,NVIDIA驅動版本R320,OSG版本號3.4. 設置可視化場景生成時屏幕的分辨率為800 * 600.

本文將自適應二叉樹場景組織算法和基于包圍球和包圍盒的層次化視錐體裁剪算法應用到三維渲染引擎上,通過實驗,對本文提出的裁剪算法與文獻[8]中提出的基于幾何投影降維的裁剪算法(該算法是在二維投影的平面上采用傳統的Cyrus-Beck算法完成對視錐體的裁剪)在裁剪的性能上作了測試,測試結果如表1和表2所示.

表1 基于包圍球和包圍盒的裁剪算法的性能

表2 基于幾何及投影降維的裁剪算法的性能

通過所得數據發現,兩種算法在場景組織方面因為均采用自適應二叉樹算法,所以在模型的多邊形總數一致的情況下,所生成的節點總數是相同的,對于裁剪,在時間消耗上,基于包圍球和包圍盒的裁剪算法所花費的時間要少于基于幾何投影降維的裁剪算法,特別是在場景復雜的情況下本文提出的裁剪算法的優勢會更加突出.

3 結語

本文采用自適應二叉樹的場景組織結構來對場景進行管理,其高效的分割平面的選擇機制,使其具有很強的自適應性,可以用來劃分各種類型的場景. 然后在此場景結構的基礎上對可見性裁剪算法進行了研究,在視錐體裁剪方面,采用了基于幾何包圍球和包圍盒的視錐體裁剪算法,該算法充分利用了自適應二叉樹的場景結構的優勢,在一定程度上減少了參與裁剪計算的節點的數量,提高了裁剪的效率,特別適合于復雜場景中各個模型的裁剪. 接下來將進一步研究如何將本文采用的場景組織算法和裁剪算法高效地運用到三維動態場景中去.

1黃曉康. 基于BSP和四叉樹的場景管理研究[碩士學位論文].南京： 南京理工大學,2008.

2張宇. 一種基于八叉樹的動態場景管理方式. 電腦知識與技術,2015,11(14)： 54-57.

3Dickheiser M. Game programming gems 6. 孟憲武,譯. 北京：人民郵電出版社,2007. 339-341.

4Yagel R,Ray W. Visibility computation for efficient walkthrough of complex environments. Presence：Teleoperators and Virtual Environments,1996,5(1)： 45-60.[doi： 10.1162/pres.1996.5.1.45]

5Zhang HS,Manocha D,Hudson T,et al. Visibility culling using hierarchical occlusion maps. Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York,NY,USA. 1997. 77-88.

6王倩,高保祿,高銳軍,等. 基于四叉樹包圍球和屏幕誤差的LOD算法. 微電子學與計算機,2016,33(5)： 127-132.

7彭艷瑩,陸國棟,李基拓,等. 基于包圍盒編碼的三維線段裁剪新算法. 計算機輔助設計與圖形學學報,2003,15(11)：1369-1374. [doi： 10.3321/j.issn：1003-9775.2003.11.008]

8余沛文. 視錐體裁剪幾何算法與測試方法研究[碩士學位論文]. 上海： 東華大學,2016.