正當防衛(wèi)（Just Cause）系列一直以開放大世界為核心要點忘晤，其中最關鍵的一項指標就是draw distance涣脚，也就是視距种呐，其中正當防衛(wèi)2（簡稱JC2）的視距號稱是能達到50 Km盗温，而其整張地圖的大小也只不過32 Km x 32 Km熔酷，相當于一次性將整個地圖都渲染進去了。
當然当娱，實際上視距并不等于將整個場景的內容全部都渲染輸出吃既，通常來說，近景處的細節(jié)會多一些趾访，物件精度也會更高态秧，而遠景處董虱，可能就只剩下一些低模扼鞋，甚至只有地形了。
那么正當防衛(wèi)2是怎么完成這個超遠視距的地形渲染的呢愤诱，我們一起來看一下云头，主要資料來源于文獻[1]，有興趣的同學可以移步原文了解更多細節(jié)淫半。
地形渲染在設計之初就設定了如下幾個目標：
- 內存消耗低
- 性能消耗低
- 畫面品質高
先來看下JC2的一張典型的地形遠景渲染效果與對應的wireframe模式：
注意觀察海岸線附近的網格密度會比附近的地形密度要稍微高一點溃槐。
1. The Concept of Patches
JC2的場景是按照Patch來組織的，Patch尺寸是POT的（比如512 m x 512 m一個Patch）科吭，且其方向是與坐標軸平齊的昏滴。
根據需求的不同猴鲫，整個場景會包含多種不同的Patch，比如Terrain Patch, Vergetation Patch等谣殊。
JC2會將以相機為中心的N x N個同類Patch稱為一個Patch Map拂共，當相機移動時，Patch Map也會發(fā)生相應的修正（Patch的增減）姻几。
為了實現Patch的LOD處理宜狐，JC2還將多個中心位置重疊且Patch數目完全相同的同類Patch Map稱之為一個Patch System（Hierarchical Patch Map），處于這個層級中的相鄰兩個Patch Map在尺寸上正好是兩倍關系蛇捌，不同層級的Patch Map對應于不同精度的場景數據抚恒。
Patch System由一個叫做Patch Manager的class管理，Patch Manager不但會負責Patch Map的更新络拌，同時還會負責Patch的裁剪與內存的管理俭驮。
2. Data Pipeline
首先是地形編輯，在編輯階段盒音，JC2開發(fā)了一個地形編輯器表鳍，JustEdit，在這個編輯器中祥诽，項目組可以創(chuàng)建地圖的地形譬圣，地形使用一張原始的高度圖（raw height map）來實現地形高度邏輯，而地形網格則是使用一張固定分辨率（即單位面積頂點密度固定）的proxy mesh來表示雄坪。
地形創(chuàng)建完成后厘熟，會將之分割成editor patch來進行存儲，在需要的時候只需要勾選就可以完成加載维哈，這種做法使得美術同學可以分別對不同的patch進行編輯而實現協(xié)作绳姨。
地圖編輯制作完成后，則會需要通過一個叫做Terrain Compiler的工具完成從編輯數據到運行時數據的轉換（類似于UE的Cook功能）阔挠，轉換成運行時所需要的Stream Patch飘庄。
3. Streaming
32 km x 32 km的地圖，一次性將所有數據都繪制出來购撼，性能無疑是扛不住的跪削，因此JC2的做法是將地圖分割成一個個的Cell，這個Cell就是Stream Patch迂求，每個Stream Patch的尺寸是512 m x 512 m碾盐，任一時刻都會保證以相機為中心的8 x 8個Stream Patch組成的Patch Map是可見的（在這種加載策略下，地形的加載范圍就是512 x 8 / 2 = 2048 m）揩局。
要做Streaming毫玖，就需要從磁盤中將Stream Patch數據讀取出來，而為了最大化加載效率，就需要降低讀盤時的Seek次數付枫。JC2的做法是分別按照行優(yōu)先順序（x/z）與列優(yōu)先順序將Stream Patch數據保存一遍烹玉，相當于每個Stream Patch都被存儲了兩次，之后根據是需要加載一行Patch（相機往Z方向移動阐滩，假設Z方向表示屏幕的上下方向）還是加載一列Patch來決定是從哪個Stream Patch存儲位置進行加載春霍，這樣只需要Seek一次，之后順序加載一行或者一列Patch即可叶眉。
最終JC2在角色移動上的速度限制為水平方向512m/s址儒，而每個Stream Patch的數據平均尺寸為128kb，之所以是平均衅疙，是因為不同的Stream Patch存儲的數據量是不確定的莲趣，那么如何保證這個平均數值不會超出128kb呢，這就需要在Terrain Compiler階段對整個地圖的數據消耗進行統(tǒng)計饱溢。
每個Stream Patch包含的數據包括三種（每個Stream Patch 512m喧伞，貼圖分辨率為4m/texel，看來應該是每個Stream Patch一套貼圖绩郎，可能Weight Map分辨率較高潘鲫，因此不會出現地表分辨率很低的感覺）：
- Terrain Textures，包括材質與法線貼圖
- Height map以及Material Map肋杖，經過壓縮處理后溉仑，每個sample大概消耗16bits。
- Terrain Mesh數據
下面對這些數據的詳情進行介紹状植。
3.1 The Terrain Textures
JC2的地形渲染方案浊竟，除了高度圖之外，還會用到如下三張貼圖：
- Normal map (A8L8 format) 津畸，這是地形的法線貼圖
- Material indices (ARGB4444 format)振定，地形所使用的材質類型的index
- Material weights (ARGB4444 format)，上面的多個材質索引在當前采樣點中的權重
Material Indices以及Material weights貼圖是PS階段對多個材質貼圖進行采樣與混合時使用的肉拓。
Terrain Texture的采樣密度是按照每個像素覆蓋4m來計算的后频，這種密度無疑是不夠的，尤其是近景處暖途，JC2的做法是使用Texture Tiling加上一定的混合策略來實現高清且pattern不會很明顯的shading效果卑惜。
這里沒有介紹貼圖混合的實施細節(jié)，不過其最終的消耗并不低丧肴，實際上有時候會發(fā)現場景中樹木較多残揉，其性能反而上升胧后，這是因為地形被遮擋住了芋浮。。。
3.2 The Height Map and Material Map
Height Map與Material Map的原始密度跟Terrain Texture一樣纸巷，都是每個像素覆蓋4m镇草，而格式則是Height Map采用16bits，Material Map采用8bits瘤旨，PC上不做任何處理梯啤，直接這樣存儲與使用；而在PS3以及XBox上存哲，則會采用一種類似于DXTC的壓縮格式對4x4個Material Map像素block進行有損壓縮因宇，從每個像素16+8bits壓縮到16bits。
Height Map的壓縮則是將格式更改成3:6的浮點格式祟偷，其中3bits用作浮點的指數（exponent）數據察滑，每個指數數據則會被2x2個sample（組成一個block）所共享，每個sample的尾數（mantissa）則是6bits的修肠。使用浮點格式的好處是贺辰，在一些低頻區(qū)域（即地形高度變化比較平緩的區(qū)域，比如平地）會具有較高的精度嵌施，而游戲場景中絕大部分區(qū)域都符合這種情況饲化，因此十分劃算。將地形高度按照block進行組織的一個好處在于進行raycast的時候可以降低消耗實現性能優(yōu)化吗伤。
當在運行時對height map進行采樣時吃靠，會通過Catmull-Rom Spline插值對Height進行插值處理，之后使用由Material Map中控制的高分辨率Displacement Map來對結果進行調制足淆，從而可以使用較少的位數來獲得較高的畫面品質撩笆。
為了滿足物理計算的需要，在一幀中需要對地形高度數據進行數以千計的采樣缸浦，為了降低消耗夕冲，JC2在PS3/Xbox上設計了一種手工調制過的采樣算法，這個算法通過一個SIMD函數來實現裂逐，大致上是借用PS3/Xbox的VMX指令集的強大功能歹鱼，而數量眾多的permute指令則進一步增強了這個優(yōu)化的作用替劈。不過由于x86架構上并沒有這種指令集绿语，因此無法進行類似的優(yōu)化，這也是為什么在PC上需要一套單獨的數據格式的原因睡陪。
3.3 The Terrain Mesh
Stream Patch是一個覆蓋范圍為512m x 512m的容器掺涛，這個容器中裝了很多東西庭敦，其中Terrain Mesh就是容器中所裝載的數據中的一部分，而Terrain Mesh在JC2的框架下也組成了一套Patch薪缆，這個Patch被稱之為Terrain Patch秧廉，這個Patch包含了對應區(qū)域的頂點/索引buffer數據。
Terrain Patch也是按照Patch System來組合的，即包含了一系列的Patch Map疼电。在JC2中嚼锄，Terrain Patch System包含了總共12級的Patch Map，每個Patch Map都包含了8 x 8個Patch蔽豺，最小的Patch Map覆蓋范圍為64 m x 64 m区丑，而最大的Patch Map則覆蓋了256 Km x 256 Km的范圍，由于Terrain Patch是包含預先生成好的Mesh數據修陡，對于那些超出地圖范圍之外的Patch是不包含Mesh數據的沧侥，對于這些區(qū)域的Patch，則會在運行時自動生成一份Mesh數據以實現各個方向的可視距離的一致魄鸦。
地形網格組織跟上圖效果很像正什，當相機移動時，新的Patch Row/Column會創(chuàng)建并添加到對應的Patch Map中号杏，而對應Patch Map中老的Patch Row/Column則會銷毀婴氮。
4. Compile-Time Mesh Construction
每個Terrain Patch都包含一個表示這個Patch覆蓋區(qū)域地形形狀的Mesh，出于渲染效率與顯示質量考慮盾致，在圖形渲染上主经，這個Mesh的分辨率（單位面積的頂點數）并不是固定的（出于使用簡便與計算性能考慮，在物理計算上庭惜，則是使用固定分辨率的mesh結構）罩驻，而是會隨著地形的變化而變化，比如高度變化比較快的區(qū)域會采用密一點的頂點护赊，高度變化比較平緩的區(qū)域則使用稀疏一點的頂點惠遏。
基于相機位置，在運行時對地形網格進行調整的算法有很多骏啰，比如比較出名的"real-time optimally adapting mesh" (ROAM)算法节吮，但這些算法有幾個缺點：
- 會跟著相機的移動而出現地形的跳變（popping），視覺上不夠自然
- 由于運行時頂點數量更新的原因判耕，會需要每幀都上傳新的地形頂點buffer數據透绩，從而影響渲染效率。
為了解決上述兩個問題壁熄，JC2采樣的是為每個Terrain Patch制作一個不隨時間與相機位置而變化的靜態(tài)Mesh（但是使用Terrain Patch Map本身就會因為Patch之間的密度不同而存在跳變呀帚豪？），而這套方案主要考慮兩個問題：
- 如果兼顧不同地形的復雜度草丧，這個問題JC2是通過在離線的時候對地形數據進行烘焙來解決的
- 如何根據到相機距離的遠近來確定地形網格分辨率狸臣，這個問題則是跟模型LOD一樣，在運行時根據距離的遠近為Terrain Patch選擇不同的LOD來做到的昌执，前面說過烛亦，Terrain Patch System包含了12套Patch Map诈泼，分別對應從近到遠的多級LOD，這些Patch Map都是以相機為中心的此洲，因此可以很容易計算出某個位置的地形對應的是哪級LOD的Terrain Patch Map。
下面看下具體的實施細節(jié)委粉。
4.1 Terrain Complexity
Mesh的表達上呜师，JC2使用了一種叫做二分三角樹（binary triangle trees，簡稱BTT）的結構贾节，這種結構從一個等腰垂直三角形出發(fā)汁汗，通過沿著對角線進行均分來對三角形進行不斷細分，從而實現不同區(qū)域的密度差異栗涂，在這種結構下知牌，一張地圖或者一個Patch，只需要兩棵樹即可完成斤程，下面給出了這個結構的與三角形分割結果的對應關系：
樹上的綠色節(jié)點表示葉子節(jié)點角寸，一個大的三角形通過這些葉子節(jié)點可以實現無重疊的完全分割。右邊的15位二進制編碼是將紅色非葉子節(jié)點以1表示忿墅，綠色葉子節(jié)點以0表示扁藕，之后按照深度優(yōu)先遍歷輸出的。
在Terrain Compiler工具中疚脐，會根據地形的拓撲復雜度來創(chuàng)建對應的BTT亿柑，地形越復雜，對應的BTT深度越高棍弄。此外望薄，除了地形復雜度之外，JC2還增加了一些其他的會對BTT深度產生影響的邏輯呼畸，比如JC2希望在海岸線上的地形密度稍微高一些痕支，以取得較為平滑的海島邊緣，就會通過對海岸線進行檢測蛮原，并據此調整對應的BTT深度采转。
Terrain Compiler的工作機制給出如下，首先從BTT的根節(jié)點出發(fā)瞬痘，對BTT上各個頂點的高度數據與根節(jié)點所代表的三角面片的平均高度之差（絕對值）進行累加（這個算法比較粗淺故慈，實際應用時還可以設計更為合理的復雜度統(tǒng)計算法），當這個累加值（應該是累加值平均值）超過一定閾值時就對三角形進行細分框全，之后對于三角形的子節(jié)點進行同樣的操作察绷，最終劃分完成的三角形就用前面給的深度遍歷二進制碼來表示，這種表示方法十分的緊湊津辩，但是僅僅只用這些數據還無法完全確定網格的形狀（比如朝向）拆撼，實際上每個Patch分成兩個三角形容劳，這是固定的，而劃分的方式也是事先約定好的闸度，因此只要有了這個二進制碼竭贩，就能夠表示整個Patch的X/Z方向的數據了。
這里的一個問題是莺禁，按照這種存儲方法留量，在運行時會需要從二進制碼中將三角形形狀恢復出來，不過這個過程因為消耗比較小哟冬，且只有加載的時候才需要楼熄，所以不會造成不良后果。
在JC1中浩峡，地形的高度數據也是同樣按照這種緊湊結構來存儲的可岂，之后再需要的時候根據planar interpolation來恢復某個triangle的高度圖數據，雖然數據存儲量小了翰灾，但是處理邏輯更為復雜了缕粹，而到了JC2，由于不需要支持PS2以及original Xbox了纸淮，現在有了更高的存儲空間致开，因此不再需要做如此復雜的處理了。
4.2 Terrain Mesh Resolution
在Terrain Compiler處理完成之后萎馅，每個Terrain Patch就對應一個二進制碼双戳，而Terrain Patch Map則包含了12個Terrain Patch，因此需要進行12次重復處理糜芳，輸出了12個代表不同覆蓋范圍與分辨率的Mesh二進制碼飒货，那些覆蓋范圍小于或者等于Stream Patch（512m）的Mesh二進制碼是直接存在Stream Patch中的，會跟隨Stream Patch的加載而加載（根據距離相機的遠近而決定加載哪級Terrain Patch）峭竣，而超出Stream Patch尺寸的Terrain Patch二進制碼則是存儲在全局的Always Loaded結構中塘辅。
這里的一個問題是Always Loaded Terrain Patch跟Stream Patch中的Terrain Patch的重疊區(qū)域是怎么處理的，兩者的銜接又是如何完成的皆撩？這兩個部分分別在下面的第七章跟第五章有介紹扣墩。
5. Geomorphing
經過前面的處理，我們現在有了一套包含12個Terrain Patch Map的Patch System扛吞，但是我們在渲染的時候不能直接將12個都一一繪制出來呻惕，這樣不但效果上會存在問題（重疊、穿插等）滥比，性能上也不是最優(yōu)的亚脆。
簡單來說，這里需要一套融合算法盲泛，用于實現當相機移動時濒持，上一幀所選擇的Patch Map與當前選擇的Patch Map之間的融合過渡键耕，從而避免跳變的發(fā)生。JC2的做法是在PS中對某個blend range之內的地形數據使用alpha blend進行融合（具體做法柑营？）屈雄，但是這種做法的弊端在于當相鄰的Terrain Map具有較大的高度差的話，可能會導致裂縫官套。
為了解決上述問題酒奶，JC2最終采用了一種叫做Geomorphing的做法。簡單來說虏杰，就是在高模版本跟低模版本交界的地方讥蟆，對高模版本的頂點高度進行調整勒虾，使得交界線上兩者的數據完全重合纺阔，如下圖所示：
不過這個做法的一個問題是，可能會在不同LOD Mesh的交界處導致T-junctions修然，但是實踐中并沒有發(fā)現過于嚴重的問題（不是在邊緣上平齊了嗎笛钝，為啥還會有T-junction？同一條邊的左右兩側繪制使用頂點數不一致愕宋，就會出現T-junction玻靡，只是因為這里將高度完全平齊了，因此浮點精度損失導致的T-junction就不會很明顯）中贝。
實際上之前設計的BTT結構囤捻，使得這個Morph過程十分的方便，如下圖所示邻寿，高分辨率版本的Terrain Patch（Child Patch）與低分辨率版本的Terrain Patch（Parent Patch）本身是有共用節(jié)點的蝎土，而Parent Patch與相鄰的低分辨率版本的Terrain Patch是吻合的（從目前的信息來看，除非是整個地圖統(tǒng)一分割绣否，不然還無法做到單個Patch與相鄰Patch在邊緣上的完全吻合）誊涯，在這種情況下，只要Child Patch與Parent Patch在分歧點上的頂點高度保持一致即可蒜撮，也就是下圖中的黃色節(jié)點上暴构，將兩者的高度調整為為一致。
6. Vertex and Index Buffer Generation
生成Terrain Patch的二進制碼之后段磨，在運行時需要根據需要構造還原出原始Mesh的VB&IB取逾，這個過程比較簡單，就是當某個Terrain Patch需要構造時苹支，會向其從屬的Stream Patch查詢這個Terrain Patch的二進制碼數據以及其Parent Patch的二進制碼數據菌赖，Parent Patch的數據是用于實現此前說過的Geomorphing使用，這里需要處理的一個問題是沐序，Parent Patch覆蓋了四個不同的Terrain Patch琉用，需要費點心思來判定當前需要加載的Terrain Patch是對應于Parent的哪個Child堕绩，下面給出實現偽代碼：
7. Partially Overlapping Patches
由于存在多級Terrain Patch Map，而每級Patch Map都是以相機為中心創(chuàng)建的邑时，這就會使得一些Patch可以完全被其Child Patch覆蓋奴紧，而一些Patch則完全沒有對應可見的Child Patch，此外還有一些Patch只有部分區(qū)域被可見Child Patch覆蓋晶丘。
對于完全被Child Patch覆蓋以及完全沒有被Child Patch覆蓋的情況黍氮，處理起來都比較簡單，直接放棄Parent Patch或者Child Patch的繪制即可浅浮，而對于部分覆蓋的Patch處理起來就稍微麻煩一點沫浆，簡單來說就是對于這種情況而言，我們需要對Patch拆成四個部分來繪制滚秩，每個部分根據是否被Child Patch覆蓋來采用不同的繪制方案专执，這個過程是通過對Index Buffer按照四分方式組織（將整個Patch的Index Buffer按照深度優(yōu)先算法進行存儲，之后給出每個子部分的起始索引）來完成的郁油。
8. Conclusion
JC2的地形方案經過驗證在眾多的硬件上都有著不錯的表現本股，這是雪崩工作室多年開發(fā)迭代的結果，這里對上面的工作做一個總結桐腌，地形渲染通常需要處理的數據可以大致分成地形模型與地形著色兩塊拄显，前者對應的是地形mesh的構建，后者對應的則是地形貼圖與材質案站。
地形mesh方面躬审，JC2的地形方案使用的是12級不同不同覆蓋范圍（相鄰兩級覆蓋范圍翻倍）的Terrain Patch Map組成，覆蓋范圍從64 m x 64 m到256 km x 256 km蟆盐，多級Patch Map之間的融合是通過Geomorphing算法實現承边，而被多級Patch Map覆蓋的位置，則會選擇分辨率最高的一級進行繪制舱禽，這個處理過程的核心為Patch按照Index Buffer四分組織炒刁，Parent Patch與Child Patch重合的部分直接使用Child Patch部分，其余部分則使用Parent Patch數據誊稚。通過這種方式可以完成2D Terrain Grid的構建翔始，而地形高度則是通過Height Map完成，雖然沒有詳細介紹里伯，不過推測不同覆蓋范圍的Terrain Patch Map應該是可以共用同一張Height Map的城瞎，這樣在邊緣處才可以完美銜接上。
地形材質與貼圖方面疾瓮，每個地形采樣點（頂點）上可以裝載4套材質（從Material Index Map的格式ARGB4444推測）脖镀，同時使用四個不同的權重來進行混合，Material Map與Weight Map的分辨率都是4m/texel（比如128 x 128的貼圖狼电，覆蓋了512m x 512m的地圖范圍蜒灰？）弦蹂，看起來雖然很低，但是在Tiling的作用下結合不同的Tiling位置使用不同的Weight Map/ Material Map也可以達到不錯的效果强窖。
參考文獻
[1] Sponsored: The World of Just Cause 2 - Using Creative Technology to Build Huge Open Landscapes
