本文是Hello Games的主程Innes Mckendrick在GDC 2017上關(guān)于No Mans Sky（無(wú)人深空）球形地形實(shí)時(shí)生成與渲染方案的實(shí)施細(xì)節(jié)分享的學(xué)習(xí)總結(jié)，文末給出了原始視頻地址。
首先看下無(wú)人深空的項(xiàng)目背景：
小團(tuán)隊(duì)，最開(kāi)始整個(gè)團(tuán)隊(duì)只有四個(gè)人，其中三個(gè)程序一個(gè)美術(shù)，即使到做這個(gè)演講的時(shí)刻整個(gè)團(tuán)隊(duì)也就20多人，其中10多個(gè)程序，好處就是可以實(shí)現(xiàn)敏捷開(kāi)發(fā)，快速迭代，壞處就是任何決策都必須謹(jǐn)慎
程序驅(qū)動(dòng)，說(shuō)的是程序驅(qū)動(dòng)，但從后面描述來(lái)看，更多是用戶體驗(yàn)驅(qū)動(dòng)，不太過(guò)于看重策劃文檔
放大美術(shù)需求
無(wú)人深空是用自研引擎開(kāi)發(fā)的，引擎用C++寫的，自研引擎的好處就是對(duì)于自定義需求可以得到很好很快的支持，而如果使用商業(yè)引擎的話，可能需要投入更多的人力，這對(duì)小團(tuán)隊(duì)而言是很重的負(fù)擔(dān)，此外在項(xiàng)目啟動(dòng)的13年，UE跟Unity都不具備項(xiàng)目所需要的voxel based地形方案，這也是其中選擇自研引擎的一個(gè)原因。
引擎是具備跨平臺(tái)支持的（PC跟PS），由于內(nèi)容需要涵蓋多個(gè)星球，每個(gè)星球的面積都很大，因此離線存儲(chǔ)與運(yùn)行時(shí)裝載到內(nèi)存中都是不現(xiàn)實(shí)的，因此無(wú)人深空最終選擇的是運(yùn)行時(shí)的world generation而非離線創(chuàng)建，不過(guò)運(yùn)行時(shí)生成就需要面對(duì)傳統(tǒng)游戲中貼圖烘焙地形預(yù)生成等做法所不會(huì)面臨的運(yùn)行時(shí)計(jì)算壓力，而且由于運(yùn)行時(shí)只會(huì)生成較少的局部信息，因此游戲的玩法就只能局限于局部空間，無(wú)法添加需要全局要素支持的玩法邏輯。
整篇文章的結(jié)構(gòu)跟GDC PPT結(jié)構(gòu)保持一致。
1. World Structure
這一節(jié)主要介紹整個(gè)世界的架構(gòu)，包括球體的分布，星球的構(gòu)成，voxel的應(yīng)用等等。
World Structure中首先需要介紹的是星球的實(shí)現(xiàn)，由于無(wú)人深空支持玩家在星球之間通過(guò)飛行器進(jìn)行穿梭，在星球內(nèi)也可以自由飛行，且Hello Games希望玩家在探索的過(guò)程中感受到星空的遼闊與自身的孤寂，因此希望將星球設(shè)計(jì)的比較大，在星球的實(shí)現(xiàn)上，Hello Games做了很多探索，下面我們一起來(lái)看下他們的探索結(jié)果與心得體會(huì)。
1.1 平面映射到球面
第一個(gè)想法是在星球上直接使用平面來(lái)代表球面（當(dāng)半徑較大的時(shí)候，表現(xiàn)是基本一致的），而當(dāng)遠(yuǎn)離星球進(jìn)入太空，則會(huì)將表面彎曲變成一個(gè)球體。
這種映射方案的優(yōu)點(diǎn)在于y軸永遠(yuǎn)朝上（不是背離球心），從而使得simulation跟地形的生成都會(huì)變得簡(jiǎn)單，具體而言，當(dāng)玩家在星球上沿著X或者Z軸行走，在運(yùn)行時(shí)會(huì)不斷的生成新的地形來(lái)填補(bǔ)視野的空缺（這里的一個(gè)問(wèn)題是，生成的內(nèi)容是否會(huì)tiling從而使得玩家沿著某個(gè)方向走上一段之后產(chǎn)生繞著星球走了一圈的感覺(jué)？理論上應(yīng)該需要添加這種處理，不過(guò)視頻中沒(méi)有介紹這部分內(nèi)容）。當(dāng)玩家乘坐飛行器起飛離開(kāi)星球的時(shí)候，就會(huì)通過(guò)shader用地形把球包起來(lái)，為了避免玩家看到極點(diǎn)處的扭曲，這里會(huì)將極點(diǎn)設(shè)置為在遠(yuǎn)離玩家的位置。
這種方案會(huì)導(dǎo)致當(dāng)飛到太空的時(shí)候，會(huì)在極點(diǎn)位置處看到不正常的扭曲（pinching），不過(guò)這個(gè)現(xiàn)象不是很明顯，所以不是太大的問(wèn)題。
比較嚴(yán)重的問(wèn)題是，玩家會(huì)在星球上行走，而持續(xù)的行走會(huì)導(dǎo)致一種叫做"swimming coordinates/texture"的現(xiàn)象，這里沒(méi)有解釋這種現(xiàn)象的具體表現(xiàn)與原因，網(wǎng)上也沒(méi)有找到相關(guān)說(shuō)明，后面有更詳細(xì)的了解再來(lái)補(bǔ)充。
另外，由于是根據(jù)玩家的XZ坐標(biāo)來(lái)生成平面地形的，而這種生成方式得到的最多是兩個(gè)圓柱體的交集，如下圖所示，沒(méi)有辦法完全匹配到球面，因此就會(huì)導(dǎo)致玩家可能會(huì)出現(xiàn)在一些根本不存在的坐標(biāo)上，而這些坐標(biāo)如果想要分享給游戲好友，而由于生成方式是受玩家降落點(diǎn)影響的（簡(jiǎn)單來(lái)說(shuō)就是以降落點(diǎn)為圓柱與，那么就會(huì)出現(xiàn)好友根據(jù)坐標(biāo)跳轉(zhuǎn)并不能跳轉(zhuǎn)到玩家當(dāng)前的位置。
上述效果為兩個(gè)垂直正交的圓柱體相交的效果，通過(guò)CSG.js完成模擬，模擬代碼為：
var a = CSG.cylinder({ radius: 0.5, start: [-0.5, 0, 0], end: [0.5, 0, 0] });
var b = CSG.cylinder({ radius: 0.5, start: [0, -0.5, 0], end: [0, 0.5, 0] });
a.setColor(1, 1, 0);
b.setColor(0, 0.5, 1);
return a.intersect(b);
理論上來(lái)說(shuō)，無(wú)法根據(jù)訪問(wèn)的坐標(biāo)抵達(dá)同樣的位置可以通過(guò)一些方式解決掉，但是這個(gè)方案還有另外一個(gè)問(wèn)題，那就是由于這個(gè)運(yùn)行時(shí)生成過(guò)程是無(wú)限循環(huán)的，那么在坐標(biāo)是通過(guò)float表達(dá)的情況下，就會(huì)出現(xiàn)浮點(diǎn)精度問(wèn)題，而要想解決這個(gè)問(wèn)題，就需要額外的處理機(jī)制對(duì)坐標(biāo)進(jìn)行wrap（重置，類似于tiling），而這個(gè)處理過(guò)程消耗不低，這里說(shuō)到都快比原始的生成算法開(kāi)銷還高了，因此這個(gè)方案只能算是一個(gè)嘗鮮的naive版本。
1.2 Map Transform
Hello Games想到的第二個(gè)方案就是類似于我們?nèi)粘Ｉ钪械氖澜绲貓D投影方式，通過(guò)一定的映射規(guī)則完成2D平面貼圖到球體的映射。他們通過(guò)對(duì)wiki上的各種世界地圖投影方式進(jìn)行實(shí)驗(yàn)，嘗試找到一種distortion最小的投影方式。
不過(guò)在搜尋的過(guò)程中發(fā)現(xiàn)并沒(méi)有一個(gè)十分契合需求的方案，因?yàn)檫@里我們不但需要從2D平面映射到球面，同時(shí)還要從球面映射回2D平面，而其中很多算法在無(wú)法保證兩個(gè)方向的映射實(shí)現(xiàn)都十分高效。
另外有一些算法可以在性能上與效果上都能滿足需要，如上圖左側(cè)的2D平面貼圖映射到右邊的球面貼圖上，但是這種方案存在一定的限制，那就是星球必須要包含一定尺寸的海面，通過(guò)壓縮海面的占比來(lái)實(shí)現(xiàn)效果的融洽，對(duì)于地球來(lái)說(shuō)這種方案是可行的，但是Hello Games希望能夠生成各種類型的星球，其中就包含了大量的不帶海洋的星球，這種方案就不太實(shí)用了。
1.3 球面坐標(biāo)系方案
Hello Games最終決定嘗試使用球面坐標(biāo)系完成模擬，這種方案是最簡(jiǎn)單直觀的，但是會(huì)有很多額外的成本在里面。
一般來(lái)說(shuō)，如果地形的生成使用球面空間坐標(biāo)系，那就需要解決星球上的球面坐標(biāo)如何跟星系的3D坐標(biāo)銜接起來(lái)的問(wèn)題，而這里的做法是直接在星球上使用3D平面坐標(biāo)系。
Hello Games在采用這種方案后導(dǎo)致的一個(gè)直觀問(wèn)題是，up方向不再是（0,1,0）了，而是需要根據(jù)當(dāng)前所在的位置與球心所在的位置計(jì)算得到，而且這個(gè)情況也會(huì)導(dǎo)致物理計(jì)算中的重力永遠(yuǎn)指向球心，因此物理計(jì)算也需要做額外的處理，此外一些面向3D平面空間的第三方庫(kù)將不再可用；不過(guò)這些問(wèn)題都還不算困難，而且up方向的計(jì)算也很簡(jiǎn)單高效。
采用這種方案遇到的第二個(gè)問(wèn)題是毛球問(wèn)題，根據(jù)毛球理論，3D球面上不存在一片連續(xù)的與球面相切的非零向量場(chǎng)（向量長(zhǎng)度非零），也就是說(shuō)在3D球面上的切線向量場(chǎng)中必定有一些位置的切向量長(zhǎng)度為0，而這種情況對(duì)于游戲中的一些計(jì)算比如光照（除了光照還有很多其他你想不到的需要使用切線的場(chǎng)合）來(lái)說(shuō)是十分不利的（因?yàn)楣庹战?jīng)常會(huì)需要使用切線空間來(lái)計(jì)算對(duì)應(yīng)的法線，當(dāng)切線為0就會(huì)導(dǎo)致光照效果異常），切線為0導(dǎo)致的大部分問(wèn)題在一些場(chǎng)合下可以通過(guò)將3個(gè)垂直平面投影到球面上來(lái)解決（triplanar projection，沒(méi)太懂，具體怎么做？是相當(dāng)于將cube上的切線投射過(guò)去嗎？），在另外一些場(chǎng)合下可以將一個(gè)long single plane的法線投射到球面上來(lái)解決，另外，還可以考慮通過(guò)local mapping方案來(lái)解決，比如以玩家抵達(dá)星球的點(diǎn)作為初始點(diǎn)，不斷沿著星球表面創(chuàng)建連續(xù)切線，從而通過(guò)將0值切線放到星球背面來(lái)解決這個(gè)問(wèn)題，雖然切線不再是deterministic（即不再是與落腳點(diǎn)無(wú)關(guān)的絕對(duì)數(shù)值分布），但是可以保證連續(xù)，不過(guò)這種做法對(duì)于新加入項(xiàng)目的同學(xué)來(lái)說(shuō)可能需要一定的理解成本。
另外，采用球面坐標(biāo)系的問(wèn)題還有數(shù)據(jù)（比如voxel數(shù)據(jù)）要如何存儲(chǔ)，這里的做法是，simulation（地形生成）采用球面空間完成，但是當(dāng)需要將數(shù)據(jù)存儲(chǔ)下來(lái)時(shí)，則會(huì)將球面空間映射到3D平面空間，使用cube的方式進(jìn)行存儲(chǔ)（從這個(gè)角度來(lái)說(shuō)，對(duì)于球面地形而言，其使用的高度圖就從原來(lái)的2D貼圖變成了cubemap）。
從上面的對(duì)比圖可以看到，這個(gè)數(shù)據(jù)存儲(chǔ)的映射關(guān)系是從cube出發(fā)的， 也就是說(shuō)對(duì)于cube上細(xì)分的每個(gè)頂點(diǎn)找到球面上對(duì)應(yīng)的映射點(diǎn)，并將結(jié)果取出來(lái)存入對(duì)應(yīng)的位置即可。voxel數(shù)據(jù)怎么存儲(chǔ)呢，看起來(lái)也是使用cube作為發(fā)起方，不過(guò)這樣做在進(jìn)行計(jì)算模擬（按照上下文的說(shuō)法，使用體素進(jìn)行地形生成的過(guò)程是在球形空間中進(jìn)行的，假設(shè)marching cube算法也是在這個(gè)空間中進(jìn)行的，那么其計(jì)算所得結(jié)果與將voxel數(shù)據(jù)映射到cube，之后從cube讀取出來(lái)的結(jié)果是一致的？）的時(shí)候不會(huì)有問(wèn)題嗎？
確實(shí)，這種方式是會(huì)有一些失真，不過(guò)丟失的信息只有voxel的密度以及每個(gè)voxel占據(jù)的的空間大小，只表現(xiàn)為對(duì)應(yīng)位置的數(shù)據(jù)精度有所下降，這個(gè)瑕疵是可以接受的。
說(shuō)到cubemap，一個(gè)經(jīng)常被問(wèn)到的問(wèn)題是，為什么不直接在cubemap上完成地形生成過(guò)程，Hello Games這邊應(yīng)該曾經(jīng)嘗試過(guò)這種方案，不過(guò)在邊界（多面交接處）處遇到了眾多的問(wèn)題，經(jīng)常會(huì)有QA跑過(guò)來(lái)告訴開(kāi)發(fā)團(tuán)隊(duì)哪哪又出問(wèn)題了，太過(guò)揪心且至今沒(méi)能找到一勞永逸的解決方案。
這里需要注意的是，Hello Games說(shuō)的使用sphere進(jìn)行模擬，并不是說(shuō)是在球面（sphere surface）空間進(jìn)行相應(yīng)計(jì)算，實(shí)際上是在以球體表面作為基礎(chǔ)高度的偏移值或者說(shuō)高度圖的方式在進(jìn)行相應(yīng)計(jì)算模擬，而這種偏移方式或者說(shuō)高度圖的方式可以直接轉(zhuǎn)換為cube上的高度圖來(lái)實(shí)現(xiàn)。
上圖算法給出了根據(jù)星球上的相對(duì)坐標(biāo)（相對(duì)于球心的坐標(biāo)，這個(gè)坐標(biāo)是3D平面空間的，而非球面空間的）計(jì)算出cube上的對(duì)應(yīng)位置的具體實(shí)現(xiàn)，可以分成如下幾步：
首先計(jì)算出當(dāng)前位置相對(duì)于球體表面的偏移（可以理解為海拔），這一步只需要計(jì)算相對(duì)坐標(biāo)（也可以看成是球心出發(fā)的向量）的長(zhǎng)度減去星球半徑即可，這個(gè)數(shù)值后面會(huì)用到
計(jì)算這個(gè)位置在球面上的投影點(diǎn)，跟上一步類似，只需要對(duì)相對(duì)坐標(biāo)（向量）的長(zhǎng)度縮放到星球半徑即可
根據(jù)投影點(diǎn)坐標(biāo)，可以計(jì)算出對(duì)應(yīng)位置在cube上對(duì)應(yīng)surface上的法線（這一點(diǎn)有點(diǎn)不解）
根據(jù)對(duì)應(yīng)位置以及法線計(jì)算出與上一步cube上的surface的交點(diǎn)，如下圖中的紅色圓點(diǎn)所示
-
在這個(gè)交點(diǎn)的基礎(chǔ)上加上法線與此前的球體海拔偏移就得到了cube上對(duì)應(yīng)的3D坐標(biāo)點(diǎn)
- 按照這種計(jì)算方式相當(dāng)于將下圖中的球面壓扁至與cube重合，也就是說(shuō)，相當(dāng)于省去了球體與cube之間的space，但實(shí)際上我們完全可以將這一段加上，得到更為正確的顯示效果的，不知道是我的理解存在問(wèn)題，還是出于其他的考慮（如計(jì)算復(fù)雜度以及浮點(diǎn)精度等）
此外，在voxels數(shù)目固定的情況下（也就是分辨率確定的情況下），需要模擬的地形高度越大，其對(duì)應(yīng)的voxel的精度也就越低，且當(dāng)需要模擬的地形高度越大，這種方案模擬的distortion會(huì)變得越來(lái)越明顯，出于這個(gè)考慮，這里選擇使用voxel來(lái)模擬球體上128m厚度的地形效果。
不過(guò)如果只能模擬128m的體素地形的話，就沒(méi)有辦法得到大家想要的高山跟深海效果，Hello Games這里的做法是在地形上添加一個(gè)低頻噪聲，使得基礎(chǔ)地形高度不再是平滑的球面，而是如上圖右側(cè)小圖所示的具有高低起伏的曲面（這個(gè)高低起伏的效果稱之為elevation，上下范圍為600~1000m，足以實(shí)現(xiàn)高山跟深海效果），之后在這個(gè)基礎(chǔ)上再添加128m厚度的voxel層。
上面是添加了elevation data之后的計(jì)算邏輯。
下面來(lái)介紹一下voxel地形方案的細(xì)節(jié)。這里將整個(gè)地形分割成一個(gè)個(gè)的chunk或者說(shuō)region，每個(gè)region對(duì)應(yīng)于32x32x32個(gè)voxels，每個(gè)voxel對(duì)應(yīng)一米的尺度，考慮到voxel在三角化的時(shí)候邊界效果難以表達(dá)（頂點(diǎn)是在8個(gè)voxel中間創(chuàng)建的？所以最外層的voxel通常無(wú)法表達(dá)所有的效果），因此在32的基礎(chǔ)上左右各加一列得到34，此外，為了避免因?yàn)榫葐?wèn)題導(dǎo)致的兩個(gè)region之間的seams，這里還需要再在外面加一層，從而使得兩個(gè)region的三角化結(jié)果能夠完美銜接起來(lái)。
各個(gè)region的處理是獨(dú)立的，每個(gè)region處理完成之后就對(duì)應(yīng)著一片區(qū)域的地形。每個(gè)voxel包含了6個(gè)bytes的數(shù)據(jù)，其中
2個(gè)bytes的density數(shù)據(jù)，每個(gè)byte對(duì)應(yīng)于兩種不同的材質(zhì)（也就是說(shuō)，總共對(duì)應(yīng)了4種材質(zhì)的密度？）的密度，這些材質(zhì)用于表明地形是什么類型的，比如grass/moutain/rock/sand等，這些材質(zhì)除了后面進(jìn)行貼圖采樣得到正確的渲染效果之外，還會(huì)影響到放置到上面的物件類型與放置規(guī)則
Material Type x 2對(duì)應(yīng)的是什么意思，對(duì)應(yīng)著當(dāng)前voxel上的四種材質(zhì)？
2個(gè)bytes用于給出材質(zhì)的濃度（the extent to which something is rock or grass)，這個(gè)數(shù)據(jù)有什么用，用于進(jìn)行材質(zhì)混合？這個(gè)extent跟前面的density的作用有什么區(qū)別？
由于數(shù)據(jù)壓縮非常低效，因此目前這塊的存儲(chǔ)都是沒(méi)有經(jīng)過(guò)壓縮的，后面可能會(huì)考慮優(yōu)化。
前面36x36x36精度的region是近景區(qū)的用法，對(duì)于一些遠(yuǎn)離相機(jī)的區(qū)域，就沒(méi)有辦法使用這么高的精度了，這里就需要考慮LOD數(shù)據(jù)，將8個(gè)高精度的voxel組合成一個(gè)低精度的voxel，這里總共設(shè)定了6級(jí)LOD，且這里為了避免接縫，視線中相鄰位置的不同LOD的Region依然會(huì)共面（共用一個(gè)voxel）。
數(shù)據(jù)存在如上圖所示的八叉樹(shù)中，這種做法的好處就不需要多說(shuō)了，這里需要注意的是，前面說(shuō)過(guò)voxel數(shù)據(jù)是存儲(chǔ)在cube上的，如右邊小圖中的紅色正方形就表示對(duì)應(yīng)的cube，因此各個(gè)voxel是圍繞著cube存放的，也就是說(shuō)紅色方框外面的才對(duì)應(yīng)著真正的voxel數(shù)據(jù)。
即使使用了八叉樹(shù)進(jìn)行數(shù)據(jù)存儲(chǔ)，依然會(huì)有不低的內(nèi)存消耗，對(duì)于一顆大星球而言，即使使用最低的lod voxel也會(huì)超過(guò)內(nèi)存的上限，因此這里還增加了一個(gè)更低的lod voxel。
整個(gè)太陽(yáng)系對(duì)應(yīng)著一棵相同的八叉樹(shù)，在星球間切換的時(shí)候，不會(huì)嘗試創(chuàng)建新的region，而是會(huì)將之前的八叉樹(shù)拿出來(lái)重用。不過(guò)，在玩家乘坐飛船飛向太空的時(shí)候則是另外一套做法，這個(gè)時(shí)候會(huì)創(chuàng)建新的region，不過(guò)由于星球像素占比小，因此消耗的內(nèi)存也很少。這個(gè)時(shí)候，星球基本上就是一個(gè)采樣cubemap的模型了。
2. Generation Pipelines
這一節(jié)會(huì)一步步的介紹如何在運(yùn)行時(shí)完成整個(gè)世界的創(chuàng)建與生成，包括地形如何從無(wú)到有的生成（比如voxel數(shù)據(jù)是如何填充的），并能夠正確的渲染（voxel數(shù)據(jù)如何繪制）與體驗(yàn)，并會(huì)介紹與之相關(guān)的線程邏輯等細(xì)節(jié)。
No Mans Sky的數(shù)據(jù)生成都是在運(yùn)行時(shí)完成的，其中在加載階段會(huì)完成一部分工作，比如一些PCG所需要的貼圖的生成，加載模型對(duì)應(yīng)的vertex數(shù)據(jù)等，之后在體驗(yàn)的時(shí)候再漸進(jìn)式的完成地形創(chuàng)建（星球過(guò)大，不會(huì)一次性完成整個(gè)星球的生成，而是只創(chuàng)建局部數(shù)據(jù)，通過(guò)類似貼圖streaming等策略不斷更新）等剩余工作。
上面是生成管線的主要執(zhí)行步驟：
Generation對(duì)應(yīng)著voxel數(shù)據(jù)的填充，這個(gè)過(guò)程是通過(guò)噪聲函數(shù)實(shí)現(xiàn)的，每次填充是以region作為基本單位（多個(gè)region的生成可并行？）
當(dāng)某個(gè)region的density數(shù)據(jù)已經(jīng)生成完畢之后，就會(huì)進(jìn)入region的三角化，最終得到一個(gè)mesh，這個(gè)階段跟上一個(gè)階段都是在cube sapce完成的。
之后將mesh映射到球面上
在mesh的基礎(chǔ)上完成物理網(wǎng)格的創(chuàng)建
在mesh的基礎(chǔ)上完成navmesh數(shù)據(jù)的生成
在地形的基礎(chǔ)上添加其他物件，比如植被，建筑，動(dòng)物以及其他游戲道具
整個(gè)生成過(guò)程不會(huì)放在主線程進(jìn)行，而是通過(guò)job system來(lái)完成的，引擎中的線程管理比較簡(jiǎn)單，包含一個(gè)主要的update線程跟一個(gè)主要的圖形渲染線程，之后在每幀會(huì)進(jìn)行一次同步，地形的生成由于需要占用較多的資源，為了避免影響到性能，這里會(huì)盡量避免這塊的計(jì)算與上述兩個(gè)線程之間的交互。
地形的生成計(jì)算在PC上是通過(guò)CPU完成，而在PS4上則是通過(guò)CS（Compute Shader）來(lái)完成。
上圖中的黃色字體對(duì)應(yīng)的是需要與主線程進(jìn)行交互的工作，除了這些工作之外的其他生成工作都是在jobs中完成。
由于相機(jī)是被一個(gè)個(gè)的region所環(huán)繞的，因此考慮到性能以及玩家體驗(yàn)，這里需要一套良好的生成策略，如上圖所示，這里根據(jù)到玩家的距離為region分派了對(duì)應(yīng)的優(yōu)先級(jí)，其中數(shù)字越小表明優(yōu)先級(jí)越高（其實(shí)就是越近的region優(yōu)先級(jí)越高）。最開(kāi)始的時(shí)候會(huì)快速創(chuàng)建一些粗精度的lod數(shù)據(jù)，對(duì)應(yīng)的是上圖中的紫色方塊，之后根據(jù)優(yōu)先級(jí)逐個(gè)逐個(gè)完成較高精度的lod的生成，對(duì)應(yīng)的是圖中的黑色方塊，整個(gè)過(guò)程的執(zhí)行速度還算比較快。
另外也可以看到，生成方塊并沒(méi)有環(huán)繞在玩家四周，而是優(yōu)先生成相機(jī)前方的region的數(shù)據(jù)。
噪聲的生成算法這里不會(huì)多說(shuō)，在Sean Murray的GDC 2017演講中會(huì)介紹其中的細(xì)節(jié)，youtube上有對(duì)應(yīng)的視頻，有興趣的同學(xué)可以去搜索來(lái)看看。
No Mans Sky的生成過(guò)程是自頂向下的，每個(gè)階段的輸入都來(lái)自于上一個(gè)階段的輸出，之后又會(huì)輸出更多的東西，直到最終得到自己想要的voxel數(shù)據(jù)。
solar system的輸入是一個(gè)position種子，之后會(huì)輸出solar system的相關(guān)信息，比如某個(gè)星球距離太陽(yáng)多遠(yuǎn)，這個(gè)星球的大氣層或者說(shuō)天空的表現(xiàn)如何
將上一個(gè)階段的輸出加上每個(gè)星球的position種子傳入到星球生成階段，這個(gè)階段會(huì)輸出星球的整體風(fēng)格數(shù)據(jù)，比如是巖石類星球還是懸崖林立類星球或者其他風(fēng)貌的，星球上主要地貌占比等。
最后將上個(gè)階段的數(shù)據(jù)傳給地形生成階段，這個(gè)階段會(huì)輸出voxel數(shù)據(jù)。
上面各個(gè)階段輸出的數(shù)據(jù)都是通過(guò)xml格式進(jìn)行存儲(chǔ)，這樣做的好處是調(diào)試方便，可以隨時(shí)知道哪個(gè)環(huán)節(jié)存在問(wèn)題。
地形生成階段包含了一系列的子階段，比如貼圖生成、voxel生成等，其中各個(gè)子階段之間可能存在交互，因此這里需要為整個(gè)生成過(guò)程添加一些整體約束：
directable對(duì)應(yīng)的是美術(shù)同學(xué)要有足夠的控制空間，需要通過(guò)調(diào)整參數(shù)得到想要的效果，consistent對(duì)應(yīng)的是同樣的參數(shù)要有同樣的輸出
實(shí)時(shí)生成
整個(gè)地形很大，需要在不同的地方有不同的地形效果，避免重復(fù)導(dǎo)致的無(wú)聊感
為了提升玩家的新奇感，這里需要能夠支持真實(shí)世界中的地形以及真實(shí)世界中不存在的一些地形效果
希望整個(gè)系統(tǒng)是模塊化的，能夠自適應(yīng)的，從而可以實(shí)現(xiàn)快速的添加與修正
最后一點(diǎn)是需要保證數(shù)據(jù)是局部的，也就是說(shuō)，每個(gè)region的生成過(guò)程需要是相互獨(dú)立的，但是有需要保證各個(gè)region能夠平滑銜接，這個(gè)比較麻煩，想象一下水體對(duì)地形的侵蝕，如何通過(guò)局部數(shù)據(jù)完成全局的侵蝕效果是一個(gè)很大的挑戰(zhàn)。
為了對(duì)整個(gè)過(guò)程做詳細(xì)說(shuō)明，這里先以2D平面的地形生成過(guò)程為例。
第一個(gè)階段就是在2D平面上劃出一些區(qū)域，比如上面這張圖中就劃分出山脈、平緩區(qū)域（Smooth），河流以及Rocky區(qū)域等四塊。這些數(shù)據(jù)不是使用voxel來(lái)存儲(chǔ)的，而是用來(lái)標(biāo)注對(duì)應(yīng)位置的voxel在mountain/smooth/river/rocky等類型地形上的傾向程度。
雖然這塊的數(shù)據(jù)會(huì)占用較大的空間，但是由于只是臨時(shí)存儲(chǔ)一下，等到切換到3D空間后，這塊的數(shù)據(jù)就會(huì)銷毀，所以不會(huì)有太多的問(wèn)題。
這里的每個(gè)數(shù)據(jù)對(duì)應(yīng)的是一個(gè)voxel colume（指的是從上到下的128個(gè)voxels？），而整個(gè)星球的地形數(shù)據(jù)就類似于heightmap（這里應(yīng)該要使用cubemap）
這是沒(méi)有做任何處理的星球地形，很平整，沒(méi)有任何的起伏，就是一個(gè)球體。
這個(gè)是加上了低頻elevation噪聲后的地形效果圖，球體上有了高低起伏的效果，不過(guò)由于沒(méi)有添加高度圖數(shù)據(jù)，所以是比較平滑的星球。
在上一步的基礎(chǔ)上，添加了高度圖效果（這里的高度圖其實(shí)應(yīng)該不是傳統(tǒng)的高度圖，而是根據(jù)前面生成的地形類型貼圖，添加對(duì)應(yīng)的噪聲得到的效果），這一步還沒(méi)有涉及到對(duì)應(yīng)的地形材質(zhì)的處理過(guò)程，因此整個(gè)地面都是sandy & flat & brown的。
在2D貼圖的基礎(chǔ)上，這里考慮通過(guò)voxel來(lái)生成3D地形，這一步跟前面的2D貼圖一樣，也是需要添加各種噪聲效果，包括simplex、perlin或者其他的比如voronoi或者cellular噪聲等。除了噪聲之外，這里還會(huì)添加一些turbulence效果，目的是為了創(chuàng)建一些類似pinching之類的漂亮效果。
不過(guò)通過(guò)3D噪聲使用voxel來(lái)創(chuàng)建地形會(huì)遇到的一個(gè)問(wèn)題是，最終生成的地形可能會(huì)出現(xiàn)3D空間的blob data（分離的大塊數(shù)據(jù)），這些data會(huì)導(dǎo)致一些異常的效果，比如大塊的浮空島嶼等在現(xiàn)實(shí)中不存在或者不符合物理定律的效果。因此，這里需要通過(guò)一定的方法對(duì)這些異常數(shù)據(jù)fade off處理甚至裁切處理，一種策略是根據(jù)voxel的高度不斷降低其density，從而保證在mountain或者h(yuǎn)ill上隨著高度的增加不會(huì)出現(xiàn)density還增加的異常
雖然最終模擬的效果是在球體上，但是voxel數(shù)據(jù)前面說(shuō)過(guò)是存儲(chǔ)在cube space的，之后在需要的時(shí)候在映射到球面上，從而避免distortion（這里說(shuō)的不是很詳細(xì)）。
在前面的3D地形的基礎(chǔ)上，這里還可以通過(guò)添加或者刪除voxel中的數(shù)據(jù)實(shí)現(xiàn)一些特殊效果，比如這里可以將地形挖空做成洞穴。
完成前面的3D數(shù)據(jù)生成后，我們就得到了一系列的voxel，每個(gè)voxel上包含了density跟material數(shù)據(jù)，不過(guò)voxel要轉(zhuǎn)換成polygons只需要density數(shù)據(jù)就夠了。
voxel轉(zhuǎn)換成polygon最常用的是marching cube算法，不過(guò)這里沒(méi)有使用這個(gè)算法，使用的是其改進(jìn)版的dual contouring算法。之所以沒(méi)有使用marching cube，是因?yàn)楫?dāng)我們有8個(gè)voxels組成的一個(gè)大的voxel，我們想要對(duì)這個(gè)voxel進(jìn)行polygonize的話，最終生成的三角面片只會(huì)lie on在這些小的voxel的edge上面，而這種方式對(duì)于創(chuàng)建corner（比如兩堵墻的銳利夾角）效果就不太方便，會(huì)丟失很多關(guān)鍵信息。
關(guān)于這個(gè)技術(shù)的具體細(xì)節(jié)可以參考上面圖中下方給出的兩個(gè)鏈接。
根據(jù)前面的內(nèi)容，我們最終可以得到上圖中的山脈效果。對(duì)于voxel數(shù)據(jù)，No Man Sky會(huì)在一些情況下使用不同的三角化方案，比如上圖中的cube就是直接采用類似“我的世界”中的三角化方案輸出的，雖然這種方案會(huì)需要消耗較多的頂點(diǎn)的，但是其三角化方案的計(jì)算消耗是很輕的。這種三角化方案對(duì)于一些高密度voxel緊鄰著低密度voxel的情況會(huì)有作用，比如對(duì)于一個(gè)mountain與一塊air（無(wú)任何填充）相鄰的情況，就可以創(chuàng)建一個(gè)flat plane之后在上面添加cube（沒(méi)看出來(lái)這么做的意義是啥，估計(jì)是哪些關(guān)鍵信息沒(méi)有傳達(dá)出來(lái)）。這種做法會(huì)創(chuàng)建較多的頂點(diǎn)，因此只會(huì)在距離相機(jī)較近的區(qū)域采用。
這里對(duì)于水面則是采用第三種三角化方案，flat plain polygonization，這是一種十分廉價(jià)的三角化方案。這里需要注意的是，由于前面的elevation數(shù)據(jù)的存在，如果只是使用voxel數(shù)據(jù)來(lái)填充的話，可能會(huì)導(dǎo)致水面存在凹凸不平的情況（低頻噪聲），這里在三角化的時(shí)候需要根據(jù)星球上的水域分布對(duì)這種情況做處理，使之符合物理規(guī)律。Hello Games也說(shuō)了，這種方式其實(shí)不太合理，后面會(huì)考慮摒棄使用三角化的方式來(lái)生成水面，而是會(huì)考慮通過(guò)在shader中完成水面的生成（implicitly）。
最終生成的地形數(shù)據(jù)除了頂點(diǎn)數(shù)據(jù)之外，還包含上述一些數(shù)據(jù)。
法線有兩套，分別對(duì)應(yīng)smooth normal與face normal，其中前者用于進(jìn)行貼圖采樣，后者用于進(jìn)行光照（還是沒(méi)看出來(lái)，為什么不可以使用同一套？），face normal用于計(jì)算光照會(huì)使得渲染效果看起來(lái)有點(diǎn)粗糙，不過(guò)這種方式卻能使得能夠在surface表面得到一個(gè)連貫的blend效果（？）。
這里還會(huì)為每個(gè)region篩選出兩個(gè)材質(zhì)，前面說(shuō)過(guò)，每個(gè)voxel中都包含兩個(gè)材質(zhì)，在最終的效果中最好的效果是每個(gè)voxel的材質(zhì)效果都能夠兼顧到，但是這種做就會(huì)很低效，這里的做法是從voxel中選出出現(xiàn)頻次最高的兩個(gè)材質(zhì)，雖然其他材質(zhì)的丟失會(huì)使得效果存在一些偏差，但是從整體上來(lái)看也沒(méi)發(fā)現(xiàn)太大問(wèn)題（PCG的還好，如果這是提供給用戶的一個(gè)工具，說(shuō)不定就差評(píng)爆表了）。
在得到上述數(shù)據(jù)之后，就可以嘗試通過(guò)triplanar方法進(jìn)行貼圖采樣了。按照這種采樣方法，在blend zone上可能會(huì)預(yù)計(jì)會(huì)得到較為奇怪丑陋的blend artifacts，但是由于地形的形狀導(dǎo)致這個(gè)blend是均勻分散到整個(gè)星球的，因此雖然有一些瑕疵但是看起來(lái)并不明顯。
前面說(shuō)到的貼圖采樣，實(shí)際上這里地形使用的基礎(chǔ)貼圖是一系列的噪聲貼圖，而真正的輸入是高度圖（也就是小圖中的左上角的圖），而頂點(diǎn)中存儲(chǔ)的材質(zhì)blend value實(shí)際上對(duì)應(yīng)的是不同材質(zhì)的貼圖組成的atlas（這里有點(diǎn)繞），這里會(huì)根據(jù)之前的材質(zhì)數(shù)據(jù)選擇對(duì)應(yīng)的兩種材質(zhì)（小圖中的兩行分別對(duì)應(yīng)兩種不同材質(zhì)的輸入貼圖），之后基于高度數(shù)據(jù)對(duì)兩者進(jìn)行混合。
另外這里需要注意的是，地形的貼圖數(shù)據(jù)有兩套，分別對(duì)應(yīng)著低精度與高精度版本，當(dāng)玩家飛起來(lái)進(jìn)入太空的時(shí)候，會(huì)逐漸從高精度過(guò)渡到低精度，反之則從低精度過(guò)渡到高精度。低精版本會(huì)負(fù)責(zé)覆蓋一塊更大的區(qū)域，而高精版本則是覆蓋一塊較小的區(qū)域，通過(guò)這種方式來(lái)降低消耗，這里只介紹了基本的理念，具體的實(shí)施細(xì)節(jié)，這里沒(méi)有聊到。
地形生成完成之后整個(gè)過(guò)程并不是就全部完成了，還有很多收尾工作要做，比如物件的擺放，物理碰撞以及NavMesh的生成等，實(shí)際上這塊的時(shí)間消耗不比地形的創(chuàng)建時(shí)間消耗要低。
首先第一步要做的就是在地圖上完成物件的擺放，這塊的時(shí)間消耗其實(shí)比較高，因此在PS4中也是通過(guò)compute shader完成，基本算法與地形生成所使用的的噪聲算法十分相似。
上面這張圖是俯視圖，從色塊的整體分布來(lái)看，有經(jīng)驗(yàn)的同學(xué)可以比較容易看出這其實(shí)跟simplex噪聲很像，實(shí)際上這里的物件擺放就是在噪聲的基礎(chǔ)上添加cutoff規(guī)則，也就是說(shuō)將低于某個(gè)值的噪聲直接清零，只保留噪聲數(shù)據(jù)中較高密度的部分。
物件擺放是遵循美術(shù)同學(xué)的布局風(fēng)格進(jìn)行的，比如說(shuō)地形上有一棵樹(shù)，之后在下面添加灌木會(huì)使得效果變得好看，之后再添加一些小石塊還會(huì)繼續(xù)美化效果，按著這種套路繼續(xù)下去就會(huì)使得場(chǎng)景變得越來(lái)越自然美觀，而這里的做法是通過(guò)噪聲來(lái)完成上述過(guò)程。
這里在物件擺放的時(shí)候，為了對(duì)物件擺放的密度進(jìn)行控制，還給出了一種offset grid的方案，將場(chǎng)景劃分成一個(gè)個(gè)的cell，對(duì)每個(gè)cell中的某種物件數(shù)目施加約束，通過(guò)這種方案可以保證同類物件之間的擺放距離。
這里說(shuō)到，物件的擺放也會(huì)考慮地形的lod，在不同的lod上會(huì)擺放不同精度的物件，比如較為粗糙的lod地形上只會(huì)擺放大型的物件（比如樹(shù)木），之后會(huì)添加灌木，以及雜草等更為精細(xì)的物件。
這里給出的是同一個(gè)物件在不同LOD精度的地形上是如何實(shí)現(xiàn)position適配從而保證物件不會(huì)出現(xiàn)懸空或者深陷地底的效果，從圖中描述來(lái)看，就是在地形LOD精度發(fā)生變化時(shí)，根據(jù)高度差做了一個(gè)偏移，只是不知道物件朝向是否會(huì)發(fā)生變化。在地形LOD切換的過(guò)程中，也同時(shí)完成了物件（也就是樹(shù)木）的LOD切換，比如可能會(huì)從imposter切換到真正的模型。
這里還給出了一個(gè)視頻來(lái)介紹最終的實(shí)現(xiàn)效果，從視頻中可以看到位置的變化是逐幀進(jìn)行的，也就是說(shuō)是平滑過(guò)渡的，而非直接跳變的，這樣看起來(lái)也更為精美。
建筑的擺放也借助了類似的生成算法，建筑是需要能夠在太空中看到的物件，因此就需要在玩家進(jìn)入星球之前就應(yīng)該能夠知道任何位置都有哪些建筑，也就是說(shuō)，需要一個(gè)技術(shù)，只需要指定球上的一點(diǎn)，就能夠找到最近的建筑物，因此這里最終使用的是offset grid技術(shù)。
將地形分割成regions，之后就可以找到每個(gè)點(diǎn)相對(duì)于region中心點(diǎn)的偏移，之后就可以根據(jù)這個(gè)偏移生成對(duì)應(yīng)的數(shù)據(jù)。
3. Simulation with Real-time generation
這一節(jié)主要介紹運(yùn)行時(shí)生成的世界是如何完成更新與模擬的，在這個(gè)過(guò)程中，由于世界是實(shí)時(shí)生成的，且當(dāng)前的可視范圍內(nèi)不會(huì)覆蓋全圖，因此會(huì)需要考慮到很多未生成的數(shù)據(jù)的影響，會(huì)需要作一些特別的考慮。
simulation需要解決的首要問(wèn)題是場(chǎng)景中的動(dòng)物的行走路徑，AI行走范圍，行走方式如果沒(méi)有仔細(xì)處理就會(huì)得到很奇怪的表現(xiàn)。
這里為動(dòng)物生成了一系列的path，這些動(dòng)物的行走可以遵循這里路徑。不過(guò)只有當(dāng)玩家十分靠近的時(shí)候才會(huì)進(jìn)行動(dòng)物的創(chuàng)建，不過(guò)動(dòng)物創(chuàng)建完成之后，即使玩家遠(yuǎn)離也不會(huì)立馬銷毀，還會(huì)保留一個(gè)距離。
物件的漸入漸出是通過(guò)dither完成的，通過(guò)傳入shader的[0, 1]范圍的可見(jiàn)度數(shù)值，可以控制物件的消隱程度。這種做法在玩家突然飛入到某個(gè)區(qū)域的時(shí)候會(huì)看到明顯的漸變過(guò)程，但是當(dāng)玩家在星球上平滑飛行的時(shí)候，這個(gè)漸變過(guò)程是不明顯的。
這里為植被添加了隨著距離fade的效果，當(dāng)相機(jī)遠(yuǎn)離的時(shí)候，會(huì)逐步消除較遠(yuǎn)處的植被（比如草），當(dāng)相機(jī)靠近的時(shí)候，則會(huì)不斷創(chuàng)建新的植被。
