基于自適應(yīng)二叉樹的場景視錐體裁剪算法①

牛 鵬, 廉東本, 蘇 謨

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

2(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽 110168)

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

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

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

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

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

1.1 場景組織

1.1.1 自適應(yīng)二叉樹的建立

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

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

1.1.2 最佳分割面的獲取準(zhǔn)則

求解最佳分割平面是ABT創(chuàng)建過程中最重要的部分,其目的是對當(dāng)前包圍盒中的幾何體進(jìn)行有效地分割,使得建立的場景樹更有利于后續(xù)的裁剪和渲染.在文獻(xiàn)[3]描述了求解有效分割面的標(biāo)準(zhǔn).

圖1 自適應(yīng)二叉樹的構(gòu)建流程圖

標(biāo)準(zhǔn)1. 最優(yōu)空間定位

該標(biāo)準(zhǔn)側(cè)重于分割當(dāng)前節(jié)點(diǎn)包圍盒最長坐標(biāo)軸的分割平面.

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

標(biāo)準(zhǔn) 2. 子節(jié)點(diǎn)體積

該標(biāo)準(zhǔn)側(cè)重于將當(dāng)前節(jié)點(diǎn)分割成對等體積子節(jié)點(diǎn)的分割平面.

f2(pos)=abs(volume_child1-volume_child2)

標(biāo)準(zhǔn) 3. 面的數(shù)量

該標(biāo)準(zhǔn)側(cè)重于將當(dāng)前幾何體表面均勻地分布到所有葉子節(jié)點(diǎn)上的分割平面.

f3(pos)=abs(numfaces_child1-numfaces_child)

標(biāo)準(zhǔn) 4. 被分割的面的數(shù)量

計(jì)算幾何體被分割平面分割的面的數(shù)量. 被分割平面分割的面越多,該分割平面越不適合作為分割面.

f4(pos)=total_number_of_split_faces

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

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

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

步驟2. 采用評分函數(shù)對候選面數(shù)據(jù)集中的每個候選面進(jìn)行評分,分?jǐn)?shù)最高者則為最佳分割面.

步驟3. 采用最佳分割面對節(jié)點(diǎn)進(jìn)行分割.

1.2 基于自適應(yīng)二叉樹的視錐體裁剪算法

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

1.2.1 算法描述

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

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

1.2.2 確定包圍球、包圍盒與視錐體的位置關(guān)系

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

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

圖3 包圍球與視錐體位置關(guān)系的判斷的流程圖

圖4 包圍盒與視錐體位置關(guān)系的判斷的流程圖

2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

通過所得數(shù)據(jù)發(fā)現(xiàn),兩種算法在場景組織方面因?yàn)榫捎米赃m應(yīng)二叉樹算法,所以在模型的多邊形總數(shù)一致的情況下,所生成的節(jié)點(diǎn)總數(shù)是相同的,對于裁剪,在時間消耗上,基于包圍球和包圍盒的裁剪算法所花費(fèi)的時間要少于基于幾何投影降維的裁剪算法,特別是在場景復(fù)雜的情況下本文提出的裁剪算法的優(yōu)勢會更加突出.

3 結(jié)語

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

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

2張宇. 一種基于八叉樹的動態(tài)場景管理方式. 電腦知識與技術(shù),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算法. 微電子學(xué)與計(jì)算機(jī),2016,33(5)： 127-132.

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

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