游戲設(shè)計(jì)----場(chǎng)景管理

1、三維游戲中的圖形技術(shù)可分為三個(gè)方面 場(chǎng)景的幾何組織與優(yōu)化 著重于提高繪制效率 場(chǎng)景的畫面真實(shí)度,采用一系列特效生成技術(shù) 包括高級(jí)紋理映射,過(guò)程式建模等 基于真實(shí)物理定律的游戲效果模擬 主要是陰影模擬和碰撞檢測(cè)本次課程將著重講解三維游戲場(chǎng)景的幾何組織,優(yōu)化管理以及在此基礎(chǔ)上的OGRE中的復(fù)雜場(chǎng)景的管理三維場(chǎng)景的組織和管理游戲場(chǎng)景的幾何優(yōu)化三維場(chǎng)景的快速可見性判斷與消隱地形場(chǎng)景的繪制與漫游碰撞檢測(cè)簡(jiǎn)介第一步 根據(jù)游戲的需要更新場(chǎng)景圖必要的部分 這種更新是部分的,不需要從根節(jié)點(diǎn)遍歷第二步 場(chǎng)景圖的剔除和繪制太陽(yáng)系的場(chǎng)景圖把場(chǎng)景物體按照繪制狀態(tài)分類繪制狀態(tài)集合A 磚塊紋理 細(xì)節(jié)紋理 紅色材質(zhì) 無(wú)融合模

2、式繪制狀態(tài)集合B 磚塊紋理 細(xì)節(jié)紋理 灰色材質(zhì) 無(wú)融合模式繪制狀態(tài)集合C 磚塊紋理 凹凸紋理 紅色材質(zhì) 無(wú)融合模式繪制狀態(tài)集合D 立方體紋理 無(wú)紋理 單色材質(zhì) 加法融合模式 繪制狀態(tài)集合實(shí)例 磚塊紋理 細(xì)節(jié)紋理 紅色材質(zhì) 無(wú)融合模式 灰色材質(zhì) 無(wú)融合模式 凹凸紋理 紅色材質(zhì) 無(wú)融合模式 立方體紋理 無(wú)紋理 單色材質(zhì) 加法融合模式 加速判斷場(chǎng)景物體之間的空間關(guān)系,主要有兩種方法 對(duì)單個(gè)物體建立包圍體,在包圍體的基礎(chǔ)上建立包圍盒層次樹 場(chǎng)景剖分 （1）包圍球 （2）AABB 包圍盒 （3）OBB 包圍盒 （4）平行六面包圍體 （5）k 對(duì)平行面包圍體 球的體積比立方體大球的體積比立方體大常用的類型

3、 增量式(incremental) 禮包式(gift-wrapping) 分治式(divide-and-conquer) 快速凸包算法(quick-hull) k-dop(discreted orientation polytope,離散有向多面體) 比上述的包圍體更緊密地包圍原物體,創(chuàng)建的層次樹節(jié)點(diǎn)更少將場(chǎng)景中的幾何物體通過(guò)層次性機(jī)制組織起來(lái) 優(yōu)點(diǎn) 使用靈活,能快速剔除層次樹的整個(gè)分枝注意注意 要保持樹的平衡要保持樹的平衡!BSP樹 （左）場(chǎng)景的BSP樹剖分；（右）BSP樹結(jié)構(gòu)示意圖 （左）一次剖分后的場(chǎng)景平面圖；（右）一次剖分后的BSP樹 （左）兩次剖分后的場(chǎng)景平面圖；（右）兩次剖分后的B

4、SP樹 用畫家算法無(wú)法處理四個(gè)嵌套遮擋的多邊形情形 （a）場(chǎng)景多邊形； （b）第一次剖分； （c）第二次剖分 （a） （b） （c）（a）初始節(jié)點(diǎn)； （b）第一次剖分； （c）第二次剖分（左）場(chǎng)景包圍體技術(shù)（右）場(chǎng)景剖分技術(shù) 技 術(shù) 名 稱適 用 場(chǎng) 景構(gòu)建復(fù)雜度實(shí) 用 性二叉樹尺寸不是特別大的室內(nèi)建筑場(chǎng)景復(fù)雜大部分三維游戲引擎四叉樹室外基于高度場(chǎng)的地形一般僅用于地形繪制八叉樹大規(guī)模三維室內(nèi)、外空間場(chǎng)景一般復(fù)雜三維游戲引擎均勻八叉樹體素表示場(chǎng)景、分布均勻的三維場(chǎng)景簡(jiǎn)單少量三維游戲引擎場(chǎng)景包圍體技術(shù)場(chǎng)景剖分技術(shù)表 示 方 式層次物體表示層次空間表示剖 分 方 式物體剖分場(chǎng)景剖分聚 類 方 式物體

5、的層次聚類空間的層次聚類層 次 細(xì) 節(jié)物體層次細(xì)節(jié)空間層次細(xì)節(jié)主 要 作 用圍繞物體將空間區(qū)域區(qū)分開來(lái)圍繞區(qū)域?qū)⑽矬w區(qū)分開來(lái)代 表 方 法包圍球樹OBB-樹、AABB樹、k-DOPS二叉樹、四叉樹、八叉樹、均勻三維網(wǎng)格、kD樹簡(jiǎn)單取舍型LOD平滑過(guò)渡型LOD靜態(tài)LOD動(dòng)態(tài)LOD頂點(diǎn)刪除邊刪除 最有效!面刪除基于邊刪除的頂點(diǎn)簡(jiǎn)化 對(duì)于數(shù)據(jù)量龐大的復(fù)雜模型 LOD模型只能預(yù)先產(chǎn)生多個(gè)間斷的簡(jiǎn)化模型 引起實(shí)時(shí)繪制時(shí)圖形畫面的跳躍為克服LOD的缺點(diǎn),Huppe等人于1995年提出 漸進(jìn)網(wǎng)格技術(shù)(Progressive Mesh) 預(yù)計(jì)算簡(jiǎn)化過(guò)程中原頂點(diǎn)和新頂點(diǎn)的關(guān)系 由基本網(wǎng)格模型逐步恢復(fù)模型細(xì)節(jié)De

6、mo適用于人造建筑物少的室外場(chǎng)景代表性算法:基于陰影體技術(shù)（左）遮擋剔除之前；（右）基于陰影體的遮擋剔除 （左）球A 至少在一個(gè)平面之外，球B在所有平面之內(nèi)，但其半徑大于球心到其中一個(gè)平面的距離，球C在所有平面之后且到所有平面的距離足夠大。（右）一種包圍球沒(méi)有被完全遮擋但包圍盒被完全遮擋的情形，故物體不應(yīng)被繪制 可見性（Visibility）算法用于決定場(chǎng)景中可能可見的物體 一般的：保守地指定這些物體并將他們發(fā)送到圖形繪制引擎 確切的可見性決定對(duì)于游戲而言是可能的，但是代價(jià)太大 因此，存在平衡：在軟件中進(jìn)行可見性判斷的時(shí)間和在硬件中繪制多余的不可見物體的代價(jià)最簡(jiǎn)單的就是繪制引擎本身自帶的視域裁

7、剪算法 但是這個(gè)算法對(duì)于高度復(fù)雜性的場(chǎng)景并不合適，特別當(dāng)很多物體位于單個(gè)象素之后 比如，第一人稱視角游戲中常見的建筑物具有高度的深度復(fù)雜性。Cell-to-Cell 可見性 告知在一個(gè)cell中的某點(diǎn)處是否可以看到其他的房間 但是無(wú)法知道每個(gè)房間的那個(gè)部分可能是可見的，也無(wú)法知道觀察者在這個(gè)房間的哪個(gè)地方可以見到另外的房間Cell-to-Region 可見性 可以知道某點(diǎn)處，其他房間的哪些部分是可見的 Cell-To-Object: 對(duì)于某給定的房間，告知哪些物體是可見的。Eye-To-Region 可見性 記錄當(dāng)前視點(diǎn)處的哪些房間的哪些部分是可見的 同理，Eye-to-Cell 以及 Eye

8、-To-Objecto 根據(jù)單元與單元之間的鄰接圖,通過(guò)深度遍歷建立起單元與單元的入口序列分為兩類 精細(xì)型入口繪制方式 粗略型入口繪制技術(shù)優(yōu)點(diǎn) 方便定義場(chǎng)景 快速繪制缺點(diǎn) 消耗大量的內(nèi)存,換取效率的提高 不適合室外渲染許多可見性算法假設(shè)單元和入口的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)類似于一個(gè)圖：節(jié)點(diǎn)是房間，邊是入口 Portals本質(zhì)的意思是兩個(gè)房間的墻之間存在洞 Portal 形狀一般是多邊形 兩個(gè)房間之間也可有多個(gè)Portals如何建立這個(gè)數(shù)據(jù)圖？ Kd-trees 或者BSP樹用于生成cell結(jié)構(gòu)以及尋找與之相關(guān)的 portals 自動(dòng)或者手工生成建筑物最合適這種情況Portals 可以是房間的邊緣（即

9、墻壁）Graph一般保存相鄰信息 每個(gè)房間保留其外向的邊（即portals）ABCDEFABCDEF跟蹤觀察者所在的房間然后遍歷graph窮舉所有可見的區(qū)域 可以預(yù)處理，對(duì)每一個(gè)房間計(jì)算可能可見集合potentially visible set (PVS) Cell-to-region 可見性，或者 cell-to-object 可見性 也可以在運(yùn)行之間更進(jìn)一步地精確獲得可見集合 從已知觀察者的位置出發(fā) Eye-to-region 或者 Eye-to-cell 可見性 平衡：節(jié)省下列的時(shí)間 vs. 計(jì)算小的可能可見集合的代價(jià) 與所在環(huán)境有關(guān)，如房間的尺寸、房間物體的個(gè)數(shù)PVS: 對(duì)于某個(gè)特定的

10、房間，可能可以看到的房間/區(qū)域/物體/多邊形 一般地，保存可以看見的物體的標(biāo)識(shí)號(hào) 也要考慮內(nèi)存的因素預(yù)處理的計(jì)算過(guò)程 應(yīng)該能良好地管理動(dòng)態(tài)變化的物體列表用法: 可見性確定 對(duì)于當(dāng)前房間，繪制所有PVS中的多邊形 做為第一步：獲得可能相關(guān)的區(qū)域，并做進(jìn)一步處理Cell A 在 B的 PVS中，當(dāng)且僅當(dāng)存在一根線，從B出發(fā)射到A，并且在途中與任何物體不相交 隔壁房間理所當(dāng)然在PVS之中IJHGACBEFDI 的PVS 包括:B, C, E, F, H, J這個(gè)樹狀結(jié)構(gòu)表示: 當(dāng)前房間的PVS 一個(gè)串著的相關(guān)的portal序列在進(jìn)一步的可見性處理中 可以減少需要檢查處理的cells/portals

11、數(shù)目ACDEA/CC/D1C/D2C/EABCDEFDFD/F大多數(shù)算法比cell-to-cell可見性算法更復(fù)雜 因?yàn)樗^(guò)估計(jì) 當(dāng)實(shí)際上99.6%的模型應(yīng)該是不可見的時(shí)候，僅排除了大約90%的模型, 而更好的算法可以排除98%但是，保持cell-to-cell可見性有利于動(dòng)態(tài)物體 當(dāng)房間中有一個(gè)移動(dòng)的物體 并且房間是靜態(tài)的存在的問(wèn)題: 將一個(gè)房間中的所有物體都標(biāo)記為可能可見，盡管只有一小部分是可能可見 如果我們要列出可能可見集意味著我們要將這個(gè)房間中的所有物體都列出來(lái)。 并沒(méi)有考慮到觀察者的位置，無(wú)法報(bào)告觀察者可能看不到的物體進(jìn)一步處理可以解決這個(gè)問(wèn)題記錄房間中某點(diǎn)處可能可見的某個(gè)房間的某個(gè)

12、區(qū)域 因此，只繪制這個(gè)區(qū)域中的物體關(guān)鍵想法視設(shè)置隔離平面（對(duì)于二維，就是隔離線):如果將左邊的portal視為光源PVS 完全是一個(gè)預(yù)處理過(guò)程 在運(yùn)行時(shí)刻，只需要繪制PVS即可更進(jìn)一步的優(yōu)化是做進(jìn)一步處理 有時(shí)候由PVS指導(dǎo) 大多數(shù)游戲不這么做一個(gè)可能的辦法是觀察者的位置已知,因此可以使用 Eye-to-Region的可見性View很多場(chǎng)景并沒(méi)有好的cell和portal結(jié)構(gòu) 場(chǎng)景中沒(méi)有大的共面多邊形去做為遮擋器或者房間的墻 例如森林-你無(wú)法看到后面的場(chǎng)景，但是總不能設(shè)置葉子為Cell解決方案? 定義一些遮擋物體，稱為occluders并利用他們來(lái)剔除幾何物體若 occluder是一個(gè)多邊形

13、否則，使用物體的側(cè)影輪廓線從視點(diǎn)和多邊形的邊構(gòu)成裁剪平面 也叫支撐平面：Supporting planes所有在支撐平面內(nèi)部的是不可見的 Occluder自身是一個(gè)裁剪平面 位于其外部的是可見的eyeoccludersupporting planesOccluders 一般在預(yù)處理階段獲得選擇的標(biāo)準(zhǔn)? 如果它遮擋了很多物體如果大的多邊形與視點(diǎn)很近，該方法很有效場(chǎng)景中的一些物體也可以融合起來(lái)形成大的occluders 例如，將很多樹的billboards融合 occluding 多邊形可以任意指定，但是，每一occluder 只對(duì)某一些視點(diǎn)區(qū)域有效問(wèn)題：如果一個(gè)物體被某個(gè)occluder部分遮擋

14、,又被另外一個(gè)部分遮擋, 那么很難決定是否該物體被全部遮擋用多個(gè)occluders來(lái)隱藏一個(gè)物體是一個(gè)很有趣的問(wèn)題 Hierarchical Z-Buffer 方法在圖像（屏幕）空間建立遮擋子 需要特殊的圖形硬件與軟件實(shí)現(xiàn) 張寒松的Hierarchical Occlusion Maps（層次遮擋圖） 將遮擋子繪制到一個(gè)紋理圖中，然后將物體與紋理比較 Schaufler Occluder Fusion 建立一個(gè)被遮擋區(qū)域的空間數(shù)據(jù)結(jié)構(gòu)當(dāng)打開遮擋面剔除時(shí)，僅需繪制7,000個(gè)三角形，幀率為50fps。當(dāng)遮擋面剔除關(guān)閉時(shí)，三角形繪制數(shù)目增長(zhǎng)到17,300, 幀率下降到20 fps （上左）地形的基礎(chǔ)

15、三角網(wǎng)格； （上右）高度圖；（下左）應(yīng)用高度圖后的地形網(wǎng)格； （下右）渲染后的地形圖 基于四叉樹的繪制方法 利用圖形硬件加速 繪制模式 保留模式 立即模式繪制優(yōu)化 使用場(chǎng)景的層次剖分技術(shù)進(jìn)行視域剔除 消除對(duì)畫面貢獻(xiàn)極小的多邊形根據(jù)當(dāng)前節(jié)點(diǎn)的誤差度量判斷是否需要繼續(xù)剖分可能在兩個(gè)相連的節(jié)點(diǎn)之間產(chǎn)生漏洞 解決方法 保證兩個(gè)相鄰節(jié)點(diǎn)之間最多相差1個(gè)層次 保證兩個(gè)相鄰的邊擁有相同的頂點(diǎn)數(shù)目 正確 錯(cuò)誤 動(dòng)態(tài)層次細(xì)節(jié)算法 缺點(diǎn) 層次之間切換會(huì)產(chǎn)生跳躍感幾何變形法 具有光滑過(guò)渡的視覺(jué)效果存儲(chǔ)量大,內(nèi)存消耗太多解決的方法 細(xì)節(jié)紋理 細(xì)節(jié)紋理的拼接具有很大的挑戰(zhàn)性!在OGRE中場(chǎng)景管理器的類型有四種： ST_

16、GENERIC 普通場(chǎng)景 ST_EXTERIOR_CLOSE 室外封閉場(chǎng)景 ST_EXTERIOR_FAR 室外無(wú)限場(chǎng)景 ST_INTERIOR 室內(nèi)場(chǎng)景首先讀入地圖包。代碼如下BspApplication() / Load Quake3 locations from a file ConfigFile cf; cf.load(quake3settings.cfg); mQuakePk3 = cf.getSetting(Pak0Location); mQuakeLevel = cf.getSetting(Map); void chooseSceneManager(void) mSceneMgr

17、 = mRoot- getSceneManager(ST_INTERIOR); void createScene(void) / Load world geometry mSceneMgr-setWorldGeometry(mQuakeLevel); / modify camera for close work mCamera-setNearClipDistance(4); mCamera-setFarClipDistance(4000); / Also change position, and set Quake-type orientation / Get random player st

18、art point ViewPoint vp = mSceneMgr-getSuggestedViewpoint(true); mCamera-setPosition(vp.position); mCamera-pitch(90); / Quake uses X/Y horizon, Z up mCamera-rotate(vp.orientation); / Dont yaw along variable axis, causes leaning mCamera-setFixedYawAxis(true, Vector3:UNIT_Z); OGRE在其引擎提供的Plugin_OctreeSc

19、eneManager.dll插件中提供了通過(guò)八叉樹算法實(shí)現(xiàn)的ST_EXTERIOR_CLOSE室外封閉場(chǎng)景管理器。 首先需要選擇室外場(chǎng)景管理器，代碼如下：virtual void chooseSceneManager(void) / Get the SceneManager, in this case a generic one mSceneMgr = mRoot-getSceneManager( ST_EXTERIOR_CLOSE );選擇好室外場(chǎng)景管理器后，通過(guò)該場(chǎng)景管理器創(chuàng)建場(chǎng)景就可以了。void createScene(void) / Set ambient light mSceneM

20、gr-setAmbientLight(ColourValue(0.5, 0.5, 0.5); / Create a light Light* l = mSceneMgr-createLight(MainLight); / Accept default settings: point light, white diffuse, just set position / NB I could attach the light to a SceneNode if I wanted it to move automatically with / other objects, but I dont l-s

21、etPosition(20,80,50); mSceneMgr - setWorldGeometry( terrain.cfg ); mSceneMgr-setFog( FOG_EXP2, ColourValue:White, .008, 0, 250 ); mRoot - showDebugOverlay( true );碰撞檢測(cè)問(wèn)題 是機(jī)器人、動(dòng)畫仿真、虛擬現(xiàn)實(shí)等領(lǐng)域不可回避的問(wèn)題基本任務(wù) 確定兩個(gè)或多個(gè)物體彼此之間是否發(fā)生接觸或穿透。起源 早期在機(jī)器人路徑規(guī)劃、自動(dòng)裝配規(guī)劃等領(lǐng)域中，為檢測(cè)機(jī)器人與場(chǎng)景中的物體或零件與零件之間是否發(fā)生碰撞，產(chǎn)生了一系列碰撞檢測(cè)算法。從兩個(gè)角度對(duì)碰撞檢測(cè)算法

22、進(jìn)行分類 從時(shí)間域的角度來(lái)分 從空間域的角度來(lái)分 分為靜態(tài)、離散和連續(xù)的碰撞檢測(cè)算法靜態(tài)碰撞檢測(cè)算法 靜止?fàn)顟B(tài)下進(jìn)行碰撞檢測(cè) Dobkin 1985Agarwal 1991Chazelle 1989 離散碰撞檢測(cè)算法 在每一時(shí)間的離散點(diǎn)上進(jìn)行碰撞檢測(cè) 是研究的重點(diǎn)和熱點(diǎn) Lin 1998Jimnez 2001 離散碰撞檢測(cè)算法 存在問(wèn)題 存在刺穿現(xiàn)象 遺漏應(yīng)該發(fā)生的碰撞 連續(xù)碰撞檢測(cè)算法 連續(xù)的時(shí)間間隔內(nèi)進(jìn)行碰撞檢測(cè) 計(jì)算速度還太慢 Cameron 1990Canny 1986Redon 2001Redon 2002a基于物體空間的碰撞檢測(cè)算法基于圖象空間的碰撞檢測(cè)算法基于物體空間的碰撞檢測(cè)算

23、法 采用一般表示模型的碰撞檢測(cè)算法 采用空間結(jié)構(gòu)的碰撞檢測(cè)算法 基于物體空間的碰撞檢測(cè)算法 采用一般表示模型的碰撞檢測(cè)算法 多邊形表示模型 多邊形集合，結(jié)構(gòu)化表示模型 非多邊形表示模型 CSG表示模型，隱函數(shù)曲面，參數(shù)曲面，體表示模型 多邊形表示模型 非多邊形表示模型 結(jié)構(gòu)化表示模型 多邊形集合 CSG 表示模型 隱函數(shù)曲面 參數(shù)曲面 幾何模型 體表示模型 基于物體空間的碰撞檢測(cè)算法 采用一般表示模型的碰撞檢測(cè)算法 面向多邊形表示模型的碰撞檢測(cè)算法 Hubbard 1995Gottschalk 1996 Klosowski 1998Zachmann 1998 面向凸體的碰撞檢測(cè)算法基于物體空間

24、的碰撞檢測(cè)算法 面向凸體的碰撞檢測(cè)算法 基于特征的碰撞檢測(cè)算法 Lin-Canny的“最鄰近特征算法”Lin 1991, Lin1993 Lin 1995, Cohen 1995, Chung 1996, Mirtich 1998, Ehmann 2000, Ehmann 2001 基于單純形（Simplex）的碰撞檢測(cè)算法 Gilbert、Johnson和Keerthi Gilbert 1988Gilbert 1990提出的GJK算法 Cameron 1997Bergen 1999 基于物體空間的碰撞檢測(cè)算法 采用一般表示模型的碰撞檢測(cè)算法 面向CSG表示模型 Zeiller 1993Su 1996Poutain 2001 面向隱函數(shù)曲面表示 Farouki 1989Miller 1991Shene 1991 面向參數(shù)曲面表示 非均勻有理B樣條曲線（NURBS） Turnbull 1998 體表示模型 主要用于虛擬手術(shù)中可變形物體的碰撞檢測(cè) Heidelb 2003Boyles1999魏迎梅 2001 基于物體空間的碰撞檢測(cè)算法采用一般表示模型的碰撞檢測(cè)算法采用空間結(jié)構(gòu)的碰撞檢測(cè)算法空間剖分法（space decomposition）均勻剖分、BSP樹、k-d樹和八叉樹（Octree）等Samet 1989Naylor 1990Bourma 1991 層次包圍