比較常用的地形生成算法有三種：
四叉樹算法,GeoMipmap算法，移動立方體算法
目前市面游戲采用的方案基本都是以這三種算法為基礎實現的，下面依次進行介紹
四叉樹算法
很經典的算法，在沒有GPU的時代就已經出現了，原始算法是純cpu的實現，不過在現在已經可以將其實現為GPU-Driven的形式。
這里主要介紹CPU上的實現，GPU實現將在之后進行單獨的介紹。
四叉樹，顧名思義，就是每個根節點最多有四個孩子的樹，其結構能夠很好的表現平面的分化。
算法簡介：
初始化時為一個根節點
視點靠近時四分
每個節點對應一個網格
分化公式：
距離/節點邊長>CL CL為自己設置的一個值，CL越大，越容易分化
此外，也可以根據屏幕占比進行分化
這里也可以進行一個優化，預處理生成一份陡峭度數據去干預分化，越復雜的地形越易分化，如果地形沒有任何起伏，那么完全不分化也是沒問題的。
下圖展示了動態的分化過程
到這里，基本的思路就已經講完了，但還需要解決一個問題，也就是“裂縫”，見下
如上圖所示，由于不同分化層級網格毗鄰處頂點數不一致，采樣精度不同，就會導致漏面的情況
在經典算法中，是這么解決的：
將網格分為5個部分，其中上下左右四個部分會根據鄰居節點的分化程度去控制網格的生成方式，如下所以，如果鄰居的分化程度較低，則會去掉一些頂點，使邊界頂點正好對齊來保證采樣精度一致。
此外，也要保證相鄰節點的lod層級最多相差1，在根據公式分化后還要依次檢測每個節點的鄰居是否存在分化程度比自身高兩個層級的節點，是的話要強制分化該節點。
這個算法其實不是很好，目前也沒看到哪個游戲采用這種方式。
解決裂縫的方式還有很多，下面主要介紹三種
1.強制對齊
2.向下生成一圈外圍網格
3.邊界處按最密進行分化
最后效果如下
至此，四叉樹算法就介紹完了，之后的實現也是采用的此算法。
此外，unity也是采用的此算法，但老版unity沒有采用GPUInstance，導致dc奇多，新版本雖然進行了優化，但由于unity本身不開源，無法進行定制開發，所以還是不推薦。
下面兩種算法我沒有進行具體的實現，所以只是簡介。
GeoMipmap算法
此算法是虛幻4采用的算法
大致思路為：
將地圖分為固定數量的mesh，每個mesh根據lod生成不同精度的網格
見下圖，lod為0時生成完整網格，lod為1時會把黑色的頂點去掉，用剩余的白色頂點去生成網格，這個過程是完全在GPU進行的。
移動端的話基本就采用的上面的兩種方式。
下面對比一下兩種方式：
四叉樹算法的網格近多遠少，且能通過GpuInstance進行優化，dc大概在10左右，面數在6w左右。當距離較遠時，極端情況只有一個mesh。由于地形一般包含多種植被，如沼澤，沙漠，森林，且移動端由于性能限制最多也只能采樣3次，所以1個mesh時會不能很好的表現整個地形面貌。但可以通過烘培一個低模，遠處用低模，近處用四叉樹的方式優化。
Geomipmap網格固定，dc固定，大概在40-60左右，頂點數在2w左右。距離較遠時，Mesh數量固定，紋理采樣不受影響。但為了減dc，一般也會烘培一個低模。
最后總結一下，unity建議自己寫四叉樹，虛幻直接用自帶的geomipmap
移動立方體算法
上面的兩種算法都存在一個缺陷，由于是基于二維高度圖，所以不能表現洞穴，地洞地形。
而移動立方體算法則解決了這個問題。無人深空中即采用了此算法。
該算法將場景看成由無限多個立方體組成。
當立方體足夠小時，可以近似將穿過該立方體的面看做標準曲面
曲面方程表示為：
F(x，y，z)=a0+a1x+a2y+a3Z+a4xy+a5yz+a6xz+a7xyz
立方體存在8個頂點，每個頂點都有一個狀態，空氣中，土壤中
由0和1表示。8個頂點可以存在一個int中，如：00011001
如果為邊界，則表示需要生成網格
一共有2的8次方，即256種情況
除去對稱的情況，歸納為15種，這里歸為15種只是為了好分析，實際編碼時仍需256種情況單獨考慮。針對每種情況，將網格生成方式存在一個查找表中。
這種算法存在一個二義性問題，如圖所示，假設黑點為在土地中，則下面兩種生成方式均可滿足。
這里假設某一面所在的平面方程為z=z0，
代入式F(x，y，z)=a0+a1x+a2y+a3Z+a4xy+a5yz+a6xz+a7xyz可以得到：
b0+b1x+b2y+b3xy=C0
兩邊除xy即可得到一個雙曲線方程
求出該雙曲線兩條漸近線的交點，根據正負即可決定最終該如何生成。
看起來很簡單，但落實到實現還有巨多坑。
其實現在看來，這個算法生成的地形其實就相當于方塊變小無數倍的“我的世界”，生成的方塊數是奇多的，在無人深空中，基本常態就是百萬量級的頂點，所以在移動端自然就被Pass了。
)
