How to convert large arrays of quad primitives to triangle primitives?

Question

I have an existing system, which provides 3D meshes. The provided data are an array of vertex coordinates with 3 components (x, y, z) and an index list. The issue is that the index list is a consecutive array of quad primitives.
The system has to be make runnable with a core profile OpenGL Context first, and later with OpenGL ES 3.x, too.

I know that all the quads have all the same winding order (counter clockwise), but I have no further information about the quads. I don't know anything about their relation or adjacencies.

Since I want to use core profile Context for rendering, I cannot use the GL_QUAD primitive type. I have to convert the quads to triangles.

Of course the array of quad indices can easily be converted to an array of triangle indices:

std::vector<unsigned int> triangles;
triangles.reserve( no_of_indices * 6 / 4 );
for ( int i = 0; i < no_of_indices; i += 4 )
{
    int tri[] = { quad[i], quad[i+1], quad[i+2], quad[i], quad[i+2], quad[i+3] };
    triangles.insert(triangles.end(), tri, tri+6 );
}

If that has to be done only once, then that would be the solution. But the mesh data are not static. The data can change dynamically. The data do not change continuously and every time, but the data change unpredictably and randomly.

An other simple solution would be to create an vertex array object, which directly refers to an element array buffer with the quads and draw them in a loop with the GL_TRIANGLE_FAN primitive type:

for ( int i = 0; i < no_of_indices; i += 4 )
    glDrawElements( GL_TRIANGLE_FAN, 4, GL_UNSIGNED_INT, (void*)(sizeof(unsigned int) * 4) );

But I hope there is a better solution. I'm searching for a possibility to draw the quads with one single draw call, or to transform the quads to triangles on the GPU.

Answer 1

If that has to be done only once, then that would be the solution. But the mesh data are not static.

The mesh data may be dynamic, but the topology of that list is the same. Every 4 vertices is a quad, so every 4 vertices represents the triangles (0, 1, 2) and (0, 2, 3).

So you can build an arbitrarily large static index buffer containing an ever increasing series of these numbers (0, 1, 2, 0, 2, 3, 4, 5, 6, 4, 6, 7, etc). You can even use baseVertex rendering to offset them to render different serieses of quads using the same index buffer.

My suggestion would be to make the index buffer use GLushort as the index type. This way, your index data only takes up 12 bytes per quad. Using shorts gives you a limit of 16384 quads in a single drawing command, but you can reuse the same index buffer to draw multiple serieses of quads with baseVertex rendering:

constexpr GLushort batchSize = 16384;
constexpr unsigned int vertsPerQuad = 6;
void drawQuads(GLuint quadCount)
{
  //Assume VAO is set up.
  int baseVertex = 0;
  while(quadCount > batchSize)
  {
    glDrawElementsBaseVertex(GL_TRIANGLES​, batchSize * vertsPerQuad, GL_UNSIGNED_SHORT, 0, baseVertex​ * 4);
    baseVertex += batchSize;
    quadCount -= batchSize;
  }
  glDrawElementsBaseVertex(GL_TRIANGLES​, quadCount * vertsPerQuad, GL_UNSIGNED_SHORT, 0, baseVertex​ * 4);
}

---

If you want slightly less index data, you can use primitive restart indices. This allows you to designate an index to mean "restart the primitive". This allows you to use a GL_TRIANGLE_STRIP primitive and break the primitive up into pieces while still only having a single draw call. So instead of 6 indices per quad, you have 5, with the 5th being the restart index. So now your GLushort indices only take up 10 bytes per quad. However, the batchSize now must be 16383, since the index 0xFFFF is reserved for restarting. And vertsPerQuad must be 5.

Of course, baseVertex rendering works just fine with primitive restarting, so the above code works too.

Answer 2

First I want to mention that this is not a question which I want to answer myself, but I want to provide my current solution to this issue. This means, that I'm still looking for "the" solution, the perfectly acceptable solution.

In my solution, I decided to use Tessellation. I draw patches with a size of 4:

glPatchParameteri( GL_PATCH_VERTICES, self.__patch_vertices )
glDrawElements( GL_PATCHES, no_of_indices, GL_UNSIGNED_INT, 0 )

The Tessellation Control Shader has a default behavior. The patch data is passed directly from the Vertex Shader invocations to the tessellation primitive generation. Because of that it can be omitted completely.

The Tessellation Evaluation Shader uses a quadrilateral patch (quads) to create 2 triangles:

#version 450

layout(quads, ccw) in;

in TInOut
{
    vec3 pos;
} inData[];

out TInOut
{
    vec3 pos;
} outData;

uniform mat4 u_projectionMat44;

void main()
{
    const int inx_map[4] = int[4](0, 1, 3, 2);

    float i_quad = dot( vec2(1.0, 2.0), gl_TessCoord.xy );
    int   inx    = inx_map[int(round(i_quad))];

    outData.pos = inData[inx].pos;
    gl_Position = u_projectionMat44 * vec4( outData.pos, 1.0 );
}

An alternative solution would be to use a Geometry Shader. The input primitive type lines_adjacency provides 4 vertices, which can be mapped to 2 triangles (triangle_strip). Of course this seems to be a hack, since a lines adjacency is something completely different than a quad, but it works anyway.

glDrawElements( GL_LINES_ADJACENCY, no_of_indices, GL_UNSIGNED_INT, 0 );

Geometry Shader:

#version 450

layout( lines_adjacency ) in;
layout( triangle_strip, max_vertices = 4 ) out;

in TInOut
{
    vec3 pos;
} inData[];

out TInOut
{
    vec3 col;
} outData;

uniform mat4 u_projectionMat44;

void main()
{
    const int inx_map[4] = int[4](0, 1, 3, 2);
    for ( int i=0; i < 4; ++i )
    {
        outData.pos = inData[inx_map[i]].pos;
        gl_Position = u_projectionMat44 * vec4( outData.pos, 1.0 );
        EmitVertex();
    }
    EndPrimitive();
}

---

An improvement would be to use Transform Feedback to capture new buffers, containing triangle primitives.