Sign in to follow this  
ElFrogo

Generalized TRISTRIP DIP PrimtiveCount equation

Recommended Posts

I was wondering if anyone had a formula for a generalized equation to compute the number of primitives to submit to DIP, given a vertex list, and index list only. (IE, trilists is gives primitivecount=numInds / 3) If, given the size of strips, we could generalize the formula to be: NumStrips * (NumIndsInStrips +2) Where, 2 equals the number of verts needed for degenerate tris. BUT, if we're trying to abstract our DIP call from the higher levels, then trying to compute the generalized equation just from vert count and ind count gets pretty difficult. I was hoping that someone out there has solved this? FROG!

Share this post


Link to post
Share on other sites
Quote:
Original post by ElFrogo
I was wondering if anyone had a formula for a generalized equation to compute the number of primitives to submit to DIP, given a vertex list, and index list only.
(IE, trilists is gives primitivecount=numInds / 3)

If, given the size of strips, we could generalize the formula to be:
NumStrips * (NumIndsInStrips +2)
Where, 2 equals the number of verts needed for degenerate tris.

BUT, if we're trying to abstract our DIP call from the higher levels, then trying to compute the generalized equation just from vert count and ind count gets pretty difficult.

I was hoping that someone out there has solved this?


FROG!


I don't know if this article helps (i have not read it yet) but you can give it a try : http://wscg.zcu.cz/wscg2004/Papers_2004_Poster/P89.pdf

Share this post


Link to post
Share on other sites
Wouldn't a DIP call for a triangle strip always use (number of indices - 2) for the primitive count? I can't think of any reason why it wouldn't.

Share this post


Link to post
Share on other sites
Well, a 4x4 terrain grid, would have 25 verts, 40 indicies, 6 degenerate indicies, 32 visible polies, and 3 degenerate polies.
giving 46 indicies, 35 polies (primitives)

46-2 = 44 != 35


For a single strip, maybe -2 would work, but when you start concantenating strips next to eachother, you have to increase the degenerate polies, which help even more to move that -2 away.

FROG!

Share this post


Link to post
Share on other sites
However the degenerates are still primitives as far as the hardware is concerned. So the DrawIndexedPrimitive call should still be told the total primitives including any degenerate.

In a triangle strip, each vertex, after the first two, makes a new triangle primitive (even if it's degenerate).

This is assuming your are wanting to know the valid value to pass into the DIP call for number of primitives. If you want to know the number of actual non-degenerate triangles, then you'll have to calculate that yourself in each case.

Share this post


Link to post
Share on other sites
BTW, mapping out a 4x4 grid on paper into a single triangle strip I end up with 32 visible triangles, 4 degenerate triangles, and a total of 38 indices. This fix exactly into the (number of indices - 2) = number of primitives for the DIP call.

Share this post


Link to post
Share on other sites
where's that math coming from?

a 4x4 grid, would yield

4 strips of 8 polies a piece. (total 32 polies)
4 sets of 10 indicies a piece. (Gives 40 indicies)
3 degenerate triangles (not adding the dangler at the end of the grid)
(giving 46 indicies)

?

FROG!

Share this post


Link to post
Share on other sites


The larger numbers are the triangles, the smaller numbers are the indices. The smaller index numbers are inside the triangle they form (except the degenerate ones). Triangles 9, 18, 19, and 28 are degenerate.

When you make it into one strip you don't have 10 indices per row. You have 10 in row one, and 8 in each of the other 3, plus the 4 degenerates. That's 38 indices and 36 primitives (32 visible, 4 degenerate).

Share this post


Link to post
Share on other sites


This is an alternate way to do the strip which more closely matches your decription. It is basically taking the 4 seperate strips and combining them without modification. However, when you do this then you have to insert some indices along with the 2 indices at the beginning of the 2nd, 3rd, and 4th strips form 4 degenerate triangles each. So, triangles 9, 10, 11, 12, 21, 22, 23, 24, 32, 33, 34, and 35 are degenerate.

This one has 44 total triangles, 12 degenerate, and 46 indices. So it's still number of indices minus one equals the primitive count.

[Edited by - reltham on August 3, 2005 6:47:42 PM]

Share this post


Link to post
Share on other sites
Okay, I fixed my image and test above for the second version.

So, indices 9, 10, & 11 are for the degenerate labeled 9.
Indices 10, 11, & 12 are for the degenerate labeled 10.
Indices 11, 12, & 13 are for the degenerate labeled 11.
Indices 12, 13, & 14 are for the degenerate labeled 12.

And the same for the other rows.


The first version is still correct and valid. It's also less indices and primitives, but it's not a combination of 4 strips like you describe. Also, it is a touch more vertex cache friendly.

[Edited by - reltham on August 3, 2005 6:21:12 PM]

Share this post


Link to post
Share on other sites
So, I was under the assumption you only needed to add 2 extra indicies for a degenerate triangle? From what your post says, I need 3? Where do those indicies go for your first diagram?

Thanks for the help BTW

FROG!

Share this post


Link to post
Share on other sites
If you are starting with seperate and complete strips, then you are only adding 2 indices between each strip to connect them together, but they end up forming 4 degenerates when combined with the 2 indices that start the strip you are attaching.

So in my diagram indices 1 thru 10 make up the first strip and indices 13 thru 22 make up the second strip (you could renumber 13-22 as 1-10 and it would be a valid strip on it's own). Adding indices 11 and 12 between them connects them together. However, now that they are a single strip indices 13 and 14 are no longer the "starting 2" of the strip and thus end up making degenerate triangles in conjunction with the added indices (that connect the two strips).

The first version doesn't need as many. All of them are there in that image.

Indices 9, 10, & 11 make up the degenerate labeled 9 that is between the first and second row (the second row builds on the opposite direction, right to left instead of left to right like the first row).

Indices 18, 19, & 20 make up the degenerated labeled 18, and then indices 19, 20, and 21 make up the degenerated labeled 19.

Finally, indices 28, 29, & 30 make up the degenerated labeled 28.

So you end up with only 4 extra indices making for degenerate triangles. You do have to build your strip differently, winding back and forth, but this is a more efficient way that is also more vertex cashe friendly (since your shared vertices are accessed closer together by the indices).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

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

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

Sign in to follow this