虛擬現實技術導論第1章概論本講大綱3.1虛擬現實模型3.2虛擬現實幾何建模3.3虛擬現實物理建模3.4虛擬現實行為建模3.5虛擬現實建模的特點與評價指標3.6幾何建模例——點云化簡3.7物理建模例——虛擬人體運動合成3.8物理建模例——基于SPH的熱帶氣旋建模3.9習題3.1虛擬現實模型模型“模型”是一個人為構造的物體，以便使人們容易觀察現實世界中的物體，例如：物理模型、數學模型……。換言之，“模型”是對物體全部或部分屬性的一個抽象。對象模型對象模型是構建虛擬環境的基礎，也是實物虛化的重要組成部分。一般的，主要包括幾何形狀、表面信息、物理特性、變化屬性等。對象模型幾何形狀描述對象形狀的幾何模型包含了點的位置信息和拓撲結構信息，主要由點、線、面等幾何元素組成。例如，使用一些現有的圖形庫來表現對象的幾何外形：大小、方向和位置等對象外表的真實感主要取決于其顏色、光照和紋理等。通過紋理元素的色彩、明暗度和透明度的變化來表現對象的表面細節，能夠減少多邊形的數量和增加對象在場景中的真實感。目前，投影法和參數表示法是兩種常用的表面紋理映射方法。表面信息為了保證視景表示和對象物體在虛擬環境中運動的合理性，經常需要建立對象物體的某些物理模型，使得場景中的對象遵循客觀的物理規律，從而生成具有一定真實感和逼真性的三維視景。一般賦予對象物體的物理特性主要有質量、動量、沖量、轉動慣量、光滑度、柔韌性和可塑性等。物理特性與變化屬性幾何模型從數學的角度，對于一個物體的幾何表示要考慮物體自身的特征，例如：

有界性、封閉性剛性：物體在剛性變換（平移、旋轉等）下是否保持不變規則性：一個物體中的點或線具有相同的性質光滑：……計算機圖形學與虛擬現實中，采用“幾何模型”的概念描述現實中的物體的幾何形狀，對物體幾何方面的屬性進行了抽象?！皫缀文Ｐ汀笔俏矬w模型的一個子集。幾何模型的表示方法基本幾何元素包括：點、邊、面、體。主要表示方法線框表示：結構簡單，用頂點和鄰邊表示形體表面表示：在上述基礎上，增加面，從而可以滿足對面的操作參數曲面三角形表示實體表示點表示……實體表示又稱為結構立體幾何表示，一般直接用立體基元表示對象物體，體積表示具有簡潔、可靠的特性，而且有時很容易計算。空間占有表示和結構立體幾何表示（CSG）是兩種主要的體積表示方法，其中CSG方法將物體表示為一個三維體積基元的集合和一個布爾運算集：并、交及差，其體積基元有塊、圓柱體、圓錐體和球等。表面或邊界法以Euler定理為基礎的結構規則，即如果V是多面體的頂角數，E是邊緣數，F是面數，則V–E+F=2,推廣到非簡單連接體為V–E+F=2（B–H），其中B是體的個數，H是“孔”或“柄”的個數。所以在表面或邊界法中，體結點描述景物結構，面結點描述表面特征，邊緣結點提供面，邊緣和頂角間的拓撲信息，頂角結點描述三維頂角的位置等。模型的組織方法（數據結構）數據結構主要是為了描述拓撲關系（即頂點連接關系、面片連接關系等）在設計數據結構時，空間與速度總是一對矛盾。線形表、樹、圖都是可以考慮的結構，在具體構建時，可以使用數組也可以使用指針精心的設計這樣的數據結構對于繪制有很大的好處往往高效的算法是以對存儲空間的占用為代價的繪制過程實際是對上述數據結構的遍歷。關鍵是如何快速的遍歷，查找挑選出需要顯示的物體，將這些內容交給底層進行繪制模型的組織方法（數據結構）模型的組織方法（數據結構）對于“任意”情況，數據結構可能需要存儲額外的信息。例如，如果對構成物體的多邊形的邊數不加限制，每個面表必須顯式存儲每個多邊形邊的數量，而且涉及到大量的內存的申請與釋放對多邊形的凸凹不加限制，額外計算量也很大所以，對多邊形構成的物體，往往對多邊形的類型加以約束，例如采用三角形描述（最簡單的一種凸多邊形）任意的多邊形可以按照一定的方法劃分為多個三角形（計算幾何）[關鍵是算法的效率問題]基于三角面片的模型表示三個頂點的空間坐標用途：空間變換，投影三個頂點的法向量（或面片的整個法向量）用途：光照計算三個頂點的紋理坐標或顏色用途：顯示顏色信息VR中采用的幾何表示方法虛擬現實領域普遍采用的表示方法是表面多邊形（三角形網格）表示法，即以一組表面多邊形來存儲物體的描述，用多邊形描述的通常被稱為“標準圖形物體”。由于所有表面以線性方程形式加以描述，大大簡化并加速了表面的繪制和顯示。也就是說，所有的三維模型都將由點、線、面來構造。3.2虛擬現實幾何建模幾何建模幾何建模形狀建模外觀建模結構建模物理建模剛體建模柔性體建模流體建模行為建模形狀建模要描述虛擬對象的形狀，最基本的任務是利用點、線、面等基本幾何元素表征虛擬對象的外邊界。目前最常用的形狀建模方式可分為顯式表示與隱式表示兩種。其中，顯式表示是指使用點云、網格、體素等表征虛擬對象外邊界的位置與拓撲信息；隱式表示則是指使用曲線曲面等參數方程、距離場（Distancefield）、水平集（Levelset）等方法描述虛擬對象的外邊界。外觀建模虛擬對象的外觀是指區別于其他虛擬對象的質地特征，如表面反照率、紋理等影響虛擬對象真實感的特征。如果不考慮存儲和計算的開銷，通過增加虛擬對象形狀多邊形的方法可以表征出十分逼真的表面，但由于VR對計算和顯示實時性要求高，實際系統中普遍采用紋理映射(TextureMapping)等技術刻畫虛擬對象的外觀。采用紋理映射技術，一方面可增加細節層次以及虛擬對象的真實感；二是可減少多邊形的數量，在不影響實時性的同時，增強了虛擬對象和場景的真實效果。結構建模除了要模擬虛擬對象的形狀和外觀，很多時候還需描述虛擬對象的空間結構信息，以體現虛擬對象內部結構或虛擬對象之間的空間關系。以虛擬人體為例，可使用骨架結構表示各關節間的關系，并應用于人體動畫、人體運動分析、不同人體的匹配等。對復雜的工業裝備來說，可建立各個組成部分（亦稱部件）的結構關系，從而對不同部分進行控制，以滿足虛擬裝配、拆裝維護等要求。幾何建模幾何建模的常用方法程序構造——利用函數、點線面直接采集——三維掃描儀、視覺建模工具——利用軟件幾何建模幾何建模的常用方法程序構造——利用函數、點線面直接采集——三維掃描儀、視覺建模工具——利用軟件幾何建模幾何建模的常用方法程序構造——利用函數、點線面直接采集——三維掃描儀、視覺建模工具——利用軟件幾何建模中涉及的基本概念層次細節（LOD）自由度（DOF）實例透明紋理映射材質動畫序列層次細節技術(LevelofDetail,LOD)LOD技術用一組復雜程度（常常以多邊形數來衡量）各不相同的層次模型來描述對象，并在運行過程中根據一些主客觀標準在這些LOD模型進行切換，從而能夠實時改變場景的復雜度。當視點變化時，所選取的細節模型可能各不相同，并在模型切換的瞬間產生跳躍的感覺，此時就需要使用過渡算法（比如，瞬時關閉技術和形狀過渡技術）來實現其中的過渡。LOD在地形表示中的應用

顯示地形最理想的情況是僅僅顯示所需的細節，而用戶卻認為地形是在以最高的分辨率顯示。因此，那些由許多小平面以最高的分辨率建模的地形，我們希望能夠用較少的較大的小平面不斷地代替，直到整個地形被降低為在所需范圍內的最低表示分辨率。層次結構的四叉樹表示NPSNET（NavalPostgraduateSchoolNetwork）使用了四叉樹的存儲策略來實現LOD。它采用了一種動態模式，可以動態地調整分辨率和幀速率，即當幀速率降低到某一門限值以下時，調整分辨率邊界值，則較多的地形自動以相對低的分辨率顯示；相反地，當幀速率超過某一門限值時，較多的地形自動以相對高的分辨率顯示。

1km*1km的地形塊地形塊的四叉樹表逸夫館中某窗戶的LOD模型15-0米時選用高級LOD：96個多邊形的窗子，全部幾何建模35-15米時選用中級LOD：34個多邊形的窗子，部分使用紋理視點距窗子75-35范圍時選用低級LOD：2個多邊形的窗子，全部使用紋理視點在室外時僅使用逸夫館外觀模型1800個三角形視點位于某一樓層時，當前樓層中的實體按距離標準選用LOD模型，其它樓層的大部分實體暫不繪制室外室內某一樓層遠距離中距離近距離

0個0個2個34個96個自由度(DegreeOfFree,DOF）紋理貼圖紋理貼圖是一個用圖像、函數或其它數據源來改變表面在每一處的外觀的過程。例如，我們不必用精確的幾何去表現一塊磚墻，而只需把一幅磚墻的圖像貼到一個多邊形上。除非觀察者非?？拷鼔?，否則我們并不會覺得缺少幾何細節（例如發現磚頭和泥漿在同一表面上）。既節省了大量的造型工作量，也節省了內存空間，加快了繪制速度。“Allittakesisfortherenderedimagetolookright”——JimBlinn紋理貼圖可能的缺陷但是，貼了紋理的磚墻還會出現并非由于缺少幾何細節而出現的不真實的缺陷。但是：磚是發亮的(shiny),但是泥漿不是。但我們會發現磚和泥漿同樣發亮。為了生成更真實的效果，我們還需要一張鏡面高光紋理貼圖。但是：磚不是平的，其表面通常是粗糙的。我們還需要凹凸紋理（Bumpmapping）廣義紋理貼圖(GeneralizedTexturing)紋理貼圖可看成是一種有效的改變物體表面屬性的一種方法。顏色、高光、凹凸、反射、透明度等等都可采用紋理貼圖。從貼圖圖像中取出相應的值代入光亮度計算方程。計算物體空間位置用投影函數計算(u,v)用對應函數找到紋素應用值變換函數改變方程或Fragment值單個紋理的廣義貼圖流水線采用該復雜流水線的原因：每一步都可給用戶提供有用的控制磚墻紋理貼圖的流水線——計算空間位置磚墻紋理貼圖的流水線——投影函數投影函數把三維空間點轉化為紋理坐標。常用的投影函數：Spherical,Cylindrical,PlanarProjections,參數曲面的(u,v)映射其它：如根據表面法向來確定6個平面投影方向sphericalcylindricalplanar應用應用應用(u,v)磚墻紋理貼圖的流水線——對應函數對應函數把參數空間的值轉化為紋理空間的位置。第一種對應函數:用API選擇一部分紋理（子紋理）進行紋理映射。另一種對應函數：用矩陣變換。由于OpenGL支持4X4矩陣操作，任何API的應用層都可采用這類變換，如平移、旋轉、比例變換、錯切等ImageTexturing在硬件圖形加速卡中，紋理圖像的大小經常為2m×2n(或者2m×2m)的紋素，其中m和n為非負整數。不同的圖形卡有不同的紋理大小上限。若投影得到的象素數目比原始紋理大，則需要把紋理圖像放大(magnification)；若投影得到的象素數目比原始紋理小，則需要把紋理圖像縮小(minification)；OpenGL

mipmapsMipmaps（使用Bi-linear

Interpolation）材質（materials）幾何建模的準則嚴格按照真實數據建立比例對應的幾何模型一般應建立各模型部件的不同層次細節，以求得漫游性能與模型質量間的均衡效果使用最少的多邊形獲取相同的視覺效果在建模階段即對具有運動特征的模型部件進行優化的數據組織，定義基本運動參數幾何建模的常見問題過于注重實體幾何尺寸、表面特性的構建，忽略了更為重要的場景數據庫整體結構的優化設計。Z值爭奪問題T型相交問題使用凹多邊形表示實體表面Z值爭奪問題多邊形位置重疊造成的Z值爭奪。即兩個多邊形在空間位置上具有相同的深度值（Z值），導致圖形系統進行場景顯示時使用Z-BUFFER消隱算法無法正確判斷哪一個多邊形應該優先顯示，引起畫面閃爍。解決此類問題的方法有多種，如多邊形剪切、子面設置等。NNN是否已經掃描了所有多邊形是否計算了此多邊形所有的像素數YYY幀緩沖區置成背景色Z緩沖區置成最小Z值掃描當前多邊形把Z(x,y)存入Z緩沖區中的(x,y)處把多邊形在(x,y)處的亮度值存入緩沖區中的(x,y)處移到下一個像素計算多邊形在該像素的深度值Z(x,y)移到下一個多邊形Z(x,y)是否大于Z緩沖區在(x,y)處的值多邊形剪切算法T型多邊形組合T型多邊形組合。此類問題常見于由二維CAD電子圖板經拉伸操作構成的三維模型中。其導致畫面閃爍的原因與Z值爭奪相似。應在建模過程中避免T型多邊形組合的出現。使用凹多邊形表示實體表面使用凹多邊形表示實體表面。大多數圖形系統都明確規定，不能使用凹多邊形繪制實體表面。一般地，圖形系統對實體表面的凹多邊形進行自動切分，將一個凹多邊形分解為多個凸多邊形。3.3虛擬現實物理建模物理建模物理建模（Physically-basedModeling，PBM）是虛擬現實中比較高層次的建模，它有機融入物理模型，將虛擬對象的物理屬性加以體現。近年來，除了靜態的物理屬性，越來越多物理學中動態過程，如人體運動解算、流體計算、燃燒計算等與VR結合，在虛擬環境中實現了面部表情的模擬、織物的模擬、爆炸的模擬等。根據虛擬對象的物理性質，可大致分為剛體建模、柔性體建模與流體建模。剛體建模剛體建模適用于僅需考慮位置與方向的改變，而不需要考慮形變的虛擬對象，建模所涉及的內容主要包括剛體的運動、碰撞檢測以及連接和約束等問題。剛體建模——剛體的運動僅包含一個部件的剛體運動較為簡單，可以采用牛頓第二定律等刻畫其運動參數及運動。對于包含多個部件的剛體，如人體、手等，相對較為復雜。在刻畫多個部件的剛體運動時，以人體運動為例，可以有關鍵幀方法、運動學方法和動力學方法等。后兩者分別通過使用運動學和動力學方法建立人體運動的物理模型。與運動學方法相比，動力學方法需指定的參數較少，而且對復雜運動過程的模擬更為逼真，但計算量較大，運動控制的難度較大。剛體建?！鲎矙z測剛體的碰撞檢測主要針對對剛體運動中的碰撞進行分析，為加速計算，一般采用樹結構對虛擬環境中的虛擬對象進行組織，通過空間剖分法或層次包圍盒法建立樹結構?？臻g剖分的策略有均勻剖分、BSP樹、kd樹和八叉樹等,適用于分布比較稀疏均勻的幾何對象間的碰撞檢測。層次包圍盒法利用形狀簡單的包圍盒刻畫復雜的虛擬對象，包圍盒的結構有層次包圍球樹、AABB（Aligned-axisBoundingBox）層次樹、OBB（OrientedBoundingBox）層次樹等，適用于復雜環境中的碰撞檢測。八叉樹空間剖分AABB層次樹剛體建?！B接和約束連接和約束建模鉸鏈類型的虛擬對象（如門窗、轉動的機械臂）在多個約束情況下的關聯運動問題。關聯運動一般可分為前向關聯運動和反向關聯運動，前向關聯運動研究給出關聯運動中每個關節的角度和長度，求解關節末端所能到達的位置；反向關聯運動研究的是給定某個位置，確定已知關節模型的可達性。柔性體建模柔性體不同于剛體，在外力的作用下會產生形變，建模難度更大。柔性體建模主要關注動力學模型及其迭代求解方法。柔性體建模中常用的動力學模型有連續體模型、彈簧-質點模型等。柔性體建?！B續體模型連續體模型使用本構模型描述不同材料的物理特性，如彈性力、阻尼力等，再使用有限元方法模擬不同形變下的力或能量。此外，為得到更加理想的物理模擬效果，還可使用力傳感、視覺傳感器等采集實際材料的力-形變關系，更加準確地描述虛擬對象的靜態與動態特性。連續體模型主要用于虛擬現實中布料、毛發、松軟組織、人體器官、肌肉、面部表情的模擬。柔性體建模——彈簧-質量模型彈簧-質點模型將柔性體表面視為離散的質點與連接質點的彈簧組成的規則網格結構。質點間通過彈簧相連，受到彈簧彈力和阻尼力，遵循胡克定律，即當實際長度大于松弛長度時，彈簧將對兩端的質點產生相向的拉力；反之，在外力作用下變形后，有恢復原樣（松弛狀態）的傾向。柔性體建?！黧w建模流體建模主要使用計算流體力學模型，如使用納維-斯托克斯（Navier-Stokes，NS）方程建模流體的運動。NS方程常見的迭代求解方法有基于網格的方法和無網格的方法?；诰W格的方法主要使用拉格朗日網格或歐拉網格模擬流體在固定網格單元上的運動，是目前流體模擬的主要方法。但是，基于網格的方法容易產生網格畸變導致計算誤差過大。此外，該方法難以模擬大形變現象，如動態裂紋擴展、流固耦合等。無網格的方法通過使用一系列任意分布的節點（或粒子）來求解具有各種邊界條件的NS方程，節點或粒子之間不需要網格進行連接，因此不僅可以保證計算的精度，還可降低計算的難度?；诰W格的流體仿真無網格（SPH）的流體仿真3.4虛擬現實行為建模行為建模VR中的行為建模主要研究虛擬環境中自治對象建模方法，如游戲中由計算機控制的角色，元宇宙中的人工智能生成的智能體等。早期工作中，行為建模的研究主要在軍事仿真領域，如ModSAF、STOW、WARSIM2000等分布式虛擬戰場環境中的計算機生成兵力。隨著VR研究與應用的發展，行為建模已拓展到公共安全、教育、文化娛樂等眾多領域，如應急仿真規劃系統(EmergencySimulationProgram，ESP）等。近年來，隨著數字孿生和元宇宙等的興起，各類VR應用對自治對象行為的智能水平提出了越來越高的要求。這一領域屬于與人工智能的交叉研究范疇，與生成式人工智能（ArtificialIntelligenceGeneratedContent，AIGC）和應用都有密切的關聯，雖進展緩慢但卻是未來VR發展的重要關注點。行為建模根據自治對象的類型，可以將行為建模分為個體建模與群體建模兩類。其中，群體又有聚合類對象和自治對象組織兩類。聚合類對象包括多個個體，但可以使用多種解析度來表示。例如，既可以將其當作整體單一的對象，也可將其看作多個個體。根據具體的事件對群體的影響，可以采用不同的解析度。例如，在考察高溫對人群行為的影響時，可以將人群看作一個整體來建模；但在考察火災對人群行為的影響時，需要采用高解析度來建模不同的個體。聚合體對象行為建模主要內容包括計算模型、多解析度表現方法，以及聚合、解聚規則等。行為建模根據自治對象的類型，可以將行為建模分為個體建模與群體建模兩類。其中，群體又有聚合類對象和自治對象組織兩類。自治對象組織的行為建模更加復雜。自治對象組織是若干獨立存在個體的組織，其中每個個體進行自主決策，同時服從組織的控制。因此，自治對象的行為表現為個體行為和整體組織行為兩個層面，不同層面對行為建模的要求不同。常用行為建模方法有限狀態自動機自治對象的簡單反應性行為可以采用有限狀態自動機進行建模。其中，自治對象每種可能的反應動作表示為一個狀態，發生的事件控制狀態間的轉換。采用有限狀態自動機是軍事仿真中常用的行為建模方法。面向專家系統的建模方法將自治對象看成一個近似的專家系統，將其行為建?？醋髦R的獲取、表示和推理系統建立的過程，比較適合個體和群體的建模。對確定性知識，采用基于邏輯、規則、框架的表示，以及相應的推理系統；對不確定性知識，可采用模糊邏輯、神經網絡、基于范例的推理和貝葉斯方法等。此外，還可使用強化學習等方法以提高自治對象的求解復雜問題的能力?；趯＜蚁到y的方法基于Agent的建模方法將人工智能中關于Agent的研究引入VR中，適用于個體和群體的行為建模。相較上述方法，基于Agent的建模方法一方面能夠描述個體對象的自主性、自治性和智能性等特征，如建模個體對象的信念、意圖、愿望等；另一方面Agent之間的通信、協商、協作等可以描述自治對象組織的協作特性。目前，基于Agent的行為建模已得到越來越多的應用?；贏gent的方法3.5虛擬現實建模的特點與評價指標虛擬現實建模的特點由于要實時操控和處理虛擬對象，虛擬現實建模方法與傳統計算機輔助設計中以幾何造型為主的建模有所不同。例如，在計算機輔助設計中，往往通過增加模型的幾何復雜度來提高建模的準確度。但在VR中，更傾向于使用紋理、層次細節等技術來提升虛擬對象的逼真度。虛擬現實建模的內容相較傳統計算機圖形學中的建模更為豐富，除對虛擬對象的外形、表觀、結構等信息進行表征外，還建模了虛擬對象的物理屬性、行為屬性等，從而為用戶提供具有沉浸感的交互體驗。虛擬現實建模的特點差異虛擬現實建模計算機輔助設計建模計算機圖形學建模特點具有真實感、實時性和交互性，考慮交互性和實現意圖；模型細節比較少，可以提高實時性具有準確性，較少考慮實時性和交互性；模型細節較多，可以犧牲實時性來獲得較高的精度具有真實感，較少考慮實時性和交互性；模型細節較多，渲染效果可以預先計算用戶親身體驗虛擬環境，身臨其境，能夠交互，無時限限制，可真實詳盡地展示能夠交互，不考慮沉浸感能夠交互，較少考慮沉浸感應用主要用于仿真，需要對用戶輸入做出反應，如飛行訓練、游戲和視景仿真等主要用于工業制造與仿真計算，如機械零件設計、芯片電路仿真等主要用于影視、流媒體、電子游戲等，以預先設計好的演示為主虛擬現實建模評價指標真實感真實感是度量虛擬對象感知精確程度的指標，包括但不限于視覺真實感、觸覺真實感等；實時性虛擬現實應用要求虛擬對象或場景的顯示幀率不低于某一閾值，否則會影響用戶的視覺感知質量；交互延遲虛擬現實應用對交互延遲有高的要求。響應時間太長會大大影響用戶的體驗；易用性虛擬現實應用對交互延遲有高的要求。響應時間太長會大大影響用戶的體驗；……3.6幾何建模例——點云化簡點云化簡點云的質量取決于采樣密度，然而較大的采樣密度往往導致虛擬對象的幾何復雜度上升，不利于存儲與處理。特別對于存儲與計算資源有限的設備，如移動終端，大規模點云往往導致較高的交互延遲，降低了用戶的視覺體驗。因此，需要引入點云的化簡技術對其進行優化。現有點云化簡算法迭代法迭代法是指不斷的從點云中去掉按某種標準計算的貢獻值或誤差值最小的點，直到誤差或貢獻值達到閾值為止，從而得到一個子集作為簡化結果。該方法類似于漸近網格的簡化方法。這類方法較為簡單高效，但是不能保證全局采樣點的均勻分布。聚類法是指把輸入點集按照一定規則進行聚類，劃分成一些小的子集，這些小的子集不能超過給定的上限范圍，如直徑的大小等。如采用基于采樣點層次結構的聚類簡化方法，該方法通過空間二分將點集遞歸地進行劃分聚類。也有方法通過PCA找到關鍵點，然后進行聚類，從而得到保持幾何特征的簡化結果。這類方法簡單且快速，但是誤差較大，且因為沒有優化策略，所以結果通常會包含很多多余的點。聚類法粒子仿真法是指通過施加點的斥力使點的分布均勻化的方法。該方法首先在表面隨機分布需要的粒子數，然后通過點的斥力移動粒子的位置直到達到平衡。該類方法能較好地控制采樣密度，但是由于收斂速度較慢，處理大規模數據時效率較低。粒子仿真法上述三類方法在簡化過程中，將點云中的點看成單純幾何意義上的點，且不能預先指定逼近誤差，因此簡化效果往往不能準確表示虛擬對象的結構，并且難以收斂?；赟plats的點云簡化方法在簡化過程中考慮到點云的繪制圖元的幾何空間影響，并能用預先指定的全局誤差進行控制，得到了較好的簡化效果。以常見的點的繪制圖元splat為例，首先在指定全局誤差下，生成每個采樣點的最大splat；然后采用貪心算法選擇能覆蓋整個表面的最小子集；最后通過全局優化算法使所有的splat均勻分布。基于繪制圖元的方法相較上述三類方法能夠取到較好的簡化結果，但是計算復雜，時間開銷較大。改進的算法思想基于MLS和splat的點云化簡方法的核心思想是使用MLS投影算子計算splat的中心點，使得splat與其覆蓋范圍內的原始點云采樣的點的子集之間的誤差和最小。由此得到一個代表鄰域的誤差最小的splat。通過上述方法獲得的所有splat的中心點的集合，就是一個化簡后的點云。整個算法包括兩個步驟：首先，為每個原始點云的采樣點創建對應的splat集；其次，通過貪心算法選擇一組能夠覆蓋整個模型且數量最小的splat集合。選擇標準是循環選取覆蓋點數增值最大的splat，直到選擇的splat集合能夠覆蓋所有的輸入采樣點集。算法實現創建splat集合MLS投影計算splat中心點Splat覆蓋區域Splat最小集選擇算法算法實現MLS投影計算splat中心點MLS是根據鄰域點進行局部多項式逼近的方法，MLS投影表示將點投影到MLS逼近的表面上。對輸入點進行MLS投影可以得到代表鄰域的誤差最小的點，將其作為splat中心點，可以得到誤差最小的代表鄰域的splat面，從而得到分布更加合理的splats集。算法實現MLS投影計算splat中心點

接下來，使用協方差分析來評估法線，其原理主要基于主成分分析。首先根據待求點??及其鄰域點計算其協方差矩陣??，如下所示：

協方差矩陣表示了點鄰域內采樣點的分布情況，對其進行特征值分析可以評估其局部表面的屬性。

算法實現splats覆蓋區域獲得splat的法線和中心點之后，需要知道每個splat的覆蓋面積，這取決于預先指定的全局最大誤差閾值。用splat來代表其覆蓋的鄰域范圍，則鄰域點中某點的誤差即點到splat在法線方向上的距離算法實現splats覆蓋區域

算法實現splats最小集選擇選擇算法的目的是獲取能覆蓋整個表面的最小splats集。具體地，通過貪心算法不斷地選取覆蓋點數增值最大的splat，直到選擇的splat子集能夠覆蓋所有的輸入采樣點。

算法實現splats最小集選擇算法

實驗結果首先，使用少量的點驗證MLS投影的效果，實驗結果如圖所示。其中，綠色點表示點（藍色點）的最近20個鄰域點，（紅色點）是點的MLS投影點。

可看出，MLS投影點比點更適合用來代表的鄰域。實驗結果接著，在不同幾何復雜度的點云上進行了化簡實驗，化簡結果如表所示。可以看出，算法可以有效地化簡模型，且計算時間較短。模型輸入點數

簡化后的點數簡化時間(s)bunny35,9450.2477180.1864130.051,559110.023,150100.014,6166santa75,7810.1638760.022,52540horse100,0000.18901110.051,695740.023,459490.015,40643igea134,3450.051,0823290.022,9501220.015,494136armadillo172,9740.29,7372150.116,7292230.0525,764229dragon437,6450.0122,576831實驗結果右圖展示了化簡后的點云的繪制結果。其中，圖(a)～圖(d)是原始虛擬對象；圖(e)～圖(h)是使用算法化簡后的虛擬對象?？梢钥闯觯涍^算法化簡的點云在點數減少的同時能夠保持原始虛擬對象的幾何特性。實驗結果使用點數規模更大的點云進行了實驗。可以看出，算法對于大規模點云同樣具有良好的簡化效果。實驗結果該圖展示了不同的全局最大誤差閾值對點云化簡的繪制效果的影響。其中，圖(a)～(c)為基于splat的繪制；圖(d)～(f)為基于球的繪制，每個球的半徑等于splat的半徑。從圖中可以看出，所選擇的splat子集在不同全局最大誤差下均能有效覆蓋虛擬對象的表面。3.7物理建模例——虛擬人體運動合成人體骨架系統構建在人體骨架系統構建方面，有兩種通用標準，分別是：VRML使用的H-Anim標準MPEG提出的虛擬人體標準H-Anim標準是一種用于描繪擬人動畫的3D虛擬人體模型標準。該標準規定虛擬人體由Humanoid、Joint、Segment、Site、Displacer等節點組成。MPEG標準與之不同，在MPEG中，虛擬人體模型由一組節點組成。其中，頂層節點BodyNode至少包括兩個子節點：人體的運動參數和表示人體模型定義的參數。人體運動參數包含296個描述虛擬人體骨架拓撲結構的參數，這些參數可被應用于MPEG兼容的虛擬人體幾何模型，并生成相同的虛擬人體運動。關節運動描述

關節運動描述為了方便對虛擬人體骨架模型的運動進行描述，一般規定兩種坐標系：一種是用于描述根節點位置和朝向的世界坐標系（也稱為絕對坐標系），另一種是關節的局部坐標系（也稱為相對坐標系）。以下圖手臂剛體結構為例，

基于運動圖的虛擬人體運動合成所謂運動合成，是指對無序的運動捕獲數據進行組織，進而根據需求對其中的若干個數據序列進行某種方式的連接與融合，得到新的運動數據序列。運動圖是一種基于圖的運動片段組織方式，本質上是由節點和邊組成的有向圖，其中的“節點”對應于靜態的人體骨架系統（也可稱為人體姿態），而“邊”對應于連接姿態的運動片段。用戶通過搜索運動圖就能合成出逼真的運動序列。

算法思想基于運動圖的交互式運動合成方法首先使用一種基于特征的人體運動捕獲數據自動分割方法將原始運動數據進行分割；然后，基于分割的運動數據片段構建運動圖；最后，在實時運動控制過程中，利用運動圖生成符合環境約束的運動，用戶可以實時改變運動軌跡，控制虛擬人體沿著指定的軌跡運動。特別地，在控制虛擬人體沿著新軌跡運動時，采用對路徑曲線弧長參數化的方法，求得原始運動在目標軌跡上的位置和朝向，從而將虛擬人體重定位到目標軌跡曲線上，完成路徑合成部分。

算法設計算法包含四個模塊：虛擬化身物理模型構建模塊運動圖構建模塊交互式軌跡編輯模塊虛擬化身運動控制模塊算法設計虛擬化身物理模型構建模塊將從運動捕捉設備獲取的數據存儲為ASF/AMC格式，并進行解析。ASF/AMC格式的運動捕獲數據文件主要包含兩部分。其中，ASF格式文件記錄人體骨架數據，AMC格式文件記錄運動數據。ASF格式文件給出了人體骨架模型，并設定了初始姿態。ASF格式文件包括捕獲系統說明、度量單位、文檔描述、根節點信息、關節信息、關節之間的層次結構等6部分。AMC格式文件與ASF格式文件的內容相對應，以幀為單位記錄了每一幀中根關節的平移和旋轉向量，以及其他各個關節在各個自由度方向上的旋轉，在ASF文件中，旋轉以歐拉角的形式給出。

算法設計虛擬化身物理模型構建模塊從ASF格式數據文件構建虛擬人體的骨架模型所構建的骨架模型包含31個關節點，各個關節點之間采用樹形的組織形式；整個人體運動模型有一個根節點，它是整個人體骨骼樹結構的根節點。根節點由6個維度構成，分別是三個方向的平移量和三個方向的旋轉量，三個方向的平移量決定了該骨骼運動樹所表示的人體運動姿態的位置，而三個方向的旋轉量決定了該骨骼運動樹所表示的人體運動姿態的朝向。其余各個子節均有1到3個自由度，表示在其父節點所表征的局部坐標系下該關節點的旋轉。此外，ASF格式文件結構給出了虛擬人體的初始姿態以及各個關節的局部坐標系信息。

算法設計虛擬化身物理模型構建模塊從骨架模型構建出虛擬人體的層次樹骨架模型中的每個關節點都成為層次樹的一個節點。其中，每個節點存儲著關節的自由度以及相應的運動描述信息。

算法設計運動圖構建運動片段分割。對運動捕獲數據進行合理分割是構建運動圖的前提和基礎。以雙足運動為例，將人與環境接觸的關鍵姿態稱為關鍵幀，如雙足運動中腳接觸地面的時刻，關鍵幀體現了該運動的運動特征。利用關鍵幀將運動數據分割為若干個運動片段，為構建運動圖提供基礎。

首先，計算一只腳（左腳或者右腳）在所有運動數據幀中的全局坐標系下的絕對位置，取腳在高度方向的坐標值；接著，尋找所選腳的第一個關鍵幀，即開始邁第一步的幀數，選擇依據是梯度由負變為正并且當前全局位置在全局最低點位置的10%鄰域內；然后，找到所選腳的第二個關鍵幀，即第一步的最高點的幀數，選擇依據是梯度由正變為負并且當前全局位置在全局最高點位置的10%鄰域；最后，尋找所選腳的第三個關鍵幀，即第一步的結束幀，選擇依據同第一個關鍵幀的選取方法。

算法設計運動圖構建構建運動圖

算法設計交互式軌跡編輯基于所構建的運動圖，使用交互式的軌跡編輯來控制虛擬人體的運動合成，從而使之按照預設的軌跡進行平滑運動。具體地，使用Kochanek-Bartels樣條函數對虛擬人體的軌跡進行擬合。

在修改虛擬人體運動軌跡的時候，首先調整視點，通過拖動鼠標對軌跡進行編輯；修改軌跡操作完成后，將視點恢復，原始運動軌跡得到修改。

視點調整以后調整運動軌跡

視點還原以后的軌跡示意圖

算法設計虛擬化身運動控制在求解虛擬人體在目標軌跡上每一幀的根節點的坐標位置和方向的時候，采用基于軌跡弧長參數化的方法來解決。將虛擬人體的位置以弧長為單位映射到目標軌跡上，使得相同的時間內移動相同的距離，從而保證虛擬人體在目標軌跡上移動的速度與在原始軌跡上的速度一致。當目標軌跡長度與原始軌跡長度不一致的時候，不能保證運動結束在軌跡末端。因此，需要根據目標軌跡長度合成新的運動，使得運動可以進行到軌跡末端，這就需要利用上面生成得到的運動圖進行合成。

實驗結果運動合成的效果下圖展示了運動數據自動分割方法結果。通過對運動捕獲數據進行自動分割，得到了四個單位步長的運動數據片段，從左往右依次是左腿跑、右腿跑、左腿走與右腿走。

實驗結果運動合成的效果基于上述運動圖構建方法，利用自動分割得到的單位步長運動數據片段合成如下運動序列。實驗結果交互式制定運動軌跡合成運動已知原始運動捕獲數據，通過交互指定運動軌跡使得虛擬人體沿著新軌跡運動

。3.8物理建模例——基于SPH的熱帶氣旋建模算法思想自Lucy和Gingold和Monaghan等分別提出了光滑質點流體動力學（SmoothedParticleHydrodynamics，簡稱SPH）方法，并且成功地應用于天體物理領域之后，SPH法已經被應用于沖擊波模擬、流體動力學、水下爆炸仿真模擬、高速碰撞等材料動態響應的數值模擬等領域。然而，SPH在計算過程中對步長的要求比較苛刻。Miles和Matthias在2013年在設計了PBF（Positionbasedfluid，基于位置的流體）算法，通過求解一組位置約束，從而強制保證不可壓縮性。與傳統SPH方法相比，PBF求解過程中不是通過先分析所有的受力情況，然后再計算仿真對象的加速度，進而求解速度和位移的過程，而是先應用平流估計，即主要外力作用和慣性產生的位移，然后在此位置上通過迭代求解滿足相應的應力作用的位移直到收斂，因此在較大時間步長下，可以實現較為真實的云的運動。算法設計算法1：PBF算法1for2

3end4loop5

for6

7

求解速度阻尼8

9

end

10

for11

12

end

13

while迭代次數＜最少迭代次數do14

15

end

16

for17

18

19

end

20

21end

算法設計

算法設計為更符合云的物理運動過程，對PBF框架進行若干修改，設計帶旋轉的基于PBF的云建模方法。算法2：帶旋轉的基于PBF的云建模算法1for2

3

4end5for6

7end

8while迭代次數＜最少迭代次數do9

for10

11

end

12

for13

14

執行碰撞檢測和響應15

end

16

for17

18

end

19end20for21

22

應用渦旋約束和XSPH粘性23

24end

與PBF算法相比，帶旋轉的基于PBF的云建模算法在第2行中使用的外力包括重力和科里奧利力；同時將PBF算法中碰撞檢測和響應過程放到求解不變形約束的約束求解過程中（第12～14行）。此外，為解決未預期的阻尼，還增加了渦旋約束和XSPH粘性。

算法設計具體改進點

算法設計具體改進點

算法設計具體改進點拉伸不穩定性在SPH仿真中常見的一個問題是由于粒子周邊鄰居粒子過少導致負壓強，導致粒子聚集的現象，如圖(a)所示。通過增加人工壓力，可保持壓力的非負性，減少粒子的凝聚性，如圖(b)所示。

具體地，在光滑核函數中增加一個人工壓力，如下所示：

算法設計具體改進點

實驗結果云例子屬性構建屬性英文名稱屬性含義位置Position粒子的當前位置半徑Radius粒子的半徑速度Velocity粒子的當前運動速度加速度Acceleration粒子運動的加速度質量Mass粒子的質量質量倒數Inversemass粒子的質量的倒數初始位置Position0粒子的初始位置上一幀位置Oldposition粒子上一幀所在的位置上兩幀位置Lastposition粒子上兩幀所在的位置實驗結果熱帶氣旋模擬結果經過粒子系統初始狀態構建后，從WRF數據集中采樣粒子的位置、速度、密度、壓強等信息，利用帶旋轉的基于PBF的云建模方法即可實現熱帶氣旋的建模。右圖展示了熱帶氣旋的建模結果。數據時間范圍為2010年9月15日0時至2010年9月15日11時30分（共12個小時），空間范圍為東經113.0到120.8度；北緯22.2到25.8度。

3.9習題習題在Unity中構造包括陸地、海洋、植物等的虛擬環境。在Unity中添加人物，并制作動畫。通過Kinect獲取室內場景，并構造室內模型。虛擬現實技術導論第1章概論本講大綱4.1虛擬現實渲染的有關概念面面4.2虛擬現實視覺渲染的主要方法4.3場景組織例——大規模虛擬場景實時碰撞檢測4.4場景繪制優化例——基于LOD的點云繪制4.5習題4.1虛擬現實渲染的有關概念虛擬現實系統邏輯結構渲染幾何建模物理建模行為建模運動建模與虛擬環境的關系和作用虛擬現實：3D+人機交互渲染目的：將虛擬環境輸出，作用于參與者繪制/渲染技術分類從感知通道角度視覺渲染：將幾何模型按照視覺原理進行表現觸/力覺渲染：提供力覺/觸力覺感知信息聽覺渲染：提供逼真的聽覺感受味/嗅渲染：提供味覺/嗅覺感知信息視覺渲染

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

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

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

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

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

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

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

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

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

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

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

算法實現虛擬場景數據組織

算法實現虛擬場景數據組織最終虛擬場景的空間結構分為兩個層次，整個虛擬場景的索引八叉樹結構，與八叉樹的每個葉節點中的幾何屬性建立的包圍盒層次結構

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

緩存中的數據塊與八叉樹節點的關系

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

緩存的數據管理流程

算法實現虛擬場景數據組織

分離軸原理示意

算法實現虛擬場景數據組織采用OBB層次樹結構組織的物體的碰撞檢測問題，歸根結底可以歸結為OBB層次樹的遍歷問題。設有兩個虛擬對象，