如何程序化生成三角网格的LOD并实现GenerateLOD函数

一、LOD顶点数量规则 #

各层级LOD的顶点数与原始网格顶点数的比例关系如下：

• LOD0：顶点数 = 原始网格顶点数 × 1/2⁰ = 完整原始顶点数
• LOD1：顶点数 = 原始网格顶点数 × 1/2¹ = 原始顶点数的1/2
• ...
• LOD8：顶点数 = 原始网格顶点数 × 1/2⁸ = 原始顶点数的1/256

二、核心实现方案 #

对于规则拓扑的网格（如平面、地形网格），可以用固定步长采样的方式快速生成LOD，实现简单且性能高效；如果是不规则拓扑的网格（如角色模型），建议使用Quadric Error Metric（QEM）边折叠算法，在减少顶点数的同时最大程度保留网格几何特征。

以下是适配你提供的代码框架的具体实现：

#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <stdint.h>

namespace Math {
    struct Vec3 { float x, y, z; Vec3(float x_=0, float y_=0, float z_=0) : x(x_), y(y_), z(z_) {} };
    struct Vec2 { float u, v; Vec2(float u_=0, float v_=0) : u(u_), v(v_) {} };
}

struct Vertex {
    Math::Vec3 Position;
    Math::Vec2 Texcoord;

    bool operator==(const Vertex& other) const {
        return Position.x == other.Position.x && Position.y == other.Position.y && Position.z == other.Position.z &&
               Texcoord.u == other.Texcoord.u && Texcoord.v == other.Texcoord.v;
    }
};

// 为Vertex实现哈希，用于去重
namespace std {
    template<> struct hash<Vertex> {
        size_t operator()(const Vertex& v) const {
            size_t h1 = hash<float>()(v.Position.x);
            h1 ^= hash<float>()(v.Position.y) << 1;
            h1 ^= hash<float>()(v.Position.z) << 2;
            size_t h2 = hash<float>()(v.Texcoord.u);
            h2 ^= hash<float>()(v.Texcoord.v) << 1;
            return h1 ^ (h2 << 3);
        }
    };
}

void GenerateLOD(const std::vector<Vertex>& InVertices,
                 const std::vector<uint32_t>& InIndices,
                 std::vector<Vertex>& outVertices,
                 std::vector<uint32_t>& outIndices,
                 int LODLevel) {
    outVertices.clear();
    outIndices.clear();

    // 限制LOD层级在0-8范围内
    if (LODLevel < 0 || LODLevel > 8) {
        return;
    }

    const float LODFactor = 1.0f / pow(2, LODLevel);
    const size_t targetVertexCount = static_cast<size_t>(InVertices.size() * LODFactor);

    // 目标顶点数不小于原始数时，直接复制原始数据
    if (targetVertexCount >= InVertices.size()) {
        outVertices = InVertices;
        outIndices = InIndices;
        return;
    }

    // 规则网格采样逻辑：按步长选取顶点
    const int step = static_cast<int>(pow(2, LODLevel));
    std::unordered_map<Vertex, uint32_t> vertexMap;
    uint32_t newIndex = 0;

    // 采样顶点并去重
    for (size_t i = 0; i < InVertices.size(); i += step) {
        const Vertex& v = InVertices[i];
        if (vertexMap.find(v) == vertexMap.end()) {
            vertexMap[v] = newIndex++;
            outVertices.push_back(v);
        }
    }

    // 映射原始索引到新顶点索引，过滤未采样的顶点
    for (uint32_t idx : InIndices) {
        if (idx % step == 0) {
            const Vertex& v = InVertices[idx];
            outIndices.push_back(vertexMap[v]);
        }
    }

    // 清理无效三角形（确保索引数是3的倍数）
    size_t validTriCount = outIndices.size() / 3;
    outIndices.resize(validTriCount * 3);
}

int main() {
    const std::vector<Vertex> MeshVertices{
        { Math::Vec3(-1.0f, -1.0f, 0.0f), Math::Vec2(0.0f, 1.0f)},
        { Math::Vec3(1.0f, -1.0f, 0.0f), Math::Vec2(1.0f, 1.0f)},
        { Math::Vec3(-1.0f, 1.0f, 0.0f), Math::Vec2(0.0f, 0.0f)},
        { Math::Vec3(1.0f, 1.0f, 0.0f), Math::Vec2(1.0f, 0.0f)},
        { Math::Vec3(-0.5f, -0.5f, 0.0f), Math::Vec2(0.25f, 0.75f)},
        { Math::Vec3(0.5f, -0.5f, 0.0f), Math::Vec2(0.75f, 0.75f)},
        { Math::Vec3(-0.5f, 0.5f, 0.0f), Math::Vec2(0.25f, 0.25f)},
        { Math::Vec3(0.5f, 0.5f, 0.0f), Math::Vec2(0.75f, 0.25f)}
    };

    const std::vector<uint32_t> MeshIndices{ 
        0, 1, 4, 1, 5, 4,
        0, 4, 2, 4, 6, 2,
        1, 3, 5, 3, 7, 5,
        2, 6, 3, 6, 7, 3
    };

    std::vector<Vertex> OutVertices;
    std::vector<uint32_t> OutIndices;

    const int LODLevel = 2;
    GenerateLOD(MeshVertices, MeshIndices, OutVertices, OutIndices, LODLevel);

    return 0;
}

代码关键说明 #

1. 顶点去重：通过std::unordered_map记录已添加的顶点，避免重复顶点占用内存。
2. 规则采样：针对规则网格，用步长2^LODLevel筛选顶点，快速达到目标顶点数比例，适合地形、平面等网格类型。
3. 索引映射：遍历原始索引，仅保留被采样顶点的索引，并映射到新顶点缓冲区的索引，同时清理无效三角形。
4. 边界处理：对LOD层级做范围校验，避免无效输入；若目标顶点数大于等于原始数，直接返回原始数据。

不规则网格优化方案 #

如果处理角色模型这类不规则拓扑网格，建议替换为QEM边折叠算法：

1. 为每个顶点计算二次误差矩阵，量化顶点移除后的几何精度损失。
2. 遍历所有边，计算边折叠后的总误差。
3. 优先折叠误差最小的边，直到顶点数达到目标数量。
4. 更新受影响顶点的误差矩阵，重复上述步骤。

内容的提问来源于stack exchange，提问作者TheChamp