比較常用的地形生成算法有三種：

四叉樹算法,GeoMipmap算法，移動(dòng)立方體算法

目前市面游戲采用的方案基本都是以這三種算法為基礎(chǔ)實(shí)現(xiàn)的，下面依次進(jìn)行介紹

四叉樹算法

很經(jīng)典的算法，在沒有GPU的時(shí)代就已經(jīng)出現(xiàn)了，原始算法是純cpu的實(shí)現(xiàn)，不過在現(xiàn)在已經(jīng)可以將其實(shí)現(xiàn)為GPU-Driven的形式。

這里主要介紹CPU上的實(shí)現(xiàn)，GPU實(shí)現(xiàn)將在之后進(jìn)行單獨(dú)的介紹。

四叉樹，顧名思義，就是每個(gè)根節(jié)點(diǎn)最多有四個(gè)孩子的樹，其結(jié)構(gòu)能夠很好的表現(xiàn)平面的分化。

算法簡(jiǎn)介：

初始化時(shí)為一個(gè)根節(jié)點(diǎn)

視點(diǎn)靠近時(shí)四分

每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)網(wǎng)格

分化公式：

距離/節(jié)點(diǎn)邊長(zhǎng)>CL CL為自己設(shè)置的一個(gè)值，CL越大，越容易分化

此外，也可以根據(jù)屏幕占比進(jìn)行分化

這里也可以進(jìn)行一個(gè)優(yōu)化，預(yù)處理生成一份陡峭度數(shù)據(jù)去干預(yù)分化，越復(fù)雜的地形越易分化，如果地形沒有任何起伏，那么完全不分化也是沒問題的。

下圖展示了動(dòng)態(tài)的分化過程

到這里，基本的思路就已經(jīng)講完了，但還需要解決一個(gè)問題，也就是“裂縫”，見下

如上圖所示，由于不同分化層級(jí)網(wǎng)格毗鄰處頂點(diǎn)數(shù)不一致，采樣精度不同，就會(huì)導(dǎo)致漏面的情況

在經(jīng)典算法中，是這么解決的：

將網(wǎng)格分為5個(gè)部分，其中上下左右四個(gè)部分會(huì)根據(jù)鄰居節(jié)點(diǎn)的分化程度去控制網(wǎng)格的生成方式，如下所以，如果鄰居的分化程度較低，則會(huì)去掉一些頂點(diǎn)，使邊界頂點(diǎn)正好對(duì)齊來保證采樣精度一致。

此外，也要保證相鄰節(jié)點(diǎn)的lod層級(jí)最多相差1，在根據(jù)公式分化后還要依次檢測(cè)每個(gè)節(jié)點(diǎn)的鄰居是否存在分化程度比自身高兩個(gè)層級(jí)的節(jié)點(diǎn)，是的話要強(qiáng)制分化該節(jié)點(diǎn)。

這個(gè)算法其實(shí)不是很好，目前也沒看到哪個(gè)游戲采用這種方式。

解決裂縫的方式還有很多，下面主要介紹三種

1.強(qiáng)制對(duì)齊

2.向下生成一圈外圍網(wǎng)格

3.邊界處按最密進(jìn)行分化

最后效果如下

至此，四叉樹算法就介紹完了，之后的實(shí)現(xiàn)也是采用的此算法。

此外，unity也是采用的此算法，但老版unity沒有采用GPUInstance，導(dǎo)致dc奇多，新版本雖然進(jìn)行了優(yōu)化，但由于unity本身不開源，無法進(jìn)行定制開發(fā)，所以還是不推薦。

下面兩種算法我沒有進(jìn)行具體的實(shí)現(xiàn)，所以只是簡(jiǎn)介。

GeoMipmap算法

此算法是虛幻4采用的算法

大致思路為：

將地圖分為固定數(shù)量的mesh，每個(gè)mesh根據(jù)lod生成不同精度的網(wǎng)格

見下圖，lod為0時(shí)生成完整網(wǎng)格，lod為1時(shí)會(huì)把黑色的頂點(diǎn)去掉，用剩余的白色頂點(diǎn)去生成網(wǎng)格，這個(gè)過程是完全在GPU進(jìn)行的。

移動(dòng)端的話基本就采用的上面的兩種方式。

下面對(duì)比一下兩種方式：

四叉樹算法的網(wǎng)格近多遠(yuǎn)少，且能通過GpuInstance進(jìn)行優(yōu)化，dc大概在10左右，面數(shù)在6w左右。當(dāng)距離較遠(yuǎn)時(shí)，極端情況只有一個(gè)mesh。由于地形一般包含多種植被，如沼澤，沙漠，森林，且移動(dòng)端由于性能限制最多也只能采樣3次，所以1個(gè)mesh時(shí)會(huì)不能很好的表現(xiàn)整個(gè)地形面貌。但可以通過烘培一個(gè)低模，遠(yuǎn)處用低模，近處用四叉樹的方式優(yōu)化。

Geomipmap網(wǎng)格固定，dc固定，大概在40-60左右，頂點(diǎn)數(shù)在2w左右。距離較遠(yuǎn)時(shí)，Mesh數(shù)量固定，紋理采樣不受影響。但為了減dc，一般也會(huì)烘培一個(gè)低模。

最后總結(jié)一下，unity建議自己寫四叉樹，虛幻直接用自帶的geomipmap

移動(dòng)立方體算法

上面的兩種算法都存在一個(gè)缺陷，由于是基于二維高度圖，所以不能表現(xiàn)洞穴，地洞地形。

而移動(dòng)立方體算法則解決了這個(gè)問題。無人深空中即采用了此算法。

該算法將場(chǎng)景看成由無限多個(gè)立方體組成。

當(dāng)立方體足夠小時(shí)，可以近似將穿過該立方體的面看做標(biāo)準(zhǔn)曲面

曲面方程表示為：

F(x，y，z)=a0+a1x+a2y+a3Z+a4xy+a5yz+a6xz+a7xyz

立方體存在8個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)都有一個(gè)狀態(tài)，空氣中，土壤中

由0和1表示。8個(gè)頂點(diǎn)可以存在一個(gè)int中，如：00011001

如果為邊界，則表示需要生成網(wǎng)格

一共有2的8次方，即256種情況

除去對(duì)稱的情況，歸納為15種，這里歸為15種只是為了好分析，實(shí)際編碼時(shí)仍需256種情況單獨(dú)考慮。針對(duì)每種情況，將網(wǎng)格生成方式存在一個(gè)查找表中。

這種算法存在一個(gè)二義性問題，如圖所示，假設(shè)黑點(diǎn)為在土地中，則下面兩種生成方式均可滿足。

這里假設(shè)某一面所在的平面方程為z=z0，

代入式F(x，y，z)=a0+a1x+a2y+a3Z+a4xy+a5yz+a6xz+a7xyz可以得到：

b0+b1x+b2y+b3xy=C0

兩邊除xy即可得到一個(gè)雙曲線方程

求出該雙曲線兩條漸近線的交點(diǎn)，根據(jù)正負(fù)即可決定最終該如何生成。

看起來很簡(jiǎn)單，但落實(shí)到實(shí)現(xiàn)還有巨多坑。

其實(shí)現(xiàn)在看來，這個(gè)算法生成的地形其實(shí)就相當(dāng)于方塊變小無數(shù)倍的“我的世界”，生成的方塊數(shù)是奇多的，在無人深空中，基本常態(tài)就是百萬量級(jí)的頂點(diǎn)，所以在移動(dòng)端自然就被Pass了。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的曲线的生成算法实现_PCGPlanet1-地形生成算法简介的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。