只羊的博客

记录游戏开发历程

策略游戏地图制作-五-地形减面-上

1.地形减面

在我们之前的地形制作中采用平铺方案制作地形Mesh，但Terrain平铺在大部分情况下是很浪费的，例如在平原这种不需要多少顶点表达的区域，或者其他坡度低、斜率低、变化小的地带。加上如果要支持超大规模的地图，还需要做很多优化，所以应当做进一步的减面处理。

下面使用经典的QEM算法对Terrain进行减面操作，写这个的过程也算是在做减面插件，只不过地形的减面需要注意不同地块之间的接缝，避免连接出问题。下面是本节结束后的减面效果演示：

    image    
图：地形Mesh减面前后对比

1.1.已有的地形减面方案

以下列举一些已有的减面工具，以供参考

-Simplygon：多平台多语言支持的工业级减面插件，广泛应用于各种游戏中，有各种丰富的特性效果，功能十分强大。能给30天的免费试用，曾对个人开发者免费，可惜现在收费了
官网：https://www.simplygon.com/

    image    
图：Simplygon插件效果（官网演示）

-UnityMeshSimplify：git上的轻量级开源项目，值得参考学习
源码：https://github.com/ecidevilin/UnityMeshSimplify/tree/master

-AutoLOD：unity官方推出的减面工具
源码：https://github.com/Unity-Technologies/AutoLOD

-UE Nanite的cluster based的方案，非常经典，不必多说
官网文档：https://dev.epicgames.com/documentation/zh-cn/unreal-engine/using-nanite-with-landscapes-in-unreal-engine

1.2.减面算法步骤

QuadricMeshReduction 是UE4使用的一种模型网格简化算法，能在尽量保持原模型拓扑结构的同时减少多边形数量。基本原理是通过计算每个顶点的 Quadric Error Metrics（误差矩阵）来评估顶点的简化程度，以此判断是否简化掉该顶点

该算法主要基于对顶点对的收缩，如图所示，v1，v2是一个vertex pair，消除v1，v2得到新顶点v-，为了确定怎么收缩，需要定义收缩的代价和收缩后新顶点的位置。

    image    
图：顶点对的收缩

算法原论文链接：
Surface simplification using quadric error metrics

收缩代价即误差矩阵（Quadric Error Metric ），它是为目标Mesh中的每个顶点计算的4x4矩阵，记录顶点位置的几何特征以及它和周围面的误差度量，以此我们可以得知简化该顶点后对整体模型的代价。以下是计算步骤：

（1）.定义Δ为一个顶点（即v=[vx, vy, vz, 1]T）到所有相邻面的距离之和

    image

展开后可以得到：

    image

其中Kp是到该顶点相邻平面ax + by + cz + d = 0的距离，可以理解为每个面的误差矩阵Qi，计算公式如下：

    image

（2）.依据上述公式我们可以为每个平面计算它的误差矩阵，得到的和即为每个顶点的误差矩阵：

    image

（3）.对于每个顶点对（v1，v2），它们的误差矩阵为：

    image

（4）.计算新顶点的位置可以采取简单的取平均值办法即v=(v1+v2)/2，但也可以取最优点，通过：

    image

可以确定新顶点，将等式联立展开后可以得到：

    image     image

解方程即可

减面的步骤中，我们需要维护一个最小堆，该最小堆存放所有待简化的顶点对，每次选择具有最小误差代价的顶点对进行合并。

合并操作会把两个顶点变成一个新顶点，并更新相关点的顶点对关系和三角型索引关系（这个过程中最小堆里的顶点对也要重新更新），以及相关面的法线和边界，确保网格合法。

重复上述取出顶点对优化的过程，直到满足预定的简化目标，如减少到指定的顶点数或面数。

最后需要一提，对于地形减面来说，因为对于每个地块的减面操作都是独立的，用以上算法得到的简化模型拼接在一起很容易产生缝隙。对此，我们只需要保持地块的最外层顶点不变即可，实现起来可以传入一个List表示不可修改的顶点索引，在建立顶点对的时候跳过包含边缘顶点的顶点对

    image
图：地块边缘顶点在简化过程中不会修改

1.3.减面算法实现

本节代码可以参考：

WarGameMap/blob/main/Runtime/Controller/Terrain/TerrainSimplifyer.cs

（1）.建立最小堆结构和顶点对结构

在上面的算法步骤中，我们可以确定最小堆是需要定制的，因为每次处理顶点对后会引发其他相关顶点对的更新。除此之外，为方面维护和计算，我们还可以为顶点对建立数据类：

顶点对数据类实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

internal class VectorPair {
    public int v1Idx { get; private set; }
    public int v2Idx { get; private set; }
    public Vector3 v1 { get; private set; }
    public Vector3 v2 { get; private set; }
    public Matrix4x4 Q1 { get; private set; }
    public Matrix4x4 Q2 { get; private set; }
    public float Error { get; private set; } // 存储合并的误差值

    public bool IsValid { get; set; }

    public VectorPair(int idx1, int idx2, Vector3 v1, Vector3 v2, Matrix4x4 q1, Matrix4x4 q2) {
        v1Idx = idx1;
        v2Idx = idx2;
        this.v1 = v1;
        this.v2 = v2;
        Q1 = q1;
        Q2 = q2;
        Error = ComputePairError(); // 计算误差
        IsValid = true;
    }

    public bool ContainsVert(int idx) {
        return idx == v1Idx || idx == v2Idx;
    }

    public void UpdatePair(int oldIdx, int newIdx, Vector3 newV, Matrix4x4 newQ) {
        if (v1Idx == v2Idx) {
            return;
        } else if ((v1Idx == oldIdx && v2Idx == newIdx) || (v2Idx == oldIdx && v1Idx == newIdx) && (oldIdx != newIdx)) {
            return;
        }
        if (oldIdx == v1Idx) {
            v1Idx = newIdx;
            v1 = newV;
            Q1 = newQ;
            Error = ComputePairError();
        } else if(oldIdx == v2Idx) {
            v2Idx = newIdx;
            v2 = newV;
            Q2 = newQ;
            Error = ComputePairError();
        }
    }

    public float ComputePairError() {
        Vector3 vOptimal = GetMergedPosition();
        Vector4 vH = new Vector4(vOptimal.x, vOptimal.y, vOptimal.z, 1);
        Matrix4x4 Q = SimplifyHelper.AddMatrices(Q1, Q2);
        return Vector4.Dot(vH, Q * vH);
    }

    public Vector3 GetMergedPosition_Optimal() {
        Matrix4x4 Q = SimplifyHelper.AddMatrices(Q1, Q2);

        Matrix4x4 A = new Matrix4x4();
        A.SetRow(0, new Vector4(Q.m00, Q.m01, Q.m02, 0));
        A.SetRow(1, new Vector4(Q.m10, Q.m11, Q.m12, 0));
        A.SetRow(2, new Vector4(Q.m20, Q.m21, Q.m22, 0));

        Vector3 b = new Vector3(-Q.m03, -Q.m13, -Q.m23);

        // 求 A 的行列式，判断是否可逆
        float det = A.determinant;
        if (Mathf.Abs(det) > 1e-6f) {
            Matrix4x4 A_inv = A.inverse;
            return A_inv.MultiplyPoint3x4(b);
        } else {
            return (v1 + v2) * 0.5f;
        }
    }

    public override bool Equals(object obj) {
        if (obj is VectorPair other) {
            return (v1Idx == other.v1Idx && v2Idx == other.v2Idx) || (v1Idx == other.v2Idx && v2Idx == other.v1Idx);
        }
        return false;
    }

    public override int GetHashCode() {
        return v1Idx.GetHashCode() ^ v2Idx.GetHashCode();
    }
}

最小堆实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

internal class QEMMinHeap {
        
    List<VectorPair> heap = new List<VectorPair>();
    Dictionary<VectorPair, int> heap_idx_dict = new Dictionary<VectorPair, int>();
    public int Count => heap.Count;
    private int Parent(int i) {
        return (i - 1) / 2;
    }
    private int LeftChild(int i) {
        return 2 * i + 1;
    }
    private int RightChild(int i) {
        return 2 * i + 2;
    }

    public void Insert(VectorPair pair) {
        heap.Add(pair);
        heap_idx_dict.Add(pair, -1);
        HeapifyUp(heap.Count - 1);
    }

    public VectorPair GetTop() {
        if (heap.Count == 0) {
            return null;
        }

        VectorPair min = heap[0];
        heap[0] = heap[heap.Count - 1];

        heap_idx_dict.Remove(min);
        heap_idx_dict[heap[0]] = 0;
        heap.RemoveAt(heap.Count - 1);

        HeapifyDown(0);
        min.IsValid = false;
        return min;
    }

public void UpdatePair(VectorPair pair) {
	// TODO：目前这一步似乎有问题，需要修复
        if (!heap_idx_dict.ContainsKey(pair)) {
            Debug.LogError($"pair 未找到: {pair.v1Idx}, {pair.v2Idx}" );
            return;
        }
        int idx = heap_idx_dict[pair];
        heap[idx] = pair; // ？？？
        HeapifyUp(idx);
        HeapifyDown(idx);
    }

    private void HeapifyUp(int i) {
        while (i > 0 && heap[i].Error < heap[Parent(i)].Error) {
            Swap(i, Parent(i));
            i = Parent(i);
        }
    }

    private void HeapifyDown(int i) {
        int smallest = i;
        int left = LeftChild(i);
        int right = RightChild(i);
        if (left < heap.Count && heap[left].Error < heap[smallest].Error)
            smallest = left;
        if (right < heap.Count && heap[right].Error < heap[smallest].Error)
            smallest = right;
        if (smallest != i) {
            Swap(i, smallest);
            HeapifyDown(smallest);
        }
    }

    private void Swap(int i, int j) {
        heap_idx_dict[heap[i]] = j;
        heap_idx_dict[heap[j]] = i;
        (heap[i], heap[j]) = (heap[j], heap[i]);
    }
    
}

（2）.对传入的Mesh数据进行处理

先不考虑normal和uv的计算，仅考虑传入的vertex和triangle，对于传入的Mesh数据：

1
2
Vector3[] vertexs;
int[] triangles;

建立如下数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
bool[] vertex_valid;								// 顶点是否被去除
Dictionary<int, List<int>> vertex_link_triangle_dict;	// 顶点相关的所有三角型
Dictionary<int, Matrix4x4> vertex_Q_dict;			// 每个顶点对应的Q矩阵
Dictionary<int, List<VectorPair>> vertex_pair_dict;	// 每个顶点以及其相连的顶点对

bool[] triangle_valid;							// 三角形是否被去除
Dictionary<int, List<int>> triangle_contains_vert_dict;// 每个三角型包含的顶点索引
Dictionary<int, Matrix4x4> triangle_Q_dict;			// 每个三角型平面对应的Q矩阵

QEMMinHeap qemMinHeap;
HashSet<int> edgeVertMap;   			// 判断顶点是否是边缘顶点（不可被去除）
HashSet<string> hasAddThisPairMap;     // 判断顶点对是否已经被加入

初始化上述数据的代码，传入Mesh，边缘顶点数据EdgeVertexs，EdgeVertexNormals，要优化到的顶点比例 simplifyTarget，例传入0.6，表示最终要优化到仅剩下60%顶点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

public void InitSimplifyer(Mesh mesh, List<int> edgeVerts, List<Vector3> edgeNormals, float simplifyTarget) {
    meshName = mesh.name;
    vertexs = mesh.vertices;
    triangles = mesh.triangles;

    vertCnt = vertexs.Length;
    targetCnt = (int)(vertexs.Length * simplifyTarget);

    // init vertex's data
    int vertNum = vertexs.Length;
    vertex_valid = new bool[vertNum];
    Array.Fill(vertex_valid, true);

    // init vert links to triangle......
    vertex_link_triangle_dict = new Dictionary<int, List<int>>(vertNum);
    vertex_Q_dict = new Dictionary<int, Matrix4x4>(vertNum);
    vertex_pair_dict = new Dictionary<int, List<VectorPair>>(vertNum);
    for (int i = 0; i < vertNum; i++) {
        vertex_link_triangle_dict[i] = new List<int>();
        vertex_pair_dict[i] = new List<VectorPair>();
    }

    // construct triangle's data
    int triIdxNum = triangles.Length;
    if(triIdxNum % 3 != 0) {
        Debug.Log($"error! not valid triangle num : {triIdxNum}");
        return;
    }
    int triNum = triIdxNum / 3;
    triangle_valid = new bool[triNum];
    Array.Fill(triangle_valid, true);

    // init triangle to vert dict
    triangle_contains_vert_dict = new Dictionary<int, List<int>>(triNum);
    triangle_Q_dict = new Dictionary<int, Matrix4x4>(triNum);

    for ( int triIdx = 0; triIdx < triNum; triIdx++ ) {
        int tri_vert_start = triIdx * 3;
        int v1 = triangles[tri_vert_start];
        int v2 = triangles[tri_vert_start + 1];
        int v3 = triangles[tri_vert_start + 2];

        triangle_contains_vert_dict[triIdx] = new List<int> { v1, v2, v3 };

        vertex_link_triangle_dict[v1].Add(triIdx);
        vertex_link_triangle_dict[v2].Add(triIdx);
        vertex_link_triangle_dict[v3].Add(triIdx);

        // set triangle's Q
        Vector4 triPlane = SimplifyHelper.GetPlaneEquation(vertexs[v1], vertexs[v2], vertexs[v3]);
        triangle_Q_dict[triIdx] = SimplifyHelper.CaculateKpForPlane(triPlane);
    }

    // init vert Idx to Q dict
    for (int i = 0; i < vertNum; i++) {
        List<int> vert_tri_idxs = vertex_link_triangle_dict[i];
        Matrix4x4 res = Matrix4x4.zero;
        foreach (var triIdx in vert_tri_idxs)
        {
            res = SimplifyHelper.AddMatrices(res, triangle_Q_dict[triIdx]);
        }
        vertex_Q_dict[i] = res;
    }

    // set edge vert's message
    edgeVertMap = new HashSet<int>(edgeVerts.Count);
    edgeVert_normals_dict = new Dictionary<int, Vector3>(edgeVerts.Count);
    for(int i = 0; i < edgeVerts.Count; i++) {
        edgeVertMap.Add(edgeVerts[i]);
    }

    // init vert pair, add them to heap;
    qemMinHeap = new QEMMinHeap();
    hasAddThisPairMap = new HashSet<string>();
    for (int triIdx = 0; triIdx < triNum; triIdx++) {
        int tri_vert_start = triIdx * 3;
        int v1 = triangles[tri_vert_start];
        int v2 = triangles[tri_vert_start + 1];
        int v3 = triangles[tri_vert_start + 2];

        bool canDelV1 = !edgeVertMap.Contains(v1);
        bool canDelV2 = !edgeVertMap.Contains(v2);
        bool canDelV3 = !edgeVertMap.Contains(v3);

        if (canDelV1 && canDelV2 &&  !HasAddThisPair(v1, v2)) {
            //建立顶点对，然后加入到最小堆中
            VectorPair vectorPair = new VectorPair(v1, v2, vertexs[v1], vertexs[v2], vertex_Q_dict[v1], vertex_Q_dict[v2]);
            qemMinHeap.Insert(vectorPair);
            vertex_pair_dict[v1].Add(vectorPair);
            vertex_pair_dict[v2].Add(vectorPair);
            SetPairAdded(v1, v2);
        }
        if (canDelV2 && canDelV3 && !HasAddThisPair(v2, v3)) {
            VectorPair vectorPair = new VectorPair(v2, v3, vertexs[v2], vertexs[v3], vertex_Q_dict[v2], vertex_Q_dict[v3]);
            qemMinHeap.Insert(vectorPair);
            vertex_pair_dict[v2].Add(vectorPair);
            vertex_pair_dict[v3].Add(vectorPair);
            SetPairAdded(v2, v3);
        }
        if (canDelV1 && canDelV3 && !HasAddThisPair(v1, v3)) {
            VectorPair vectorPair = new VectorPair(v1, v3, vertexs[v1], vertexs[v3], vertex_Q_dict[v1], vertex_Q_dict[v3]);
            qemMinHeap.Insert(vectorPair);
            vertex_pair_dict[v1].Add(vectorPair);
            vertex_pair_dict[v3].Add(vectorPair);
            SetPairAdded(v1, v3);
        }
    }
}

private bool HasAddThisPair(int v1, int v2) {
    string pair_id1 = string.Format("{0}_{1}", v1, v2);
    string pair_id2 = string.Format("{0}_{1}", v2, v1);
    if (hasAddThisPairMap.Contains(pair_id1) || hasAddThisPairMap.Contains(pair_id2)) {
        return true;
    }
    return false;
}

private void SetPairAdded(int v1, int v2) {
    string pair_id1 = string.Format("{0}_{1}", v1, v2);
    string pair_id2 = string.Format("{0}_{1}", v2, v1);
    hasAddThisPairMap.Add(pair_id1);
    hasAddThisPairMap.Add(pair_id2);
}

（3）.执行减面操作

减面过程上面已经叙述，每次取出Q最小的顶点对然后删除，然后刷新顶点相关的数据。中间的一些步骤很容易踩坑，特别是更新顶点对相关数据时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

public void StartSimplify() {
    int curCnt = vertCnt;
    int iterCnt = 0;    // 防止无限循环
    int maxIter = vertCnt - 1;
    while(curCnt > targetCnt && iterCnt < maxIter) {

        VectorPair pair = qemMinHeap.GetTop();

        Vector3 newV = pair.GetMergedPosition();
        Matrix4x4 newM = SimplifyHelper.AddMatrices(pair.Q1, pair.Q2);
        int idx1 = pair.v1Idx;
        int idx2 = pair.v2Idx;
        
        if (!vertex_valid[idx1]) {
            //Debug.LogError($"vert {idx1} is not valid， 本次 iter cnt ：{iterCnt}");
            continue;
        }
        if (!vertex_valid[idx2]) {
            //Debug.LogError($"vert {idx2} is not valid， 本次 iter cnt ：{iterCnt}");
            continue;
        }

        // keep v1, use v1 to storage new V, erase v2
        vertexs[idx1] = newV;
        vertex_valid[idx2] = false;

        // update all pair that link to idx2, idx1
        int length2 = vertex_pair_dict[idx2].Count;
        for(int i = length2 - 1; i >= 0; i--) {
            var idx2_pair = vertex_pair_dict[idx2][i];
            if (pair.Equals(idx2_pair) || pair == idx2_pair) {
                vertex_pair_dict[idx2].RemoveAt(i);
                continue;
            }

            idx2_pair.UpdatePair(idx2, idx1, newV, newM);
            //qemMinHeap.UpdatePair(idx2_pair);
        }

        int length1 = vertex_pair_dict[idx1].Count;
        for (int i = length1 - 1; i >= 0; i--) {
            var idx1_pair = vertex_pair_dict[idx1][i];
            if (pair.Equals(idx1_pair) || pair == idx1_pair) {
                vertex_pair_dict[idx1].RemoveAt(i);
                continue;
            }

            idx1_pair.UpdatePair(idx1, idx1, newV, newM);
            //qemMinHeap.UpdatePair(idx1_pair);
        }

        // add all v2's vertex pair to v1
        foreach (var idx2_pair in vertex_pair_dict[idx2]) {
            if (idx2_pair.v1Idx != idx1 && idx2_pair.v2Idx != idx1) {
                Debug.LogError($"不应该出现的情况，idx1 没有设置正确 * 2 ：{idx2_pair.v1Idx},{idx2_pair.v2Idx},{idx1},{idx2},iterCnt: {iterCnt}");
                //continue;
            }
            vertex_pair_dict[idx1].Add(idx2_pair);
        }

        // update all triangle that link to idx2, replace them to idx1
        int commonTriCnt = 0;
        foreach (var triIdx in vertex_link_triangle_dict[idx2]) {
            if (!triangle_valid[triIdx]) {
                continue;
            }

            if (IsCommonTriangle(idx1, idx2, triIdx)) {
                triangle_valid[triIdx] = false;
                commonTriCnt++;
            }

            UpdateTriangleVert(idx2, idx1, triIdx);
        }

        // 把 idx2 的所有相邻三角形，移交给 idx1 顶点
        foreach (var triIdx in vertex_link_triangle_dict[idx2]) {
            if (!triangle_valid[triIdx]) {
                continue;
            }

            if (!vertex_link_triangle_dict[idx1].Contains(triIdx)) {
                vertex_link_triangle_dict[idx1].Add(triIdx);
            }
        }

        curCnt--;

        iterCnt++;
        if (iterCnt >= maxIter) {
            Debug.LogError("simplify end because iterCnt has reach its limit");
        }
    }

}

private bool IsCommonTriangle(int idx1, int idx2, int triIdx) {

    // triangle that use this pair as common egde, set them not valid
    int tri_vert_start = triIdx * 3;
    int tri_v1 = triangles[tri_vert_start];
    int tri_v2 = triangles[tri_vert_start + 1];
    int tri_v3 = triangles[tri_vert_start + 2];

    bool exist_idx1 = tri_v1 == idx1 || tri_v2 == idx1 || tri_v3 == idx1;
    bool exist_idx2 = tri_v1 == idx2 || tri_v2 == idx2 || tri_v3 == idx2;

    bool flag = false;
    if (tri_v1 == idx1 && tri_v1 == idx2) {
        flag = true;
    } else if (tri_v2 == idx1 && tri_v2 == idx2) {
        flag = true;
    } else if (tri_v3 == idx1 && tri_v3 == idx2) {
        flag = true;
    }
    if (flag) {
        Debug.LogError($"不应该出现的情况！计算共边三角型时发现 两个顶点落在了同样的索引上！{idx1}");
        return false;
    }

    if (exist_idx1 && exist_idx2) {
        return true;
    } else {
        return false;
    }
}

private void UpdateTriangleVert(int oldIdx, int newIdx, int triIdx) {
    int tri_vert_start = triIdx * 3;
    if (triangle_contains_vert_dict[triIdx][0] == oldIdx) {
        triangles[tri_vert_start] = newIdx;
        triangle_contains_vert_dict[triIdx][0] = newIdx;
    } 
    if (triangle_contains_vert_dict[triIdx][1] == oldIdx) {
        triangles[tri_vert_start + 1] = newIdx;
        triangle_contains_vert_dict[triIdx][1] = newIdx;
    } 
    if (triangle_contains_vert_dict[triIdx][2] == oldIdx) {
        triangles[tri_vert_start + 2] = newIdx;
        triangle_contains_vert_dict[triIdx][2] = newIdx;
    }
}


（4）.最后结束减面，去除不合法的顶点，返回新Mesh

结束时先遍历顶点数组，刷新相关三角型关系，最后用合法的顶点与三角型组成新Mesh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public Mesh EndSimplify() {

    // delete vertex not valid
    int vertNum = vertexs.Length;
    List<Vector3> newVerts = new List<Vector3>();
    int curOffset = 0;
    for (int i = 0; i < vertNum; i++) {
        if (!vertex_valid[i]) {
            curOffset++;
            continue;
        }

        int newIdx = i - curOffset;
        // old idx is bigger，so no conflict
        foreach (var triIdx in vertex_link_triangle_dict[i])
        {
            UpdateTriangleVert(i, newIdx, triIdx);
        }

        newVerts.Add(vertexs[i]);
    }

    // delete un valid tris
    List<int> newTriangles = new List<int>();
    int triIdxNum = triangles.Length;
    int triNum = triIdxNum / 3;
    for (int triIdx = 0; triIdx < triNum; triIdx++) {
        if (!triangle_valid[triIdx]) {
            continue;
        }

        int tri_vert_start = triIdx * 3;
        int v1 = triangles[tri_vert_start];
        int v2 = triangles[tri_vert_start + 1];
        int v3 = triangles[tri_vert_start + 2];

        newTriangles.Add(v1);
        newTriangles.Add(v2);
        newTriangles.Add(v3);
    }

    // TODO : normals和uv的计算
    mesh.vertices = newVerts.ToArray();
    mesh.triangles = newTriangles.ToArray();
    mesh.RecalculateBounds();
    mesh.RecalculateNormals();
    return mesh;
}

1.4.目前减面存在的问题

首先， Heap的刷新目前有些问题，现在还未在每次去除顶点对时更新堆内其他相连顶点对的误差值，所以算法进行的不完整，减面效果未达到预期，后续把这部分补上。

其次，上述步骤仅计算了Mesh的vertex和triangle关系，normal和uv均未设置，得到的Mesh也无法正确应用地貌贴图。

最后，目前的减面效果还存在一些问题，以下Mesh是某次减面操作中出现的：

    image
图：Mesh减面目前存在的问题

可以看到上面的顶点中有些三角型重合了，说明计算过程中的顶点对维护依然存在问题，这对于后续Mesh的构建并不利。

最近这段时间一边忙着毕设论文一边做地图包更新，还阅读地形减面相关资料的同时还要读论文，所以代码维护上有些力不从心，后续再补上本节所说的各种问题，同时讲讲最近思考的地形优化思路