c++algorithmvertex

What is a good algorithm that can be used to get an EBO from a VBO? Is there a general solution?


I am making a program where I read vertices from an image-file but I am having trouble in figuring out the best way to construct an EBO from the resulting VBO of vertices from said image-file. (Triangles are used when drawing)

I know programs like blender can output file formats where vertices and indices are split up, in models with very different topology. This suggests to me that there is a general solution to making an EBO from a list of vertices, but I am having a hard time even making an algorithm for a 2D grid of vertices. I have tried looking around but I can't seem to find information on how to do this properly (probably using the wrong searchwords). So I just gave my best shot at making it myself.

This is what I came up with:

for (int x = 0; x < (GridWidth - 1); ++x)
    {
    for (int y = 0; y < GridHeight; ++y)
        {
        if (y == 0)
            {
            Indices[(x * 3)] = Vertices[x * VBOSIZE];
            Indices[(x * 3) + 1] = Vertices[(x + 1) * VBOSIZE];
            Indices[(x * 3) + 2] = Vertices[(x + GridWidth) * VBOSIZE]; 
            }
        else if (y == (GridHeight - 1))
            {
            Indices[(x * 3)] = Vertices[(x + 1 - GridWidth) * VBOSIZE];
            Indices[(x * 3) + 1] = Vertices[(x + 1) * VBOSIZE];
            Indices[(x * 3) + 2] = Vertices[x * VBOSIZE]; 
            }
        else
            {
            //Left, Right, Left Down
            Indices[(x * 3)] = Vertices[x * VBOSIZE];
            Indices[(x * 3) + 1] = Vertices[(x + 1) * VBOSIZE];
            Indices[(x * 3) + 2] = Vertices[(x + GridWidth) * VBOSIZE]; 
            
            //Up Right, Right, Left
            Indices[(x * 3)] = Vertices[(x + 1 - GridWidth) * VBOSIZE];
            Indices[(x * 3) + 1] = Vertices[(x + 1) * VBOSIZE];
            Indices[(x * 3) + 2] = Vertices[x * VBOSIZE]; 
            }
        }
    }

I go from left to right making triangles using the Left, Right, Left Down vertices and the Up Right, Right, Left vertices. (See Diagram)

enter image description here

What bothers me with this is that it only works in this usecase and it needs to check if you are at ypos 0 and height - 1. This honestly feels like a bandaid solution to a badly designed algorithm to me. If anyone has any leads or information on how to make a more generalized solution it would be greatly appreciated.


Solution

  • For the special case that you have m-rows and n-cols of vertices, the indices for a grid-mesh could be generated like this:

        int *indices = pointer_to_a_block_of_ints;
        int row=0;
        int col=0;
    
        do { //foreach row
            do { //foreach col
    
                const int left_top     = row * cols + col;
                const int left_bottom  = (row + 1) * cols + col;
                const int right_top    = row * cols + (col + 1);
                const int right_bottom = (row + 1) * cols + (col + 1);
        
                //- the idea is to render quads
                //- a quad can be decomposed into two triangles
                //- we start at the lower left corner, CCW
        
                //triangle 1
                *indices++ = left_bottom;
                *indices++ = right_top;
                *indices++ = left_top;
        
                //triangle 2
                *indices++ = left_bottom;
                *indices++ = right_bottom;
                *indices++ = right_top;
    
            } while (++col < cols - 1);
        } while (++row < rows - 1);
    

    As said, this code works only for a special case of a mesh. There is no generalized solution for all kinds of meshes. Imagine the set of vertices of a sphere, where there is only a single vertex at the poles and increasing vertex count towards the equator.

    Authoring tools (like blender) do know how the mesh was constructed and is therefore able to export the vertex and index data based on that knowledge. Without that information, a set of vertices is nothing more than a set of vertices (could be anything from points to lines to line strips to triangles to triangle strips to triangle fans or anything non primitive).