Concatenating Triangle Strips
by Marc Reilly

Just thought I'd write a quick tute about some stuff that I wish I'd known about before I knew it.

Why concatenate?

Basically, concatenating triangle strips helps improve batching, and in the case of indexed primitives, there are fewer wasted transformations.

More Details

DirectX's DrawIndexedPrimitive function goes something like this:

HRESULT	 DrawIndexedPrimitive(	
             D3DPRIMITIVETYPE T,	
             UINT MinIndex, UINT NumVertices,
             UINT StartIndex, UINT PrimitiveCount);

As some of you may already know, when a call is made to draw an indexed primitive(s), the entire range of vertices specified by MinIndex and NumVertices is transformed each call.

Example

Lets say we have a vertex buffer (VB) that has 500 elements, and we want to draw two triangles. The first has indices 3, 100 and 456 and the second has indices 10, 300 and 375.

If we were to draw the triangles with two separate calls to DIP the first call would transform the 4th vertex all the way up to the 457th vertex. The second call would transform the 11th vertex up to the 376th vertex. The second 365 transformations are thus performed twice.

Now, I haven't exactly picked the roundest numbers for us to work with, but it should be obvious that there are many more transformation going on than is necessary.

The solution for this case is easy: draw both triangles in the one call, i.e. fill the index buffer with 3, 100, 456, 11, 300, 375 and call DIP for 2 primitives.

This approach doesn't work if we are using triangle strips however.

B--D--F	H--J--L-
|\ |\ |	|\ |\ |
| \| \|	| \| \|
A--C--E	G--I--K-

ABCDEF + GHIJKL gives:

B--D--F--H--J--L-
|\ |\ |\ |\ |\ |
| \| \| \| \| \|
A--C--E--G--I--K-

ABCDEFGHIJKL

As we can see there are two unwanted triangles, EFG and FGH created between the two strips (Note that in a triangle strip any three consecutive verts /indices form a triangle)

Where its really at

However, we can overcome this by inserting a few degenerate triangles between the two strips:

= ABCDEF+ FGGH + GHIJKL

  B--D--F   H--J--L
=	|\ |\ |   |\ |\ |
  | \| \|   | \| \|
  A--C--E   G--I--K

= … DEF + EFF + FFG + FGG + GGH + GHG + GGH + GHI + …

Where above, the triangles in italics are degenerate (they share a vertex) and will not be visible.

To sum it up so far

When concatenating two triangle strips, we need to create degenerate triangles between the two strips. To do this, we repeat the last vertex of the first strip (the F), add the first vertex of the second strip (the G), add it again (the 2nd G), then add the second vertex of the second strip (the H), then add the second strip itself.

By doing this we've created 4 extra indices vertices to pass thru and 6 extra triangles for the device to worry about. (Does anyone know if the device would totally ignore these?) But we've enabled a greater number of primitives to be able to be rendered in the one call. (i.e. better batching, fewer unnecessary transformations)

Limitations

For smaller strips, concatenation seems unnecessary. Let's look quickly at a less efficient case:

B--D    F--H	
|\ |    |\ |	
| \|    | \|	
A--C    E--G

Concatenated strip: ABCD + DEEF + EFGH
Triangle list: ABC +CBD +EFG +GFH

Setting this up as a triangle list would have used the same number of indices, but without the 6 extra triangles.

Winding order

So far I haven't shown much consideration for winding order. DX automatically reverses the winding order for the even numbered triangles in a strip. If you cannot see why this is, compare the way the triangles are defined by a strip and list

Concatenated strip:   ABCD + DEEF + EFGH
                      ABC +BCD +… +… + EFG +FGH
Triangle list:        ABC +CBD +       EFG +GFH
                            ^                ^
                           see how these are reversed?

Because winding order is automatically reversed, we don't have to worry about it unless we start concatenating strips with odd numbers of vertices (thus faces).

Say we add strip B, with 12 tris, to strip A, with 11 tris. The 6 triangles created between A and B will mean that the first triangle of B will be automatically reversed by DX, and the second triangle of strip B, which should have been reversed, isn't, and consequently the entire strip isn't visible (and any following strips, unless there is another odd strip to restore correct winding order).

Getting around this

In theory, you can easily avoid this by replicating one of the 4 wedging indices so that there's 5 wedging indices (DEEEF or DDEEF or DEEFF) and 7 degenerate faces. This could be done at 'concatenation time', but the way I did it was to make sure that any strips always have an even number of verts, and if they should have had an odd number, duplicate the last vertex. It just seemed the easiest way at the time, because the extra vertex has to be added sometime or other, and it lets me make assumptions for other bits of my code.

Conclusion

To concatenate strips: add 4 extra vertices, 6 degenerate faces, or 5 extra verts and 7 degenerate faces if the preceding strip has an odd number of triangles.

The source code

'A good tutorial would not be a good tutorial without some code to go with it.'

This then, is not a good tutorial.

If I can figure it out, so can you.

Call Me Now

Despite the preceding comments, if anyone is having genuine difficulty, or wants to compare methods, I would encourage them to contact me: reillyhead@hotmail.com

or post a message on the gamedev directx board. Likewise I would be stoked if anybody who found this useful, or has corrections etc., contacts me.

Discuss this article in the forums

Date this article was posted to GameDev.net: 11/27/2002
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General
Sweet Snippets