Apple recommends to use OpenGL GL_TRIANGLE_STRIP and VBOs for iPhone geometry, so when I started looking into terrain generator, the very first question I asked myself was how to programmatically generate a rectangular mesh using single GL_TRIANGLE_STRIP.  After a bit of research and coding I wrote this simple mesh generator:

An Xcode project for the iPhone is provided with full src code, which you can use in your own project. The mesh generator provides two APIs (see mesh.h): one which takes number of verticies in column and row, and the other one which takes desired triangle count. The core code is written in plain C, so the project should be very easy to port over to GLUT or any other framework.

A mesh, for our purposes is defined as a rectangular piece of geometry, defined by its vertices. A very simple example of our mesh is a 3×3 rectangle defined by 9 vertices (8 triangles) – see Fig. 1:

Such mesh is pretty easy to generate (see meshCreate in mesh.c) and is stored in an array of MeshVertex structures, with 3 GLfloat per entry. Those vertices will be later uploaded to GPU using glBufferData (see _meshCreate in pen.c). Next we need to create an array of vertex indicies that will tell the GPU how to construct our triangles – see Fig. 2:

Looking at Fig. 2a and Fig. 2b it’s easy to see how the indicies for strips are generated. Triangle #1 is defined by indicies 1, 4 and 2, triangle #2 is defined by indicies 4, 2 and 5, and so on… This is what makes the triangle strips so efficient – the 1st triangle requires 3 vertices (9 GLfloats), but to define the next one, all we need is just one additional explicit vertex (3 GLfloats). The indicies are stored in an array of GLushort. The implications of using GLushort, for storing the indicies is that the mesh can not have more than 2^16 (ie. 65536) entries. A good optimization here would be to use the smallest, but large enough type to hold our indicies (ie, GLushort or GLubyte).

Now that we know how to create strips that define mesh rows, we need to figure out how to stitch the strips together to create one long strip – see Fig. 3:

Our task here is to tell the GPU how to jump from the end of one strip to the beginning of the next one. The solution is to insert degenerate (zero area) triangles – such triangles will not be drawn by the GPU. A degenerate triangle is defined by 3 verticies, at least 2 of which are the same. In our case, we will repeat last index of the previous strip and first index of the next one. By inserting 2 extra indicies we create 4 additional (degenerate) triangles, ie:

- triangle #1 defined by indicies: 3, 6, 6

- triangle #2 defined by indicies: 6, 6, 4

- triangle #3 defined by indicies: 6, 4, 4

- triangle #4 defined by indicies: 4, 4, 7

That’s it. To render the mesh all we need to do is to call glDrawElements once per frame. Such a mesh can be used to render more than just terrain, we could even use it to wrap around a sphere if we wanted to. Too bad OpenGL has no such thing as “GL_TRIANGLE_MESH” - it wouldn’t even need the explicit index array, if it could assume only rectangular meshes.

While researching this topic I found the following discussions useful: http://www.gamedev.net/community/forums/topic.asp?topic_id=208950 http://www.gamedev.net/reference/articles/article1871.asp

For a quick overview of GL_TRIANGLE_STRIP please see this wikipedia entry; the advantage here is that triangle strips save VRAM and lay out vertices in optimal format for the GPU, both of which contribute to higher performance (this optimization is not as important for desktop GPUs).

For a quick overview of VBOs please see this wikipedia entry; the theory here is that we eliminate copying of vertices from RAM (CPU) to VRAM (GPU) whenever we need to draw them, by uploading the verticies only once, which again helps the performance (today’s iPhone/iPods use integrated memory, which means that this optimization is not currently as important).