mesh – Implementing Edge-Collase Algorithm

Background

Hey. 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 venture and raymath to do the mathematics operations.

Subject

I’m having difficulties implementing the algorithm. Some faces disappear when collapsing the mesh, and others overlap different faces. This concern presents an enormous downside for the entire venture, so I got here right here to ask in your assist explaining the algorithm in simple language, and evaluate the code, with me.

The picture ought to visually clarify my concern.

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.measurement(); 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.measurement(); ++i) {
        HalfEdge& he = halfEdges[i];

        for (size_t j = i + 1; j < halfEdges.measurement(); ++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) ),
                    halfEdges.finish());
}




std::vector<unsigned brief> computeIndices(const std::vector<Vector3>& vertices) {
    std::vector<unsigned brief> indices;
    
    for (size_t i = 0; i < vertices.measurement(); 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.measurement());
    int triangleCount = static_cast<int>(indices.measurement()) / 3;

    lodMesh.vertexCount = vertexCount;
    lodMesh.triangleCount = triangleCount;
    lodMesh.vertices = (float*)malloc(sizeof(float) * 3 * vertexCount);
    lodMesh.indices = (unsigned brief*)malloc(sizeof(unsigned brief) * indices.measurement());
    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.measurement(); 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 fundamental() {
    
    SetConfigFlags(FLAG_WINDOW_RESIZABLE);
    InitWindow(screenWidth, screenHeight, "Half-Edge Collapsing");

    Camera3D digital camera = { 0 };
    digital camera.place = { 0.0f, 1.0f, -5.0f };
    digital camera.goal = { 0.0f, 0.0f, 0.0f };
    digital camera.up = { 0.0f, 1.0f, 0.0f };
    digital camera.fovy = 45.0f;
    digital camera.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(&digital camera, 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(digital camera);
        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.measurement())), 10, 40, 20, BLACK);
        for (size_t i = 0; i < vertices.measurement(); ++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;
}