• 11/27/02 05:40 PM
    Sign in to follow this  
    Followers 0

    Concatenating Triangle Strips

    Graphics and GPU Programming

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


    [size="5"]Why concatenate?

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


    [size="5"]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.

    [size="3"]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.

    [font="Courier New"][color="#000080"]B--D--F H--J--L-
    |\ |\ | |\ |\ |
    | \| \| | \| \|
    A--C--E G--I--K-[/color][/font]

    ABCDEF + GHIJKL gives:

    [font="Courier New"][color="#000080"]B--D--F--H--J--L-
    |\ |\ |\ |\ |\ |
    | \| \| \| \| \|
    A--C--E--G--I--K-

    ABCDEFGHIJKL[/color][/font]

    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)


    [size="5"]Where its really at

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

    [font="Courier New"][color="#000080"]= ABCDEF+ FGGH + GHIJKL

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

    = ... DEF + EFF + FFG + FGG + GGH + GHG + GGH + GHI + ...[/color][/font]

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


    [size="5"]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)


    [size="5"]Limitations

    For smaller strips, concatenation seems unnecessary. Let's look quickly at a less efficient case:
    [font="Courier New"][color="#000080"]
    B--D F--H
    |\ | |\ |
    | \| | \|
    A--C E--G [/color][/font]

    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.


    [size="5"]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

    [font="Courier New"]Concatenated strip:[nbsp][nbsp] ABCD + DEEF + EFGH
    [nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]ABC +BCD +... +... + EFG +FGH
    Triangle list:[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]ABC +CBD +[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp] EFG +GFH
    [nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]^[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]^
    [nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp] see how these are reversed?[/font]

    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).


    [size="5"]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.


    [size="5"]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.


    [size="5"]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.


    [size="5"]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: [email="reillyhead@hotmail.com"]reillyhead@hotmail.com[/email]

    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.
    0


    Sign in to follow this  
    Followers 0


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!


    Register a new account

    Sign in

    Already have an account? Sign in here.


    Sign In Now

    There are no reviews to display.