基于CSG體的投影包圍盒加速算法研究

陸濟(jì)湘，唐雙平，嚴(yán)曉鳳

(武漢理工大學(xué)理學(xué)院，湖北 武漢 430070)

在基本的光線跟蹤算法中，每一條射線都要和場(chǎng)景中的所有物體求交，然后再對(duì)所給的求交數(shù)據(jù)進(jìn)行分析排序，這是一個(gè)重復(fù)迭代的過(guò)程，需要對(duì)大量的光線進(jìn)行一遍又一遍同樣的操作[1]。而對(duì)于復(fù)雜環(huán)境的場(chǎng)景，這種簡(jiǎn)單的處理渲染效率很低。為了提高渲染效率，需要對(duì)光線跟蹤算法進(jìn)行加速，加速技術(shù)主要包括以下幾個(gè)方面:提高求交速度、減少求交次數(shù)、減少光線跟蹤條數(shù)和采用并行計(jì)算等。提高求交速度的算法在計(jì)算機(jī)圖形學(xué)中已經(jīng)發(fā)展得較為成熟;而減少光線跟蹤條數(shù)會(huì)降低圖形的渲染質(zhì)量;采用并行計(jì)算則需要硬件的支持。因此，現(xiàn)在的研究重點(diǎn)在減少求交次數(shù)。為減少求交次數(shù)，在光線跟蹤中可采用包圍盒技術(shù)[2－5]。包圍盒技術(shù)是加速光線跟蹤的基本方法之一，其基本思想是用一些簡(jiǎn)單的包圍盒(如球面、長(zhǎng)方體)將復(fù)雜景物包圍起來(lái)，求交的光線首先與包圍盒進(jìn)行求交測(cè)試，若相交，則光線再與景物求交，否則光線與景物必?zé)o交[6]。簡(jiǎn)單的包圍盒技術(shù)效率并不高，因?yàn)楸桓櫟墓饩€必須與場(chǎng)景中每一個(gè)景物的包圍盒進(jìn)行求交測(cè)試。

由于包圍盒形狀簡(jiǎn)單(一般是長(zhǎng)方體)，在三維空間中不能緊密的包圍景物;景物之間也有空隙，且包圍盒是將整個(gè)場(chǎng)景都包裹，這就造成了大量的無(wú)效求交測(cè)試。為了進(jìn)一步提高求交效率，筆者提出了一種新的包圍盒，即投影包圍盒技術(shù)。

投影包圍盒是指場(chǎng)景中的物體投影在屏幕上一塊包裹物體的矩形區(qū)域，即將三維的數(shù)據(jù)轉(zhuǎn)化為二維數(shù)據(jù)。這樣，在減少數(shù)據(jù)分析量的同時(shí)，光線跟蹤也不用對(duì)整個(gè)屏幕進(jìn)行迭代，只需要對(duì)投影在屏幕的區(qū)域進(jìn)行迭代，從而縮短渲染的時(shí)間。構(gòu)造實(shí)體幾何(CSG)的布爾操作(交，并，差)是CSG的核心內(nèi)容。對(duì)于基于CSG的投影包圍盒，需要在預(yù)處理階段掃描CSG物體對(duì)應(yīng)的樹(shù)，在每個(gè)節(jié)點(diǎn)處對(duì)物體進(jìn)行布爾操作，構(gòu)建CSG體的投影包圍盒。

1 CSG體數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

構(gòu)造實(shí)體幾何(CSG)是由基本的幾何形體通過(guò)布爾操作構(gòu)造的，這些基本的形體包括正方體、圓柱體、球和圓錐體等。這些形體之間可以進(jìn)行幾何變換和布爾操作。利用二叉樹(shù)將這些形體保存起來(lái)，構(gòu)造一棵CSG樹(shù)，可以顯著減少對(duì)場(chǎng)景中物體進(jìn)行排序的時(shí)間[7]。通過(guò)二叉樹(shù)來(lái)表示CSG體的信息，如圖1所示。

構(gòu)造CSG樹(shù)時(shí)，葉節(jié)點(diǎn)對(duì)應(yīng)于基本的幾何形體，非葉節(jié)點(diǎn)則對(duì)應(yīng)于布爾操作。葉節(jié)點(diǎn)的數(shù)據(jù)結(jié)果描述如下:

由于布爾體沒(méi)有自己的仿射變換，而在SDL文件中，沒(méi)有經(jīng)過(guò)仿射變換的是默認(rèn)方式的形體，如正方體，默認(rèn)邊長(zhǎng)為1，圖1中的A是正方體經(jīng)過(guò)了幾何變換后得到的，因此要將幾何變換保存在節(jié)點(diǎn)中，對(duì)于圖1的CSG樹(shù)，可將幾何變換寫(xiě)入節(jié)點(diǎn)中，即葉節(jié)點(diǎn)對(duì)應(yīng)的是幾何變換后的形體，如圖2所示(T表示幾何變換)。

圖1 CSG樹(shù)

圖2 幾何變換后的形體示意圖

保持節(jié)點(diǎn)中的顯式變換，可以在CSG體被構(gòu)建后，通過(guò)單獨(dú)使用樹(shù)中的一個(gè)變換來(lái)調(diào)整形狀，而這也為尋找布爾體的更緊致的包圍盒提供了可能。

2 投影包圍盒算法設(shè)計(jì)

2.1 點(diǎn)束的采集

CSG體的投影包圍盒要求在預(yù)處理階段為每個(gè)物體求投影包圍盒，并且把它與對(duì)應(yīng)的物體存儲(chǔ)起來(lái)，因此必須在預(yù)處理階段為場(chǎng)景中的所有物體構(gòu)建點(diǎn)束[8－10]。由于CSG體是由基本的形體通過(guò)布爾操作完成的，因此在預(yù)處理階段為基本的形體建立點(diǎn)束。長(zhǎng)方體和平面的點(diǎn)束可以直接采用頂點(diǎn)，而對(duì)于球體和其他的形體則用一個(gè)緊緊包裹這些形體的多面體，點(diǎn)束就是多面體的頂點(diǎn)[11]。如球體采用一個(gè)20面體來(lái)包裹它，頂點(diǎn)則在離球心大約1.26倍半徑的地方。

2.2 投影包圍盒的建立

通過(guò)上述方法建立的點(diǎn)束，可以快速地建立投影包圍盒。當(dāng)然，這種情況下所求的投影包圍盒的坐標(biāo)是在OpenGL下的坐標(biāo)，因此要將點(diǎn)束轉(zhuǎn)化為屏幕坐標(biāo)系下的坐標(biāo)。投影包圍盒主要記錄4個(gè)坐標(biāo)信息，即屏幕上矩形區(qū)域的{left，right，top，bottom}，點(diǎn)束中的每個(gè)點(diǎn)都投影到所對(duì)應(yīng)的屏幕上，如圖3所示。

圖3 點(diǎn)束投影示意圖

偽代碼如下:

2.3 創(chuàng)建CSG體的投影包圍盒

利用上述方法可以實(shí)現(xiàn)物體投影包圍盒的創(chuàng)建，同時(shí)一個(gè)CSG體的每個(gè)節(jié)點(diǎn)的投影包圍盒的構(gòu)建與其長(zhǎng)方體包圍盒的構(gòu)建相同。每個(gè)節(jié)點(diǎn)的投影包圍盒由其左右子樹(shù)的投影包圍盒組成。用P(object)來(lái)表示object的投影包圍盒，則有如下表示:

并集:P(L∪R)=P(P(L)∪P(R))

差集:P(L∩R)=P(L)∩P(R)

交集:P(L－R)=P(L)

以CSG體交集為例，則CSG差集的投影包圍盒的 4 個(gè)坐標(biāo)信息{left，top，right，bottom}如下:

3 實(shí)驗(yàn)與分析

為驗(yàn)證筆者提出算法的有效性，利用VC++6.0和OpenGL對(duì)圖形庫(kù)進(jìn)行了交、并、差3種布爾操作。比較基于光線跟蹤下，CSG體在未使用投影包圍盒和使用投影包圍盒的時(shí)間，所得到的結(jié)果是:投影包圍盒可以快速提高CSG體的渲染時(shí)間。

(1)CSG體并集運(yùn)算在兩種情況下的時(shí)間比較如圖4所示。場(chǎng)景中的物體是由兩個(gè)圓柱的并操作而來(lái)的。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以觀察到:使用投影包圍盒，渲染的時(shí)間從原來(lái)的2 891 μs減少到359 μs，時(shí)間縮短至原來(lái)的大約1/8，渲染效率有了很大的提高。

圖4 CSG體并集運(yùn)算在兩種情況下的時(shí)間比較

(2)CSG體差集運(yùn)算在兩種情況下的時(shí)間比較如圖5所示。場(chǎng)景中的物體是通過(guò)兩個(gè)半徑不相等的半球做差運(yùn)算而來(lái)的。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn):CGS體原來(lái)的渲染時(shí)間是現(xiàn)在的大約8.4倍，渲染效率同樣也有很大的提高。

圖5 CSG體差集運(yùn)算在兩種情況下的時(shí)間比較

(3)CSG體交集運(yùn)算在兩種情況下的時(shí)間比較如圖6所示。場(chǎng)景中的物體是通過(guò)3個(gè)圓柱體做布爾操作的交集運(yùn)算而得到的。對(duì)比兩個(gè)時(shí)間數(shù)據(jù)渲染效率提高了10倍。

圖6 CSG體交集運(yùn)算在兩種情況下的時(shí)間比較

對(duì)CSG體的3種布爾操作，通過(guò)實(shí)驗(yàn)分析數(shù)據(jù)可以發(fā)現(xiàn)，在運(yùn)用光線跟蹤的投影包圍盒算法時(shí)，場(chǎng)景的渲染效率可提高8～10倍。結(jié)合以上的分析，筆者設(shè)計(jì)并實(shí)現(xiàn)了基于CSG體的投影包圍盒加速算法。獲取實(shí)驗(yàn)數(shù)據(jù)的計(jì)算機(jī)配置為酷睿雙核，2.21 GHz，512 DDR內(nèi)存，屏幕分辨率為1 024×768，光源為點(diǎn)光源與環(huán)境光。

4 結(jié)論

光線跟蹤是建立CSG體的重要技術(shù)，提高光線跟蹤算法效率是研究的重點(diǎn)之一。筆者采用投影包圍盒算法，并結(jié)合CSG體中的布爾操作來(lái)實(shí)現(xiàn)和提高光線跟蹤的渲染效率。實(shí)驗(yàn)表明，該算法能夠?qū)SG體的渲染效率提高8～10倍。

[1] FRANCIS S H，STPHEN J M K.計(jì)算機(jī)圖形學(xué)(OpenGL版)[M].胡事民，譯.北京:清華大學(xué)出版社，2009:32－89.

[2] 吳慧欣，薛惠鋒，刑書(shū)寶.限定TN與CSG集成仿真模型生成算法研究[J].計(jì)算機(jī)應(yīng)用，2007(2):475－478.

[3] KOZO O，DAISUKE N，MITSURU B.3 － D shape measurement by inverse raytracing approach[C]//SICE Annual Conference.[S.l.]:[s.n.]，2008:1531 －1535.

[4] 郭小凱.光線跟蹤及其加速算法的研究[D].西安:西安電子科技大學(xué)圖書(shū)館，2008.

[5] 楊勛年，汪國(guó)昭.三維凸包的快速算法[J].浙江大學(xué)學(xué)報(bào):自然科學(xué)版，1999(2):3－6.

[6] 占春生，蔡勇.一種基于光線相關(guān)性的快速光線跟蹤算法[J].計(jì)算機(jī)與現(xiàn)代化，2003(6):4－6.

[7] 劉廣忠，黃琳娜.基于二叉樹(shù)的散亂點(diǎn)集快速凸包算法[J].測(cè)繪科學(xué)，2008(4):86－88.

[8] FABIANO R，LUIZ V.Hardware－ assisted rending of CSG models[J].Computer Graphics and Image Processing，2006，19(6):139 －146.

[9] WIEGAND T F.Interactive readering of CSG models[J].Computer Graphics Forum，1996，15(4):249 －261.

[10] FLORIAN K，JURGEN D.Rendering techniques for hardware－accelerated image－ based CSG[J].Journal of WSCG，2004，12(2):221 －228.

[11] 崔新友，李東亮.三維模型的布爾運(yùn)算研究[J].科技信息，2010(15):444－445.