Help getting vertex indices from a grid

Question

I'm folloing this little tutorial on how to get indices from a grid to build a GL_TRIANGLE_STRIP mesh http://dan.lecocq.us/wordpress/2009/12/25/triangle-strip-for-grids-a-construction/

I'm getting some of the indices in the right order but I can't workout the logic on vertices 7 and 8 as he shows in the last figure

Here is my code:

cols = 4;
rows = 4;

sizeW = 320.0f;
sizeH = 240.0f;

float spaceX = sizeW / cols;
float spaceY = sizeH / rows;

// Mesh indices
for ( int x = 0; x < cols-1; x++ ) {
    for ( int y = 0; y < rows-1; y++ ) {
        int i = y + x * rows;

        cout << "{a, b, c}: " << i << ", " << i+4 << ", " << (i+4)-3;
        cout << endl;
    }
    cout << "------------" << endl;
}
vboMesh.setMesh( mesh, GL_DYNAMIC_DRAW );

cout << "mesh number of vertices: " << mesh.getNumVertices() << endl;

And here is my output:

0, 4, 1
1, 5, 2
2, 6, 3
--------
4, 8, 5
5, 9, 6
6, 10, 7
--------
8, 12, 9
9, 13, 10
10, 14, 11

UPDATE: Following the comments, I workout another algorithm to get the indices, this is what I have so far:

// Mesh indices
int totalQuads  = (cols-1) * (rows-1);
int totalTriangles  = totalQuads * 2;
int totalIndices    = (cols*2) * (rows-1);
cout << "total number of quads: " << totalQuads << endl;
cout << "total number of triangles: " << totalTriangles << endl;
cout << "total number of indices: " << totalIndices << endl;

int n = 0;
int ind = 0;
vector<int> indices;
for ( int i = 0; i < totalIndices; i++ ) {
    //cout << i % (cols*2) << ", ";
    ind = i % (cols*2);
    if ( i % (cols*2) == 0 ) {
        n++;
        cout << n << endl;

        if ( n%2 == 1 ) {
            cout << "forward" << endl;
        }
        else {
            cout << "backward" << endl;
        }
    }

    indices.push_back( ind );
}
//cout << endl;

This code tells me when I need to go forward and when I need to go backward, by doing i % (cols*2) I get a list like 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, so in theory all I need to do now is +4 -3 going forward and +4 -5 going backward

UPDATE 2: Made some progress, these are the new results 0, 4, 1, 5, 2, 6, 3, 7, 7, 11, 6, 10, 5, 9, 4, 8, 14, 18, 15, 19, 16, 20, 17, 21 the last set of numbers is still wrong

// Mesh indices
int totalQuads      = (cols-1) * (rows-1);
int totalTriangles  = totalQuads * 2;
int totalIndices    = (cols*2) * (rows-1);
cout << "total number of quads: " << totalQuads << endl;
cout << "total number of triangles: " << totalTriangles << endl;
cout << "total number of indices: " << totalIndices << endl;

bool isGoingBackwards = false;
int n = 0;
int ind = 0;
vector<int> indices;

for ( int i = 0; i < totalIndices; i++ ) {
    if ( i % (cols*2) == 0 ) {
        ind++;
        if ( ind%2 == 1 ) {
        n = ((cols*2) - 1) * (ind-1);
            cout << "forward " << n << endl;
        isGoingBackwards = false;
        }
        else {
            n = ((cols*2) - 1) * (ind-1);
        cout << "backward " << n << endl;
        isGoingBackwards = true;
        }
    }

    indices.push_back( n );


    if ( i%2 == 0 ) {
        n += 4;
    }
    else {
        ( isGoingBackwards ) ? n -= 5 : n -= 3;
    }
}

UPDATE 3:

I finally got it! here is the new code

int n   = 0;
int colSteps = cols * 2;
int rowSteps = rows - 1;
vector<int> indices;
for ( int r = 0; r < rowSteps; r++ ) {
    for ( int c = 0; c < colSteps; c++ ) {
        int t = c + r * colSteps;

        if ( c == colSteps - 1 ) {
            indices.push_back( n );
        }
        else {
            indices.push_back( n );

            if ( t%2 == 0 ) {
                n += cols;
            }
            else {
                (r%2 == 0) ? n -= (cols-1) : n -= (cols+1);
            }
        }
    }
}

score 2 · Accepted Answer · answered Aug 10 '11 at 13:06

2

The vertex order for the first row would actually be

0 4 1 5 2 6 3 7

and then continue with

7 11 6 10 5 9 4 8
8 12 9 13 10 14 11 15

The culling of a triangle strip reverses every triangle. The reason why you have to put the 7 and the 8 in twice is that at those points the culling should actually NOT be reversed. The only possibility to achieve that is by reversing the culling twice (actually rendering one invisible polygon) so you continue with the same culling-direction as before.

answered Aug 10 '11 at 13:06

Tobias Schlegel

3,970
18
22

I see, my for loops are all wrong, all I need to do is to build and array with that sequence, ok I'll give it a try... I'm new to opengl so all this is proving to be kind of hard to digest – Ricardo Sanchez Aug 10 '11 at 13:17

score 0 · Answer 2 · answered Aug 10 '11 at 12:58

The way you do it and write it out is obviously wrong. Remember, you are generating a triangle strip and not individual triangles. I don't have code for you (but he explains the principles quite well), but you have to traverse the rows in alternating direction, meaning the top row from left to right and the next one from right to left, just as he explains in his text and figures. The logic behind the repetion of vertices (in this case 7 and 8) is, that you need to change the direction of the strip at those vertices, so you need to duplicate these vertices (and this way insert degenerate triangles, that won't draw any pixels).

Help getting vertex indices from a grid

2 Answers2