閆秋羽 張興剛 郝冬冬

摘 ?要： 針對(duì)交互型虛擬現(xiàn)實(shí)室內(nèi)場(chǎng)景建設(shè)以及人物漫游問(wèn)題，提出一種基于改進(jìn)二叉樹BSP的室內(nèi)場(chǎng)景管理方法，并采用遺傳算法實(shí)現(xiàn)該場(chǎng)景下的人物路徑規(guī)劃。首先，在基于幾何建模法的虛擬漫游系統(tǒng)中，利用改進(jìn)的二叉空間剖分BSP樹算法對(duì)三維場(chǎng)景進(jìn)行預(yù)處理，從而提高實(shí)時(shí)圖形繪制的效率;然后，對(duì)漫游場(chǎng)景進(jìn)行柵格化處理，并采用遺傳算法實(shí)現(xiàn)兩點(diǎn)間最短漫游路徑的計(jì)算。室內(nèi)場(chǎng)景漫游測(cè)試結(jié)果表明，相比傳統(tǒng)的A*算法，提出的BSP?遺傳漫游算法在耗時(shí)和最短路徑長(zhǎng)度兩方面均表現(xiàn)出一定的優(yōu)勢(shì)。

關(guān)鍵詞： 室內(nèi)場(chǎng)景管理; 虛擬現(xiàn)實(shí)技術(shù); 三維場(chǎng)景預(yù)處理; 實(shí)時(shí)圖形繪制; 路徑規(guī)劃; 漫游技術(shù)

中圖分類號(hào)： TN02?34; TP391.41 ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2019）19?0095?03

Abstract： An indoor scene management method based on improved binary tree BSP is proposed， and the genetic algorithm is used to realize the path planning of the character in the scene， so as to solve the problem of interactive virtual reality indoor scene construction and character roaming. The improved binary space split BSP tree algorithm is used in the virtual roaming system based on geometric modeling method to preprocess the 3D scene， which is beneficial to the improvement of the real?time graphics rendering efficiency. The roaming scene is rasterized， and the genetic algorithm is used to calculate the shortest roaming path between two points. The indoor scene roaming test results show that the proposed BSP?genetic roaming algorithm has more obvious advantages in both time?consuming and path length in comparison with the traditional A* algorithm.

Keywords： indoor scene management; virtual reality technology; 3D scene preprocessing; real?time graphic rendering; path planning; roaming technology

0 ?引 ?言

隨著虛擬現(xiàn)實(shí)技術(shù)的不斷發(fā)展，各種行業(yè)中應(yīng)用虛擬現(xiàn)實(shí)技術(shù)的場(chǎng)景越來(lái)越多。虛擬現(xiàn)實(shí)技術(shù)不僅應(yīng)用在航空、航天等特殊領(lǐng)域，更應(yīng)用在現(xiàn)實(shí)生活中，例如，虛擬游戲、真實(shí)3D電影、三維室內(nèi)漫游等，為用戶營(yíng)造出一種身臨其境的感覺(jué)[1]。

虛擬漫游技術(shù)是虛擬現(xiàn)實(shí)技術(shù)中的一項(xiàng)基本功能。為了不斷增加用戶的真實(shí)感，虛擬現(xiàn)實(shí)系統(tǒng)的圖形分辨率質(zhì)量和三維場(chǎng)景復(fù)雜度也隨之不斷提高，以便提供較好的逼真度。因此，如何采用先進(jìn)的場(chǎng)景處理方法構(gòu)建室內(nèi)場(chǎng)景中的三維模型，以及通過(guò)路徑規(guī)劃實(shí)現(xiàn)場(chǎng)景內(nèi)人物的交互成為一個(gè)很重要的研究方向。文獻(xiàn)[2]對(duì)沉浸式三維虛擬漫游技術(shù)進(jìn)行了研究，提出基于Multigen Creator和3DMAX的虛擬城鎮(zhèn)場(chǎng)景建模方法，并通過(guò)二叉空間剖分BSP樹在Vega軟件中實(shí)現(xiàn)虛擬場(chǎng)景中的人物漫游交互。文獻(xiàn)[3]提出一種三維巷道場(chǎng)景中虛擬漫游路徑優(yōu)化技術(shù)，該方法根據(jù)OpenGL視點(diǎn)變換模型原理，在BSP樹基礎(chǔ)上實(shí)現(xiàn)視點(diǎn)追蹤，并結(jié)合線性分形插值函數(shù)和Cardinal曲線擬合算法，對(duì)追蹤路徑進(jìn)行優(yōu)化。文獻(xiàn)[4]提出基于滑動(dòng)窗口和A*算法的四足機(jī)器人路徑規(guī)劃方法。但是，BSP樹算法的計(jì)算復(fù)雜度較大，在處理復(fù)雜場(chǎng)景時(shí)效率會(huì)有所降低。同時(shí)，新型智能化路徑規(guī)劃算法也不斷出現(xiàn)，遺傳算法解決柵格地圖上的最短路徑求解問(wèn)題時(shí)，具有較好的求解質(zhì)量和效率[5]。因此，在以上研究的基礎(chǔ)上，本文提出一種基于改進(jìn)二叉樹BSP的室內(nèi)場(chǎng)景設(shè)計(jì)方法，并采用遺傳算法實(shí)現(xiàn)該場(chǎng)景下的人物路徑規(guī)劃。首先，利用球體樹原理構(gòu)造粗略、模糊的空間分割法，從而使基于二叉樹BSP算法的三維漫游場(chǎng)景構(gòu)造速度得到加快;其次，對(duì)漫游場(chǎng)景進(jìn)行柵格化處理，并采用遺傳算法實(shí)現(xiàn)該場(chǎng)景下的人物路徑規(guī)劃，得到最短漫游路徑。測(cè)試結(jié)果驗(yàn)證了提出漫游方法的優(yōu)越性能。

[6] 吳曉雪，王魏，李響，等.基于osgEarth虛擬校園漫游的研究[J]. 現(xiàn)代電子技術(shù)，2017，40（20）：18?21.

WU Xiaoxue， WANG Wei， LI Xiang， et al. Study on virtual campus roaming based on osgEarth [J]. Modern electronics technique， 2017， 40（20）： 18?21.

[7] BASTUG E， BENNIS M， MEDARD M， et al. Toward interconnected virtual reality： opportunities， challenges， and enablers [J]. IEEE communications magazine， 2017， 55（6）： 110?117.

[8] WALSH C M. Assessment of competence in pediatric gastrointestinal endoscopy [J]. Current gastroenterology reports， 2014， 16（8）： 1?10.

[9] LEE N Y， LEE D K， SONG H S. Effect of virtual reality dance exercise on the balance， activities of daily living， and depressive disorder status of Parkinson′s disease patients [J]. Journal of physical therapy science， 2015， 27（1）： 145?152.

[10] SONG B， WANG Z， SHENG L. A new genetic algorithm approach to smooth path planning for mobile robots [J]. Assembly automation， 2016， 36（2）： 138?145.

[11] MAPLES?KELLER J L， BUNNELL B E， KIM S J， et al. The use of virtual reality technology in the treatment of anxiety and other psychiatric disorders [J]. Harv rev psychiatry， 2017， 25（3）： 103?113.

[12] QU B， ZHANG Z， LI F， et al. Research and application of oil operator training system based on virtual reality technology [J]. Journal of Petrochemical Universities， 2017， 30（1）： 54?59.