When should I use indexed arrays of OpenGL vertices?

Question

I'm trying to get a clear idea of when I should be using indexed arrays of OpenGL vertices, drawn with gl[Multi]DrawElements and the like, versus when I should simply use contiguous arrays of vertices, drawn with gl[Multi]DrawArrays.

(Update: The consensus in the replies I got is that one should always be using indexed vertices.)

I have gone back and forth on this issue several times, so I'm going to outline my current understanding, in the hopes someone can either tell me I'm now finally more or less correct, or else point out where my remaining misunderstandings are. Specifically, I have three conclusions, in bold. Please correct them if they are wrong.

One simple case is if my geometry consists of meshes to form curved surfaces. In this case, the vertices in the middle of the mesh will have identical attributes (position, normal, color, texture coord, etc) for every triangle which uses the vertex.

This leads me to conclude that:

1. For geometry with few seams, indexed arrays are a big win.

Follow rule 1 always, except:

For geometry that is very 'blocky', in which every edge represents a seam, the benefit of indexed arrays is less obvious. To take a simple cube as an example, although each vertex is used in three different faces, we can't share vertices between them, because for a single vertex, the surface normals (and possible other things, like color and texture co-ord) will differ on each face. Hence we need to explicitly introduce redundant vertex positions into our array, so that the same position can be used several times with different normals, etc. This means that indexed arrays are of less use.

e.g. When rendering a single face of a cube:

 0     1   o---o   |\  |   | \ |   |  \|   o---o  3     2 

(this can be considered in isolation, because the seams between this face and all adjacent faces mean than none of these vertices can be shared between faces)

if rendering using GL_TRIANGLE_FAN (or _STRIP), then each face of the cube can be rendered thus:

verts  = [v0, v1, v2, v3] colors = [c0, c0, c0, c0] normal = [n0, n0, n0, n0] 

Adding indices does not allow us to simplify this.

From this I conclude that:

2. When rendering geometry which is all seams or mostly seams, when using GL_TRIANGLE_STRIP or _FAN, then I should never use indexed arrays, and should instead always use gl[Multi]DrawArrays.

(Update: Replies indicate that this conclusion is wrong. Even though indices don't allow us to reduce the size of the arrays here, they should still be used because of other performance benefits, as discussed in the comments)

The only exception to rule 2 is:

When using GL_TRIANGLES (instead of strips or fans), then half of the vertices can still be re-used twice, with identical normals and colors, etc, because each cube face is rendered as two separate triangles. Again, for the same single cube face:

 0     1   o---o   |\  |   | \ |   |  \|   o---o  3     2 

Without indices, using GL_TRIANGLES, the arrays would be something like:

verts =   [v0, v1, v2,  v2, v3, v0] normals = [n0, n0, n0,  n0, n0, n0] colors =  [c0, c0, c0,  c0, c0, c0] 

Since a vertex and a normal are often 3 floats each, and a color is often 3 bytes, that gives, for each cube face, about:

verts   = 6 * 3 floats = 18 floats normals = 6 * 3 floats = 18 floats colors  = 6 * 3 bytes  = 18 bytes  = 36 floats and 18 bytes per cube face. 

(I understand the number of bytes might change if different types are used, the exact figures are just for illustration.)

With indices, we can simplify this a little, giving:

verts   = [v0, v1, v2, v3]     (4 * 3 = 12 floats) normals = [n0, n0, n0, n0]     (4 * 3 = 12 floats) colors  = [c0, c0, c0, c0]     (4 * 3 = 12 bytes) indices = [0, 1, 2,  2, 3, 0]  (6 shorts)  = 24 floats + 12 bytes, and maybe 6 shorts, per cube face. 

See how in the latter case, vertices 0 and 2 are used twice, but only represented once in each of the verts, normals and colors arrays. This sounds like a small win for using indices, even in the extreme case of every single geometry edge being a seam.

This leads me to conclude that:

3. When using GL_TRIANGLES, one should always use indexed arrays, even for geometry which is all seams.

Please correct my conclusions in bold if they are wrong.

Answer 1

From this I conclude that when rendering geometry which is all seams or mostly seams, when using GL_TRIANGLE_STRIP or _FAN, then I should never use indexed arrays, and should instead always use gl[Multi]DrawArrays.

No, and the reason is quite simple.

Your conclusion is based on the fact you have analysed a single quad composed by two triangles. These two triangles drawn using triangle fan/strip cannot be simplified using indexed arrays.

But try to think about a large terrain geometry. Each terrain block is drawn as a quad, using triangle fan/strip primitive. For example:

Each triangle strip in the figure has in common all vertices with adjacent triangle strips, and using indices allow to compress the geometry definition, instead of repeating vertices for each triangle strip.

---

Basically, drawing primitives (triangles, fans and strips) using indices are usefull whenever you can share most of vertices of a single primitive with another one.

Sharing the information allow to save information transmission bandwidth, but it is not the only advantage. Actually indexed arrays allow:

• Avoid the synchronization of the information belonging to the same "conceptual" vertex, specified many times
• Allow to perform the same shader operation on a single vertex instead executing many times, one for each vertex duplication.
• Furthermore, combining the use of triangle strips/fans and indices allow the application to compress the indices buffer, since the strip/fan specification requires less indices (a triangle requires always 3 indices for each face).

Indexed array cannot be used, as you have specified, whenever a vertex cannot share every information associated with it (color, texture coords and so on) with another coincident vertex.

---

Just for the sake of completeness, the size of the information necessary for the geometry specification is not the only factor wich determine the optimal rendering operation.

Infact, another fundamental factor for primitive rendering is the cache localization of the data. Badly specified geometry data (non interleaved buffer objects, long triangle strips...) causes a lot of cache misses, degrading graphic card performance.

In order to optimize the rendering operation, the vertex specification shall be reordered in a way to reuse previously specified vertices, with the most probability. In such way, the graphic card cache line can reuse previously specified vertices without fetching them from memory.