I’m working with WebGL and as such, I’m discovering some quirks about OpenGL ES 2.0. I have been using display lists as long as I’ve been using OpenGL, but WebGL doesn’t have support for them. So, I’m buckled down and familiarized myself with vertex buffer objects, the (perhaps better) alternative.

At any rate, I need to render a regular 2D grid, and as it doesn’t support quads, either, I was forced to use triangles. In the interest of getting things running, I just provided a wasteful list of discrete triangles. This is wasteful because it references many more vertices than necessary – I ended up declaring $$6n^2$$ vertices when in reality there are only $$n^2 + n + 1$$ unique vertices. This worked fine, until I wanted to increase the resolution. It turns out, JavaScript doesn’t like large arrays.

That’s fair, because the implementation was pretty wasteful. A triangle strip was the best choice anyway. A triangle strip is a highly compact form of representing a mesh. For $$n$$ triangles, it requires only $$n + 2$$ vertices defined. Well, that’s roughly true. We’ll see another case in a minute. It’s useful when many triangles share vertices, and perhaps I’ll let Wikipedia’s explanation stand.

It wasn’t immediately obvious how to define a grid out of a single triangle strip and so I got out a pen and paper. I kept in mind a neat trick: if in a triangle strip, you need to skip the use of a vertex, a vertex can be introduced twice in a row. That is, if I need triangles (6, 3, 7) and (7, 11, 6) in that order, you can just make your strip with 6, 3, 7, 7, 11, 6. You can think of it as if there are two triangles created (3, 7, 7) and (7, 7, 11), but they have no area and a degenerate case – a line. Furthermore, these lines lie on triangles already defined.

Perhaps the obvious choice doesn’t yield any results, and in fact in this layout, it can’t be easily done (you have to have vertices appear three times in a row):

This is a bad idea for a topology if you want to use a single triangle strip.

To better convince yourself, try to come up with a good way to put this in a triangle strip. I’ll make the case that it is pretty difficult with a claim from graph theory. In order for a triangle mesh to be turned into a triangle strip, each consecutive triangle must share an edge. We can then think of the mesh as a connectivity graph (the dual of the mesh) and then the problem will emerge more clearly:

The dual graph of the bad idea.

To make the triangle strip “nice,” we ought to be able to visit each node once and exactly once. There’s good and bad news in this – it’s the same problem as finding a Hamlitonian path which is NP complete. The good news is that if we find a solution to our small problem, we’ve found a solution to all such grids (with arbitrarily many triangles). Note that we don’t need an Eulerian path.

If you stare long enough at the above connectivity graph, you’ll hopefully convince yourself that there’s no way to traverse it visiting each node once and exactly once. Go ahead and try – it’s pretty infuriating.

Looking at how we would traverse one strip (triangles a, b, c, d, e and f) actually gives us a clue. A triangular strip for that case would be 0, 4, 1, 5, 2, 6, 3, 7, and happiness ensues and we should move onto the next row. Unfortunately, in the context of this new row, we’re starting in a different place (topologically) than we started with the first strip. Vertex 0 has two connected neighbors in its row – 1 and 4. Vertex 7 has three in its row: 6, 10 and 11. It turns out we can change up the topology to remedy this simply:

A much better topology for drawing this with a single triangle strip.

A much better topology for drawing this with a single triangle strip.

We can also see that this is a much better solution by looking at this new graph’s dual:

The dual of the better topological choice.

You can probably easily find a Hamlitonian path in this case. But this still leaves us with how to determine the vertex orderings. We decided that the first row ought to be 0, 4, 1, 5, 2, 6, 3, 7, but moving on from there we need a bit of “glue” to move onto the next row. We insert 7 again, and then continue on from there: 7, 11, 6, 10, 5, 9, 4, 8. A bit more glue for the third row: 8, 12, 9, 13, 10, 14, 11, and 15:

An alternative representation of the vertex ordering

Looking at the indices from the first row, starting at 0, we can get the next index by alternately adding 4 and then subtracting 3. On the next row, we’ll continue to add 4, but then alternately subtract 5. The 4 is derived as being the number of vertices on a side (if there are $$n$$ divisions, then there are $$n+1$$ vertices), and the 3 and 5 are explained by the fact that we need to change columns in the mesh, by one step at a time.

An clean implementation is not trivial, but not extremely difficult. In terms of results, I can fit more than 4 times as many vertices into the mesh than with a per-triangle implementation. And to boot, it has cut the work of the vertex shader a great deal.

Tagged with:
 

10 Responses to “Triangle Strip for Grids – A Construction”

  1. jeckil says:

    One of the best tutorials I have ever seen on the theory behind the topic.

    One thing I don’t understand yet:

    “the 3 and 5 are explained by the fact that we need to change columns in the mesh, by one step at a time.” Can you elaborate on this more please? what do the columns mean?, one step at a time?

    Thanks a lot. :)

  2. dan.lecocq says:

    Here columns refers to the columns of vertices, like (0, 4, 8, 12) or (2, 6, 10, 14). Suppose we have n vertices in a row (in this case, 4) and we are at vertex indexed a (let’s say 5). Then a + 4 would be the vertex below it, and a – 4 would be the vertex above it.

    If instead of adding or subtracting n = 4 from a, we added or subtracted n + 1 = 5, we would get the vertex in the row below it, and one column to the right. For example, vertex a + 5 = 10 is diagonal from a in this fashion. Using n – 1 = 3 does the same thing, except for one column to the left (a + 3 = 8 is one row down from a and one column to the left).

    I hope this clarifies a little bit!

  3. Noa says:

    It was very helpful for me to, thanks. I implemented it, and realized at some point that the normals are inverted at every change of row (because I’m setting normals per vertex). I had to add some more “glue” every time. So in the previous explanation, I inserted “7″ twice, and got 0, 4, 1, 5, 2, 6, 3, 7,7,7,8, 12, 9, 13, 10, 14, 11, and 15. That way the normal stays in the right orientation.

    Noa

  4. dan.lecocq says:

    I hadn’t noticed any funny business with the normals, but that’s good to know! I wonder if it was because I was using my own shader — were you using the fixed-function pipeline?

  5. Noa says:

    Dan,

    Yes I was using the FFP, pre-computing the normals per vertex on cpu. Because the orientation of the triangles on the triangle strip alternates, my normals where miss-oriented on every odd row. Because I need to compute normals per vertex, I had to modify the algorithm and add some glue.

  6. John says:

    Thanks for trying to cheer me up. I still prefer display lists in more ways than one. It’s a shame they’re trying to bury such a flexible and powerful feature. VBOs are just a crippled version of the display list.

  7. John says:

    Correction: it looks like gl.NewList (); is available. Was it added after this article? Feel free to skip my post or update the article if display lists are truly currently supported in webgl.

    Thanks

  8. dan.lecocq says:

    As far as I know, WebGL doesn’t have display lists. At least in Chrome and WebKit/Safari, I didn’t find a gl.NewList(). I’d be surprised if there were, as it’s supposed to essentially follow the OpenGL ES 2.0 spec, which doesn’t include display lists.

    In what environment did you find gl.NewList()? You’ve make me curious!

  9. Ricardo Sanchez says:

    Dan excellent tutorial!

    I am new to opengl in general and I am struggling to implement this, I start a stackoverflow topic on the subject and I wonder if you will be able to have a look and let me know and assist on my implementation, any help will be much appreciated

    Here is the link
    http://stackoverflow.com/questions/7011017/help-getting-vertex-indices-from-a-grid

    Thanks

  10. Nathan Upchurch says:

    Excellent tutorial! Wish I would have read it sooner!

Leave a Reply