mesh – Implementing Edge-Collapse Algorithm

Background

Hi there. I’m attempting to implement Dynamic LOD and I’ve to implement an algorithm to decimate a mesh. I selected Edge Collapsing to Decimate the mesh. I’m utilizing raylib to deal with the graphical a part of the undertaking and raymath to do the maths operations.

Situation

I’m having difficulties implementing the algorithm. Some faces disappear when collapsing the mesh, and others overlap different faces. This problem presents a giant drawback for the entire undertaking, so I got here right here to ask to your assist explaining the algorithm in straightforward language, and evaluation the code, with me.

The picture ought to visually clarify my problem.

Code

#embody <algorithm>
#embody <cmath>
#embody <iostream>
#embody <set>
#embody <vector>
#embody "raylib.h"
#embody "raymath.h"

#embody "embody/rlImGui.h"
#embody "imgui.h"


const int screenWidth = 1200;
const int screenHeight = 450;


struct HalfEdge {
    int vertexIndex;
    int pairIndex;
    int nextIndex;
    bool isBoundary;
};


std::vector<HalfEdge> initializeHalfEdges(const std::vector<Vector3>& vertices) {
    std::vector<HalfEdge> halfEdges;

    
    for (size_t i = 0; i < vertices.dimension(); i += 3) {
        
        for (int j = 0; j < 3; ++j) {
            HalfEdge he;
            he.vertexIndex = i + j;
            he.nextIndex = i + (j + 1) % 3;
            he.pairIndex = -1;
            he.isBoundary = true;
            halfEdges.push_back(he);
        }
    }

    
    for (size_t i = 0; i < halfEdges.dimension(); ++i) {
        HalfEdge& he = halfEdges[i];

        for (size_t j = i + 1; j < halfEdges.dimension(); ++j) {
            HalfEdge& different = halfEdges[j];

            if (he.vertexIndex == different.nextIndex && he.nextIndex == different.vertexIndex) {
                he.pairIndex = j;
                different.pairIndex = i;
                he.isBoundary = false;
                different.isBoundary = false;
                break;
            }
        }
    }

    return halfEdges;
}


void halfEdgeCollapse(std::vector<HalfEdge>& halfEdges, std::vector<Vector3>& vertices, float threshold) {
    size_t vertexToKeep = 0;
    size_t vertexToRemove = 1;

    for (HalfEdge& he : halfEdges) {
        float distance = Vector3Distance(vertices[he.vertexIndex], vertices[he.nextIndex]);

        if (distance <= threshold) {
            vertices.erase(vertices.start() + vertexToRemove);

            if (he.vertexIndex == vertexToRemove) {
                he.vertexIndex = vertexToKeep;
            }
            if (he.nextIndex == vertexToRemove) {
                he.nextIndex = vertexToKeep;
            }
            if (he.pairIndex == vertexToRemove) {
                he.pairIndex = vertexToKeep;
            }

            if (he.vertexIndex > vertexToRemove) {
                he.vertexIndex--;
            }
            if (he.nextIndex > vertexToRemove) {
                he.nextIndex--;
            }
            if (he.pairIndex > vertexToRemove) {
                he.pairIndex--;
            }
        }
    }

    halfEdges.erase(std::remove_if(halfEdges.start(), halfEdges.finish(),
                                   [vertexToRemove](const HalfEdge& he)  he.nextIndex == vertexToRemove;
                                   ),
                    halfEdges.finish());
}




std::vector<unsigned brief> computeIndices(const std::vector<Vector3>& vertices) {
    std::vector<unsigned brief> indices;
    
    for (size_t i = 0; i < vertices.dimension(); i += 3) {
        indices.push_back(static_cast<unsigned brief>(i));
        indices.push_back(static_cast<unsigned brief>(i + 1));
        indices.push_back(static_cast<unsigned brief>(i + 2));
    }
    return indices;
}

Mesh generateLODMesh(const std::vector<Vector3>& vertices, const std::vector<unsigned brief>& indices, Mesh sourceMesh) {
    Mesh lodMesh = { 0 };

    if (vertices.empty() || indices.empty()) {
        TraceLog(LOG_WARNING, "generateLODMesh: Enter arrays are empty.");
        return sourceMesh;
    }


    int vertexCount = static_cast<int>(vertices.dimension());
    int triangleCount = static_cast<int>(indices.dimension()) / 3;

    lodMesh.vertexCount = vertexCount;
    lodMesh.triangleCount = triangleCount;
    lodMesh.vertices = (float*)malloc(sizeof(float) * 3 * vertexCount);
    lodMesh.indices = (unsigned brief*)malloc(sizeof(unsigned brief) * indices.dimension());
    lodMesh.normals = (float*)malloc(sizeof(float) * 3 * vertexCount);


    if (!lodMesh.vertices || !lodMesh.indices || !lodMesh.normals) {
        TraceLog(LOG_ERROR, "generateLODMesh: Reminiscence allocation failed.");
        
        
        if (lodMesh.vertices) free(lodMesh.vertices);
        if (lodMesh.indices) free(lodMesh.indices);
        if (lodMesh.normals) free(lodMesh.normals);

        return sourceMesh;
    }


    
    for (int i = 0; i < triangleCount; ++i) {
        Vector3 regular = Vector3Normalize(Vector3CrossProduct(
            Vector3Subtract(vertices[indices[i * 3 + 1]], vertices[indices[i * 3]]),
            Vector3Subtract(vertices[indices[i * 3 + 2]], vertices[indices[i * 3]])));

        lodMesh.normals[indices[i * 3] * 3] += regular.x;
        lodMesh.normals[indices[i * 3] * 3 + 1] += regular.y;
        lodMesh.normals[indices[i * 3] * 3 + 2] += regular.z;

        lodMesh.normals[indices[i * 3 + 1] * 3] += regular.x;
        lodMesh.normals[indices[i * 3 + 1] * 3 + 1] += regular.y;
        lodMesh.normals[indices[i * 3 + 1] * 3 + 2] += regular.z;

        lodMesh.normals[indices[i * 3 + 2] * 3] += regular.x;
        lodMesh.normals[indices[i * 3 + 2] * 3 + 1] += regular.y;
        lodMesh.normals[indices[i * 3 + 2] * 3 + 2] += regular.z;
    }

    for (int i = 0; i < vertexCount; ++i) {
        lodMesh.normals[i * 3] /= 3.0f;
        lodMesh.normals[i * 3 + 1] /= 3.0f;
        lodMesh.normals[i * 3 + 2] /= 3.0f;
    }

    
    for (int i = 0; i < vertexCount; i++) {
        lodMesh.vertices[i * 3] = vertices[i].x;
        lodMesh.vertices[i * 3 + 1] = vertices[i].y;
        lodMesh.vertices[i * 3 + 2] = vertices[i].z;
    }

    for (size_t i = 0; i < indices.dimension(); i++) {
        lodMesh.indices[i] = indices[i];
    }

    UploadMesh(&lodMesh, false);

    if (lodMesh.vertexCount == 0 || lodMesh.triangleCount == 0 || !lodMesh.vertices || !lodMesh.indices) {
        TraceLog(LOG_ERROR, "generateLODMesh: Mesh creation failed.");
        
        if (lodMesh.vertices) {
            free(lodMesh.vertices);
            lodMesh.vertices = NULL;
        }

        if (lodMesh.normals) {
            free(lodMesh.normals);
            lodMesh.normals = NULL;
        }
    }
    
    return lodMesh;
}


int most important() {
    
    SetConfigFlags(FLAG_WINDOW_RESIZABLE);
    InitWindow(screenWidth, screenHeight, "Half-Edge Collapsing");

    Camera3D digicam = { 0 };
    digicam.place = { 0.0f, 1.0f, -5.0f };
    digicam.goal = { 0.0f, 0.0f, 0.0f };
    digicam.up = { 0.0f, 1.0f, 0.0f };
    digicam.fovy = 45.0f;
    digicam.projection = CAMERA_PERSPECTIVE;

    
    Shader shader = LoadShader(0, "Engine/Lighting/shaders/lod.fs");
    Mesh mesh = GenMeshSphere(1, 15, 15);
    Mannequin mannequin = LoadModelFromMesh(mesh);
    mannequin.supplies[0].shader = shader;

    
    std::vector<Vector3> vertices;
    for (int i = 0; i < mesh.vertexCount; i++) {
        float x = mesh.vertices[i * 3];
        float y = mesh.vertices[i * 3 + 1];
        float z = mesh.vertices[i * 3 + 2];
        vertices.push_back({ x, y, z });
    }

    std::vector<HalfEdge> halfEdges = initializeHalfEdges(vertices);

    
    float threshold = 0.0;
    SetTargetFPS(50);
    rlImGuiSetup(true);

    
    whereas (!WindowShouldClose()) {
        
        if (IsMouseButtonDown(MOUSE_BUTTON_RIGHT))
            UpdateCamera(&digicam, CAMERA_FREE);

        
        vertices.clear();
        for (int i = 0; i < mesh.vertexCount; i++) {
            float x = mesh.vertices[i * 3];
            float y = mesh.vertices[i * 3 + 1];
            float z = mesh.vertices[i * 3 + 2];
            vertices.push_back({ x, y, z });
        }
        halfEdgeCollapse(halfEdges, vertices, threshold);

        
        std::vector<unsigned brief> newIndices = computeIndices(vertices);

        
        BeginDrawing();
        ClearBackground(GRAY);

        
        BeginMode3D(digicam);
        if (IsModelReady(mannequin))
            DrawModel(mannequin, Vector3Zero(), 1.0f, RED);
        EndMode3D();

        
        DrawText("Half-Edge Collapsing", 10, 10, 20, BLACK);
        DrawText(TextFormat("Collapsed Vertices: %d", mesh.vertexCount - static_cast<int>(vertices.dimension())), 10, 40, 20, BLACK);
        for (size_t i = 0; i < vertices.dimension(); ++i) {
            DrawText(TextFormat("Vertex %d: [%.2f, %.2f, %.2f]", i, vertices[i].x, vertices[i].y, vertices[i].z), 10, 70 + 30 * i, 20, BLACK);
        }

        
        rlImGuiBegin();
        if (ImGui::Start("Inspector Window", NULL))
        {
            if (ImGui::SliderFloat("Simplification Issue", &threshold, 0, 1)) {

                vertices.clear();
                for (int i = 0; i < mesh.vertexCount; i++) {
                    float x = mesh.vertices[i * 3];
                    float y = mesh.vertices[i * 3 + 1];
                    float z = mesh.vertices[i * 3 + 2];
                    vertices.push_back({ x, y, z });
                }

                halfEdgeCollapse(halfEdges, vertices, threshold);
                mannequin = LoadModelFromMesh(generateLODMesh(vertices, newIndices, mesh));

                if (threshold == 0) {
                    vertices.clear();
                    for (int i = 0; i < mesh.vertexCount; i++) {
                        float x = mesh.vertices[i * 3];
                        float y = mesh.vertices[i * 3 + 1];
                        float z = mesh.vertices[i * 3 + 2];
                        vertices.push_back({ x, y, z });
                    }
                    newIndices = computeIndices(vertices);
                    mannequin = LoadModelFromMesh(generateLODMesh(vertices, newIndices, mesh));
                }

                mannequin.supplies[0].shader = shader;
            }
            ImGui::Finish();
        }
        
        rlImGuiEnd();

        
        EndDrawing();
    }

    
    CloseWindow();

    return 0;
}