【培訓(xùn)課件】游戲中的場景管理技術(shù)(共99張)

1、 對游戲的評價（每個人） 10% 小組游戲proposal (每組) 10% 對其他小組游戲proposal的評價（每組）10% 請用OGRE實現(xiàn)任意一項 10% 三維光照 場景組織 光影特效（包括陰影） 大程作業(yè) 40% 平時點名 20%三維游戲中的圖形技術(shù)可分為三個方面 場景的幾何組織與優(yōu)化 著重于提高繪制效率 場景的畫面真實度,采用一系列特效生成技術(shù) 包括高級紋理映射,過程式建模等 基于真實物理定律的游戲效果模擬 主要是陰影模擬和碰撞檢測本次課程將著重講解三維游戲場景的幾何組織,優(yōu)化管理以及在此基礎(chǔ)上的OGRE中的復(fù)雜場景的管理三維場景的組織和管理游戲場景的幾何優(yōu)化三維場景的快速可見性判

2、斷與消隱地形場景的繪制與漫游碰撞檢測簡介第一步 根據(jù)游戲的需要更新場景圖必要的部分 這種更新是部分的,不需要從根節(jié)點遍歷第二步 場景圖的剔除和繪制太陽系的場景圖把場景物體按照繪制狀態(tài)分類繪制狀態(tài)集合A 磚塊紋理 細(xì)節(jié)紋理 紅色材質(zhì) 無融合模式繪制狀態(tài)集合B 磚塊紋理 細(xì)節(jié)紋理 灰色材質(zhì) 無融合模式繪制狀態(tài)集合C 磚塊紋理 凹凸紋理 紅色材質(zhì) 無融合模式繪制狀態(tài)集合D 立方體紋理 無紋理 單色材質(zhì) 加法融合模式 繪制狀態(tài)集合實例 磚塊紋理 細(xì)節(jié)紋理 紅色材質(zhì) 無融合模式 灰色材質(zhì) 無融合模式 凹凸紋理 紅色材質(zhì) 無融合模式 立方體紋理 無紋理 單色材質(zhì) 加法融合模式 加速判斷場景物體之間的空間關(guān)

3、系,主要有兩種方法 對單個物體建立包圍體,在包圍體的基礎(chǔ)上建立包圍盒層次樹 場景剖分 （1）包圍球 （2）AABB 包圍盒 （3）OBB 包圍盒 （4）平行六面包圍體 （5）k 對平行面包圍體 球的體積比立方體大球的體積比立方體大常用的類型 增量式(incremental) 禮包式(gift-wrapping) 分治式(divide-and-conquer) 快速凸包算法(quick-hull) k-dop(discreted orientation polytope,離散有向多面體) 比上述的包圍體更緊密地包圍原物體,創(chuàng)建的層次樹節(jié)點更少將場景中的幾何物體通過層次性機(jī)制組織起來 優(yōu)點 使用靈

4、活,能快速剔除層次樹的整個分枝注意注意 要保持樹的平衡要保持樹的平衡!BSP樹 （左）場景的BSP樹剖分；（右）BSP樹結(jié)構(gòu)示意圖 （左）一次剖分后的場景平面圖；（右）一次剖分后的BSP樹 （左）兩次剖分后的場景平面圖；（右）兩次剖分后的BSP樹 用畫家算法無法處理四個嵌套遮擋的多邊形情形 （a）場景多邊形； （b）第一次剖分； （c）第二次剖分 （a） （b） （c）（a）初始節(jié)點； （b）第一次剖分； （c）第二次剖分（左）場景包圍體技術(shù)（右）場景剖分技術(shù) 技 術(shù) 名 稱適 用 場 景構(gòu)建復(fù)雜度實 用 性二叉樹尺寸不是特別大的室內(nèi)建筑場景復(fù)雜大部分三維游戲引擎四叉樹室外基于高度場的地形一般

5、僅用于地形繪制八叉樹大規(guī)模三維室內(nèi)、外空間場景一般復(fù)雜三維游戲引擎均勻八叉樹體素表示場景、分布均勻的三維場景簡單少量三維游戲引擎場景包圍體技術(shù)場景剖分技術(shù)表 示 方 式層次物體表示層次空間表示剖 分 方 式物體剖分場景剖分聚 類 方 式物體的層次聚類空間的層次聚類層 次 細(xì) 節(jié)物體層次細(xì)節(jié)空間層次細(xì)節(jié)主 要 作 用圍繞物體將空間區(qū)域區(qū)分開來圍繞區(qū)域?qū)⑽矬w區(qū)分開來代 表 方 法包圍球樹OBB-樹、AABB樹、k-DOPS二叉樹、四叉樹、八叉樹、均勻三維網(wǎng)格、kD樹簡單取舍型LOD平滑過渡型LOD靜態(tài)LOD動態(tài)LOD頂點刪除邊刪除 最有效!面刪除基于邊刪除的頂點簡化 對于數(shù)據(jù)量龐大的復(fù)雜模型 LO

6、D模型只能預(yù)先產(chǎn)生多個間斷的簡化模型 引起實時繪制時圖形畫面的跳躍為克服LOD的缺點,Huppe等人于1995年提出 漸進(jìn)網(wǎng)格技術(shù)(Progressive Mesh) 預(yù)計算簡化過程中原頂點和新頂點的關(guān)系 由基本網(wǎng)格模型逐步恢復(fù)模型細(xì)節(jié)Demo適用于人造建筑物少的室外場景代表性算法:基于陰影體技術(shù)（左）遮擋剔除之前；（右）基于陰影體的遮擋剔除 （左）球A 至少在一個平面之外，球B在所有平面之內(nèi)，但其半徑大于球心到其中一個平面的距離，球C在所有平面之后且到所有平面的距離足夠大。（右）一種包圍球沒有被完全遮擋但包圍盒被完全遮擋的情形，故物體不應(yīng)被繪制 可見性（Visibility）算法用于決定場景

7、中可能可見的物體 一般的：保守地指定這些物體并將他們發(fā)送到圖形繪制引擎 確切的可見性決定對于游戲而言是可能的，但是代價太大 因此，存在平衡：在軟件中進(jìn)行可見性判斷的時間和在硬件中繪制多余的不可見物體的代價最簡單的就是繪制引擎本身自帶的視域裁剪算法 但是這個算法對于高度復(fù)雜性的場景并不合適，特別當(dāng)很多物體位于單個象素之后 比如，第一人稱視角游戲中常見的建筑物具有高度的深度復(fù)雜性。Cell-to-Cell 可見性 告知在一個cell中的某點處是否可以看到其他的房間 但是無法知道每個房間的那個部分可能是可見的，也無法知道觀察者在這個房間的哪個地方可以見到另外的房間Cell-to-Region 可見性

8、 可以知道某點處，其他房間的哪些部分是可見的 Cell-To-Object: 對于某給定的房間，告知哪些物體是可見的。Eye-To-Region 可見性 記錄當(dāng)前視點處的哪些房間的哪些部分是可見的 同理，Eye-to-Cell 以及 Eye-To-Objecto 根據(jù)單元與單元之間的鄰接圖,通過深度遍歷建立起單元與單元的入口序列分為兩類 精細(xì)型入口繪制方式 粗略型入口繪制技術(shù)優(yōu)點 方便定義場景 快速繪制缺點 消耗大量的內(nèi)存,換取效率的提高 不適合室外渲染許多可見性算法假設(shè)單元和入口的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)類似于一個圖：節(jié)點是房間，邊是入口 Portals本質(zhì)的意思是兩個房間的墻之間存在洞 Port

9、al 形狀一般是多邊形 兩個房間之間也可有多個Portals如何建立這個數(shù)據(jù)圖？ Kd-trees 或者BSP樹用于生成cell結(jié)構(gòu)以及尋找與之相關(guān)的 portals 自動或者手工生成建筑物最合適這種情況Portals 可以是房間的邊緣（即墻壁）Graph一般保存相鄰信息 每個房間保留其外向的邊（即portals）ABCDEFABCDEF跟蹤觀察者所在的房間然后遍歷graph窮舉所有可見的區(qū)域 可以預(yù)處理，對每一個房間計算可能可見集合potentially visible set (PVS) Cell-to-region 可見性，或者 cell-to-object 可見性 也可以在運行之間更進(jìn)

10、一步地精確獲得可見集合 從已知觀察者的位置出發(fā) Eye-to-region 或者 Eye-to-cell 可見性 平衡：節(jié)省下列的時間 vs. 計算小的可能可見集合的代價 與所在環(huán)境有關(guān)，如房間的尺寸、房間物體的個數(shù)PVS: 對于某個特定的房間，可能可以看到的房間/區(qū)域/物體/多邊形 一般地，保存可以看見的物體的標(biāo)識號 也要考慮內(nèi)存的因素預(yù)處理的計算過程 應(yīng)該能良好地管理動態(tài)變化的物體列表用法: 可見性確定 對于當(dāng)前房間，繪制所有PVS中的多邊形 做為第一步：獲得可能相關(guān)的區(qū)域，并做進(jìn)一步處理Cell A 在 B的 PVS中，當(dāng)且僅當(dāng)存在一根線，從B出發(fā)射到A，并且在途中與任何物體不相交 隔壁

11、房間理所當(dāng)然在PVS之中IJHGACBEFDI 的PVS 包括:B, C, E, F, H, J這個樹狀結(jié)構(gòu)表示: 當(dāng)前房間的PVS 一個串著的相關(guān)的portal序列在進(jìn)一步的可見性處理中 可以減少需要檢查處理的cells/portals 數(shù)目ACDEA/CC/D1C/D2C/EABCDEFDFD/F大多數(shù)算法比cell-to-cell可見性算法更復(fù)雜 因為它過估計 當(dāng)實際上99.6%的模型應(yīng)該是不可見的時候，僅排除了大約90%的模型, 而更好的算法可以排除98%但是，保持cell-to-cell可見性有利于動態(tài)物體 當(dāng)房間中有一個移動的物體 并且房間是靜態(tài)的存在的問題: 將一個房間中的所有物

12、體都標(biāo)記為可能可見，盡管只有一小部分是可能可見 如果我們要列出可能可見集意味著我們要將這個房間中的所有物體都列出來。 并沒有考慮到觀察者的位置，無法報告觀察者可能看不到的物體進(jìn)一步處理可以解決這個問題記錄房間中某點處可能可見的某個房間的某個區(qū)域 因此，只繪制這個區(qū)域中的物體關(guān)鍵想法視設(shè)置隔離平面（對于二維，就是隔離線):如果將左邊的portal視為光源PVS 完全是一個預(yù)處理過程 在運行時刻，只需要繪制PVS即可更進(jìn)一步的優(yōu)化是做進(jìn)一步處理 有時候由PVS指導(dǎo) 大多數(shù)游戲不這么做一個可能的辦法是觀察者的位置已知,因此可以使用 Eye-to-Region的可見性View很多場景并沒有好的cell

13、和portal結(jié)構(gòu) 場景中沒有大的共面多邊形去做為遮擋器或者房間的墻 例如森林-你無法看到后面的場景，但是總不能設(shè)置葉子為Cell解決方案? 定義一些遮擋物體，稱為occluders并利用他們來剔除幾何物體若 occluder是一個多邊形 否則，使用物體的側(cè)影輪廓線從視點和多邊形的邊構(gòu)成裁剪平面 也叫支撐平面：Supporting planes所有在支撐平面內(nèi)部的是不可見的 Occluder自身是一個裁剪平面 位于其外部的是可見的eyeoccludersupporting planesOccluders 一般在預(yù)處理階段獲得選擇的標(biāo)準(zhǔn)? 如果它遮擋了很多物體如果大的多邊形與視點很近，該方法很有

14、效場景中的一些物體也可以融合起來形成大的occluders 例如，將很多樹的billboards融合 occluding 多邊形可以任意指定，但是，每一occluder 只對某一些視點區(qū)域有效問題：如果一個物體被某個occluder部分遮擋,又被另外一個部分遮擋, 那么很難決定是否該物體被全部遮擋用多個occluders來隱藏一個物體是一個很有趣的問題 Hierarchical Z-Buffer 方法在圖像（屏幕）空間建立遮擋子 需要特殊的圖形硬件與軟件實現(xiàn) 張寒松的Hierarchical Occlusion Maps（層次遮擋圖） 將遮擋子繪制到一個紋理圖中，然后將物體與紋理比較 Scha

15、ufler Occluder Fusion 建立一個被遮擋區(qū)域的空間數(shù)據(jù)結(jié)構(gòu)當(dāng)打開遮擋面剔除時，僅需繪制7,000個三角形，幀率為50fps。當(dāng)遮擋面剔除關(guān)閉時，三角形繪制數(shù)目增長到17,300, 幀率下降到20 fps （上左）地形的基礎(chǔ)三角網(wǎng)格； （上右）高度圖；（下左）應(yīng)用高度圖后的地形網(wǎng)格； （下右）渲染后的地形圖 基于四叉樹的繪制方法 利用圖形硬件加速 繪制模式 保留模式 立即模式繪制優(yōu)化 使用場景的層次剖分技術(shù)進(jìn)行視域剔除 消除對畫面貢獻(xiàn)極小的多邊形根據(jù)當(dāng)前節(jié)點的誤差度量判斷是否需要繼續(xù)剖分可能在兩個相連的節(jié)點之間產(chǎn)生漏洞 解決方法 保證兩個相鄰節(jié)點之間最多相差1個層次 保證兩個相

16、鄰的邊擁有相同的頂點數(shù)目 正確 錯誤 動態(tài)層次細(xì)節(jié)算法 缺點 層次之間切換會產(chǎn)生跳躍感幾何變形法 具有光滑過渡的視覺效果存儲量大,內(nèi)存消耗太多解決的方法 細(xì)節(jié)紋理 細(xì)節(jié)紋理的拼接具有很大的挑戰(zhàn)性!在OGRE中場景管理器的類型有四種： ST_GENERIC 普通場景 ST_EXTERIOR_CLOSE 室外封閉場景 ST_EXTERIOR_FAR 室外無限場景 ST_INTERIOR 室內(nèi)場景首先讀入地圖包。代碼如下BspApplication() / Load Quake3 locations from a file ConfigFile cf; cf.load(quake3settings.

17、cfg); mQuakePk3 = cf.getSetting(Pak0Location); mQuakeLevel = cf.getSetting(Map); void chooseSceneManager(void) mSceneMgr = mRoot- getSceneManager(ST_INTERIOR); void createScene(void) / Load world geometry mSceneMgr-setWorldGeometry(mQuakeLevel); / modify camera for close work mCamera-setNearClipDist

18、ance(4); mCamera-setFarClipDistance(4000); / Also change position, and set Quake-type orientation / Get random player start point ViewPoint vp = mSceneMgr-getSuggestedViewpoint(true); mCamera-setPosition(vp.position); mCamera-pitch(90); / Quake uses X/Y horizon, Z up mCamera-rotate(vp.orientation);

19、/ Dont yaw along variable axis, causes leaning mCamera-setFixedYawAxis(true, Vector3:UNIT_Z); OGRE在其引擎提供的Plugin_OctreeSceneManager.dll插件中提供了通過八叉樹算法實現(xiàn)的ST_EXTERIOR_CLOSE室外封閉場景管理器。 首先需要選擇室外場景管理器，代碼如下：virtual void chooseSceneManager(void) / Get the SceneManager, in this case a generic one mSceneMgr = mR

20、oot-getSceneManager( ST_EXTERIOR_CLOSE );選擇好室外場景管理器后，通過該場景管理器創(chuàng)建場景就可以了。void createScene(void) / Set ambient light mSceneMgr-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 positio

21、n / NB I could attach the light to a SceneNode if I wanted it to move automatically with / other objects, but I dont l-setPosition(20,80,50); mSceneMgr - setWorldGeometry( terrain.cfg ); mSceneMgr-setFog( FOG_EXP2, ColourValue:White, .008, 0, 250 ); mRoot - showDebugOverlay( true );碰撞檢測問題 是機(jī)器人、動畫仿真、

22、虛擬現(xiàn)實等領(lǐng)域不可回避的問題基本任務(wù) 確定兩個或多個物體彼此之間是否發(fā)生接觸或穿透。起源 早期在機(jī)器人路徑規(guī)劃、自動裝配規(guī)劃等領(lǐng)域中，為檢測機(jī)器人與場景中的物體或零件與零件之間是否發(fā)生碰撞，產(chǎn)生了一系列碰撞檢測算法。從兩個角度對碰撞檢測算法進(jìn)行分類 從時間域的角度來分 從空間域的角度來分 分為靜態(tài)、離散和連續(xù)的碰撞檢測算法靜態(tài)碰撞檢測算法 靜止?fàn)顟B(tài)下進(jìn)行碰撞檢測 Dobkin 1985Agarwal 1991Chazelle 1989 離散碰撞檢測算法 在每一時間的離散點上進(jìn)行碰撞檢測 是研究的重點和熱點 Lin 1998Jimnez 2001 離散碰撞檢測算法 存在問題 存在刺穿現(xiàn)象 遺漏應(yīng)

23、該發(fā)生的碰撞 連續(xù)碰撞檢測算法 連續(xù)的時間間隔內(nèi)進(jìn)行碰撞檢測 計算速度還太慢 Cameron 1990Canny 1986Redon 2001Redon 2002a基于物體空間的碰撞檢測算法基于圖象空間的碰撞檢測算法基于物體空間的碰撞檢測算法 采用一般表示模型的碰撞檢測算法 采用空間結(jié)構(gòu)的碰撞檢測算法 基于物體空間的碰撞檢測算法 采用一般表示模型的碰撞檢測算法 多邊形表示模型 多邊形集合，結(jié)構(gòu)化表示模型 非多邊形表示模型 CSG表示模型，隱函數(shù)曲面，參數(shù)曲面，體表示模型 多邊形表示模型 非多邊形表示模型 結(jié)構(gòu)化表示模型 多邊形集合 CSG 表示模型 隱函數(shù)曲面 參數(shù)曲面 幾何模型 體表示模型

24、基于物體空間的碰撞檢測算法 采用一般表示模型的碰撞檢測算法 面向多邊形表示模型的碰撞檢測算法 Hubbard 1995Gottschalk 1996 Klosowski 1998Zachmann 1998 面向凸體的碰撞檢測算法基于物體空間的碰撞檢測算法 面向凸體的碰撞檢測算法 基于特征的碰撞檢測算法 Lin-Canny的“最鄰近特征算法”Lin 1991, Lin1993 Lin 1995, Cohen 1995, Chung 1996, Mirtich 1998, Ehmann 2000, Ehmann 2001 基于單純形（Simplex）的碰撞檢測算法 Gilbert、Johnson和

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