• 日期: 2024-08-04
  • 标签: 常规

OpenGL 三角网格简化：QEM 算法实现与代码示例

三角网格简化是一种将复杂模型转化为更简单的模型的技术，这在渲染效率和模型存储方面都有优势。QEM（Quadric Error Metric）算法是一种常见的三角网格简化算法，它通过计算每个顶点周围的二次误差度量来决定哪些顶点可以合并。

以下是一个使用 OpenGL 实现三角网格简化算法的示例代码，展示了如何使用 QEM 算法来简化一个简单的三角网格模型：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <GL/glut.h>

using namespace std;

// 三维点结构体
struct Point3D {
    float x, y, z;
};

// 三角面片结构体
struct Triangle {
    int v1, v2, v3;
};

// 顶点结构体，包含位置和法向量
struct Vertex {
    Point3D position;
    Point3D normal;
};

// 顶点合并误差矩阵
struct QEM {
    float matrix[4][4];
};

// 三角网格模型
class Mesh {
public:
    vector<Vertex> vertices; // 顶点集合
    vector<Triangle> triangles; // 三角面片集合

    // 添加顶点
    void addVertex(float x, float y, float z) {
        Vertex vertex;
        vertex.position.x = x;
        vertex.position.y = y;
        vertex.position.z = z;
        vertices.push_back(vertex);
    }

    // 添加三角面片
    void addTriangle(int v1, int v2, int v3) {
        Triangle triangle;
        triangle.v1 = v1;
        triangle.v2 = v2;
        triangle.v3 = v3;
        triangles.push_back(triangle);
    }

    // 计算顶点法向量
    void calculateNormals() {
        for (int i = 0; i < vertices.size(); i++) {
            vertices[i].normal.x = 0.0f;
            vertices[i].normal.y = 0.0f;
            vertices[i].normal.z = 0.0f;
        }

        for (int i = 0; i < triangles.size(); i++) {
            int v1 = triangles[i].v1;
            int v2 = triangles[i].v2;
            int v3 = triangles[i].v3;

            Point3D p1 = vertices[v1].position;
            Point3D p2 = vertices[v2].position;
            Point3D p3 = vertices[v3].position;

            Point3D normal;
            normal.x = (p2.y - p1.y) * (p3.z - p1.z) - (p2.z - p1.z) * (p3.y - p1.y);
            normal.y = (p2.z - p1.z) * (p3.x - p1.x) - (p2.x - p1.x) * (p3.z - p1.z);
            normal.z = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);

            vertices[v1].normal.x += normal.x;
            vertices[v1].normal.y += normal.y;
            vertices[v1].normal.z += normal.z;

            vertices[v2].normal.x += normal.x;
            vertices[v2].normal.y += normal.y;
            vertices[v2].normal.z += normal.z;

            vertices[v3].normal.x += normal.x;
            vertices[v3].normal.y += normal.y;
            vertices[v3].normal.z += normal.z;
        }

        for (int i = 0; i < vertices.size(); i++) {
            float length = sqrt(vertices[i].normal.x * vertices[i].normal.x +
                                vertices[i].normal.y * vertices[i].normal.y +
                                vertices[i].normal.z * vertices[i].normal.z);
            vertices[i].normal.x /= length;
            vertices[i].normal.y /= length;
            vertices[i].normal.z /= length;
        }
    }

    // 计算两个顶点之间的误差矩阵
    QEM calculateErrorMatrix(int v1, int v2) {
        QEM qem;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                qem.matrix[i][j] = 0.0f;
            }
        }

        Point3D p1 = vertices[v1].position;
        Point3D p2 = vertices[v2].position;

        for (int i = 0; i < triangles.size(); i++) {
            Triangle triangle = triangles[i];
            if (triangle.v1 == v1 || triangle.v2 == v1 || triangle.v3 == v1 ||
                triangle.v1 == v2 || triangle.v2 == v2 || triangle.v3 == v2) {
                continue;
            }

            Point3D p3 = vertices[triangle.v1].position;
            Point3D p4 = vertices[triangle.v2].position;
            Point3D p5 = vertices[triangle.v3].position;

            float nx = (p3.y - p1.y) * (p4.z - p1.z) - (p3.z - p1.z) * (p4.y - p1.y);
            float ny = (p3.z - p1.z) * (p4.x - p1.x) - (p3.x - p1.x) * (p4.z - p1.z);
            float nz = (p3.x - p1.x) * (p4.y - p1.y) - (p3.y - p1.y) * (p4.x - p1.x);

            float distance = nx * p1.x + ny * p1.y + nz * p1.z;

            qem.matrix[0][0] += nx * nx;
            qem.matrix[0][1] += nx * ny;
            qem.matrix[0][2] += nx * nz;
            qem.matrix[0][3] += nx * distance;

            qem.matrix[1][0] += nx * ny;
            qem.matrix[1][1] += ny * ny;
            qem.matrix[1][2] += ny * nz;
            qem.matrix[1][3] += ny * distance;

            qem.matrix[2][0] += nx * nz;
            qem.matrix[2][1] += ny * nz;
            qem.matrix[2][2] += nz * nz;
            qem.matrix[2][3] += nz * distance;

            qem.matrix[3][0] += nx * distance;
            qem.matrix[3][1] += ny * distance;
            qem.matrix[3][2] += nz * distance;
            qem.matrix[3][3] += distance * distance;
        }

        return qem;
    }

    // 顶点合并
    void mergeVertices(int v1, int v2) {
        vertices[v1].position.x = (vertices[v1].position.x + vertices[v2].position.x) / 2.0f;
        vertices[v1].position.y = (vertices[v1].position.y + vertices[v2].position.y) / 2.0f;
        vertices[v1].position.z = (vertices[v1].position.z + vertices[v2].position.z) / 2.0f;

        // 更新法向量
        Point3D normal;
        normal.x = vertices[v1].normal.x + vertices[v2].normal.x;
        normal.y = vertices[v1].normal.y + vertices[v2].normal.y;
        normal.z = vertices[v1].normal.z + vertices[v2].normal.z;
        float length = sqrt(normal.x * normal.x + normal.y * normal.y + normal.z * normal.z);
        vertices[v1].normal.x = normal.x / length;
        vertices[v1].normal.y = normal.y / length;
        vertices[v1].normal.z = normal.z / length;

        // 删除顶点v2
        vertices.erase(vertices.begin() + v2);

        // 更新三角面片中的顶点索引
        for (int i = 0; i < triangles.size(); i++) {
            if (triangles[i].v1 == v2) {
                triangles[i].v1 = v1;
            }
            if (triangles[i].v2 == v2) {
                triangles[i].v2 = v1;
            }
            if (triangles[i].v3 == v2) {
                triangles[i].v3 = v1;
            }
        }
    }

    // 三角网格简化
    void simplifyMesh(int targetVertices) {
        // 初始化顶点合并误差矩阵队列
        priority_queue<pair<float, pair<int, int>>> q;
        for (int i = 0; i < vertices.size(); i++) {
            for (int j = i + 1; j < vertices.size(); j++) {
                QEM qem = calculateErrorMatrix(i, j);
                float error = qem.matrix[3][3];
                q.push(make_pair(error, make_pair(i, j)));
            }
        }

        // 顶点合并
        while (vertices.size() > targetVertices) {
            int v1 = q.top().second.first;
            int v2 = q.top().second.second;
            q.pop();

            mergeVertices(v1, v2);

            // 更新顶点合并误差矩阵
            for (int i = 0; i < vertices.size(); i++) {
                if (i == v1) {
                    continue;
                }
                QEM qem = calculateErrorMatrix(i, v1);
                float error = qem.matrix[3][3];
                q.push(make_pair(error, make_pair(i, v1)));
            }
        }
    }

    // 绘制三角网格模型
    void drawMesh() {
        for (int i = 0; i < triangles.size(); i++) {
            int v1 = triangles[i].v1;
            int v2 = triangles[i].v2;
            int v3 = triangles[i].v3;

            glBegin(GL_TRIANGLES);
            glNormal3f(vertices[v1].normal.x, vertices[v1].normal.y, vertices[v1].normal.z);
            glVertex3f(vertices[v1].position.x, vertices[v1].position.y, vertices[v1].position.z);

            glNormal3f(vertices[v2].normal.x, vertices[v2].normal.y, vertices[v2].normal.z);
            glVertex3f(vertices[v2].position.x, vertices[v2].position.y, vertices[v2].position.z);

            glNormal3f(vertices[v3].normal.x, vertices[v3].normal.y, vertices[v3].normal.z);
            glVertex3f(vertices[v3].position.x, vertices[v3].position.y, vertices[v3].position.z);
            glEnd();
        }
    }
};

// 全局变量
Mesh mesh;

// 初始化函数
void init() {
    glClearColor(0.0f, 0.0f, 0.0f, 1.0f);
    glEnable(GL_DEPTH_TEST);
    glEnable(GL_LIGHTING);
    glEnable(GL_LIGHT0);
}

// 显示函数
void display() {
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glLoadIdentity();
    gluLookAt(0.0f, 0.0f, 5.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f);

    glColor3f(1.0f, 1.0f, 1.0f);
    mesh.drawMesh();

    glutSwapBuffers();
}

// 窗口大小变化回调函数
void reshape(int width, int height) {
    glViewport(0, 0, width, height);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluPerspective(45.0f, (float)width / (float)height, 0.1f, 100.0f);
    glMatrixMode(GL_MODELVIEW);
}

int main(int argc, char** argv) {
    // 创建三角网格模型
    mesh.addVertex(0.0f, 0.0f, 0.0f);
    mesh.addVertex(1.0f, 0.0f, 0.0f);
    mesh.addVertex(1.0f, 1.0f, 0.0f);
    mesh.addVertex(0.0f, 1.0f, 0.0f);
    mesh.addTriangle(0, 1, 2);
    mesh.addTriangle(0, 2, 3);

    // 计算法向量
    mesh.calculateNormals();

    // 简化三角网格模型
    mesh.simplifyMesh(2);

    // 初始化OpenGL
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH);
    glutInitWindowSize(800, 600);
    glutCreateWindow('Triangle Mesh Simplification');

    // 注册回调函数
    glutDisplayFunc(display);
    glutReshapeFunc(reshape);

    // 初始化
    init();

    // 进入主循环
    glutMainLoop();

    return 0;
}

该代码示例创建了一个简单的正方形，并通过 QEM 算法将顶点数减少到 2。代码中包含了以下关键步骤：

  1. 定义数据结构: 定义了 Point3D、Triangle、Vertex 和 QEM 结构体来存储模型数据。
  2. 创建网格类: Mesh 类用于存储和操作网格模型，包括添加顶点、添加三角形、计算法向量、计算误差矩阵和合并顶点等功能。
  3. QEM 误差矩阵计算: calculateErrorMatrix() 函数计算两个顶点之间的误差矩阵。
  4. 顶点合并: mergeVertices() 函数将两个顶点合并为一个新的顶点，并更新相关数据。
  5. 三角网格简化: simplifyMesh() 函数使用优先队列来保存所有顶点对的误差，每次选取误差最小的顶点对进行合并，直到达到目标顶点数。
  6. OpenGL 显示: 使用 OpenGL 绘制简化后的模型。

注意： 这个示例代码只是一个简单的实现，可能并不完整或者有一些错误。具体的实现方式和效果可以根据实际需求进行修改和调整。

本代码示例仅供参考，如有任何问题或需要改进的地方，请随时提出。

OpenGL 三角网格简化：QEM 算法实现与代码示例

原文地址: https://www.cveoy.top/t/topic/o8Ff 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录