三維場景的組織與繪制課件

三維場景的組織與繪制三維場景的組織與繪制1一.三維場景的組織與管理一.三維場景的組織與管理2場景圖是一種將場景中的各種數(shù)據(jù)以圖的形式組織在一起的場景數(shù)據(jù)管理方式。它是一個K-樹,場景圖中的每一個節(jié)點(diǎn)都是數(shù)據(jù)的存儲結(jié)構(gòu),父結(jié)點(diǎn)會影響子結(jié)點(diǎn)。每個節(jié)點(diǎn)信息包括：（1）場景的組織結(jié)構(gòu)信息，如父節(jié)點(diǎn)或子節(jié)點(diǎn)的句柄；（2）支持繪制流程的各種信息，如節(jié)點(diǎn)在當(dāng)前幀中是否繪制的標(biāo)識，節(jié)點(diǎn)的包圍體等；（3）描述表現(xiàn)自身所需的各類特征屬性信息，如位置坐標(biāo)、變換矩陣以及顏色、材質(zhì)等。1.基于場景圖的表達(dá)與管理1.基于場景圖的表達(dá)與管理3場景圖BVH是最常用的數(shù)據(jù)結(jié)構(gòu)簡單容易理解Simpletounderstand編程簡單不過它僅僅存儲幾何信息繪制不僅僅是幾何信息場景在BVH基礎(chǔ)上擴(kuò)展了

:光照（Lights）紋理（Textures）變換（Transforms）更多...場景圖BVH是最常用的數(shù)據(jù)結(jié)構(gòu)4第5章三維場景的組織與繪制5例:模擬一個星系

恒星

|

旋轉(zhuǎn)

/\

行星1

行星

|

|

旋轉(zhuǎn)

旋轉(zhuǎn)

/

\

/

\

衛(wèi)星A

衛(wèi)星B

衛(wèi)星C

衛(wèi)星D例:模擬一個星系6·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用第一個旋轉(zhuǎn)

渲染行星1

保存當(dāng)前矩陣

· 運(yùn)用第二個旋轉(zhuǎn)

· 渲染衛(wèi)星A

· 渲染衛(wèi)星B

恢復(fù)我們保存的矩陣

渲染行星2

保存當(dāng)前矩陣

·運(yùn)用行星2的旋轉(zhuǎn)

· 渲染衛(wèi)星C

· 渲染衛(wèi)星D

恢復(fù)我們保存的矩陣

·恢復(fù)我們保存的矩陣·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用第一個旋轉(zhuǎn)

7恒星

|

旋轉(zhuǎn)

/\

行星1

行星

|

|

旋轉(zhuǎn)

旋轉(zhuǎn),搖擺

/

\

/

\

衛(wèi)星A

衛(wèi)星B

衛(wèi)星C

衛(wèi)星D行星A搖晃恒星

|

行8·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用旋轉(zhuǎn)

·保存當(dāng)前矩陣

運(yùn)用搖晃

渲染行星A

保存當(dāng)前矩陣

·運(yùn)用旋轉(zhuǎn)

·渲染衛(wèi)星A

· 渲染衛(wèi)星B

·恢復(fù)矩陣

·恢復(fù)矩陣

恢復(fù)矩陣

運(yùn)用旋轉(zhuǎn)

渲染行星2

保存當(dāng)前矩陣

· 運(yùn)用行星2的旋轉(zhuǎn)

· 渲染衛(wèi)星C

· 渲染衛(wèi)星D

恢復(fù)我們保存的矩陣

·恢復(fù)我們保存的矩陣·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用旋轉(zhuǎn)

·9場景繪制過程根據(jù)游戲的需要,更新場景中的部分結(jié)構(gòu),從下到上；場景圖的剔除繪制過程：要修改一個行星的位置,只需修改星結(jié)點(diǎn)的屬性,不更改任何子節(jié)點(diǎn)的屬性.場景繪制過程10場景圖一般包含下列節(jié)點(diǎn):幾何節(jié)點(diǎn)變換節(jié)點(diǎn)平移，旋轉(zhuǎn)，縮放開關(guān)節(jié)點(diǎn) 通過當(dāng)前狀態(tài)對子節(jié)點(diǎn)進(jìn)行選擇的節(jié)點(diǎn)場景圖一般包含下列節(jié)點(diǎn):11把場景中的物體按照繪制狀態(tài)分類，對相同狀態(tài)的物體設(shè)置一次狀態(tài)；狀態(tài)切換是一個比較耗時的運(yùn)算；繪制狀態(tài)包括：紋理映射的參數(shù)設(shè)置材質(zhì)參數(shù)，包括泛光、漫射光等各類其他渲染模式：多邊形插值、融合等半條命2.基于繪制狀態(tài)的場景管理把場景中的物體按照繪制狀態(tài)分類，對相同狀態(tài)的物體設(shè)置一次狀態(tài)12建立狀態(tài)樹按狀態(tài)集進(jìn)行排序遵照“盡量使?fàn)顟B(tài)轉(zhuǎn)換最少”按深度優(yōu)先遍歷狀態(tài)樹，依次繪制建立狀態(tài)樹13由于可見性檢測、求交、碰撞等都可歸結(jié)為空間關(guān)系的計算。對每個物體建立包圍體；對場景建立包圍體層次樹；快速判斷一個點(diǎn)是否在物體的凸包圍體中。3.基于景物包圍體的場景組織由于可見性檢測、求交、碰撞等都可歸結(jié)為空間關(guān)系的計算。3.14常用的場景物體包圍體包圍球AABB包圍盒OBB包圍盒平行六邊包圍體K對平行六面包圍體常用的場景物體包圍體15二.優(yōu)化場景繪制的幾何剖分技術(shù)二.優(yōu)化場景繪制的幾何剖分技術(shù)16常用的三種:1.BSP樹（二叉空間平分樹）應(yīng)用于深度排序，碰撞檢測，繪制，節(jié)點(diǎn)裁減和可見性判斷，加速三維場景的漫游；空間中的任意平面把空間分成兩部分：一份為二地空間剖分方法；一直遞歸下去，結(jié)束的條件：空間中沒有物體了；剖分的深度達(dá)到了指定的數(shù)值就停下常用的三種:1.BSP樹（二叉空間平分樹）17BSP樹的建立先對物體建立包圍體結(jié)構(gòu)，然后以包圍體為單位建立場景的BSP樹；剖分方式：均勻剖分：適于場景中物體分布均勻平行坐標(biāo)軸剖分：室內(nèi)游戲選取場景中面積最大和遮擋物體最多的面：判斷物體與剖分面的關(guān)系稍負(fù)責(zé)BSP樹的建立18BSP（BinarySpacePartitioning）樹兩種類型:沿軸（Axis-aligned）沿多邊形(Polygon-aligned)

總體思想:用平面劃分多邊形把幾何排序后存放到它所屬的空間遞歸，直到都完成如果按某種方式遍歷，可以得到沿一個軸排序的幾何對于沿多邊形的方法很準(zhǔn)確沿軸的方法則結(jié)果是近似的BSP（BinarySpacePartitioning19沿軸BSP樹(1)僅能沿x,y或產(chǎn)生一個分裂面最小的box沿面分裂沿面分裂沿面分裂沿軸BSP樹(1)僅能沿x,y或產(chǎn)生一個分裂面最小的沿面20沿軸BSP樹(2)每個內(nèi)部節(jié)點(diǎn)擁有一個分割面；葉子具有幾何信息與BVH比不同提供閉合空間，并且有序BV層次能用任何方式構(gòu)造（無序）；BVHs能夠使用任何所需要的BV類型ABCDEPlane0Plane1aPlane1bPlane201aAB1bC2DE沿軸BSP樹(2)每個內(nèi)部節(jié)點(diǎn)擁有一個分割面；ABCDE21沿軸BSP樹粗略排序沿視點(diǎn)測試平面從根遞歸測試?yán)^續(xù)從當(dāng)前面從前向后排序eye01aAB1bC2DE11a1b202345沿多邊形BSP樹用同樣的方法---但給的是準(zhǔn)確排序沿軸BSP樹粗略排序沿視點(diǎn)測試平面eye01aAB1bC222BSP樹的遍歷：深度優(yōu)先廣度優(yōu)先BSP樹局限性：不太適合動態(tài)場景構(gòu)造時間長BSP樹的遍歷：23常用于地形繪制；以包圍四邊形逼近場景，然后迭代地一分為四。均勻剖分：適于場景中物體分布均勻平行坐標(biāo)軸剖分：室內(nèi)游戲選取場景中面積最大和遮擋物體最多的面：判斷物體與剖分面的關(guān)系稍負(fù)責(zé)最大的優(yōu)點(diǎn)：層次剔除2.四叉樹常用于地形繪制；2.四叉樹24長方體遞歸地剖分為八個長方體；構(gòu)建時間比BSP樹短，容易使用。常用于視域裁剪、碰撞檢測。3.八叉樹3.八叉樹25比較

技術(shù)名稱適用場景構(gòu)建復(fù)雜度實(shí)用性二叉樹尺寸不大的室內(nèi)場景復(fù)雜大部分游戲引擎四叉樹室外地形一般僅用于地形繪制八叉樹大規(guī)模室內(nèi)空間場景一般復(fù)雜游戲引擎均勻八叉樹分布均勻的三維場景簡單少量三維游戲引擎比較

技術(shù)名稱適用場景構(gòu)建復(fù)雜度實(shí)用性二叉樹尺寸不大的室內(nèi)場26三.游戲場景的幾何優(yōu)化三.游戲場景的幾何優(yōu)化27空間數(shù)據(jù)結(jié)構(gòu)用來加快渲染和各種查詢?yōu)槭裁葱枰斓乃俣?圖形硬體6個月速度翻倍!我們總不滿足屏幕分辨率:3000x1500真實(shí)感:全局光照幾何復(fù)雜度:無上界!場景的幾何優(yōu)化空間數(shù)據(jù)結(jié)構(gòu)用來加快渲染和各種查詢場景的幾何優(yōu)化28LOD在不影響畫面視覺效果情況下，逐步簡化景物表面的細(xì)節(jié)來減少場景的幾何復(fù)雜性；四類：簡單取舍型設(shè)置閾值，小于則不繪平滑過渡型大于上限，正常繪制；小于，不繪；中間，線性過渡靜態(tài)LOD型預(yù)計算同一物體的多個不同精度的版本，根據(jù)不同距離切換使用不同的物體跳躍：增加霧化效果1.層次細(xì)節(jié)技術(shù)(LOD)LOD1.層次細(xì)節(jié)技術(shù)(LOD)29動態(tài)LOD型在場景漫游過程中動態(tài)地根據(jù)相機(jī)的位置和物體的重要性動態(tài)簡化網(wǎng)格；簡化算法：基于頂點(diǎn)的刪除基于邊的刪除：定義代價函數(shù)，刪除代價最小的邊基于面的刪除漸進(jìn)網(wǎng)格和連續(xù)多分辨率繪制動態(tài)LOD型30在不同的距離處（從視點(diǎn))使用不同的層次細(xì)節(jié)離視點(diǎn)更近出，使用更多的三角形在不同的距離處（從視點(diǎn))使用不同的層次細(xì)節(jié)31目的:有些看不見的可以不繪制從而加快繪制速度2.快速可見性判斷與消隱目的:2.快速可見性判斷與消隱32類型物體層的算法：場景聚類技術(shù)決定相對于視點(diǎn)面的前后排列二叉樹和八叉樹，入口技術(shù)，潛在可見集，單物體分塊頂點(diǎn)層算法：頂點(diǎn)剔除算法背面剔除視域剔除裁剪面剔除象素層的算法：圖像空間排序深度緩沖消隱層次緩沖消隱時空連貫性類型33不同的剪切技術(shù)viewfrustumdetailbackfaceportalocclusion不同的剪切技術(shù)viewfrustumdetailbackf34基于入口技術(shù)的可見性判斷適用于室內(nèi)游戲根據(jù)單元與單元之間的鄰接圖，通過深度遍歷建立單元與單元的入口序列，從而得到單元對單元的可見性集合。入口技術(shù)的優(yōu)點(diǎn)：方便定義場景：可方便地動態(tài)創(chuàng)建和修改場景快速繪制基于入口技術(shù)的可見性判斷35基于入口技術(shù)的裁剪ImagescourtesyofDavidP.LuebkeandChrisGeorges平均:裁減去20-50%多邊形加速:fromslightlybetterto10times基于入口技術(shù)的裁剪ImagescourtesyofDa36基于入口技術(shù)的裁剪舉例上面的建筑中球是要畫的對象基于入口技術(shù)的裁剪舉例上面的建筑中37基于入口技術(shù)的裁剪算法(1)分割帶有門的單元(建立圖)對于每一幀:定位視點(diǎn)的位置，并把整個場景2DAABB初始化*繪制當(dāng)前單元用帶有w.r.t.AABB的視點(diǎn)六面體裁減方法對最近的單元遍歷(通過門戶)遍歷門戶的AABB&AABB交叉Goto*基于入口技術(shù)的裁剪算法(1)分割帶有門的單元(建立圖)38遮擋面剔除技術(shù)基于陰影體的遮擋剔除選擇遮擋體，生成一個陰影體：尺寸最大的多邊形或多個三角形組成的一個大的凸包；利用包圍盒測試與遮擋體的關(guān)系基于視點(diǎn)的遮擋剔除對多個遮擋體，按重要性排序遮擋面剔除技術(shù)39遮擋裁剪主要思想:完全在另一個后的物體可以被裁剪效率問題很難解決這個領(lǐng)域有很多研究遮擋裁剪主要思想:完全在另一個后的物體可以被裁剪40例如最終圖像表明“入口裁剪”屬于遮擋裁剪類型例如最終圖像表明“入口裁剪”屬于遮擋裁剪類型41背向面裁剪簡單的方法是剖其背離視點(diǎn)的面用于:閉合面(例如:球sphere)不管是否我們只知道這個面是否可見(例如:室內(nèi)的墻)兩種方法(屏幕空間,視空間)背向面裁剪簡單的方法是剖其背離視點(diǎn)的面42背向面裁剪(續(xù))通常用API完成OpenGL:glCullFace(GL_BACK);D3D：SetRenderState(D3DRS_CULLMODE,TRUE);

怎樣確定是背向面?首先,必須有一個連續(xù)朝向的多邊形musthaveconsistentlyorientedpolygons,e.g.,counterclockwise012frontfacing012backfacing背向面裁剪(續(xù))通常用API完成012frontfacin43Twowaysindifferentspaces:screenspace102front012backeyefrontbackeyespaceHowtocullbackfacesTwowaysindifferentspaces:s44View-FrustumCullingBoundevery“natural”groupofprimitivesbyasimplevolume(e.g.,sphere,box)Ifaboundingvolume(BV)isoutsidetheviewfrustum,thentheentirecontentsofthatBVisalsooutside(notvisible)View-FrustumCullingBoundever45Canweaccelerateviewfrustumcullingfurther?Dowhatwealwaysdoingraphics…Useahierarchicalapproach,e.g.,aspatialdatastructure(BVH,BSP,scenegraph)Whichstagesbenefits?GeometryandRasterizerBusbetweenCPUandGeometryCanweaccelerateviewfrustum46ExampleofHierarchicalViewFrustumCullingrootcameraExampleofHierarchicalViewF47Occlusioncullingalgorithm

UsesomekindofocclusionrepresentationORforeachobjectgdo:if(notOccluded(OR,g))render(g);update(OR,g);end;end;Occlusioncullingalgorithm Us48Target:urbanscenerydenseocclusionviewerisabout2metersabovegroundAlgorithm:Processsceneinfront-to-backusingaquadtreeMaintainapiecewiseconstanthorizonCullobjectsagainsthorizonAddvisibleobjects’occludingpowertothehorizonOcclusionHorizon:AsimplealgorithmTarget:urbansceneryOcclusion49OcclusiontestingwithocclusionhorizonsToprocesstetrahedron(whichisbehindgreyobjects):findaxis-alignedboxofprojectioncompareagainstocclusionhorizonculledOcclusiontestingwithocclusi50UpdatehorizonWhenanobjectisconsideredvisible:Addits“occludingpower”totheocclusionrepresentationUpdatehorizonWhenanobjecti51OcclusionCullingwithDirectX9

實(shí)現(xiàn)IDirect3DQuery9函數(shù):Rendereveryobject'sboundingmeshForeveryobject:BeginqueryRe-rendertheboundingmeshEndqueryRetrieveocclusionquerydata.Ifthepixelsvisiblearegreaterthanzero,theobjectshouldberendered.Otherwise,theobjectshouldbeoccludedfromrendering.OcclusionCullingwithDirectX52Step1:

AboundingmeshisusedStep1:53Step2:ObjectDeclaration

Fortheocclusionprocess,interfacesofLPDIRECT3DQUERY9,LPD3DXRENDERTOSURFACE,LPDIRECT3DSURFACE9,andLPDIRECT3DTEXTURE9needtobedeclared.Step2:54SettinguptheOcclusionObjects

Thequeryitselfmustbecreated,alongwiththetextureandtherender-to-surface.D3DUSAGE_RENDERTARGETisusedduringthecreationofthetextureThesurfaceitselfisobtainedthroughtheGetSurfaceLevel()functionofLPDIRECT3DTEXTURE9.SettinguptheOcclusionObjec55CullingtheObjects

First,theLPD3DXRENDERTOSURFACEisactivatedandcleared.Second,everyobject'sboundingmeshisrendered.Themeshesarere-renderedandthentheirocclusionqueriesareretrieved.Finally,thesurface'ssceneisendedanddeactivated.CullingtheObjects56TheRenderLoopTheRenderLoop57ScreenshotofResultScreenshotofResult58一個D3D漫游系統(tǒng)的繪制建模:模型導(dǎo)入程序生成繪制:紋理映射特殊技巧漫游控制:第一人稱第三人稱視角一個D3D漫游系統(tǒng)的繪制建模:59例子例子60地形的繪制與漫游

基于高度圖生成地形高度基于四叉樹來遍歷繪制采用LOD加速紋理壓縮減少存儲量地形的繪制與漫游

基于高度圖生成地形高度61三維場景的組織與繪制三維場景的組織與繪制62一.三維場景的組織與管理一.三維場景的組織與管理63場景圖是一種將場景中的各種數(shù)據(jù)以圖的形式組織在一起的場景數(shù)據(jù)管理方式。它是一個K-樹,場景圖中的每一個節(jié)點(diǎn)都是數(shù)據(jù)的存儲結(jié)構(gòu),父結(jié)點(diǎn)會影響子結(jié)點(diǎn)。每個節(jié)點(diǎn)信息包括：（1）場景的組織結(jié)構(gòu)信息，如父節(jié)點(diǎn)或子節(jié)點(diǎn)的句柄；（2）支持繪制流程的各種信息，如節(jié)點(diǎn)在當(dāng)前幀中是否繪制的標(biāo)識，節(jié)點(diǎn)的包圍體等；（3）描述表現(xiàn)自身所需的各類特征屬性信息，如位置坐標(biāo)、變換矩陣以及顏色、材質(zhì)等。1.基于場景圖的表達(dá)與管理1.基于場景圖的表達(dá)與管理64場景圖BVH是最常用的數(shù)據(jù)結(jié)構(gòu)簡單容易理解Simpletounderstand編程簡單不過它僅僅存儲幾何信息繪制不僅僅是幾何信息場景在BVH基礎(chǔ)上擴(kuò)展了

:光照（Lights）紋理（Textures）變換（Transforms）更多...場景圖BVH是最常用的數(shù)據(jù)結(jié)構(gòu)65第5章三維場景的組織與繪制66例:模擬一個星系

恒星

|

旋轉(zhuǎn)

/\

行星1

行星

|

|

旋轉(zhuǎn)

旋轉(zhuǎn)

/

\

/

\

衛(wèi)星A

衛(wèi)星B

衛(wèi)星C

衛(wèi)星D例:模擬一個星系67·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用第一個旋轉(zhuǎn)

渲染行星1

保存當(dāng)前矩陣

· 運(yùn)用第二個旋轉(zhuǎn)

· 渲染衛(wèi)星A

· 渲染衛(wèi)星B

恢復(fù)我們保存的矩陣

渲染行星2

保存當(dāng)前矩陣

·運(yùn)用行星2的旋轉(zhuǎn)

· 渲染衛(wèi)星C

· 渲染衛(wèi)星D

恢復(fù)我們保存的矩陣

·恢復(fù)我們保存的矩陣·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用第一個旋轉(zhuǎn)

68恒星

|

旋轉(zhuǎn)

/\

行星1

行星

|

|

旋轉(zhuǎn)

旋轉(zhuǎn),搖擺

/

\

/

\

衛(wèi)星A

衛(wèi)星B

衛(wèi)星C

衛(wèi)星D行星A搖晃恒星

|

行69·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用旋轉(zhuǎn)

·保存當(dāng)前矩陣

運(yùn)用搖晃

渲染行星A

保存當(dāng)前矩陣

·運(yùn)用旋轉(zhuǎn)

·渲染衛(wèi)星A

· 渲染衛(wèi)星B

·恢復(fù)矩陣

·恢復(fù)矩陣

恢復(fù)矩陣

運(yùn)用旋轉(zhuǎn)

渲染行星2

保存當(dāng)前矩陣

· 運(yùn)用行星2的旋轉(zhuǎn)

· 渲染衛(wèi)星C

· 渲染衛(wèi)星D

恢復(fù)我們保存的矩陣

·恢復(fù)我們保存的矩陣·渲染恒星

·保存當(dāng)前矩陣

應(yīng)用旋轉(zhuǎn)

·70場景繪制過程根據(jù)游戲的需要,更新場景中的部分結(jié)構(gòu),從下到上；場景圖的剔除繪制過程：要修改一個行星的位置,只需修改星結(jié)點(diǎn)的屬性,不更改任何子節(jié)點(diǎn)的屬性.場景繪制過程71場景圖一般包含下列節(jié)點(diǎn):幾何節(jié)點(diǎn)變換節(jié)點(diǎn)平移，旋轉(zhuǎn)，縮放開關(guān)節(jié)點(diǎn) 通過當(dāng)前狀態(tài)對子節(jié)點(diǎn)進(jìn)行選擇的節(jié)點(diǎn)場景圖一般包含下列節(jié)點(diǎn):72把場景中的物體按照繪制狀態(tài)分類，對相同狀態(tài)的物體設(shè)置一次狀態(tài)；狀態(tài)切換是一個比較耗時的運(yùn)算；繪制狀態(tài)包括：紋理映射的參數(shù)設(shè)置材質(zhì)參數(shù)，包括泛光、漫射光等各類其他渲染模式：多邊形插值、融合等半條命2.基于繪制狀態(tài)的場景管理把場景中的物體按照繪制狀態(tài)分類，對相同狀態(tài)的物體設(shè)置一次狀態(tài)73建立狀態(tài)樹按狀態(tài)集進(jìn)行排序遵照“盡量使?fàn)顟B(tài)轉(zhuǎn)換最少”按深度優(yōu)先遍歷狀態(tài)樹，依次繪制建立狀態(tài)樹74由于可見性檢測、求交、碰撞等都可歸結(jié)為空間關(guān)系的計算。對每個物體建立包圍體；對場景建立包圍體層次樹；快速判斷一個點(diǎn)是否在物體的凸包圍體中。3.基于景物包圍體的場景組織由于可見性檢測、求交、碰撞等都可歸結(jié)為空間關(guān)系的計算。3.75常用的場景物體包圍體包圍球AABB包圍盒OBB包圍盒平行六邊包圍體K對平行六面包圍體常用的場景物體包圍體76二.優(yōu)化場景繪制的幾何剖分技術(shù)二.優(yōu)化場景繪制的幾何剖分技術(shù)77常用的三種:1.BSP樹（二叉空間平分樹）應(yīng)用于深度排序，碰撞檢測，繪制，節(jié)點(diǎn)裁減和可見性判斷，加速三維場景的漫游；空間中的任意平面把空間分成兩部分：一份為二地空間剖分方法；一直遞歸下去，結(jié)束的條件：空間中沒有物體了；剖分的深度達(dá)到了指定的數(shù)值就停下常用的三種:1.BSP樹（二叉空間平分樹）78BSP樹的建立先對物體建立包圍體結(jié)構(gòu)，然后以包圍體為單位建立場景的BSP樹；剖分方式：均勻剖分：適于場景中物體分布均勻平行坐標(biāo)軸剖分：室內(nèi)游戲選取場景中面積最大和遮擋物體最多的面：判斷物體與剖分面的關(guān)系稍負(fù)責(zé)BSP樹的建立79BSP（BinarySpacePartitioning）樹兩種類型:沿軸（Axis-aligned）沿多邊形(Polygon-aligned)

總體思想:用平面劃分多邊形把幾何排序后存放到它所屬的空間遞歸，直到都完成如果按某種方式遍歷，可以得到沿一個軸排序的幾何對于沿多邊形的方法很準(zhǔn)確沿軸的方法則結(jié)果是近似的BSP（BinarySpacePartitioning80沿軸BSP樹(1)僅能沿x,y或產(chǎn)生一個分裂面最小的box沿面分裂沿面分裂沿面分裂沿軸BSP樹(1)僅能沿x,y或產(chǎn)生一個分裂面最小的沿面81沿軸BSP樹(2)每個內(nèi)部節(jié)點(diǎn)擁有一個分割面；葉子具有幾何信息與BVH比不同提供閉合空間，并且有序BV層次能用任何方式構(gòu)造（無序）；BVHs能夠使用任何所需要的BV類型ABCDEPlane0Plane1aPlane1bPlane201aAB1bC2DE沿軸BSP樹(2)每個內(nèi)部節(jié)點(diǎn)擁有一個分割面；ABCDE82沿軸BSP樹粗略排序沿視點(diǎn)測試平面從根遞歸測試?yán)^續(xù)從當(dāng)前面從前向后排序eye01aAB1bC2DE11a1b202345沿多邊形BSP樹用同樣的方法---但給的是準(zhǔn)確排序沿軸BSP樹粗略排序沿視點(diǎn)測試平面eye01aAB1bC283BSP樹的遍歷：深度優(yōu)先廣度優(yōu)先BSP樹局限性：不太適合動態(tài)場景構(gòu)造時間長BSP樹的遍歷：84常用于地形繪制；以包圍四邊形逼近場景，然后迭代地一分為四。均勻剖分：適于場景中物體分布均勻平行坐標(biāo)軸剖分：室內(nèi)游戲選取場景中面積最大和遮擋物體最多的面：判斷物體與剖分面的關(guān)系稍負(fù)責(zé)最大的優(yōu)點(diǎn)：層次剔除2.四叉樹常用于地形繪制；2.四叉樹85長方體遞歸地剖分為八個長方體；構(gòu)建時間比BSP樹短，容易使用。常用于視域裁剪、碰撞檢測。3.八叉樹3.八叉樹86比較

技術(shù)名稱適用場景構(gòu)建復(fù)雜度實(shí)用性二叉樹尺寸不大的室內(nèi)場景復(fù)雜大部分游戲引擎四叉樹室外地形一般僅用于地形繪制八叉樹大規(guī)模室內(nèi)空間場景一般復(fù)雜游戲引擎均勻八叉樹分布均勻的三維場景簡單少量三維游戲引擎比較

技術(shù)名稱適用場景構(gòu)建復(fù)雜度實(shí)用性二叉樹尺寸不大的室內(nèi)場87三.游戲場景的幾何優(yōu)化三.游戲場景的幾何優(yōu)化88空間數(shù)據(jù)結(jié)構(gòu)用來加快渲染和各種查詢?yōu)槭裁葱枰斓乃俣?圖形硬體6個月速度翻倍!我們總不滿足屏幕分辨率:3000x1500真實(shí)感:全局光照幾何復(fù)雜度:無上界!場景的幾何優(yōu)化空間數(shù)據(jù)結(jié)構(gòu)用來加快渲染和各種查詢場景的幾何優(yōu)化89LOD在不影響畫面視覺效果情況下，逐步簡化景物表面的細(xì)節(jié)來減少場景的幾何復(fù)雜性；四類：簡單取舍型設(shè)置閾值，小于則不繪平滑過渡型大于上限，正常繪制；小于，不繪；中間，線性過渡靜態(tài)LOD型預(yù)計算同一物體的多個不同精度的版本，根據(jù)不同距離切換使用不同的物體跳躍：增加霧化效果1.層次細(xì)節(jié)技術(shù)(LOD)LOD1.層次細(xì)節(jié)技術(shù)(LOD)90動態(tài)LOD型在場景漫游過程中動態(tài)地根據(jù)相機(jī)的位置和物體的重要性動態(tài)簡化網(wǎng)格；簡化算法：基于頂點(diǎn)的刪除基于邊的刪除：定義代價函數(shù)，刪除代價最小的邊基于面的刪除漸進(jìn)網(wǎng)格和連續(xù)多分辨率繪制動態(tài)LOD型91在不同的距離處（從視點(diǎn))使用不同的層次細(xì)節(jié)離視點(diǎn)更近出，使用更多的三角形在不同的距離處（從視點(diǎn))使用不同的層次細(xì)節(jié)92目的:有些看不見的可以不繪制從而加快繪制速度2.快速可見性判斷與消隱目的:2.快速可見性判斷與消隱93類型物體層的算法：場景聚類技術(shù)決定相對于視點(diǎn)面的前后排列二叉樹和八叉樹，入口技術(shù)，潛在可見集，單物體分塊頂點(diǎn)層算法：頂點(diǎn)剔除算法背面剔除視域剔除裁剪面剔除象素層的算法：圖像空間排序深度緩沖消隱層次緩沖消隱時空連貫性類型94不同的剪切技術(shù)viewfrustumdetailbackfaceportalocclusion不同的剪切技術(shù)viewfrustumdetailbackf95基于入口技術(shù)的可見性判斷適用于室內(nèi)游戲根據(jù)單元與單元之間的鄰接圖，通過深度遍歷建立單元與單元的入口序列，從而得到單元對單元的可見性集合。入口技術(shù)的優(yōu)點(diǎn)：方便定義場景：可方便地動態(tài)創(chuàng)建和修改場景快速繪制基于入口技術(shù)的可見性判斷96基于入口技術(shù)的裁剪ImagescourtesyofDavidP.LuebkeandChrisGeorges平均:裁減去20-50%多邊形加速:fromslightlybetterto10times基于入口技術(shù)的裁剪ImagescourtesyofDa97基于入口技術(shù)的裁剪舉例上面的建筑中球是要畫的對象基于入口技術(shù)的裁剪舉例上面的建筑中98基于入口技術(shù)的裁剪算法(1)分割帶有門的單元(建立圖)對于每一幀:定位視點(diǎn)的位置，并把整個場景2DAABB初始化*繪制當(dāng)前單元用帶有w.r.t.AABB的視點(diǎn)六面體裁減方法對最近的單元遍歷(通過門戶)遍歷門戶的AABB&AABB交叉Goto*基于入口技術(shù)的裁剪算法(1)分割帶有門的單元(建立圖)99遮擋面剔除技術(shù)基于陰影體的遮擋剔除選擇遮擋體，生成一個陰影體：尺寸最大的多邊形或多個三角形組成的一個大的凸包；利用包圍盒測試與遮擋體的關(guān)系基于視點(diǎn)的遮擋剔除對多個遮擋體，按重要性排序遮擋面剔除技術(shù)100遮擋裁剪主要思想:完全在另一個后的物體可以被裁剪效率問題很難解決這個領(lǐng)域有很多研究遮擋裁剪主要思想:完全在另一個后的物體可以被裁剪101例如最終圖像表明“入口裁剪”屬于遮擋裁剪類型例如最終圖像表明“入口裁剪”屬于遮擋裁剪類型102背向面裁剪簡單的方法是剖其背離視點(diǎn)的面用于:閉合面(例如:球sphere)不管是否我們只知道這個面是否可見(例如:室內(nèi)的墻)兩種方法(屏幕空間,視空間)背向面裁剪簡單的方法是剖其背離視點(diǎn)的面103背向面裁剪(續(xù))通常用API完成OpenGL:glCullFace(GL_BACK);D3D：SetRenderState(D3DRS_CULLMODE,TRUE);

怎樣確定是背向面?首先,必須有一個連續(xù)朝向的多邊形musthaveconsistentlyorientedpolygons,e.g.,counterclockwise012frontfacing012backfacing背向面裁剪(續(xù))通常用API完成012frontfacin104Twowaysindifferentspaces:screenspace102front012backeyefrontbackeyespaceHowtocullbackfacesTwowaysindifferentspaces:s105View-FrustumCullingBoundevery“natural”groupofprimitivesbyasimplevolume(e.g.,sphere,box)Ifaboundingvolume(BV)isoutsidetheviewfrustum,thentheentirecontentsofthatBVisalsooutside(notvisible)View-FrustumCullingBoundever106Canweaccelerateviewfrustumcullingfurther?Dowhatwealwaysdoingraphics…Useahierarchicalapproach,e.g.,aspatialdatastructure(BVH,BSP,scenegraph)Whichstagesbenefits?GeometryandRasterizerBusbetweenCPUandGeometryCanweaccelerateviewfrustum107ExampleofHierarchicalViewFrustumCullingrootcameraExampleofHierarchicalViewF108Occlusioncullingalgorithm

UsesomekindofocclusionrepresentationORforeachobjectgdo:if(notOccluded(OR,g))render(g);update(OR,g);end;end;Occlusioncullingalgorithm Us109Target:urbanscenerydenseocclusionviewerisabout2metersabovegroundAlgorithm:Processsceneinfront-to-backusingaquadtreeMaintainapiecewiseconstanthorizonCullobjectsagainsthorizonAddvisibleobjects’occludingpowertothehorizonOcclusionHorizon:AsimplealgorithmTarget:urbansceneryOcclusion110OcclusiontestingwithocclusionhorizonsToprocesstetrahedron(whichisbehindgreyobjects):findaxis-alignedboxofproje