Generate a plane with triangle strips

Question

What would be the best algorithm to generate a list of vertices to draw a plane using triangle strips?

I'm looking for a function which receives the plane's width and height and returns a float array containing correctly indexed vertices.

width represents the number of vertices per row.

height represents the number of vertices per column.

float* getVertices( int width, int height ) {
    ...
}

void render() {
    glEnableClientState(GL_VERTEX_ARRAY);
    glVertexPointer(3, GL_FLOAT, 0, getVertices(width,heigth));
    glDrawArrays(GL_TRIANGLE_STRIP, 0, width*height);
    glDisableClientState(GL_VERTEX_ARRAY);
}

Coveney

Are there any restrictions? I mean, you could generate a plane with 4 vertices. :) – Autopilot

Need more information. A rhombus, parallelogram, rectangle, trapezoid, and square all define a plane, but each would be composed of different triangular strips. Angle information is needed or the ability to calculate an angle in order to draw triangles. Are there assumptions you didn't tell us about? – Splore

It's just a square, but it must be sub-divided into many triangles so that i can play with vertex position and change the plane shape. WIDTH represents the number of vertices per row, and HEIGHT the number of vertices per column. – Coveney

You might want to look at stackoverflow.com/search?q=tesselation and flipcode.net/archives/Efficient_Polygon_Triangulation.shtml – Pimpernel

And in addition have a look at this: chadvernon.com/blog/resources/directx9/… Not OpenGl, but still useful I guess – Autopilot

Answer 1

Thanks you all. I've coded this. Is it correct? Or is the generated strip somehow wrong?

int width;
int height;
float* vertices = 0;
int* indices = 0;

int getVerticesCount( int width, int height ) {
    return width * height * 3;
}

int getIndicesCount( int width, int height ) {
    return (width*height) + (width-1)*(height-2);
}

float* getVertices( int width, int height ) {
    if ( vertices ) return vertices;

    vertices = new float[ getVerticesCount( width, height ) ];
    int i = 0;

    for ( int row=0; row<height; row++ ) {
        for ( int col=0; col<width; col++ ) {
            vertices[i++] = (float) col;
            vertices[i++] = 0.0f;
            vertices[i++] = (float) row;
        }
    }

    return vertices;
}

int* getIndices( int width, int height ) {
    if ( indices ) return indices;

    indices = new int[ iSize ];
    int i = 0;

    for ( int row=0; row<height-1; row++ ) {
        if ( (row&1)==0 ) { // even rows
            for ( int col=0; col<width; col++ ) {
                indices[i++] = col + row * width;
                indices[i++] = col + (row+1) * width;
            }
        } else { // odd rows
            for ( int col=width-1; col>0; col-- ) {
                indices[i++] = col + (row+1) * width;
                indices[i++] = col - 1 + + row * width;
            }
        }
    }
    if ( (mHeight&1) && mHeight>2 ) {
        mpIndices[i++] = (mHeight-1) * mWidth;
    }

    return indices;
}

void render() {
    glEnableClientState( GL_VERTEX_ARRAY );
    glVertexPointer( 3, GL_FLOAT, 0, getVertices(width,height) );
    glDrawElements( GL_TRIANGLE_STRIP, getIndicesCount(width,height), GL_UNSIGNED_INT, getIndices(width,height) );
    glDisableClientState( GL_VERTEX_ARRAY );
}

With width=4 and height=4 this is what I got:

And here I'm modifying some vertex height:

Coveney

Well, you might be able to answer this yourself. Does it work as you expect or are there any problems? If you don't render the wireframe, but solid triangles, does it still look fine? – Autopilot

Note: I've fixed getIndices function, it wasn't creating correct strips for odd heights – Coveney

Note: thaks for reputation, i've uploaded photos! – Coveney

Are you sure that there is not a problem in the edge of the surface? – Prendergast

yup, there are artifacts on the edges. – Prendergast

Can you also explain this part? if ( (mHeight&1) && mHeight>2 ) { mpIndices[i++] = (mHeight-1) * mWidth; } – Cleanly

Can you please explain what iSize is? – Darryl

Following my thought process, I found the getIndicesCount() function to be different.. can somebody tell me if is it right? int getIndicesCount( int width, int height ) { return (2*width) + ((2*width)*(height-2)); } – Eisteddfod

VVZen, it's not. Using your formula, for i.e 4x3 grid you would get 16 indices, when really you should need only 15. For i.e 3x4 grid you would get 18 indices when you really would need only 16. I'm using this formula: "numStripes = height - 1", "numIndices = numStripes * (2 * width - 1) + 1;". (p.s. NIGO's formula is correct too) – Collaborationist

Steve M. Bay, because in the way how (odd row) columns are handled in NIGO's code (the "for loop" from right to left) will skip one indice. It will be added later when/if (even row) columns are handled. That last line just makes sure that missing indice is added. If grid's height value is odd, this mean we will be missing one indice - so just add it. – Collaborationist

There is a problem with this approach. At any 'row' end (at the vertical boundary), the indices are repeated in a straight line, so unless it's a flat surface at the edges, it's going to create extra triangles. @Coveney : You should be able to see that by adding some height to some of the boundary vertices rather than the internal ones. – Survival

Sorry what are mHeight, mWidth, mpIndices? – Gilly

Please acknowledge us about the mHeight and mWidth – Gerardogeratology

Answer 2

Here is some code that does this (not tested, but you get the idea at least):

void make_plane(int rows, int columns, float *vertices, int *indices) {
    // Set up vertices
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < columns; ++c) {
            int index = r*columns + c;
            vertices[3*index + 0] = (float) c;
            vertices[3*index + 1] = (float) r;
            vertices[3*index + 2] = 0.0f;
        }
    }

    // Set up indices
    int i = 0;
    for (int r = 0; r < rows - 1; ++r) {
        indices[i++] = r * columns;
        for (int c = 0; c < columns; ++c) {
            indices[i++] = r * columns + c;
            indices[i++] = (r + 1) * columns + c;
        }
        indices[i++] = (r + 1) * columns + (columns - 1);
    }
 }

The first loop sets up the vertex array in a standard rectangular grid. There are R*C vertices.

The second loop sets up the indices. In general, there are two vertices per square in the grid. Each vertex will cause a new triangle to be drawn (with the previous two vertices), so each square is drawn with two triangles.

The first and last vertex at the start and end of each row is duplicated. This means there are two triangles of zero area (degenerate triangles) between each row. This allows us to draw the entire grid in one big triangle strip. This technique is called stitching.

Dodd

Answer 3

none of the code above gives a correct mesh generation. A very good article about how to make a strip of triangles on a simple plane: http://www.learnopengles.com/android-lesson-eight-an-introduction-to-index-buffer-objects-ibos/

Here is my test code that actually tested and fully working:

int plane_width = 4; // amount of columns
int plane_height = 2; // amount of rows

int total_vertices = (plane_width + 1) * (plane_height + 1);
planeVert = new CIwFVec2[total_vertices];
memset(planeVert, 0, sizeof(CIwFVec2) * total_vertices);

int numIndPerRow = plane_width * 2 + 2;
int numIndDegensReq = (plane_height - 1) * 2;
int total_indices = numIndPerRow * plane_height + numIndDegensReq;

planeInd = new uint16[total_indices];

make_plane(plane_width, plane_height, planeVert, planeInd);

...

void make_plane(int width, int height, CIwFVec2 *vertices, uint16 *indices)
{
width++;
height++;

int size = sizeof(CIwFVec2);
// Set up vertices
for(int y = 0; y < height; y++)
{
    int base = y * width;
    for(int x = 0; x < width; x++)
    {
        int index = base + x;
        CIwFVec2 *v = vertices + index;
        v->x = (float) x;
        v->y = (float) y;
        Debug::PrintDebug("%d: %f, %f", index, v->x, v->y);
    }
}

Debug::PrintDebug("-------------------------");

// Set up indices
int i = 0;
height--;
for(int y = 0; y < height; y++)
{
    int base = y * width;

    //indices[i++] = (uint16)base;
    for(int x = 0; x < width; x++)
    {
        indices[i++] = (uint16)(base + x);
        indices[i++] = (uint16)(base + width + x);
    }
    // add a degenerate triangle (except in a last row)
    if(y < height - 1)
    {
        indices[i++] = (uint16)((y + 1) * width + (width - 1));
        indices[i++] = (uint16)((y + 1) * width);
    }
}

for(int ind=0; ind < i; ind++)
    Debug::PrintDebug("%d ", indices[ind]);
}

Premolar

also, if you need UV coordinates: CIwFVec2 *uv = pUV + index; uv->x = v->x / (width-1); uv->y = v->y / (height-1); – Premolar

There is nothing wrong with NIGO's code. Regarding the "An Introduction to Index Buffer Objects (IBOs)" Note that there is a bug! Triangle stip generation will fail for w<h grids. (There are some places where you need to replace "yLength" with "xLength", read post's comments on how to fix that) In addition, that method would require much more indices because more degenerate triangles are used there just to maintain the same triangle direction. Plus, some degenerate triangles would be visible in wireframe if your grid is not flat. – Collaborationist

Answer 4

I was doing something similar and using the first two answers I have come up with this (tested, C#, XNA)

        // center x,z on origin
        float offset = worldSize / 2.0f, scale = worldSize / (float)vSize;

        // create local vertices
        VertexPositionColor[] vertices = new VertexPositionColor[vSize * vSize];

        for (uint z = 0; z < vSize; z++) {
            for (uint x = 0; x < vSize; x++) {
                uint index = x + (z * vSize);
                vertices[index].Position = new Vector3((scale*(float)x) - offset, 
                                                       heightValue, 
                                                       (scale*(float)z) - offset);
                vertices[index].Color = Color.White;
            }
        }

        // create local indices
        var indices = new System.Collections.Generic.List<IndexType>();

        for (int z = 0; z < vSize - 1; z++) {
            // degenerate index on non-first row
            if (z != 0) indices.Add((IndexType)(z * vSize));

            // main strip
            for (int x = 0; x < vSize; x++) {
                indices.Add((IndexType)(z * vSize + x));
                indices.Add((IndexType)((z + 1) * vSize + x));
            }

            // degenerate index on non-last row
            if (z != (vSize-2)) indices.Add((IndexType)((z + 1) * vSize + (vSize - 1)));
        }

This is easily convertable to c++, just make indices an std::vector.

The notable features for my solution are that: a) It doesn't need to change the winding order per substrip - adding two points creates two degenerate triangles, so the order is correct for the next substrip. b) You should conditionally add the first and last dg triangle vertices.

Diorio