策略游戏地图制作(三)-地块LOD

1.LOD技术概述

LOD（Level Of Detail）是游戏制作中的重要技术，它的思想很简单，即根据模型在屏幕的占比或直接根据摄像机到模型的距离决定该模型应该采用的精度级别，离的远采用更低精度，以降低渲染成本。

       

图：不同LOD级别的模型

通常来讲我们可以预制不同LOD的Mesh，程序启动时载入内存，然后去做动态切换。像UE可以对导入的模型自动生成不同LOD级别模型，这样做的代价是存储了更多模型Mesh，所以LOD也算一种空间换时间的做法。

LOD不仅仅体现在渲染优化上，它更应该理解为一种思想。LOD在其他领域中也有应用，比如引擎的物理碰撞、动画更新、AI等都可以使用LOD的思想进行优化，许多游戏在做gameplay时也会考虑应用LOD

1.1.LOD 选取

LOD选取即确定一个模型应该采用的LOD级别，在Unity的LOD Group组件中，提供距离过渡和占屏幕比例的过渡方式，这是比较常用的方法

       

图：Unity的LOD Group（虽然它更像是个玩具）

一些游戏会采用更复杂的LOD方案，比如采用四叉树，采用四叉树可以达到更精细的划分效果。

       

图：四叉树中不同层级的地块

网上有许多四叉树方案的具体实现，例如：
http://www.cppblog.com/liangairan/articles/48705.html
https://www.cnblogs.com/rainbow70626/p/5268770.html

1.2.LOD 过渡

LOD过渡是处理不同LOD级别之间的过程，由于不同的LOD级别存在精度差别，会出现裂缝，要修补这类问题，通常有以下的解决方法：

（1）.直接设置顶点位置；很简单粗暴的解决方案，但很多时候却意外地有效，尤其是在修补因Mesh而产生的接缝上，原理图如下。这种修复方式依然会在不同LOD层级之间留下可见的界限

       

图：直接设置顶点位置来修补接缝

（2）.采用特殊的过渡地带；如用精细的三角型组成条带，但这样做也在每个层级间都留下明显的分界线。

       

图：采用特殊的过渡地带修补接缝

（3）.无缝过渡；采用一些网格变形算法可以实现不同LOD级别之间的无缝过渡，例如CDLOD，其实现链接：
https://github.com/fstrugar/CDLOD

       

图：CDLOD的演示视频（太糊了）

1.3.其他LOD相关技术

除了上面举例的一些方案外，也有许多被广泛应用的LOD方案，以下举例

（1）.HLOD；HLOD在UE中有内置的支持，它适用于一些3A大世界游戏，基本思想是用一个网格代替多个网格，当距离足够远的时候合并静态网格，可以减少渲染的drawcall，还能节省内存
HLOD的介绍：
https://docs.google.com/document/d/1OPYDNpwGFpkBorZ3GCpL9Z4ck-6qRRD1tzelUQ0UvFc/edit
UE的HLOD实现：
https://dev.epicgames.com/documentation/en-us/unreal-engine/hierarchical-level-of-detail-in-unreal-engine

（2）.Nanite；其实Nanite也算一个LOD方案，它以一个网格上的Cluster（簇）为单位进行LOD切换，所以切换时玩家不会感觉到明显的突兀。如何划分Cluster、如何修补Cluster之间接缝都是非常有意思的问题。
UE官方的视频：
https://www.youtube.com/watch?v=TMorJX3Nj6U&t=7978s
感兴趣的也可以看看这个视频对Nanite的解读：
https://www.bilibili.com/video/BV1VV4y157Zb/

       

图：Nanite划分簇

2.在策略游戏地图中应用LOD

通常我们在评价地形系统的效果时，都会考虑到渲染性能，渲染性能主要体现在网格顶点的数量上，这是最基本的。除此之外，纹理处理、地表植被处理等也很重要，不过这是后话。

在上一节中，我们为地形做了Cluster-Tile两个层级的划分，这种以Chunk形式组织地图数据的思想在大地图游戏中是非常常用的。以Tile作为LOD的切换单位，采用ChunkLOD的思想去实际应用LOD，具体思路如下：

1.以TerrainTile作为LOD切换的基本单位；
2.LOD的切换时机根据摄像机到地块的距离决定，因为是线性的，不会出现跨LOD级别的地块连在一起的情况；
3.LOD的过渡地带采用直接设置顶点位置的方式，无他，因为操作简单。采用特殊的过渡地带或者无缝过渡暂不考虑；
4.不同LOD的Mesh建议静态生成，程序启动时加载进入内存进行切换（当然如果Mesh数据过大，不想做持久化，也可以动态生成）

有以上思路后，可以确定做LOD的基本步骤：
1.为TerrainTile类添加生成不同LOD级别的方法
2.增加UpdateTerrain方法，用于动态地根据摄像机距离决定每个Tile应采取的LOD级别
3.在Update或者其他Tick方法中调用UpdateTerrain，
4.因为LOD级别随时可能改变，LOD接缝处理放到UpdateTerrain中

2.1.构建不同LOD Mesh

在Tile中需要为每个Tile构建不同LOD级别的Mesh，对于每个更低级的LOD级别，顶点数目设置成一半即可，例如我们有4级LOD分级，Tile的尺寸为256，那么LOD0：256顶点每行，LOD1：128每行，LOD2：64每行，LOD3：32每行

       

图：生成不同LOD层级网格

在TerrainCluster构建Tile时添加：

int[] lodLevels = new int[LODLevel];
for (int i = 0; i < LODLevel; i++) {
    lodLevels[i] = i;
}
// generate mesh data for every LOD level
int curLODLevel = LODLevel - 1;
while (curLODLevel >= 0) {
    // when num fix == 1, the vert num per line is equal to tileSize
    int vertexNumFix = (int)Mathf.Pow(2, (LODLevel - curLODLevel - 1));
    if (vertexNumFix > tileSize) {
        // wrong
        break;
    }
    for (int i = 0; i < tileNumPerLine; i++) {
        for (int j = 0; j < tileNumPerLine; j++) {
            terrainTileList[i, j].SetMeshData(curLODLevel, tileSize, vertexNumFix, terrainClusterSize, heightDataManager);
        }
    }
    curLODLevel--;
}

在TerrainTile构建Mesh时添加如下代码。原理很简单，每次生成较低精度的LOD级别时，省略一半的顶点，

public void SetMeshData(int curLODLevel, int tileSize, int vertexNumFix, Vector3Int terrainClusterSize, HeightDataManager heightDataManager) {
    this.tileSize = tileSize;
    this.heightDataManager = heightDataManager;
    // caculate tile's start point
    float startX = tileIdxX * tileSize;
    float startZ = tileIdxY * tileSize;
    Vector3 startPoint = new Vector3(startX, 0, startZ) + this.clusterStartPoint;       // 
    tileCenterPos = startPoint + new Vector3(tileSize / 2, 0, tileSize / 2);
    int gridNumPerLine = tileSize / vertexNumFix;
    int gridSize = tileSize / gridNumPerLine;
    int vertexPerLine = tileSize / vertexNumFix + 1;
    int gridNumPerLineFixed = gridNumPerLine + 2;
    int vertexPerLineFixed = vertexPerLine + 2;
    LODMeshes[curLODLevel] = new MeshData();
    MeshData meshData = LODMeshes[curLODLevel];
    meshData.InitMeshData(gridNumPerLine, gridNumPerLineFixed, vertexPerLine, vertexPerLineFixed);
    int curInVertIdx = 0;
    int curOutVertIdx = -1;
    //int[,] vertexIndiceMap = new int[vertexPerLineFixed, vertexPerLineFixed];
    // TODO: use job system
    Vector3 offsetInMeshVert = new Vector3(gridSize, 0, gridSize);
    for(int i = 0; i < vertexPerLineFixed; i++) {
        for (int j = 0; j < vertexPerLineFixed; j++) {
            bool isVertOutOfMesh = (i == 0) || (i == vertexPerLineFixed - 1) || (j == 0) || (j == vertexPerLineFixed - 1);
            Vector3 vert = new Vector3(gridSize * i, 0, gridSize * j) + startPoint - offsetInMeshVert;
            //float height = SampleFromHeightData(terrainClusterSize, vert);
            float height = heightDataManager.SampleFromHeightData(longitude, latitude, vert, clusterStartPoint);
            //float height = 0;
            vert.y = height;
            Vector2 uv = new Vector2(vert.x / terrainClusterSize.x, vert.z / terrainClusterSize.z);
            if (isVertOutOfMesh) {
                meshData.AddVertex(vert, uv, curOutVertIdx);
                meshData.SetIndiceInMap(i, j, curOutVertIdx);
                //vertexIndiceMap[i, j] = curOutVertIdx;
                curOutVertIdx --;
            } else {
                meshData.AddVertex(vert, uv, curInVertIdx);
                meshData.SetIndiceInMap(i, j, curInVertIdx);
                //vertexIndiceMap[i, j] = curInVertIdx;
                curInVertIdx ++;
            }
        }
    }
    int curGridIdx = 0;
    for (int i = 0; i < gridNumPerLineFixed; i++) {
        for (int j = 0; j < gridNumPerLineFixed; j++) {
            // i, j 是当前遍历到的 grid 的 index
            int cur_w = curGridIdx % gridNumPerLineFixed;
            int cur_h = curGridIdx / gridNumPerLineFixed;
            int next_w = cur_w + 1;
            int next_h = cur_h + 1;
            int a = meshData.GetIndiceInMap(cur_w, cur_h);
            int b = meshData.GetIndiceInMap(cur_w, next_h);
            int c = meshData.GetIndiceInMap(next_w, next_h);
            int d = meshData.GetIndiceInMap(next_w, cur_h);
            meshData.AddTriangle(a, b, c, i, j);
            meshData.AddTriangle(a, c, d, i, j);
            curGridIdx++;
        }
    }
    meshData.RecaculateNormal();
}

2.2.UpdateTerrain

UpdateTerrain处主要是为了在程序运行时做LOD的更新，以下是关键代码。下方代码中的一些部分留到后面讲解，并到后面修接缝时给出一些方法的代码。

public void UpdateTerrain() {
    // NOTE : 当前直接使用主摄像机位置判断是否要加载此块
    Vector3 cameraPos = Camera.main.transform.position;
    foreach (var cluster in clusterList) {
        if (cluster.IsValid) {
            int x = cluster.idxX;
            int y = cluster.idxY;
            int leftIdx = x - 1;
            int rightIdx = x + 1;
            int upIdx = y + 1;
            int downIdx = y - 1;
            int[,] direction = new int[4, 2]{
                {leftIdx, y},{rightIdx, y}, {x, upIdx}, {x, downIdx}
            };
            //  find neighbours, the sequence is : left, right, up, down;
            List<TerrainCluster> terrainClusters = new List<TerrainCluster>(4) { null, null, null, null};
            for(int i = 0; i < 4; i++) {
                int neighborX = direction[i, 0];
                int neighborY = direction[i, 1];
                if (clusterList.IsValidIndex(neighborX, neighborY) && clusterList[neighborX, neighborY].IsValid) {
                    terrainClusters[i] = clusterList[neighborX, neighborY];
                }
            }
            TDList<int> fullLodLevelMap = clusterList[x, y].GetFullLODLevelMap(cameraPos, 
                terrainClusters[0], terrainClusters[1], terrainClusters[2], terrainClusters[3]);
            cluster.UpdateTerrainCluster(fullLodLevelMap);
        }
    }
    Debug.Log(string.Format("update terrain cluster num {0}", clusterList.GetLength(0) * clusterList.GetLength(0)));
}

更新时机可以自己确定，建议用摄像机移动事件触发更新，每当摄像机移动到不同地块时触发更新，以降低检测代价。这里的UpdateTerrain直接放到了编辑器用按钮来执行，运行时的机制暂时未写，放到后面做。

2.3.获得全局LODMap

之前提到过，要在UpdateTerrain中去处理LOD接缝，因为每个地块的LOD接缝都是动态改变的，我们需要实时地知道每个Tile当前的LOD级别，所以需要在确定LOD后，再进行接缝修补。为此我们只需要一个二维数组，记录每个Index下的Tile的LOD即可完成

同样地因为在TerrainCluster中我们只知道这个Cluster下属的Tile的LOD级别，而不知道其他cluster下的Tile的LOD，这就会导致不同Cluster衔接的Tile之间出现接缝，如下图所示：

       

图：不同Cluster之间的接缝(图右)

为此我们需要获得全局的LODMap然后传入到Cluster中进行更新。在上方的代码中，我们获取了fullLodLevelMap，即：

TDList<int> fullLodLevelMap = clusterList[x, y].GetFullLODLevelMap(cameraPos, terrainClusters[0],  terrainClusters[1],  terrainClusters[2],  terrainClusters[3]);

这个方法会返回本Cluster下的所有Tile的LOD级别，并会多包含Cluster相邻的其他Cluster下的Tile的LOD级别。具体逻辑很简单，获取到相邻的四个TerrainCluster即可，代码如下：

internal TDList<int> GetFullLODLevelMap(Vector3 cameraPos, TerrainCluster left, TerrainCluster right, TerrainCluster up, TerrainCluster down) {
    int tileWidth = terrainTileList.GetLength(1);
    int tileHeight = terrainTileList.GetLength(0);
    TDList<int> lodLevelMap = GetLODLevelMap(cameraPos);
    TDList<int> fullLodLevelMap = new TDList<int>(tileWidth + 2, tileHeight + 2);
    // copy cluster's lodlevelmap to fulllodlevelmap
    for(int i = 1; i < tileWidth + 1; i++) {
        for(int j = 1; j < tileHeight + 1; j++) {
            fullLodLevelMap[i, j] = lodLevelMap[i - 1, j - 1];
        }
    }
    // copy egde's lodlevelmap to fulllodlevelmap. careful for the sequence
    List<int> leftLODLevel = new List<int>() { -1, -1, -1, -1};
    if (left != null) {
        leftLODLevel = left.GetEdgeLODLevel(cameraPos, GetEdgeDir.Right);
    }
    for(int i = 0; i < tileHeight; i ++) {
        fullLodLevelMap[0, i + 1] = leftLODLevel[i];
    }
    List<int> rightLODLevel = new List<int>() { -1, -1, -1, -1 };
    if (right != null) {
        rightLODLevel = right.GetEdgeLODLevel(cameraPos, GetEdgeDir.Left);
    }
    for (int i = 0; i < tileHeight; i++) {
        fullLodLevelMap[tileHeight + 1, i + 1] = rightLODLevel[i];
    }
    List<int> upLODLevel = new List<int>() { -1, -1, -1, -1 };
    if (up != null) {
        upLODLevel = up.GetEdgeLODLevel(cameraPos, GetEdgeDir.Down);
    }
    for (int i = 0; i < tileWidth; i++) {
        fullLodLevelMap[i + 1, tileWidth + 1] = upLODLevel[i];
    }
    List<int> downLODLevel = new List<int>() { -1, -1, -1, -1 };
    if (down != null) {
        downLODLevel = down.GetEdgeLODLevel(cameraPos, GetEdgeDir.Up);
    }
    for (int i = 0; i < tileWidth; i++) {
        fullLodLevelMap[i + 1, 0] = downLODLevel[i];
    }
    return fullLodLevelMap;
}

2.4.处理LOD接缝

在上面的UpdateTerrain方法中，为了减轻代码量，将部分的更新逻辑放到了Cluster中做，即下方所示：

cluster.UpdateTerrainCluster(fullLodLevelMap);

该方法的逻辑处理中，会多一步判断相邻的Tile的LOD级别是否不同，如果不同就表示要修复对应的边，完整代码如下：

public void UpdateTerrainCluster(TDList<int> fullLodLevelMap) {
    foreach (var tileMeshData in terrainTileList) {
        // use full lod map, so index offset is 1
        int x = tileMeshData.tileIdxX + 1;
        int y = tileMeshData.tileIdxY + 1;
        int lodLevel = fullLodLevelMap[x, y];
        int left = x - 1;
        int right = x + 1;
        int top = y + 1;
        int bottom = y - 1;
        // check if should fix LOD seam
        int fixSeamDirection = 10000;
        int[,] direction = new int[4, 2]{
            {left, y},{right, y}, {x, top}, {x, bottom}
        };
        for (int i = 0; i < 4; i++) {
            int idxX = direction[i, 0];
            int idxY = direction[i, 1];
            if (fullLodLevelMap.IsValidIndex(idxX, idxY) && lodLevel > fullLodLevelMap[idxX, idxY]) {
                fixSeamDirection |= (1 << i);
            }
        }
        // 不管LOD层级有没有发生改变，都必须重新刷新mesh，因为要处理LOD接缝
        Mesh mesh = tileMeshData.GetMesh(lodLevel, fixSeamDirection);
        tileMeshData.SetMesh(mesh);
    }
    //Debug.Log(string.Format("update successfully! handle tile num {0}", terrainTileList.GetLength(0)));
}

在Tile的MeshData类中，传入具体的LOD级别和需要修复的边即可完成接缝修复。对于要修复的边，如果相邻的Tile的LOD级别更大（更没那么精细），我们只需要将它的多余的顶点设置为相邻顶点的高度即可，原理图如下所示：

       

图：如果相邻Tile的LOD不同则需要修复

完整代码如下（注：下方的RecaculateBorderNormal作用和RecaculateNormal一样，但仅计算边缘顶点的法线，因为没必要再重新计算Tile内部的顶点法线了）：

public Mesh GetMesh(int tileIdxX, int tileIdxY, int fixDirection) {
    Mesh mesh = new Mesh();
    mesh.name = string.Format("TerrainMesh_LOD{0}_Idx{1}_{2}", curLODLevel, tileIdxX, tileIdxY);
    // fix the lod seam
    fixedVertexs = vertexs;
    fixedOutMeshVertexs = outofMeshVertexs;
    bool fixLeft = ((fixDirection >> 0) & 1) == 1;
    bool fixRight = ((fixDirection >> 1) & 1) == 1;
    bool fixTop = ((fixDirection >> 2) & 1) == 1;
    bool fixBottom = ((fixDirection >> 3) & 1) == 1;
    if (fixLeft) {
        // NOTE : 这块代码和外层 TileMeshData.SetMeshData 存在耦合，很重的耦合
        FixLODEdgeSeam(true, 0, 1);
    }
    if (fixRight) {
        FixLODEdgeSeam(true, vertexPerLineFixed - 1, vertexPerLineFixed - 2);
    }
    if (fixTop) {
        FixLODEdgeSeam(false, vertexPerLineFixed - 1, vertexPerLineFixed - 2);
    }
    if (fixBottom) {
        FixLODEdgeSeam(false, 0, 1);
    }
    //RecaculateNormal();
    RecaculateBorderNormal();
    mesh.vertices = fixedVertexs;
    mesh.normals = normals;
    mesh.triangles = triangles;
    mesh.uv = uvs;
    mesh.colors = colors;
    return mesh;
}

对每个需要修复的边缘，封装如下方法进行操作，该方法会根据传入的参数判断对哪条边进行修复：

private void FixLODEdgeSeam(bool isVertical, int outIdx, int inIdx) {
    for (int i = 2; i < vertexPerLine + 1; i += 2) {
        // traverse the indice map and reset the vertex position to neighbor's average
        int outNgb1Idx, outNgb2Idx, outofMeshIdx;
        int inNgb1Idx, inNgb2Idx, inMeshIdx;
        //Vector3 pointA = (indexA < 0) ? outofMeshVertexs[-indexA - 1] : vertexs[indexA];
        if (isVertical) {
            outNgb1Idx = vertexIndiceMap[outIdx, i - 1];
            outNgb2Idx = vertexIndiceMap[outIdx, i + 1];
            outofMeshIdx = vertexIndiceMap[outIdx, i];
            inNgb1Idx = vertexIndiceMap[inIdx, i - 1];
            inNgb2Idx = vertexIndiceMap[inIdx, i + 1];
            inMeshIdx = vertexIndiceMap[inIdx, i];
        } else {
            outNgb1Idx = vertexIndiceMap[i - 1, outIdx];
            outNgb2Idx = vertexIndiceMap[i + 1, outIdx];
            outofMeshIdx = vertexIndiceMap[i, outIdx];

            inNgb1Idx = vertexIndiceMap[i - 1, inIdx];
            inNgb2Idx = vertexIndiceMap[i + 1, inIdx];
            inMeshIdx = vertexIndiceMap[i, inIdx];
        }
        fixedOutMeshVertexs[-outofMeshIdx - 1] = (fixedOutMeshVertexs[-outNgb1Idx - 1] + fixedOutMeshVertexs[-outNgb2Idx - 1]) / 2;
        fixedVertexs[inMeshIdx] = (fixedVertexs[inNgb1Idx] + fixedVertexs[inNgb2Idx]) / 2;
    }
    
}

执行UpdateTerrain后，最终结果，无缝地形：

           

图：修补接缝后的地形