Chenyj Space

什么是网格体（Mesh）？

网格体（Mesh）是 3D 计算机图形学中最基本的几何表示形式。它由一系列顶点（Vertices）、边（Edges）和面（Faces）组成，用来描述 3D 物体的形状和表面。

网格体是实时渲染、3D 建模、游戏开发和科学可视化等领域的核心数据结构。

网格体的基本组成

1. 顶点（Vertex）

顶点是网格体的最基本元素，表示 3D 空间中的一个点：

cpp

struct Vertex {
    glm::vec3 position;  // 位置坐标
    glm::vec3 normal;    // 法线向量
    glm::vec2 texCoord;  // 纹理坐标
    glm::vec3 tangent;   // 切线向量
    glm::vec3 color;     // 顶点颜色
};

2. 边（Edge）

边连接两个顶点，是三角形的边界：

cpp

struct Edge {
    uint32_t vertex0;
    uint32_t vertex1;
    uint32_t face0;
    uint32_t face1;
};

3. 面（Face）

面通常由三个顶点组成的三角形（Triangle）：

cpp

struct Triangle {
    uint32_t indices[3];  // 三个顶点的索引
};

网格体的数据结构

1. 三角形列表（Triangle List）

最简单的表示方式，每三个顶点组成一个三角形：

cpp

std::vector<Vertex> vertices = {
    // 三角形 1
    {glm::vec3(-1, 0, 0), glm::vec3(0, 1, 0)},
    {glm::vec3(1, 0, 0), glm::vec3(0, 1, 0)},
    {glm::vec3(0, 1, 0), glm::vec3(0, 1, 0)},
    // 三角形 2
    // ...
};

2. 索引三角形列表（Indexed Triangle List）

使用顶点索引来避免重复顶点：

cpp

std::vector<Vertex> vertices = {
    {glm::vec3(-1, 0, 0)},  // 0
    {glm::vec3(1, 0, 0)},   // 1
    {glm::vec3(0, 1, 0)},   // 2
    {glm::vec3(0, -1, 0)},  // 3
};

std::vector<uint32_t> indices = {
    0, 1, 2,  // 三角形 1
    0, 1, 3,  // 三角形 2
};

3. 半边结构（Half-Edge）

高级数据结构，便于遍历和修改：

cpp

struct HalfEdge {
    uint32_t vertex;
    uint32_t face;
    uint32_t next;
    uint32_t twin;
};

struct Mesh {
    std::vector<glm::vec3> positions;
    std::vector<HalfEdge> halfEdges;
    std::vector<uint32_t> faces;
};

网格体的拓扑

1. 流形（Manifold）

流形网格满足以下条件：

每条边恰好被两个面共享
每个顶点周围的面形成一个闭合的环

cpp

bool isManifold(const Mesh& mesh) {
    // 检查每条边是否被恰好两个面共享
    std::unordered_map<EdgeKey, int> edgeCount;
    
    for (const auto& triangle : mesh.triangles) {
        for (int i = 0; i < 3; i++) {
            EdgeKey key = makeEdgeKey(triangle.indices[i], triangle.indices[(i + 1) % 3]);
            edgeCount[key]++;
        }
    }
    
    for (const auto& [key, count] : edgeCount) {
        if (count != 2) {
            return false;
        }
    }
    
    return true;
}

2. 亏格（Genus）

亏格描述网格体的"洞"的数量：

亏格 0：球体、立方体
亏格 1：环面（甜甜圈）
亏格 2：双环面

cpp

int computeGenus(const Mesh& mesh) {
    int V = mesh.vertices.size();
    int E = mesh.edges.size();
    int F = mesh.triangles.size();
    
    // 欧拉公式：V - E + F = 2 - 2g
    return (2 - V + E - F) / 2;
}

网格体的几何属性

1. 法线计算

顶点法线可以通过相邻面的法线平均得到：

cpp

glm::vec3 computeFaceNormal(const glm::vec3& v0, const glm::vec3& v1, const glm::vec3& v2) {
    glm::vec3 edge1 = v1 - v0;
    glm::vec3 edge2 = v2 - v0;
    return glm::normalize(glm::cross(edge1, edge2));
}

void computeVertexNormals(Mesh& mesh) {
    mesh.normals.resize(mesh.vertices.size(), glm::vec3(0.0f));
    
    for (const auto& tri : mesh.triangles) {
        glm::vec3 normal = computeFaceNormal(
            mesh.vertices[tri.indices[0]],
            mesh.vertices[tri.indices[1]],
            mesh.vertices[tri.indices[2]]
        );
        
        mesh.normals[tri.indices[0]] += normal;
        mesh.normals[tri.indices[1]] += normal;
        mesh.normals[tri.indices[2]] += normal;
    }
    
    for (auto& normal : mesh.normals) {
        normal = glm::normalize(normal);
    }
}

2. 面积计算

三角形面积可以通过叉积计算：

cpp

float computeTriangleArea(const glm::vec3& v0, const glm::vec3& v1, const glm::vec3& v2) {
    glm::vec3 edge1 = v1 - v0;
    glm::vec3 edge2 = v2 - v0;
    return 0.5f * glm::length(glm::cross(edge1, edge2));
}

float computeMeshArea(const Mesh& mesh) {
    float area = 0.0f;
    
    for (const auto& tri : mesh.triangles) {
        area += computeTriangleArea(
            mesh.vertices[tri.indices[0]],
            mesh.vertices[tri.indices[1]],
            mesh.vertices[tri.indices[2]]
        );
    }
    
    return area;
}

3. 包围盒

轴对齐包围盒（AABB）用于快速剔除：

cpp

struct AABB {
    glm::vec3 min;
    glm::vec3 max;
};

AABB computeAABB(const Mesh& mesh) {
    AABB bbox;
    bbox.min = glm::vec3(FLT_MAX);
    bbox.max = glm::vec3(-FLT_MAX);
    
    for (const auto& vertex : mesh.vertices) {
        bbox.min = glm::min(bbox.min, vertex);
        bbox.max = glm::max(bbox.max, vertex);
    }
    
    return bbox;
}

网格体优化

1. 网格简化

减少三角形数量，保持形状：

cpp

// 边折叠（Edge Collapse）简化
void simplifyMesh(Mesh& mesh, int targetTriangles) {
    while (mesh.triangles.size() > targetTriangles) {
        // 找到代价最小的边
        Edge minEdge = findMinCostEdge(mesh);
        
        // 执行边折叠
        collapseEdge(mesh, minEdge);
    }
}

2. 网格细分

增加细节，平滑表面：

cpp

// Loop 细分
void subdivideLoop(Mesh& mesh) {
    std::vector<Vertex> newVertices;
    std::vector<Triangle> newTriangles;
    
    // 为每条边创建新顶点
    for (const auto& edge : mesh.edges) {
        glm::vec3 newPos = computeEdgePosition(mesh, edge);
        newVertices.push_back({newPos});
    }
    
    // 更新原始顶点位置
    for (size_t i = 0; i < mesh.vertices.size(); i++) {
        mesh.vertices[i].position = computeVertexPosition(mesh, i);
    }
    
    // 创建新三角形
    for (const auto& tri : mesh.triangles) {
        // 每个三角形分成四个三角形
        // ...
    }
}

3. 网格平滑

消除噪声，平滑表面：

cpp

// 拉普拉斯平滑
void smoothMesh(Mesh& mesh, int iterations, float lambda) {
    for (int iter = 0; iter < iterations; iter++) {
        std::vector<glm::vec3> newPositions(mesh.vertices.size());
        
        for (size_t i = 0; i < mesh.vertices.size(); i++) {
            glm::vec3 laplacian(0.0f);
            int count = 0;
            
            // 计算相邻顶点的平均位置
            for (uint32_t neighbor : getNeighbors(mesh, i)) {
                laplacian += mesh.vertices[neighbor].position;
                count++;
            }
            
            laplacian /= static_cast<float>(count);
            laplacian -= mesh.vertices[i].position;
            
            newPositions[i] = mesh.vertices[i].position + lambda * laplacian;
        }
        
        // 更新顶点位置
        for (size_t i = 0; i < mesh.vertices.size(); i++) {
            mesh.vertices[i].position = newPositions[i];
        }
    }
}

高级网格处理

1. 网格分割

将大网格分成多个小块：

cpp

std::vector<Mesh> splitMesh(const Mesh& mesh, int maxTrianglesPerChunk) {
    std::vector<Mesh> chunks;
    
    // 使用空间分割或图分割算法
    // ...
    
    return chunks;
}

2. Meshlet 生成

为 GPU 渲染优化的小块：

cpp

struct Meshlet {
    uint32_t vertexCount;
    uint32_t triangleCount;
    uint32_t vertices[64];
    uint8_t indices[124 * 3];
};

std::vector<Meshlet> generateMeshlets(const Mesh& mesh) {
    // 使用 meshoptimizer 库
    size_t maxMeshlets = meshopt_buildMeshletsBound(
        mesh.indices.size(), 64, 124);
    
    std::vector<meshopt_Meshlet> meshlets(maxMeshlets);
    std::vector<unsigned int> meshletVertices(maxMeshlets * 64);
    std::vector<unsigned char> meshletTriangles(maxMeshlets * 124 * 3);
    
    size_t meshletCount = meshopt_buildMeshlets(
        meshlets.data(), meshletVertices.data(), meshletTriangles.data(),
        mesh.indices.data(), mesh.indices.size(),
        &mesh.vertices[0].position.x, mesh.vertices.size(), sizeof(Vertex),
        64, 124, 0.0f);
    
    // 转换为自定义格式
    // ...
}

3. 碰撞检测

使用网格进行物理碰撞：

cpp

bool rayMeshIntersection(const Ray& ray, const Mesh& mesh, float& t) {
    bool hit = false;
    t = FLT_MAX;
    
    for (const auto& tri : mesh.triangles) {
        float tTri;
        if (rayTriangleIntersection(ray,
            mesh.vertices[tri.indices[0]].position,
            mesh.vertices[tri.indices[1]].position,
            mesh.vertices[tri.indices[2]].position,
            tTri)) {
            if (tTri < t) {
                t = tTri;
                hit = true;
            }
        }
    }
    
    return hit;
}

网格文件格式

1. OBJ 格式

最常见的 3D 模型格式：

obj

# 顶点
v 1.0 0.0 0.0
v 0.0 1.0 0.0
v 0.0 0.0 1.0

# 法线
vn 0.0 0.0 1.0

# 纹理坐标
vt 0.0 0.0
vt 1.0 0.0
vt 0.5 1.0

# 面（顶点/纹理/法线）
f 1/1/1 2/2/1 3/3/1

2. glTF 格式

现代的 3D 传输格式：

json

{
  "meshes": [{
    "primitives": [{
      "attributes": {
        "POSITION": 0,
        "NORMAL": 1,
        "TEXCOORD_0": 2
      },
      "indices": 3
    }]
  }]
}

3. FBX 格式

工业标准格式，支持动画：

cpp

// 使用 FBX SDK 加载
FbxManager* manager = FbxManager::Create();
FbxScene* scene = FbxScene::create(manager, "");
FbxImporter* importer = FbxImporter::create(manager, "");

importer->Initialize("model.fbx");
importer->Import(scene);

// 遍历网格节点
FbxNode* root = scene->GetRootNode();
for (int i = 0; i < root->GetChildCount(); i++) {
    FbxNode* node = root->GetChild(i);
    FbxMesh* mesh = node->GetMesh();
    
    if (mesh) {
        // 提取顶点和索引
        // ...
    }
}

性能优化

1. 顶点缓存优化

重新排序顶点以提高缓存命中率：

cpp

void optimizeVertexCache(Mesh& mesh) {
    // 使用 Forsyth 算法或类似方法
    meshopt_optimizeVertexCache(
        mesh.indices.data(), mesh.indices.data(),
        mesh.indices.size(), mesh.vertices.size());
}

2. 顶点预取优化

优化顶点数据布局：

cpp

void optimizeVertexFetch(Mesh& mesh) {
    meshopt_optimizeVertexFetch(
        mesh.vertices.data(), mesh.indices.data(),
        mesh.indices.size(), mesh.vertices.data(),
        mesh.vertices.size(), sizeof(Vertex));
}

3. Overdraw 优化

减少过度绘制：

cpp

void optimizeOverdraw(Mesh& mesh) {
    meshopt_optimizeOverdraw(
        mesh.indices.data(), mesh.indices.data(),
        mesh.indices.size(), &mesh.vertices[0].position.x,
        mesh.vertices.size(), sizeof(Vertex), 1.0f);
}

常用工具

1. meshoptimizer

高性能网格优化库：

cpp

#include <meshoptimizer.h>

// 简化
meshopt_simplify(indices, indices, index_count, vertices, vertex_count,
                 sizeof(Vertex), target_index_count, target_error);

2. Assimp

模型导入库：

cpp

#include <assimp/Importer.hpp>
#include <assimp/scene.h>
#include <assimp/postprocess.h>

Assimp::Importer importer;
const aiScene* scene = importer.ReadFile("model.obj",
    aiProcess_Triangulate | aiProcess_GenNormals);

3. OpenMesh

半边网格库：

cpp

#include <OpenMesh/Core/IO/MeshIO.hh>
#include <OpenMesh/Core/Mesh/TriMesh_ArrayKernelT.hh>

typedef OpenMesh::TriMesh_ArrayKernelT<> MyMesh;
MyMesh mesh;

OpenMesh::IO::read_mesh(mesh, "model.obj");

实际应用

1. 游戏开发

角色模型
场景环境
碰撞体

2. 3D 打印

模型修复
支撑生成
切片处理

3. 科学可视化

有限元网格
医学图像重建
地形生成

总结

网格体是 3D 图形学的基础，理解其核心概念对于图形编程至关重要：

基本组成：顶点、边、面
数据结构：索引列表、半边结构
几何属性：法线、面积、包围盒
优化技术：简化、细分、平滑
文件格式：OBJ、glTF、FBX

参考资源

Real-Time Rendering - 图形学经典教材
meshoptimizer - 网格优化库
OpenMesh - 半边网格库
Assimp - 模型导入库
glTF Specification - 现代 3D 格式