triangle strip

Synopsis

A triangle strip is a speed- and space-efficient way of storing a set of triangles on a computer, usually for computer graphics.

Detail

Take, for example, a modern graphics processor, capable of drawing millions of polygons per second. One of the major limiting factors is not the triangle-drawing ability of the processor; without triangle strips often the limiting factor is the data bus between the graphics processor and the memory storing the triangles¹. Triangle strips reduce the memory bandwidth needed by a graphics processor by not transmitting redundant information. Each triangle is comprised of three separate vertices, but in many cases you can find a set of topologically connected triangles which share common edges. Triangle strips exploit this fact. So what does this mean?

Consider a simple square, which would be stored as two triangles:

0--1
| /|
|/ |
2--3

Thus, the square is made up of the triangles (0, 1, 2) and (1, 2, 3)². A naive storage format for this square would just store both those triangles, costing 6 (2 x 3) vertices. Notice how in both of those triangles, the edge (1, 2) is specified. A triangle strip simply stores that square as (0, 1, 2, 3), where the two constituent triangles share the middle edge (1, 2). In a triangle strip of length N, there are (N-2) triangles; with each triangle being a vertex and its two previous vertices. This means the square is now stored in 4 vertices, and if we wanted to add another connected triangle (sharing edge (2,3) with triangle (1, 2, 3)) we only need to add an extra vertex:

0--1
| /|
|/ |
2--3
| /
|/
4

This is extremely space efficient; in a perfect strip each extra triangle costs us only another vertex.

If you imagine a typical polygonal mesh, for example a triangulated teapot, you can see that the majority of the triangles share edges with other triangles around them. This makes finding long strips of connected triangles relatively easy, and indeed such shapes can be stored very efficiently using strips.

Given an arbitrary polygon soup, finding the perfect set of triangle strips which represent it is a difficult problem. There is a potentially infinite number of different strips you could choose to represent an object, but for efficiency's sake the strips used must be as long as possible. In fact, this process (known as triangle stripping or sometimes stripification) in an NP complete problem. However, armed with some simple heuristics you can usually come up with a near-perfect solution. There are a number of GPL libraries around for performing stripification, including a particularly good one called Stripe.

As you've seen, strips are space-efficient; it takes less vertices to specify a mesh using strips. However, it is also speed-efficient. In rasterizing a triangle, a graphics processor has to perform a fair degree of calculations, particularly if it supports something like programmable vertex shaders. When rendering a strip, if the previous two vertices are cached, then after the first triangle has been drawn, the next only requires one extra vertex calculation.

There's another trick that can be used; normally there's a set up cost associated with starting a strip on modern graphics hardware. So reducing the total number of triangle strips is beneficial too - this can be achieved using degenerate (zero area) triangles. Given two strips, you can stitch them together by duplicating the last vertex of the first strip, and the first vertex of the second strip, and then concatenating them. Consider two separated squares:

0--1     4--5
| /|     | /|
|/ |     |/ |
2--3     6--7

These squares can be expressed as a single triangle strip (0, 1, 2, 3, 3, 4, 4, 5, 6, 7) with four degenerate triangles (2, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 5). As the triangles have zero area (which is quick to detect), they usually cost very little to process, and in most circumstances these long concatenated strips are more efficient than lots of small strips³.

Any task involving large numbers of triangles can benefit from triangle stripping, for example collision detection, or ray tracing.

1. Indexing vertices and storing vertex data separately to topology information is another common way of reducing the bandwidth, which is compatible with stripping.
2. Usually triangles are stored with a consistant winding order, I ignore winding issues here for clarity. Where winding order is important (e.g. on graphics processors) note that every other triangle's winding order is opposite, and this is taken into account by the hardware.
3. Some specialist applications (e.g. the PlayStation 2's rendering system) store an extra piece of information with each vertex: whether that vertex and its previous two vertices should be considered a valid triangle. This allows an even more efficient way of stitching triangles together; you can simply concatenate strips together and ensure the first two vertices are not marked as valid triangles. For example, using an asterisk to mark valid triangles, the two squares can be expressed as (0, 1, 2*, 3*, 4, 5, 6*, 7*) using such a system.