基于Voronoi圖的快速可見(jiàn)性計(jì)算.pdf

1、在虛擬場(chǎng)景漫游時(shí),觀察者走到每一點(diǎn)都需要盡可能快得確定哪些對(duì)象是可見(jiàn)的,因此設(shè)計(jì)合適的可見(jiàn)性計(jì)算方法不僅能實(shí)現(xiàn)快速繪制,還能節(jié)省存儲(chǔ)空間和內(nèi)存空間。二維情況下,就是確定觀察者在多邊形內(nèi)任一點(diǎn),在一定視覺(jué)范圍內(nèi)能看見(jiàn)哪些邊以及邊上的哪些部分。
　　 本文研究背景是山東大學(xué)虛擬考古博物館漫游系統(tǒng),該系統(tǒng)采用Voronoi圖作為統(tǒng)一的數(shù)據(jù)結(jié)構(gòu),展廳的設(shè)計(jì)、路徑規(guī)劃等都使用該結(jié)構(gòu)。本文主要基于該數(shù)據(jù)結(jié)構(gòu)研究和設(shè)計(jì)了快速可見(jiàn)性計(jì)算方法。<

2、br>　　 本文算法共分為潛在可見(jiàn)集計(jì)算和可見(jiàn)性實(shí)時(shí)計(jì)算兩個(gè)階段。算法的核心部分為潛在可見(jiàn)集計(jì)算階段,主要是利用采樣點(diǎn)和點(diǎn)的可見(jiàn)性計(jì)算方法獲得觀察區(qū)域的潛在可見(jiàn)性集合。在潛在可見(jiàn)集計(jì)算階段中,首先生成虛擬博物館平面結(jié)構(gòu)圖的Voronoi剖分,接著細(xì)分復(fù)雜的Voronoi區(qū)域,獲得更加合適的觀察單元,然后對(duì)每個(gè)觀察單元的邊界邊進(jìn)行自適應(yīng)地點(diǎn)采樣,計(jì)算每個(gè)采樣點(diǎn)處的精確可見(jiàn)性集合,并由這些點(diǎn)的可見(jiàn)性集合合并為該觀察單元的潛在可見(jiàn)性集合(P

3、VS)。在可見(jiàn)性實(shí)時(shí)計(jì)算階段中,首先獲得視點(diǎn)所在的觀察單元,然后使用該觀察單元的PVS直接計(jì)算該視點(diǎn)的可見(jiàn)邊,以此實(shí)現(xiàn)三維室內(nèi)場(chǎng)景的實(shí)時(shí)漫游。當(dāng)視點(diǎn)連續(xù)移動(dòng)時(shí),根據(jù)Voronoi圖的鄰近性可以快速確定新的觀察單元。
　　 本文算法的工作與貢獻(xiàn)主要是提出了一種基于Voronoi圖的可見(jiàn)性計(jì)算方法,該方法利用點(diǎn)的可見(jiàn)性算法計(jì)算區(qū)域可見(jiàn)信息,給出了啟發(fā)式的自適應(yīng)采樣方法和各點(diǎn)處的可見(jiàn)性集合合并策略,以獲得更加緊湊的PVS。該方法與虛擬