基于虛擬現(xiàn)實(shí)的復(fù)雜場(chǎng)景加載優(yōu)化算法①

葉 誠(chéng),羅 訓(xùn)

(天津理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,天津 300384)

現(xiàn)階段場(chǎng)景模型生成技術(shù)并不發(fā)達(dá),程序員在處理生成模型場(chǎng)景問(wèn)題上還存在很多情況沒(méi)有解決.本研究在游戲引擎的實(shí)驗(yàn)環(huán)境下,討論了大規(guī)模復(fù)雜場(chǎng)景生成階段的一些重要問(wèn)題,優(yōu)化了相關(guān)算法.本文主要研究大規(guī)模復(fù)雜場(chǎng)景生成后場(chǎng)景模型的優(yōu)化,根據(jù)模型和攝像機(jī)的遠(yuǎn)近實(shí)時(shí)調(diào)用不同層級(jí)的模型方面進(jìn)行研究.大型復(fù)雜生成場(chǎng)景文件在游戲引擎中的漫游存在著模型渲染上和模型調(diào)取的問(wèn)題,該研究使用了模型加載及其渲染優(yōu)化技術(shù),優(yōu)化了場(chǎng)景漫游的工程簡(jiǎn)化了制作流程;在模型場(chǎng)景渲染技術(shù)上,通過(guò)使用一種基于LOD 場(chǎng)景模型的新型算法,解決了大規(guī)模復(fù)雜場(chǎng)景的實(shí)時(shí)渲染有許多技術(shù)上的難點(diǎn),主要包括海量地形數(shù)據(jù)的表示和組織、動(dòng)態(tài)場(chǎng)景的管理以及場(chǎng)景的真實(shí)感表現(xiàn)等.即按照生成模型的規(guī)模大小,使用模型切割代碼將模型切割成尺寸大小均等的不同尺寸,滿(mǎn)足工程對(duì)于場(chǎng)景漫游的要求;相關(guān)論文研究了關(guān)于大規(guī)模地形的快速渲染方法,其思想是將之前分割好的地塊都先簡(jiǎn)化為一些不同細(xì)節(jié)層次的網(wǎng)格模型,存儲(chǔ)在外部存儲(chǔ)介質(zhì)上.程序根據(jù)攝像機(jī)距離模型的遠(yuǎn)近調(diào)取合適的地形塊導(dǎo)入內(nèi)存,再進(jìn)行模型的渲染.這種方法的缺陷是增加了很多的步驟,在不同的模型切換時(shí)會(huì)產(chǎn)生視覺(jué)上的卡頓問(wèn)題.本文對(duì)于自動(dòng)LOD 技術(shù)進(jìn)行探討采用網(wǎng)格簡(jiǎn)化算法結(jié)合視點(diǎn)的動(dòng)態(tài)LOD 技術(shù),提高了幀率減少了當(dāng)前占用CPU 進(jìn)行計(jì)算的時(shí)間,并且減少了攝像機(jī)下的三角形和頂點(diǎn)數(shù)從而減少了渲染的工作量.

本文在游戲引擎中使用天津工業(yè)大學(xué)的生成模型(如圖1)進(jìn)行漫游,采用不同方法對(duì)該工程進(jìn)行優(yōu)化處理,提出將LOD 技術(shù)和動(dòng)態(tài)網(wǎng)格簡(jiǎn)化算法并行計(jì)算形成一種新型的自動(dòng)LOD 構(gòu)建算法,主要貢獻(xiàn)可以概括為:

(1)將游戲引擎中LOD 技術(shù)與動(dòng)態(tài)網(wǎng)格簡(jiǎn)化算法并行節(jié)省渲染時(shí)間.

(2)提出了自動(dòng)LOD 構(gòu)建方法只需要使用一套模型就可以應(yīng)用LOD 技術(shù).

圖1 天津工業(yè)大學(xué)模型

1 相關(guān)技術(shù)介紹

在大型場(chǎng)景中經(jīng)常使用的優(yōu)化算法主要有:LOD技術(shù),遮擋剔除算法,動(dòng)態(tài)加載,本文主要對(duì)這LOD 技術(shù)和網(wǎng)格簡(jiǎn)化算法進(jìn)行了結(jié)合改進(jìn)從而提出了自動(dòng)LOD 算法.

1.1 LOD 技術(shù)

LOD 技術(shù),也稱(chēng)為層次細(xì)節(jié)技術(shù),是在實(shí)時(shí)渲染顯示系統(tǒng)中采取的細(xì)節(jié)省略技術(shù),此技術(shù)于1976年由Clark 提出[1].作為目前主要的場(chǎng)景優(yōu)化方法,它根據(jù)物體的重要性、視點(diǎn)的相對(duì)速度或者位置等衡量標(biāo)準(zhǔn),動(dòng)態(tài)改變場(chǎng)景中三維模型的復(fù)雜程度,模型距離視點(diǎn)越近,顯示的模型細(xì)節(jié)越豐富,從而降低了CPU 和GPU需要處理的的頂點(diǎn)數(shù)量,提高場(chǎng)景的渲染速度[2].在復(fù)雜模型的動(dòng)態(tài)顯示中,當(dāng)觀(guān)察點(diǎn)距離某一物體很近時(shí),該物體的圖像將在屏幕上占據(jù)較多的像素點(diǎn);而當(dāng)觀(guān)察點(diǎn)距離某一物體很遠(yuǎn)時(shí),該物體的圖像只能在屏幕上占據(jù)很少的像素點(diǎn).在這種情況下,用大量的面去精確表示該物體是不必要的[3].認(rèn)為當(dāng)物體覆蓋屏幕較小區(qū)域時(shí),可以使用該物體描述較粗的模型,并給出了一個(gè)用于可見(jiàn)面判定算法的幾何層次模型,以便對(duì)復(fù)雜場(chǎng)景進(jìn)行快速繪制.LOD 技術(shù)在不影響畫(huà)面視覺(jué)效果的條件下,通過(guò)逐次簡(jiǎn)化景物的表面細(xì)節(jié)來(lái)減少場(chǎng)景的幾何復(fù)雜性,從而提高繪制算法的效率.該技術(shù)通常對(duì)每一原始多面體模型建立幾個(gè)不同精度的幾何模型.與原模型相比,每個(gè)模型均保留了一定層次的細(xì)節(jié).在繪制時(shí),根據(jù)不同的標(biāo)準(zhǔn)選擇適當(dāng)?shù)膶哟文Ｐ蛠?lái)表示物體.LOD 技術(shù)具有廣泛的應(yīng)用領(lǐng)域.目前在實(shí)時(shí)圖像通信、交互式可視化、虛擬現(xiàn)實(shí)、地形表示、飛行模擬、碰撞檢測(cè)、限時(shí)圖形繪制等領(lǐng)域都得到了應(yīng)用,已經(jīng)成為一項(xiàng)要害技術(shù).很多造型軟件和VR 開(kāi)發(fā)系統(tǒng)都開(kāi)始支持LOD 模型表示.LOD 生成的一種常用方法是網(wǎng)格簡(jiǎn)化.目前常用的網(wǎng)格簡(jiǎn)化方式有邊壓縮、面收縮、點(diǎn)聚合和頂點(diǎn)刪除等[4].

1.2 遮擋剔除算法

遮擋剔除算法利用遮擋剔除(occlusion culling)技術(shù),在游戲引擎中使用遮擋剔除時(shí),會(huì)在渲染對(duì)象被送進(jìn)渲染管線(xiàn)之前,將因?yàn)檎趽醵粫?huì)被看到的隱藏對(duì)象或隱藏面進(jìn)行剔除,從而減少了每幀的渲染數(shù)據(jù)量,提高了渲染性能[5].可見(jiàn)性剔除是提高大規(guī)模復(fù)雜場(chǎng)景的加速技術(shù)之一,目的是減少送入圖形管線(xiàn)的面片數(shù)量,降低場(chǎng)景規(guī)模增長(zhǎng)對(duì)圖形系統(tǒng)的負(fù)擔(dān)[6].對(duì)于給定的場(chǎng)景和觀(guān)察視點(diǎn),通過(guò)判斷場(chǎng)景中物體的可見(jiàn)性,快速拒絕那些顯然不可見(jiàn)的繪制元素,從而減少送入圖形繪制管線(xiàn)的幾何復(fù)雜度[7].在遮擋密集的場(chǎng)景中,性能提升會(huì)更加明顯.遮擋剔除是當(dāng)一個(gè)物體被其他物體遮擋住而不在攝像機(jī)的可視范圍內(nèi)時(shí),不對(duì)其進(jìn)行渲染.在3D 圖形計(jì)算中并不是一個(gè)自動(dòng)進(jìn)行的過(guò)程,因?yàn)樵诮^大多數(shù)情況下離相機(jī)最遠(yuǎn)的物體首先被渲染,靠近攝像機(jī)的物體后渲染,并覆蓋先前渲染的物體(這種重復(fù)渲染又叫做“OverDraw”),它不同于視錐剪裁.視錐剪裁只是不渲染攝像機(jī)視角范圍外的物體,而對(duì)于那些被其他物體遮擋,但是依然在鏡頭范圍內(nèi)的物體,則不會(huì)被視錐剔除.當(dāng)然當(dāng)你使用遮擋剔除時(shí),視錐裁剪還是會(huì)生效的.由于地形場(chǎng)景一般較為復(fù)雜,對(duì)CPU 開(kāi)銷(xiāo)很大.為了降低地形的遮擋剔除過(guò)程中CPU的負(fù)荷,提出了以GPU 具有遮擋查詢(xún)功能為基礎(chǔ)的遮擋剔除算法[8].

2 流程優(yōu)化

在游戲引擎中,如果想使用傳統(tǒng)的LOD 技術(shù)(如圖2)就必須先將面數(shù)最大的模型分別簡(jiǎn)化為幾種面數(shù)不同,導(dǎo)出后再放入游戲引擎中使用LOD 技術(shù)優(yōu)化工程.在這種新型的LOD 技術(shù)中,動(dòng)態(tài)網(wǎng)格簡(jiǎn)化算法采用網(wǎng)格預(yù)先簡(jiǎn)化的方法事先生成LOD 模型避免了直接使用網(wǎng)格簡(jiǎn)化算法所需完成的大量計(jì)算,有效地降低了算法的時(shí)間開(kāi)銷(xiāo).在串行計(jì)算環(huán)境下,網(wǎng)格簡(jiǎn)化算法使得一些較小規(guī)模(包含1 05以下量級(jí)三角面單元)的網(wǎng)格模型的在交互幀率下的動(dòng)態(tài)LOD 模型構(gòu)建成為可能.然而在面對(duì)大規(guī)模網(wǎng)格模型(包含1 05及以上量級(jí)三角面單元)時(shí),卻仍無(wú)法滿(mǎn)足交互幀率繪制需求.

在動(dòng)態(tài)網(wǎng)格簡(jiǎn)化算法使用在大規(guī)模復(fù)雜模型的時(shí)候其時(shí)間性能需要有所提升,該理論基于網(wǎng)格的動(dòng)態(tài)LOD 構(gòu)建方法,并且使用了三維模型的簡(jiǎn)化算法,創(chuàng)造出一個(gè)新型高效率的自動(dòng)LOD 算法,如圖3.

圖2 傳統(tǒng)LOD 加載算法處理步驟

圖3 自動(dòng)LOD 加載算法處理步驟

算法主要具備如下優(yōu)勢(shì):

(1)適用于較大面數(shù)的模型,具備良好的擴(kuò)展性.

(2)只需要一套模型.

(3)可以自由縮減模型的面數(shù).

3 自動(dòng)LOD 算法

3.1 自動(dòng)LOD 加載模型流程

自動(dòng)LOD 加載模型總體流程如圖4所示.

圖4 自動(dòng)LOD 加載模型流程

3.2 三角邊坍縮

為了能夠?qū)δＰ褪褂镁W(wǎng)格簡(jiǎn)化選擇三角邊坍縮的辦法實(shí)現(xiàn),可以讓兩個(gè)頂點(diǎn)并成一個(gè)頂點(diǎn),如圖5所示.

圖5 三角邊坍縮

要實(shí)現(xiàn)邊uv的坍縮需要?jiǎng)h除兩側(cè)的面A和B,使用點(diǎn)v來(lái)代替點(diǎn)u,需要進(jìn)行點(diǎn)的連接操作,目標(biāo)是連接點(diǎn)v和點(diǎn)u的鄰點(diǎn)還要除去點(diǎn)u,點(diǎn)v為點(diǎn)u的坍縮目標(biāo).

對(duì)于1 個(gè)實(shí)體模型(具有封閉的邊界,根據(jù)邊界可以將空間分為模型內(nèi)部和模型外部2 部分),1 次坍縮,可以移除2 個(gè)三角面,3 條邊和1 個(gè)頂點(diǎn).通過(guò)反復(fù)的迭代,最終就會(huì)使模型簡(jiǎn)化到預(yù)期的面數(shù).

如果想要?jiǎng)h除掉某個(gè)點(diǎn)還要盡量保持原始模型外觀(guān)這就需要考慮到坍縮的代價(jià)公式如下:

在式(1)中頂點(diǎn)u的三角形被包含于集合Tu里,頂點(diǎn)u和頂點(diǎn)v的三角形被包含于集合Tuv里.

式(1)中需要考慮兩個(gè)頂點(diǎn)點(diǎn)u坍縮到點(diǎn)v并且需要將頂點(diǎn)u刪除這一系列操作所花費(fèi)的代價(jià).首先需要處理的是邊,在網(wǎng)格簡(jiǎn)化的流程中,無(wú)關(guān)緊要的部分是首要剔除的部分.其次應(yīng)該要注意頂點(diǎn)u附近的曲率,因?yàn)橹挥挟?dāng)點(diǎn)周?chē)那试狡教?那么這個(gè)點(diǎn)也就越不重要.值得關(guān)注的是,連個(gè)頂點(diǎn)從點(diǎn)u坍縮到點(diǎn)v和從點(diǎn)v坍縮到點(diǎn)u的代價(jià)有所不同.

根據(jù)上述公式,依賴(lài)于針對(duì)點(diǎn)與其周?chē)忺c(diǎn)坍縮的代價(jià)進(jìn)行計(jì)算,再?zèng)Q定以代價(jià)最小的鄰點(diǎn)為目標(biāo)進(jìn)行坍縮運(yùn)算.

3.3 實(shí)現(xiàn)細(xì)節(jié)

根據(jù)以上的描述,可以將實(shí)現(xiàn)分為以下步驟:

(1)遍歷模型上點(diǎn)、邊和面的關(guān)系.

(2)計(jì)算坍縮代價(jià)和坍縮目標(biāo),并排序.

(3)通過(guò)公式找到坍縮代價(jià)最小的頂點(diǎn),通過(guò)衡量相鄰頂點(diǎn)的的坍縮代價(jià)和坍縮目標(biāo),實(shí)時(shí)調(diào)整有序列表.

(4)再次遍歷頂點(diǎn),計(jì)算設(shè)置頂點(diǎn)數(shù)量是否小于現(xiàn)頂點(diǎn)數(shù)量,如果是則重復(fù)第(3)步.

因?yàn)樵诔绦蜻\(yùn)行的時(shí)候不能夠?qū)崟r(shí)進(jìn)行上述步驟,特別是第(2)步,因?yàn)槿康捻旤c(diǎn)被遍歷了很多次,不必要的工作量過(guò)于繁重.因此,可以考慮將工作分成離線(xiàn)烘培和運(yùn)行時(shí)這兩個(gè)步驟,具體實(shí)現(xiàn)步驟如圖6所示.

圖6 實(shí)現(xiàn)步驟

3.4 離線(xiàn)烘焙

離線(xiàn)烘焙會(huì)輸出兩個(gè)int 數(shù)組:permutation和vertex_map.

步驟:

(1)收集頂點(diǎn)信息:主要是頂點(diǎn)位置和index,另外需要初始化兩個(gè)列表:包含頂點(diǎn)的三角面列表和頂點(diǎn)的鄰居列表.

(2)收集三角面信息:需要得到模型上所有三角面里所含有的頂點(diǎn)和計(jì)算法線(xiàn)(目的是計(jì)算曲率).并且不斷更新頂點(diǎn)的三角面列表將新的三角形填入列表,還需要使每個(gè)頂點(diǎn)加入另外兩個(gè)頂點(diǎn)的鄰居列表中.

(3)通過(guò)不斷分析點(diǎn)與該點(diǎn)鄰點(diǎn)的坍縮代價(jià),決定坍縮代價(jià)最小的鄰點(diǎn)為最終的目標(biāo).

(4)依據(jù)坍縮代價(jià)對(duì)所有的頂點(diǎn)進(jìn)行排序.

(5)替換坍縮代價(jià)最小的頂點(diǎn):根據(jù)坍縮公式設(shè)法得到代價(jià)最小的點(diǎn)u和它的鄰邊目標(biāo)點(diǎn)v,讀取包含頂點(diǎn)u的三角面列表,只要哪個(gè)三角面里面含有頂點(diǎn)v就刪除該三角面,如果不能遍歷到就將頂點(diǎn)u與頂點(diǎn)v進(jìn)行交換.再次分析頂點(diǎn)u鄰點(diǎn)的坍縮代價(jià)以及坍縮目標(biāo),根據(jù)最新的信息重新編排列表.

(6)令permutation[u.index]=當(dāng)前頂點(diǎn)數(shù)量,令vertex_map[u.index]=v.index(如果沒(méi)有坍縮目標(biāo),則賦值為-1).

(7)目前的點(diǎn)數(shù)大于0,如果是將返回第(5)步.

permutation保存了每個(gè)頂點(diǎn)被移除的倒數(shù)次序(1 是最后被移除的,最大的是第一個(gè)被移除的),vertex_map保存了每個(gè)頂點(diǎn)的坍縮目標(biāo)的位置.

3.5 運(yùn)行時(shí)

輸入需要繪制的最大頂點(diǎn)數(shù)量n.

步驟:

(1)遍歷三角面.

①獲得當(dāng)前三角面的三個(gè)頂點(diǎn)的index,即idx0、idx1和idx2.

②如果permutation[idx0]=n則idx0=vertex_map[idx0],否則執(zhí)行第⑤步.

③如果idx0==-1 oridx1==idx0 oridx2==idx0,該三角面不參與繪制.同理映射并判斷idx1 和idx2.

④返回第①步.

⑤當(dāng)前三角面加入繪制列表.

(2)根據(jù)三角面的數(shù)據(jù),整理頂點(diǎn)屬性.

值得注意的是,員網(wǎng)格信息將不會(huì)被刪除,再程序運(yùn)行的時(shí)候,還能夠再任意的層次細(xì)節(jié)模型上切換.

3.6 細(xì)節(jié)優(yōu)化

如果想要有出色的游戲性能以及更佳的畫(huà)面效果,該研究還可繼續(xù)改進(jìn)上述步驟:

(1)最小堆排序:在離線(xiàn)烘培的第(4)步中,應(yīng)該考慮需刪除點(diǎn)的鄰點(diǎn)的坍縮代價(jià),同時(shí)坍縮列表也要隨之更新.因此可以選擇最小優(yōu)先隊(duì)列(最小堆)記住頂點(diǎn)和坍縮代價(jià),根據(jù)新的信息重新完善頂點(diǎn)的順序.

(2)刪除不用頂點(diǎn):需要提高幀率并通過(guò)減少攝像機(jī)前的三角面和頂點(diǎn)降低渲染壓力,在第(2)步中,需要依靠三角面的數(shù)據(jù)對(duì)Mesh 的頂點(diǎn)數(shù)組(還有uv、uv2、colors、normals、tangents、boneWeights等)和三角面數(shù)組進(jìn)行重新排列.

(3)邊界點(diǎn)處理:在處理過(guò)程中有兩個(gè)問(wèn)題比較棘手,一種是不閉合的三角面,例如飄帶、披風(fēng)等.另外一種是兩個(gè)墊高點(diǎn)雖然有相同的坐標(biāo),但是不同的uv或normal,例如Unity3D 的Sphere 是有一條接縫的.假如這兩種情況不進(jìn)行參考,在坍縮的過(guò)程中,將會(huì)出現(xiàn)沒(méi)能指出對(duì)的坍縮目標(biāo)來(lái)代替原頂點(diǎn),會(huì)發(fā)生鏤空和破損的情況.根據(jù)上面說(shuō)的問(wèn)題,我們?cè)诳紤]坍縮消耗的問(wèn)題上,會(huì)將這些邊緣點(diǎn)的曲率設(shè)為2 (可以在編輯器里調(diào)整).

(4)內(nèi)存優(yōu)化:如果不想多次重新建立Mesh 的vertices等數(shù)組,可以選擇unsafe 的方式來(lái)改變數(shù)組的大小.

(5)JobSystem:離線(xiàn)烘焙中使用了JobSystem 來(lái)加速烘焙.

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

本論文選取天津工業(yè)大學(xué)的生成模型場(chǎng)景為例子,驗(yàn)證過(guò)程為自動(dòng)LOD 算法與遮擋刪除技術(shù),動(dòng)態(tài)加載,普通漫游分別對(duì)同一場(chǎng)景隨即視點(diǎn)位置進(jìn)行渲染,對(duì)比各項(xiàng)渲染數(shù)據(jù).

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

FPS (Time per frame and FPS):Frames Per Seconds表示引擎處理和渲染一個(gè)游戲幀所花費(fèi)的時(shí)間,該數(shù)字主要受到場(chǎng)景中渲染物體數(shù)量和GPU 性能的影響,FPS 數(shù)值越高,游戲場(chǎng)景的漫游體驗(yàn)會(huì)更加平穩(wěn)和舒適.

CPU:獲取到當(dāng)前占用CPU 進(jìn)行計(jì)算的時(shí)間絕對(duì)值或時(shí)間點(diǎn),如果Unity 主進(jìn)程處于掛斷或休眠狀態(tài)時(shí),CPU time 將會(huì)保持不變.

Tris ＆Verts:攝像機(jī)下的所有三角形和頂點(diǎn)這也是主要瓶頸.

圖7中描述了各個(gè)算法之間在同一場(chǎng)景下,攝像機(jī)前三角面和頂點(diǎn)的數(shù)量,三角面與頂點(diǎn)的數(shù)量呈反比,數(shù)量越大計(jì)算機(jī)所需要做的工作就越多.

圖7 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

圖8中描述了各個(gè)算法之間在同一場(chǎng)景下,幀率和CPU 進(jìn)行計(jì)算的時(shí)間,因?yàn)镕PS 和CPU 的數(shù)值與三角面和頂點(diǎn)數(shù)量有直接關(guān)系,所以提出自動(dòng)LOD 算法.

圖8 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

文中使用的方法自動(dòng)LOD 考慮到了之前幾種優(yōu)化方法的缺點(diǎn)(算法優(yōu)缺點(diǎn)對(duì)比如表1所示),通過(guò)使用三角邊坍縮算法,不僅節(jié)省了模型導(dǎo)出和導(dǎo)入步驟還節(jié)省了大量的內(nèi)存空間.

表1 算法優(yōu)缺點(diǎn)對(duì)比

5 總結(jié)

針對(duì)大型場(chǎng)景漫游提出了新的自動(dòng)LOD 技術(shù),實(shí)驗(yàn)解決了只使用一套生成模型就可以應(yīng)用LOD 技術(shù)的方法,減少了工作的步驟,對(duì)工程中大型生成場(chǎng)景模型的漫游實(shí)施了優(yōu)化處理,不僅提高游戲幀率,而且減少當(dāng)前占用CPU 進(jìn)行計(jì)算的時(shí)間,還節(jié)省了不必要的存儲(chǔ)空間,具有一定的參考價(jià)值和實(shí)際意義.