【摘要】：提出了一種基于稀疏體素有向無環(huán)圖(SVDAG)的光照計(jì)算加速結(jié)構(gòu)。通過自下而上地合并相同節(jié)點(diǎn),將稀疏體素八叉樹轉(zhuǎn)化為SVDAG;同時(shí),利用給定節(jié)點(diǎn)的遍歷路徑和子掩碼,消除了空間位置的多義性。針對(duì)閉合幾何體,基于雙層深度圖算法可自適應(yīng)合并位于閉合區(qū)域的節(jié)點(diǎn),在保證光照計(jì)算性能的前提下,進(jìn)一步減小了存儲(chǔ)開銷。提出了一種基于時(shí)域相關(guān)性的SVDAG幀間復(fù)用方法,利用動(dòng)態(tài)場(chǎng)景的全部幀構(gòu)成SVDAG加速結(jié)構(gòu)整體,提高了更新速度。實(shí)驗(yàn)結(jié)果表明,新算法提高了三維場(chǎng)景的繪制效率,在面對(duì)高分辨率的動(dòng)態(tài)場(chǎng)景時(shí),仍能獲得較高的幀速率。
【圖文】：

區(qū)域?qū)?yīng)的節(jié)點(diǎn)，避免了對(duì)空白節(jié)點(diǎn)的存儲(chǔ)。在ＳＶＯ構(gòu)建過程中，每個(gè)節(jié)點(diǎn)的子掩碼一共８ｂｉｔ，“０”表示子節(jié)點(diǎn)為空，“１”表示子節(jié)點(diǎn)為實(shí)節(jié)點(diǎn)。因此，指向空節(jié)點(diǎn)的指針可以完全被剔除，僅需要保留指向第一個(gè)非空子節(jié)點(diǎn)的指針，其子節(jié)點(diǎn)可以按照約定順序（如廣度優(yōu)先順序）連續(xù)地存儲(chǔ)在內(nèi)存空間中，層級(jí)內(nèi)部可采用Ｍｏｒｔｏｎ碼順序，也不需要保留指針，從而達(dá)到減小存儲(chǔ)開銷的目的，如圖１所示。因此，只要知道子掩碼和約定的遍歷順序，，就可以通過節(jié)點(diǎn)的連續(xù)存儲(chǔ)順序恢復(fù)出ＳＶＯ的完整結(jié)構(gòu)。圖１ＳＶＯ節(jié)點(diǎn)排列順序及指針安排的二維示意圖Ｆｉｇ．１Ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｃｈｅｍａｔｉｃｏｆｏｒｄｅｒａｎｄｐｏｉｎｔｅｒｓｅｔｔｉｎｇｏｆｎｏｄｅｓｉｎＳＶＯ０８２０００１－２

合并操作，某些節(jié)點(diǎn)可能擁有多個(gè)父節(jié)點(diǎn)，因此，ＳＶＯ就從樹形結(jié)構(gòu)擴(kuò)展為ＳＶＤＡＧ。按照上述思路，將ＳＶＯ轉(zhuǎn)化為ＳＶＤＡＧ最簡(jiǎn)單的方法就是從根節(jié)點(diǎn)開始，搜索是否存在完全相同的子樹，并繼續(xù)遞歸每一個(gè)子樹，直至遇到葉子節(jié)點(diǎn)。這個(gè)方法雖然簡(jiǎn)單，但是遞歸操作需要將整個(gè)場(chǎng)景的所有節(jié)點(diǎn)推入堆棧后進(jìn)行回溯，分辨率較高時(shí)內(nèi)存開銷的峰值很大。因此，為了避免遞歸，提出了如下一種自下而上的方法以實(shí)現(xiàn)從ＳＶＯ到ＳＶＤＡＧ的轉(zhuǎn)換。１）從ＳＶＯ的底部開始，搜索相同的葉子節(jié)點(diǎn)并進(jìn)行合并，如圖２所示。在ＳＶＯ中，由于葉子節(jié)點(diǎn)僅表示對(duì)應(yīng)空間位置上是否存在對(duì)應(yīng)體素，因此合并后的葉子節(jié)點(diǎn)最多兩種。圖２搜索相同葉子節(jié)點(diǎn)并進(jìn)行合并Ｆｉｇ．２Ｓｅａｒｃｈｉｎｇｆｏｒｓａｍｅｌｅａｆｎｏｄｅｓａｎｄｍｅｒｇｉｎｇ２）繼續(xù)往上層處理，搜索子掩碼和指針完全相同的節(jié)點(diǎn)，這樣的節(jié)點(diǎn)具有相同的子樹，可以進(jìn)行合并，如圖３所示。需要注意的是，壓縮這些層級(jí)的節(jié)點(diǎn)時(shí)，只要考慮子樹的根節(jié)點(diǎn)，這是因?yàn)楹喜⒉僮魇亲韵露线M(jìn)行的，節(jié)點(diǎn)本身具有相同的子掩碼和指針即說明它們的下級(jí)子樹直至葉子節(jié)點(diǎn)都是相同的。圖３自下而上地將ＳＶＯ轉(zhuǎn)化為ＳＶＤＡＧ的示意圖Ｆｉｇ．３ＳｃｈｅｍａｔｉｃｏｆｃｏｎｖｅｒｔｉｎｇＳＶＯｔｏＳＶＤＡＧｆｒｏｍｂｏｔｔｏｍｔｏｔｏｐ３）自下而上進(jìn)行搜索和合并操作，參與合并的節(jié)點(diǎn)越來越多，直到?jīng)]有節(jié)點(diǎn)可以合并或到達(dá)根節(jié)點(diǎn)，獲得最終的ＳＶＤＡＧ，如圖４所示。該算法同樣適用于深度不均勻的ＳＶＯ，同時(shí)也可對(duì)不同子樹分別進(jìn)行轉(zhuǎn)化操作然后再組合。由于整個(gè)ＳＶＯ的數(shù)據(jù)規(guī)模可能遠(yuǎn)大于對(duì)應(yīng)的ＳＶＤＡＧ的數(shù)據(jù)規(guī)模，可以利用

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉峰;王越;;針對(duì)有向無環(huán)圖結(jié)構(gòu)的多版本分布模式優(yōu)化[J];計(jì)算機(jī)工程;2011年11期

2 范偉;劉峰;徐世軍;邢茜;;多節(jié)點(diǎn)有向無環(huán)圖優(yōu)化算法[J];重慶理工大學(xué)學(xué)報(bào)(自然科學(xué));2011年12期

3 王櫻;彭景斌;王靜;;經(jīng)濟(jì)模式下基于有向無環(huán)圖的優(yōu)化調(diào)度算法設(shè)計(jì)[J];福建電腦;2011年07期

4 何黎剛,韓宗芬,秦嘯,龐麗萍;一種基于有向無環(huán)圖的實(shí)時(shí)任務(wù)調(diào)度算法[J];華中理工大學(xué)學(xué)報(bào);2000年10期

5 王櫻;李琳;王杰;;基于有向無環(huán)圖的時(shí)間—費(fèi)用優(yōu)化調(diào)度算法[J];衡陽師范學(xué)院學(xué)報(bào);2010年03期

6 曾陽紅;黃海于;汪維富;;基于有向無環(huán)圖的成本-時(shí)間優(yōu)化調(diào)度算法[J];電腦知識(shí)與技術(shù)(學(xué)術(shù)交流);2007年15期

7 韓中;陳富民;高智勇;高建民;;系統(tǒng)建模中基于對(duì)象的有向無環(huán)圖節(jié)點(diǎn)粒度的轉(zhuǎn)換[J];西安交通大學(xué)學(xué)報(bào);2008年09期

8 程剛;鐘秋海;;相似案例自適應(yīng)選擇算法及其應(yīng)用[J];控制與決策;2007年03期

9 紀(jì)凌光;高世臣;王娟;;一個(gè)新的基于GA的有向無環(huán)圖畫圖算法[J];微計(jì)算機(jī)信息;2009年30期

10 余冬梅;;基于DAG的高校培養(yǎng)計(jì)劃圖自動(dòng)生成算法[J];陜西理工學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年05期

本文編號(hào)：2560955