虛擬現(xiàn)實技術(shù)導論 課件 第4章 虛擬現(xiàn)實渲染及相關(guān)技術(shù)

虛擬現(xiàn)實技術(shù)導論第1章概論本講大綱4.1虛擬現(xiàn)實渲染的有關(guān)概念面面4.2虛擬現(xiàn)實視覺渲染的主要方法4.3場景組織例——大規(guī)模虛擬場景實時碰撞檢測4.4場景繪制優(yōu)化例——基于LOD的點云繪制4.5習題4.1虛擬現(xiàn)實渲染的有關(guān)概念虛擬現(xiàn)實系統(tǒng)邏輯結(jié)構(gòu)渲染幾何建模物理建模行為建模運動建模與虛擬環(huán)境的關(guān)系和作用虛擬現(xiàn)實：3D+人機交互渲染目的：將虛擬環(huán)境輸出，作用于參與者繪制/渲染技術(shù)分類從感知通道角度視覺渲染：將幾何模型按照視覺原理進行表現(xiàn)觸/力覺渲染：提供力覺/觸力覺感知信息聽覺渲染：提供逼真的聽覺感受味/嗅渲染：提供味覺/嗅覺感知信息視覺渲染

在J.J.Gibson提出的概念模型中，人的感知系統(tǒng)也是劃分為視覺、聽覺、觸覺、味/嗅覺和方向感五部分，其中對客觀世界的感知信息75%-80%來自視覺

為了在有限的計算、存儲資源條件下提高虛擬環(huán)境中用戶視覺感知的逼真性，需要對視覺感知系統(tǒng)的主要要素抽象視覺渲染分類基于幾何的繪制技術(shù)：輸入數(shù)據(jù)為虛擬對象的幾何信息基于圖像的繪制技術(shù)：常見方法有光場計算、流明圖、同心拼圖、全景拼圖等幾何與圖像結(jié)合的繪制技術(shù)：主要研究圖像圖形融合時的幾何一致性和光照一致性等方面的工作虛擬現(xiàn)實視覺渲染技術(shù)大都是圍繞提高真實感和實時性展開的聽覺渲染聽覺是人類僅次于視覺的第2大感知來源，人類對客觀世界的感知信息有15%左右來自聽覺。聽覺渲染就是要對這些聲源的音頻特征和空間信息進行渲染，包括聲音的模擬、合成及定位等。空間信息可以體現(xiàn)虛擬環(huán)境的立體感和真實感，所以，聲音定位是實現(xiàn)逼真三維音效的關(guān)鍵技術(shù)。聽覺渲染相關(guān)概念頭部相關(guān)傳輸函數(shù)（Head-relatedTransferFunction，HRTF）通過理論計算獲取：邊界元法、有限元法和非有限元法IFEM等通過實驗測量獲?。韩@取真實空間聽覺測量數(shù)據(jù)，然后經(jīng)過特征提取，基于已知的測量數(shù)據(jù)預測非測量點上的數(shù)據(jù)聲音紋理在聲音節(jié)點中增加效果域（增強了對三維聲音的空間表現(xiàn)力，使聽覺渲染更為逼真和富有沉浸感）在聲音效果節(jié)點中設(shè)置預設(shè)域（簡化了對環(huán)境聲音的描述）用來描述人的聽覺系統(tǒng)對不同方位的聲音產(chǎn)生的不同頻譜特性使用節(jié)點和域的方法對環(huán)境聲音進行建模力/觸覺渲染技術(shù)力/觸覺渲染需要借助力觸覺設(shè)備進行碰撞檢測和碰撞響應用戶操縱力觸覺設(shè)備碰撞檢測碰撞檢測算法發(fā)生碰撞碰撞響應提供虛擬對象的相關(guān)力觸覺信息空間剖分、層次細節(jié)LOD由于人的觸覺靈敏，力觸覺渲染至少需要1kHz的刷新頻率才能給人以真實感。因此，高刷新率和快速計算成為力觸覺渲染技術(shù)研究的一個重點。力/觸覺渲染技術(shù)力/觸覺渲染需要對物體表面的紋理進行模擬當三維物體的表面紋理是由二維圖像直接映射而成時，采用基于圖像的觸覺紋理映射，將紋理的二維紋元中的顏色和灰度信息映射為高度信息也可以通過參數(shù)化的方法合成觸覺紋理，例如使用噪聲紋理，經(jīng)過適當?shù)臄_動函數(shù)生成自然紋理。對象的幾何和物理建模提供的屬性反作用力觸覺紋理計算映射適當擾動使用戶能夠感知并區(qū)分不同的物體表面基于圖像的映射基于過程的映射嗅/味覺渲染嗅覺是由化學刺激產(chǎn)生的，研究表明與氣味有關(guān)的感受器至少有數(shù)百個，而且每個感受器可檢測多種分子，所以類比視覺中的顏色空間，使用幾種“基礎(chǔ)氣味”來合成任意氣味的思路的實現(xiàn)是困難的

鑒于特定應用環(huán)境中所需要的氣味并不是很多，目前虛擬現(xiàn)實系統(tǒng)中主要研究氣味的傳播。嗅/味覺表現(xiàn)技術(shù)示例日本的千元國宏等開發(fā)的嗅覺模擬器，用戶把能放出香味的換裝嗅覺提示裝置套在手上，換裝裝置里裝著8個小瓶，分別盛著8種水果的香料。童虎頭戴虛擬環(huán)境圖像顯示器，看到對應的水果，用指尖把顯示器拉到鼻尖上，位置感應器檢測到鼻子的位置與顯示器接近，嗅覺提示裝置就會根據(jù)顯示器上的水果形象釋放特定的香味。由于味覺與化學物質(zhì)、觸覺和聲音等多方面的因素有關(guān)，對其進行表現(xiàn)的難度很大。Iwata等因此稱之為虛擬現(xiàn)實的最后戰(zhàn)線。4.2虛擬現(xiàn)實視覺渲染的主要方法虛擬現(xiàn)實視覺渲染的主要方法大部分技術(shù)來源于計算機圖形學中的真實感渲染技術(shù)和實時渲染技術(shù)：基于幾何的繪制（Geometry-basedRendering）基于圖像的繪制（Image-basedRendering）幾何與圖像結(jié)合的繪制基于幾何的繪制虛擬對象的幾何模型網(wǎng)格、體素、點云，或是參數(shù)化的函數(shù)等虛擬對象具備了空間位置信息、表面、材質(zhì)等屬性高真實感的渲染結(jié)果表現(xiàn)形式幾何建模真實感光照計算真實感光照計算是指在虛擬場景中模擬真實光照，計算虛擬對象在特定光照下的呈現(xiàn)效果。復雜紋理映射紋理映射是指將具有顏色信息的圖像附著在幾何對象的表面真實感光照計算局部光照計算虛擬對象某一點的亮度時，只考慮虛擬場景中的所有預定義的虛擬對象全局光照將整個環(huán)境作為光源，不僅考慮虛擬場景中的虛擬對象對被繪制對象的直接影響，還考慮光纖經(jīng)反射、折射或散射后對被繪制對象產(chǎn)生的間接影響現(xiàn)象：顏色滲透、陰影/軟陰影、焦散、次級表面散射等典型算法：光線追蹤算法、輻射度方法、光子映射（PhotonMapping）等全局光照模型可大大增強繪制結(jié)果的真實感，也是目前研究的重點全局光照光線追蹤算法：模擬光沿直線傳播，通過計算光線與虛擬對象的交點來確定光線強度，能夠生成高質(zhì)量圖像，但計算量大。相比之下，輻射度算法基于熱傳導理論，從光的能量傳遞角度處理圖像。輻射度算法：計算場景能量分布來獲得光照強度，適用于漫反射表面，但計算量大，近年來使用神經(jīng)網(wǎng)絡(luò)如NeRF加速渲染成為熱點。光子映射：通過追蹤光子在場景中的反射或折射，收集像素周圍的光子來確定顏色，適合表現(xiàn)次級散射和焦散效果，特別適用于復雜材質(zhì)對象的繪制。復雜紋理映射凹凸映射：凹凸映射通過擾動表面法向量來增強細節(jié)和真實感，不改變對象形狀或輪廓線，僅添加粗糙感而非顏色。位移映射：位移映射根據(jù)高度圖移動頂點位置，增強表面粗糙感，但計算量大；視差映射：視差映射通過逐像素深度的貼圖調(diào)整紋理坐標，提供深度感且計算量較小，但不能產(chǎn)生自陰影效果。浮雕映射：浮雕映射通過圖像變形和逐像素深度技術(shù)在平面上生成復雜的三維效果，比視差映射更準確且支持自陰影，但計算量較大。凹凸映射視差映射基于圖像的繪制與傳統(tǒng)的基于幾何的繪制技術(shù)相比，可使用較少的計算資源。所依賴的參考視點圖像既可以是真實數(shù)字圖像，也可以是虛擬圖像，方法的復雜程度不會因場景復雜度的變化而變化。全光函數(shù)與全光建模全景圖

視圖插值分層深度圖像其他繪制方法分層深度圖像繪制效果基于圖像的繪制技術(shù)利用已有多視角目標場景圖像生成新視角下的結(jié)果圖像。幾何與圖像結(jié)合的繪制技術(shù)基于幾何的繪制方法基于圖像的繪制方法優(yōu)點：利用較多的已知信息，不局限于幾何、表面屬性、光源信息等，便于一些特殊效果處理，如光照計算、物體變形優(yōu)點：繪制的逼真度高，計算量小缺點：交互性較差缺點：計算量大，繪制效果與真實世界仍存在一定差異幾何與圖像結(jié)合的繪制技術(shù)幾何與圖像結(jié)合的繪制方法幾何一致性：虛擬對象在透視上應該與真實場景的圖像一致，并保持正確的遮擋關(guān)系光照一致性：虛擬對象與真實場景的圖像應具有一致的光照效果，這就需要恢復出真實場景的光照模型，然后計算真實場景光照對虛擬對象的影響大規(guī)模虛擬場景渲染的關(guān)鍵技術(shù)虛擬現(xiàn)實視覺渲染除確保單個虛擬對象渲染的真實感之外，還需要考慮大規(guī)模虛擬場景渲染帶來的技術(shù)挑戰(zhàn)。大規(guī)模虛擬場景實時渲染問題優(yōu)化虛擬場景的幾何復雜度幾何模型化簡細節(jié)等級管理單元分割使用場景組織技術(shù)場景圖空間分割自然景物繪制技術(shù)水波毛發(fā)植物細節(jié)層次管理技術(shù)細節(jié)層次管理技術(shù)是指對虛擬場景中的不同虛擬對象采用多種不同幾何細節(jié)層次管理的方法。具體地，對每一個虛擬對象，在多種不同的幾何細節(jié)層次儲存虛擬對象，以便在繪制階段動態(tài)加載不同數(shù)據(jù)量的負載，以滿足實時性要求。虛擬對象的幾何模型中可保存不同級別的LOD，當虛擬對象離觀察者較近的時候，使用具有最多細節(jié)的幾何模型，當虛擬對象遠離觀察者時，使用細節(jié)減少的層次，以此類推，距離越遠，就渲染出更少細節(jié)的LOD模型。幾何模型化簡技術(shù)不同類型的虛擬現(xiàn)實系統(tǒng)對渲染的視覺精細程度有不同需求。因此，對于高實時性的網(wǎng)絡(luò)傳輸、移動終端等輕量化應用，可以通過對虛擬場景包含的虛擬對象的幾何模型進行化簡，降低幾何復雜度，從而減少渲染的時間開銷。針對不同的幾何模型表示方式，可以采用不同的幾何模型化簡方法。頂點聚類算法LOD漸進LOD在網(wǎng)格中，合并幾何特征不明顯的頂點，從而降低幾何模型的復雜度也可在幾何誤差范圍內(nèi)，在確保幾何拓撲不變的前提下刪除若干點、線、面等幾何元素根據(jù)觀察視點自適應地構(gòu)建幾何模型的細節(jié)層次表示根據(jù)觀察視點自適應地構(gòu)建幾何模型的細節(jié)層次表示化簡方法單元分割技術(shù)將虛擬場景分割成較小單元的過程稱為單元分割。分割后，只有當前視野中的物體會被渲染，從而大大減少了渲染的復雜度。這種方法特別適用于大型建筑場景。在分割后，大部分場景在給定視野中不起作用。除非跨越某個閾限（如從一個房間到另一個房間），否則視野中的多邊形數(shù)基本保持不變。對于規(guī)整的場景，分割可以自動完成；對于變化較少的場景，可以在預計算階段離線處理。虛擬場景組織技術(shù)除降低虛擬場景的幾何復雜度外，另一種解決大規(guī)模虛擬場景實時繪制的思路是降低大規(guī)模虛擬場景中的光照計算、碰撞檢測、裁剪等任務的算法復雜度。為了加快處理的速度，通常需要將虛擬場景按照某種數(shù)據(jù)結(jié)構(gòu)進行空間劃分，從而能夠快速地排除不需要的計算，降低面片數(shù)量對算法復雜度的影響。場景圖優(yōu)點:真實描述了虛擬對象的邏輯組織結(jié)構(gòu)容易操縱虛擬對象支持重用和擴展圖形軟件開發(fā)速度塊基于空間細分的數(shù)據(jù)結(jié)構(gòu)二元空間分割樹（BinarySpacePartitioning，BSP） BSP樹是用來對N維空間中的元素進行排序和查找的二叉樹。八叉樹（Octree）

八叉樹是另一種空間分割數(shù)據(jù)結(jié)構(gòu)，類似于軸對齊BSP樹。BSP樹的基本思想是空間中的任何平面都將整個空間分割成兩個半空間，所有位于該平面某一側(cè)的點定義了一個半空間，位于另一側(cè)的點定義了另一個半空間八叉樹基本思想沿著長方體包圍盒的三條軸對長方體進行同時分割，分割點必須位于這個包圍盒的中心，這樣一個包圍盒就能生成8個新的等大小的小長方體包圍盒二元空間分割樹（BSP）（左）場景的BSP樹剖分（右）BSP樹結(jié)構(gòu)示意圖

（左）一次剖分后的場景平面圖；（右）一次剖分后的BSP樹（左）兩次剖分后的場景平面圖；（右）兩次剖分后的BSP樹八叉樹（a）初始節(jié)點；（b）第一次剖分；（c）第二次剖分包圍體層次結(jié)構(gòu)

包圍體層次是虛擬場景實時繪制最常用的一種空間數(shù)據(jù)結(jié)構(gòu)，場景以層次樹狀結(jié)構(gòu)進行組織，包含一個根節(jié)點、內(nèi)部節(jié)點以及葉子節(jié)點。常見的包圍體有：球體、軸對齊包圍盒、有向包圍盒等包圍體層次適用于動態(tài)場景。當虛擬對象移動時，檢查它是否仍在父節(jié)點的包圍體內(nèi)。如果是，則BVH仍有效；如果不是，則需要刪除節(jié)點并更新樹結(jié)構(gòu)。當虛擬場景中有大量的移動虛擬對象更新操作時，BVH樹會變得不平衡，效率下降，需要更多計算資源，這是BVH樹的缺點。場景包圍體和場景剖分技術(shù)比較（左）場景包圍體技術(shù)（右）場景剖分技術(shù)自然景物的繪制技術(shù)水波的模擬基于構(gòu)造的方法，用數(shù)學函數(shù)構(gòu)造出水波的外形，然后變換時間參數(shù)生成水波基于物理的方法，從水波的物理原理出發(fā)，通過求解流體力學方程，得到流體質(zhì)點在各個時刻的狀態(tài)采用粒子系統(tǒng)，主要用于模擬雪花、浪花、瀑布等較為合適能滿足視覺上的效果，但不能反映水流的規(guī)律效果比較真實，但計算復雜，效率很低自然景物的繪制技術(shù)毛發(fā)的模擬先對毛發(fā)進行幾何建模，將每根毛發(fā)建模成三角面片或圓錐體，然后進行光照計算將毛發(fā)看作是半透明的圓柱體，采用全局光照算法渲染，在此過程中，使用類似參與介質(zhì)的渲染方法，設(shè)計毛發(fā)的多散射模型計算量大，無法滿足實時要求路徑追蹤算法計算效率有所提高自然景物的繪制技術(shù)植物的模擬分形技術(shù)，遞歸地生成植物，與真實世界差異很大。此外，分形模型由于幾何細節(jié)較多，對其使用全局光照算法計算量較大，難以滿足實時性要求。目前大多數(shù)情況下，把植物看作紋理，使用紋理映射技術(shù)得到具有一定真實感的視景。并行繪制技術(shù)例如，在光線追蹤算法中，可以將椎體分為n部分，同時發(fā)射n條光線并行處理。根據(jù)并行在繪制流水線中發(fā)生的階段，可以將并行繪制技術(shù)分為3種類型：Sort-firstSort-middleSort-last虛擬對象的繪制天然具有功能并行性和數(shù)據(jù)并行性，易于實現(xiàn)并行處理在繪制初期分配圖元和屏幕區(qū)域給處理器，通信量小但易導致繪制負載不平衡在幾何轉(zhuǎn)換與光柵化之間分配圖元，由各處理器獨立光柵化，最后拼接圖像，適合硬件實現(xiàn)但可能導致負載不均衡在光柵化的最后階段分配像素，解決了負載不平衡問題，但通信量大，需使用壓縮技術(shù)4.3場景組織例——大規(guī)模虛擬場景實時碰撞檢測算法思想隨著數(shù)據(jù)獲取技術(shù)和設(shè)備的不斷發(fā)展，虛擬場景的模型數(shù)據(jù)量迅速增大，甚至已經(jīng)超過了目前普通PC機內(nèi)存的容量。

右圖展示了NorthCarolina大學提供的PowerPlant場景。該虛擬場景擁有13000000個三角面片，為其建立完整的OBB層次樹結(jié)構(gòu)需要的OBB約為260000000個，總計需要1.8GB的空間來存儲OBB層次樹的結(jié)構(gòu)信息，再加上虛擬場景本身的幾何數(shù)據(jù)，總存儲量超過了2GB。由此可見，直接在內(nèi)存中為整個虛擬場景建立OBB層次結(jié)構(gòu)顯然是不合理的。因此，必須首先將虛擬場景進行劃分，將完整的虛擬場景數(shù)據(jù)存儲在外存中，而僅將劃分后的每個數(shù)據(jù)塊送入內(nèi)存進行實時處理。

算法思想使用外存進行碰撞檢測，除了算法復雜性的增大，在運行階段還需要實時讀取外存的數(shù)據(jù)，對碰撞檢測的速度造成較大影響。而要較好地支持多人協(xié)同的虛擬場景，又必須實時地向用戶反饋碰撞信息并進行相應處理。因此，解決在有限內(nèi)存下與外存模型進行實時碰撞檢測，提高碰撞檢測的效率，對保障虛擬現(xiàn)實應用的實時性有重要意義。

算法設(shè)計算法主要分為兩個階段：離線階段與實時階段離線階段主要任務是對虛擬場景進行組織。對外存模型來說，不僅需要高效的查詢效率，還需要將虛擬場景按空間劃分為可讀入內(nèi)存的數(shù)據(jù)塊，并提供實時調(diào)度的信息。由于進行碰撞檢測的數(shù)據(jù)量大，在實時階段首先需要對內(nèi)外存的數(shù)據(jù)進行有效的管理，實現(xiàn)數(shù)據(jù)的內(nèi)外存調(diào)度，然后依次完成相交測試與虛擬對象的碰撞預測。

算法實現(xiàn)虛擬場景數(shù)據(jù)組織對于基于外存的虛擬場景，需要將虛擬場景劃分為能夠讀入內(nèi)存的子數(shù)據(jù)塊，這里選用八叉樹對虛擬場景進行劃分和組織。傳統(tǒng)基于內(nèi)存模型的八叉樹結(jié)構(gòu)將虛擬場景數(shù)據(jù)直接存儲在八叉樹相應的葉節(jié)點內(nèi)，當虛擬場景復雜度高時是無法實現(xiàn)的。因此，這里使用外存索引的八叉樹結(jié)構(gòu)。與內(nèi)存模型的八叉樹不同，外存索引的八叉樹中，每個葉節(jié)點并不保存實際的幾何信息，而是保存本節(jié)點中的幾何信息所對應的外存文件的索引。

算法實現(xiàn)虛擬場景數(shù)據(jù)組織

算法實現(xiàn)虛擬場景數(shù)據(jù)組織最終虛擬場景的空間結(jié)構(gòu)分為兩個層次，整個虛擬場景的索引八叉樹結(jié)構(gòu)，與八叉樹的每個葉節(jié)點中的幾何屬性建立的包圍盒層次結(jié)構(gòu)

每個非空葉節(jié)點的幾何面片信息和相應的OBB層次樹結(jié)構(gòu)信息分別保存為單獨的外存文件，最后將整個八叉樹的層次結(jié)構(gòu)信息也保存為一個單獨的文件所有外存文件的總存儲量大小隨著虛擬場景復雜度的增加而增大，最終將超過內(nèi)存容量。然而在這一過程中，索引八叉樹只保存了八叉樹的層次結(jié)構(gòu)信息，并不會隨著場景復雜度的增加而增加，因此可以完全讀入內(nèi)存算法實現(xiàn)內(nèi)外存數(shù)據(jù)管理當為虛擬場景建立了索引八叉樹結(jié)構(gòu)后，八叉樹的所有葉節(jié)點相當于對虛擬場景的一個劃分，而每個葉節(jié)點中的幾何數(shù)據(jù)量由葉節(jié)點的最大頂點閾值限制在較小的范圍，因此在數(shù)據(jù)緩存的管理和調(diào)度中以八叉樹的葉節(jié)點為基本單位。葉節(jié)點的索引包括幾何文件和OBB文件，因此在數(shù)據(jù)調(diào)度時每一個葉節(jié)點都包括幾何面片數(shù)據(jù)和相應的OBB層次樹結(jié)構(gòu)數(shù)據(jù)。由于不同葉節(jié)點中的幾何圖元數(shù)量并不相等，對應文件的數(shù)據(jù)量大小也不同，因此數(shù)據(jù)緩存管理調(diào)度的基本單位不是固定大小的，會隨著所調(diào)入的葉節(jié)點的幾何圖元數(shù)的不同而具有不同的大小。

緩存中的數(shù)據(jù)塊與八叉樹節(jié)點的關(guān)系

算法實現(xiàn)內(nèi)外存數(shù)據(jù)管理虛擬對象在虛擬場景中運動具有連續(xù)性，其與虛擬場景的碰撞也具有時空連續(xù)性，即上一次發(fā)生碰撞的葉節(jié)點很可能在接下來也發(fā)生碰撞。因此，為了避免剛調(diào)入內(nèi)存的數(shù)據(jù)在不久又被刪除的情況，在數(shù)據(jù)調(diào)入調(diào)出時采用最近最少未使用策略，利用數(shù)據(jù)訪問的局部性來提高數(shù)據(jù)的命中率，防止局部時間內(nèi)對相同數(shù)據(jù)反復調(diào)入調(diào)出帶來的額外開銷。

緩存的數(shù)據(jù)管理流程

算法實現(xiàn)虛擬場景數(shù)據(jù)組織

分離軸原理示意

算法實現(xiàn)虛擬場景數(shù)據(jù)組織采用OBB層次樹結(jié)構(gòu)組織的物體的碰撞檢測問題，歸根結(jié)底可以歸結(jié)為OBB層次樹的遍歷問題。設(shè)有兩個虛擬對象，分別為它們建立OBB層次樹。在樹中每個節(jié)點上的包圍盒都對應于組成該虛擬對象的基本幾何元素集合的一個子集，根節(jié)點為整個虛擬對象的包圍盒?；贠BB層次樹的碰撞檢測算法核心就是：通過遍歷這兩棵樹，確定在當前位置下，兩個虛擬對象是否發(fā)生碰撞。這是一個雙重遍歷的過程

算法實現(xiàn)碰撞預測基于外存的碰撞檢測需要實時地調(diào)入當前碰撞檢測計算所需的數(shù)據(jù)，當數(shù)據(jù)不在內(nèi)存時，必須從外存讀入，造成碰撞檢測計算等待外存數(shù)據(jù)。低速的磁盤I/O操作將極大地影響碰撞檢測的實時性考慮到碰撞檢測具有時空連續(xù)性的特點以及八叉樹對場景規(guī)則的劃分，給出一種基于八叉樹鄰居的碰撞預測方法來得到潛在碰撞集使用單獨的預取線程對潛在碰撞集中所對應的數(shù)據(jù)進行讀取。在碰撞預測得到潛在碰撞集后便向預取線程發(fā)送預取請求，預取線程處理所有的預取請求，將需要的數(shù)據(jù)讀入內(nèi)存。

碰撞預測和多線程數(shù)據(jù)預取算法實現(xiàn)碰撞預測在虛擬場景的八叉樹結(jié)構(gòu)之上，設(shè)計基于鄰居的碰撞預測算法，計算潛在碰撞集，即下一幀或幾幀內(nèi)可能發(fā)生碰撞的葉節(jié)點集合。在實時運行初讀入八叉樹結(jié)構(gòu)文件，并建立八叉樹結(jié)構(gòu)后，為八叉樹所有葉節(jié)點計算其相應的面鄰居信息八叉樹葉節(jié)點代表的長方體區(qū)域（即AABB）具有六個面，除了外部節(jié)點，其每個面都有自己相對應的鄰居節(jié)點。為了使預測得到的潛在碰撞集更加準確，即與實際發(fā)生碰撞的葉節(jié)點集合相差不大，結(jié)合物體的運動方向和運動步長，以及八叉樹節(jié)點的鄰居信息，將滿足條件的葉節(jié)點加入潛在碰撞集，作為預測結(jié)果八叉樹葉節(jié)點鄰居查找

算法實現(xiàn)碰撞預測

根據(jù)虛擬對象運動方向考慮節(jié)點的不同面算法實現(xiàn)碰撞預測

??

?各分量符號與考慮面的關(guān)系分量正（+）負（﹣）RLUDBF算法實現(xiàn)碰撞預測

根據(jù)閾值計算潛在碰撞集

實驗結(jié)果——外存模型索引八叉樹的性能實驗所使用的場景模型為PowerPlant場景，整個虛擬場景的索引八叉樹劃分結(jié)果如圖PowerPlant場景的索引八叉樹

頂點閾值h八叉樹最大深度節(jié)點數(shù)原面片數(shù)最終面片數(shù)外存文件總大小30001110312113743213318971965.29GB5000115679313743213278094914.67GB7000103724913743213232014794.20GB10000102451313743213170367463.81GB15000101596913743213150168123.56GB頂點閾值h的增大，八叉樹最大深度，節(jié)點總數(shù)均減小，并且由于因跨多個葉節(jié)點而重復存儲的面片數(shù)量減少，最終的幾何面片數(shù)也減少，從而使外存文件大小總和也降低。實驗結(jié)果——相交測試上圖(a)展示了虛擬對象未與虛擬場景發(fā)生碰撞的情況，可以看到虛擬場景中的管道從虛擬對象自身的空隙處穿過，不會檢測到碰撞。上圖(b)中，恐龍發(fā)生旋轉(zhuǎn)，尾部與管道發(fā)生了碰撞，紅色的面片表示虛擬場景與虛擬對象相交的面片；恐龍尾部黃色邊組成的面片表示虛擬對象與虛擬場景發(fā)生碰撞的面片。實驗結(jié)果——碰撞預測基于鄰居的碰撞預測示意圖

實驗結(jié)果——算法性能在實驗中，使物體分別在采用的碰撞預測和多線程預取以及未采用預測和預取的情況下沿同一路徑運動并進行幀率的統(tǒng)計，其中2000幀的統(tǒng)計數(shù)據(jù)如圖所示有無碰撞預測和多線程預取下的幀率對比

4.4場景繪制優(yōu)化例——基于LOD的點云繪制算法思想基于長軸二分法的點云LOD構(gòu)造算法構(gòu)建層次包圍球的過程核心思想是構(gòu)建樹狀層次包圍球結(jié)構(gòu)，按空間劃分構(gòu)建出不同精度的層次樹(a)~

(c)展示了一個二維空間的分裂過程(c)~

(f)展示了數(shù)據(jù)合并的過程算法實現(xiàn)基于長軸二分法的點云LOD構(gòu)造算法構(gòu)建層次包圍