Generating Formulas for glDrawElements with Tile Grids

glDrawElements can be used to save you from uploading a lot of vertices to the GPU.

Many 2D games use tiles, which are rendered in grids.

I have done some experimenting with the indices array. For a 3x3 grid of tiles, the indices for glDrawElements are as follows:

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

Already, calculating this is incredibly tedious and the grid is only a 3x3 one.

The proportion of vertices used with glDrawElements for power of two grids is (s + 1)^2 / s^2 * 6, where s is the grid width or height. Here are some grid sizes and savings:

• 10x10 : <0.2
• 30x20 : <0.18
• 50x50 : >0.17
• 100x100 : 0.17

How could one generate an array of indices in the correct order for a grid of tiles, of either width w and height h (or size s for power of two grids if that's more simple)?

Well if you want to generate the indices it really depends on how you store the vertices. But lets say you store it like I show below. So vertex 0 is the bottom left and vertex 24 is the upper right.

The bottom triangle 015, notice the pattern that 1=0+1 and 5=0+(4+1). So you can iterate through all the bottom left vertices and calculate the indices. Generally speaking with this format, give me any number V representing the bottom left vertex in the tile and your three indices are {V,V+1,V+(w+1)} for the bottom triangle. For the upper triangle you notice a similar pattern {V+1,V+(w+2),V+(w+1)}. Make sure you don't go outside the grid.

Example code.

int[] ind = int[w*h*6]; // The indices
int j = 0;

// Remember to draw all triangle counter-clockwise
for (y = 0; y < h; y++) {
for (x = 0; x < w; x++) {
int v = y*w+x;

// Bottom triangle in tile
ind[j]   = v;
ind[j+1] = v+1;
ind[j+2] = v+w+1;

// Top triangle in tile
ind[j+3] = v+1;
ind[j+4] = v+w+2;
ind[j+5] = v+w+1;
j += 6
}
}


Now just pass the ind[] array to OpenGL as an element buffer. If you store the vertices in a different order you will have to change the formulas a bit, but the idea is the same. Hopefully this is what you wanted.

• The code is slightly broken: use ind[j++] to add to the array instead of the j += 6 at the end to fix it. – Lolums Nov 22 '15 at 17:34
• @Lolums Sorry about that, haven't gotten to test the code. Fixed it now. I personally prefer this format, but ind[j++] should work as well, yeah. – Christer Nov 22 '15 at 17:41
• Thanks! The formula doesn't quite work though. After switching around the 4th and 5th insertions, it works as expected with w >= 1 but only if h = 1. – Lolums Nov 22 '15 at 17:50
• Well I don't see why this would happen. The insertion order doesn't matter per triangle, it only affects which face of the triangle is the front. If you need more help it would be nice if you posted a link to your code. – Christer Nov 22 '15 at 18:06
• Oh, I understand after analysing it for a bit. Yeah, it works now. Thanks a bunch! – Lolums Nov 22 '15 at 18:12