3D遊戲引擎實用的執行方法
(A Practical Implementation of a 3-D Game Engine)
摘要：
制作一個3-D遊戲引擎並不是一件很簡單的任務，因為現在的遊戲玩家常常要求在遊戲中有著高性能和高質量的輸出。在這篇文章中，我們向大家展示了多種實時渲染的算法如何用來在一個實際的3-D遊戲引擎中提高性能。我們探究了一個通用的3-D遊戲引擎的結構並且討論了在3-D遊戲引擎中的視景圖像的任務。我們將從軟件工程的角度來研究視景圖像，我們將向你展示一種面向對象的和可以方便的通過不同渲染引擎來設計的視景圖像。接下來，我們解釋了在我們的3-D遊戲引擎中用來提高引擎性能的算法。我們在視景圖像和物體幾何層面上對我們的3-D遊戲引擎進行了優化。我們提出的算法在靜態和動態的場景中表現的都是相當的好。最後，我們用多處理器在視景圖像方面用並行處理的方式來建立個3-D遊戲引擎方面作了一下簡單的展望。
一、介紹：
在過去的十年裡面，計算機遊戲行業經歷了巨大的增長的黃金時期。在過去的幾年裡，隨著3-D加速硬件設備的飛快的進步，遊戲制造行業都將焦點集中在用創新的思想來生產交互式的3-D遊戲。3-D遊戲引擎是驅動這些遊戲的核心技術。簡單的來講，一個3-D擎獲得遊戲中的3-D物體的幾何數據並將這些數據展示在顯示設備上，典型的顯示設備就是顯示器。這個過程就是我們通常所知的渲染。3-D物體的幾何數據通常通過一系列的頂點來定義，物體的具體特性（象漫射的顏色，鏡面反射以及發射出的顏色等），紋理圖，紋理匹配以及一些常用的向量。所有的這些數據在3-D遊戲引擎處理途徑中經歷不同的階段來決定著這些3-D物體的最終顯示的效果。
圖1 一個完整的3-D引擎的處理過程。高層的視景圖像給用戶一種直覺的方式來模擬一個場景，優化的場景保證了場景對于渲染的高效率。
高層視景圖像規定了在遊戲中的物體之間的關系，它對于遊戲開發者來講也是在遊戲中操縱這些物體的一個應用程序接口（API）。在一個場景被渲染之前，視景圖像必須為了渲染而被優化。這種優化處理就是典型的將高層視景圖像轉變成（編譯成）優化的視景圖像，這種被優化的視景圖像就是用了一種非常適用于渲染的數據結構。這就要求開發者去詳細的確定每個物體的“線索”：比如這個物體是靜止的還是移動的，物體的結構是否隨著時間的變化而變化等等。視景物體剔除就是將觀察者不能看到的物體丟棄掉的處理過程，盡管細節層次控制可以將相對于觀察著者比較遠的一些無關緊要的物體給刪除掉。所有這些思想的背後就是減少渲染那些你看不見的東西以及減少遠端物體幾何數據，為了是將送往最終渲染管線的數據減到最少，這些將會明顯的提高渲染性能。這些就是一個3-D遊戲引擎為了提高它的性能而所要完成的主要任務。
後續的任務，諸如燈光，視角轉換，裁減，投影變換以及光柵化，都是渲染引擎為了完成渲染流程所需要承擔的任務。渲染引擎，就是經常提及的立即模式渲染引擎，往往都可以被3-D加速硬件支持。兩種主要的適用于PC機的渲染引擎就是微軟的Direct3D和Silicon Graphics 公司的OpenGL。在這種渲染引擎上開發遊戲往往是枯燥和耗費時間的，這些引擎所給的程序接口都是些程序性的和面向硬件的。在接下來的部分，我們將在集中在建立3-D遊戲引擎的三個主要的模塊：（1）為我們的3-D引擎建立高層場景圖像；（2）為了建立優化的場景圖像的算法；（3）如何丟棄不在觀察者視野範圍內的物體，並且適當的控制細節層次控制物體。
2.在3-D引擎中的設計問題
視景圖像設計由于它直接牽扯到整個3-D引擎的性能所以顯得非常重要。它定義了一種讓程序員來模擬視景的方式。一個好的視景圖像設計應該允許程序員將更多的視景（諸如物體和它們的排列）包含在視景中，並且想到用最好的方式來展現它們，並且可以忽略掉渲染管線的復雜的控制。程序員將通過視景圖像的API來設計3-D引擎。
視景圖像設計
在視景圖像設計中的第一個問題就是要考慮物體的表現。就像我們上面提到的一樣，象Direct3D和OpenGl這樣的立即模式的渲染引擎均傾向于擁有自己的面向圖形硬件的渲染程序功能函數。很顯然，這種面向渲染的設計並不適合于完成我們的視景圖像的設計的目標。一個面向對象的視景圖像設計明顯的是一種比較好的程序模式，在這種模式中允許程序員在視景中用對象的概念來設計3-D遊戲。我們將所有的遊戲對象都當作視景中的3-D對象來對待。Strauss和Carey已經介紹了完全面向對象的視景圖像框架。這個框架的基本的思想就是將3-D視景描述為物體的圖像，這種圖像成為節點。有很多種類型的節點並且每一個節點都有不同的相關屬性。比如說，圓柱形狀的節點包含兩個參數：半徑和高度，但是球狀物體僅僅包含一個參數，那就是半徑。有一些特定的節點可以包含屬于它們的子節點的一些參數。例如，在圖2中，描繪了一個汽車的一部分的視景圖像。節點組命名為“Body”，它擁有4個子節點來組成汽車的車身。紋理節點包含了定義汽車車身紋理圖像的參數。這些參數同樣會被命名為“門”的一組節點繼承，這些節點用來組成汽車車身的車門。因此，汽車車門將會擁有和車身一樣的紋理。通過應用這種方式，我們不僅可以增加資源的可重復利用度，而且也是簡單的模擬場景的方式，尤其當我們處理一些視景物體的相對位置時，這種方式顯得更有效。變換節點用來描述在父節點下的對象的位置和方向的變換。這些都是相對于父節點的變換。為了得到這些節點的絕對變換（相對于整個場景的變換），當前的這些節點將和它們的父節點的變換相結合（通過矩陣相乘）起來。這樣就可以很輕鬆和簡單的一個對象相對與父節點的位置和方向了。這種模型就是通常我們所說的等級場景模型並且是骨骼動畫的基礎，這種模型通常用來在遊戲中的動畫的運動部分。
2.2 可移植的視景圖形
為了保證我們的遊戲能滿足盡可能多的玩家的要求，我們必須保證我們的3-D遊戲引擎可以在不同的平台和不同的操作系統上運行。因此可移植性是我們設計視景圖形的另外一個問題。一個視景圖形必須能夠在各種目標平台上運行渲染引擎，而且遊戲的代碼還不能做任何的改動。一個可移植的視景圖形必須設計成為不依賴于特殊的渲染引擎才能運行。D
3.1場景結構優化
為了實現在可見性剔除算法的光敏感輸出，它們不能簡單的重復計算整個場景中的物體並且決定哪一個是可見的。我們應用一種特定的數據結構來將場景中的物體分組，這樣的話，用一個簡單的查詢，算法就可以一下子決定是接受還是丟棄一組物體。我們還可以建議使用分等級的數據結構來根據物體的位置來將場景中的物體歸成幾個區域。通過這種方式，如果一個特定的區域被發現是相對于觀察者來講是不可見的或是隱藏的那麼大部分的物體將不會被渲染。為了得到這些分級的數據結構場景必須要被預處理。假設這個預處理是非常耗費時間的，那麼它必須在初始化階段被完成。
我們應用混合式八叉樹作為空間數據結構來存儲3-D引擎中的物體。我們選擇八叉樹的主要原因是基于我們回顧其他的優化技術，我們優化的場景結構的可適應性可以擴展到不同的算法。八叉樹模型用一個立方體順著三個緯度來一次性的劃分空間物體。在每一個階段，用八個相等的立方體沿著三個軸面上均勻的劃分整個場景（xz,xy和yz面）。圖5證明在2維視角上驗證了這個過程。
圖5 一個二維版本的八叉樹的四方塊的構建。每個面上再遞歸的劃分為四個相等的小的相等的四方塊，直到裡面的物體為空或是一整個物體。
這樣就可以創建一個每個節點都包含有八個字節點的樹。通過劃分每個物體都會和它所嵌套子節點的的相應的立方體相關聯。如果一個物體恰好被一個面所劃分（圖5的c）,那麼這個物體就可以用幾種方法來處理。一種方法就是根據與劃分面的關系來劃分物體，根據物體在他的子節點的所關聯的立方體的空間尺度來關聯部分物體。分裂算法有點復雜並且這種方法同時也會增加場景中物體的數量。另外一種方法就是將原始的物體既可以與它的父節點相關聯也可以與它的裝入的子節點相關聯。當立方體為空時，或是一整個物體都包含在立方體時就停止向下劃分（圖5的d）。當算法結束時，實際的物體都會包含在八叉樹的葉節點內，每個葉節點會包含少于或是等于指定的物體的數量。
3.2物體的可見性剔除
視錐體剔除法是通過執行觀察者視角與裝入最大立方體的一系列物體的交集測試來運行的，如果測試失敗則將這些物體在最初的階段裁減掉，否則進行與最小的立方體進行一次最終的測試。八叉樹不僅可以很好的應用在靜態的場景，同時它也可以方便的應用于動態的場景中。遮擋剔除法算法可以緊接著應用于丟棄掉其他的一大部分不在觀察者視線內的物體，尤其對于場景內物體密度比較大的情況更加有效。張提出了一種比較新穎的應用分級的空間圖形遮擋地圖的遮擋剔除算法。這個算法有兩部分測試組成：一個在Z軸方向上的一維度深度測試和兩維度的空間圖形的交迭測試來共同決定一個物體是否被遮擋住。
對于兩維度的交迭測試，一個遮擋表示就是被渲染一系列潛在的很好的遮光板而構建的，這個遮擋在場景結構完成時就被確定了。張還建議一些大的或比較靠近觀察者的物體當作比較好的遮光板。這些遮光板被渲染成沒有紋理，燈光和開啟Z-buffering的一塊在黑背景下的一塊白顏色的脫離屏幕的圖形緩衝。這些操作允許將一些列小的遮光板拼成一塊大的遮光板。這個被渲染過的圖像就是最高分辨率的遮擋地圖，這個方案是基于分級的遮擋地圖的。這個層級是通過從最高分辨率向下到最小分辨率一層層遞歸取樣形成的，象圖6所示。圖形硬件可以用縮小倍率的過濾的雙線性插補的紋理映射來加速這個過程。
圖6 a 接近建立一個遮擋圖的遮光板
（b）在不同級別的分層次的遮擋圖
交集測試是通過測試物體是否投影在屏幕空間的範圍內，這一點和分層次的遮擋圖形的同尺寸的像素對應于相同尺度的邊框內的尺寸是不一樣的。如果邊框內所有的元素與映射的交集為不透明（全白），那麼這個算法就認為這個物體是被遮擋的。然而，這個算法會遞歸的檢查比它低一層次的不透明的像素。這個算法獨特的一點是比較接近可見性剔除，也就是忽略掉對那些僅通過小洞或是透過遮光物體才能見到的物體的渲染。對于這點，在遮擋映射裡像素並不完全等同于全部透明，而是相對于一個透明的閾值（灰度）。這個值越小那麼這個算法就越接近于剔除，場景內物體會由于被忽略渲染而導致部分可見。張已經得出了一個計算在層次中的不同等級的閾值的公式。這個特征就好像是增加剔除率，當場景不需要物體被看見事可以通過一些遮擋物的一些小的和一些不是特別清醒的圖來代替這個物體。
一維度的Z-depth 是用來檢查一個物體是否在遮擋物體的後面。張提議用深度估計緩衝來將屏幕分成一系列的小的矩形區域。對于每個區域，所有的遮擋物體的視線內的最遠的頂點的z-value被加入緩衝。深度估計緩衝在每一幀禎都需要建立。在渲染是，如果一個物體的所佔的體積的最近的頂點的Z-value要比這個物體所能覆蓋的區域的所存儲的Z-value都大的話，這個物體才會通過深度測試。為了使一個物體被遮擋，這個物體必須同時能通過用分級的遮擋映射的交集測試和用深度估計緩衝的深度測試才行。
3.3動態物體的優化
為了處理八叉樹內的動態物體，最直接的方法就是每次當物體運動是，就在八叉樹內把它刪除掉，接下來通過插入它的新位置。這並不是最佳的處理方法，因為這樣會使我們陷入到頻繁修改八叉樹的結構。舉個例子來說，刪除八叉樹的節點有時會合並剛剛分開的節點，就像圖7所示。另外，它還經常需要一個很長的路徑來尋找物體的相對于根節點的插入的新節點。為了避免因為刪除和建立節點而頻繁更新八叉樹，Sudarsky建議僅更新那些具有最少共同祖先的子樹的物體的新老位置。（圖8）對于一個八叉樹很深的大場景，這種方法會很明顯的減少更新八叉樹的時間，因為LCA要比根節點更加接近葉節點。
為了避免對每個動態物體的每一幀都要更新八叉樹的結構，Sudarsky用了一個懶惰計算技術，即我們在一個物體是絕對需要的之前不計算任何事情。這就需要一個與每個動態物體相關聯的臨時的邊界體（TBV）。這個TBV是一個保證在某些特定時間內能包含一個動態物體的邊界體。這段時間就是指TBV的有效時間，失效其就是這個時間的最後時刻。現在比較流行的TBV的構建方法往往基于一些物體運動和行為的前期知識。舉個例子，sweep曲面可以用作TBV的物體上的邊界；如果最大的速度和加速度已知的話，球形也是可以用的。應用這種技術，動態物體的TBV可以用在上述視錐體剔除法的交集測試中。在下列情況下一個運動的物體可以被認為是個隱藏的或是不可見的：(1)它的TBV是可見的，也就意味著物體本身可能是可見的；(2)它的TBV過期了,意味著這個TBV不再保證包含一個物體了。一個優先隊列用來存儲所有的TBV的過期的數據。為了得到更適宜的性能，我們所關心的有效期必須被關閉。一個適當的算法在大多數環境下都能很好的應對這種情況。如果一個物體在確實被看見之前它的TBV就過期了，也就意味著它的有效期太短並且在下一個TBV中將賦予它更長的有效期。相比之下，如果一個TBV在它過期之前就被看見了，那麼在下一個TBV中將賦予它更短的有效期。
圖8）當動態物體被更新是八叉樹的節點經常被刪掉和建立。
（a）最初有兩個物體的八叉樹
(b)一個動態物體從八叉樹內被刪除
(c)動態物體又被重新插入到新的位置
3.4物體的幾何優化
場景物體的幾何數據可以通過試圖產生代表從不同觀察者的距離的物體的不同層次細節（LOD）進一步的優化。這種情況的背後的原因是我們不需要展現所有的完整的物體的數據因為物體距離我們比較遠並且在圖形上看起來很小。我們只需要展現那些距離觀察者比較近的物體的完整數據，這些物體的精細的數據都可以被展現出來。這樣就可以明顯的減少物體的數據，因為我們只需要發送那些最需要物體到渲染引擎裡去。圖9證明了一個Stanford兔子在LOD控制下在兩個相對于觀察者不同的距離下的顯示情況。
圖9（a）最高細節的原始的兔子模型（35947個頂點，69451個三角形）
（b）相對于觀察者比較遠的距離情況下同樣的減少了LOD的兔子模型
(c)一個擴大（b）的版本，展示給我們一個粗糟的兔子模型（359個頂點，508個三角形）
通過簡化物體的LOD控制是一種為了提高我們3-D引擎性能的必須的技術。LOD兩個比較出名的簡化技術是分數倍採樣和聚類方法。分數被採樣是在分類的基礎上減少頂點、邊或是三角形。那些對于整個顯示貢獻比較少的頂點將被標注為候選頂點。當一個最不重要的頂點被刈除後，剩下的漏洞將被補上。這個過程一直到達到預期的目的後才會結束。在聚類方法中，一組高權重的頂點將被預決定了。靠近這些頂點的週圍的一些頂點將被聚類。只有那些權重高的頂點被送到渲染引擎中去，這些頂點都關聯著網格的形成。這種方法非常快但是這種簡化的方法的質量比較差。
簡化算法的保真度可以通過在簡化過程中瞄準那些小的共面的網格來得以提高。為了得到這些網格，可以用長度，面積，體積，角度等，來測量每個頂點的其他臨近的頂點。當這些共面的頂點被刈除或是被大的三角形代替，多邊形的數量減少了，但是物體的形狀仍和原來物體相差不多。這樣原來的物體將被盡可能多的保留下來。
4.將來3-D遊戲引擎
上面我們討論的所有的算法都是串行的，都是設計運行在一個處理器的計算機上。盡管今天主流的遊戲者都在用這種配置，多處理器的計算機是未來工業的一種趨勢。現在在多處理器上的3-D引擎算法方面作了很多的研究工作。Rohlf and Helman解釋了3-D引擎的不同構件之間如何用不同的並行散發進行優化。他們研究的3-D引擎用多處理技術來劃分多個處理器之間的工作，並且用管道來管理數據。他們同時也證明了處理器如何同步在不同環境下它們之間的操作。
Igehy介紹了一個感興趣的方向將OpenGL程序接口擴展到並行處理上。他的擴展允許多個繪圖設備同時來畫一張圖。最初所包括的同步化是允許並行橫行一個明確的有序的場景。在一個24處理器的系統上應用這個程序接口的運行證明了它的有效性。
5.總結
我們已經介紹了一些主要的方面來執行一個實際的3-D遊戲引擎。這個引擎的設計是輕便的和有效的，因為它允許遊戲程序有效的構建和控制場景對象。我們也強調了很多3-D引擎應用的優化技術。光敏感輸出是我們在3-D引擎中所用算法的必要部分。在場景和物體層面為了將對靜態和動態物體的渲染性能提高到最大優化是必須要做的。最後，簡單討論了一些額外的用來提高並行處理的3-D引擎性能的源碼。
