Triangle strip length
Hey again, I just hacked together a quick and dirty triangle stripper algorithm, and I'm wonder what to expect from these things. I implemented the basic algorithm that goes something like this:
The average strip length is around 8 triangles, which seems a little low to me. I might consider adding modifications to the algorithm, like choosing a random polygon not in a strip (instead of the first one in the array), then maybe even generating entire random strips for the model like 10 times with a different seed for the random number generator, then saving the one with the longest average strip length.
However, is it worth it? I don't know if 8 triangles is worth keeping, or if I should aim higher with a few modifications.
Code:
loop {
choose first polygon not in a strip
for each of the three sides of the triangle, generate a
strip in that direction
when out of polygons to add to the current strip, extend
the strip the opposite direction as far as possible too
once all three strips are generated for that polygon, store
the longest one and discard the others
} repeat until all the polygons are stored in the strips
However, is it worth it? I don't know if 8 triangles is worth keeping, or if I should aim higher with a few modifications.
Heh, I just checked a more important statistic and was very pleased  the number of needed vertex calls dropped from roughly 2,400 to around 1,200. That's what I call progress!
I'll still keep this thread around for anyone's thoughts on how much I should try improving the algorithm, if at all. I'm still pretty new at this stuff so it would probably be helpful.
I'll still keep this thread around for anyone's thoughts on how much I should try improving the algorithm, if at all. I'm still pretty new at this stuff so it would probably be helpful.
The triangle strip idea is really cool, and I was thinking about doing the same thing several years ago until I read John Carmack saying they don't bother with it. IOW, it ain't worth the hassle in the end nowadays. Triangle soup is what it's all about. For a few specialized applications it might be okay, but... Real progress is passing a pile of triangles to the video card from a VBO and being done with it. Geometry can be so complex for any given model that trying to break it down efficiently into something else other than a simple triangle (or quad for that matter) is just plain silly when the hardware manufacturers keep figuring out how to pump higher volume on a yearly basis that the effort to optimize at this point doesn't pay back real easy in the long term. How's that for a runon sentence?
There's been a lot of fuss about trianglestripping, but I've never bothered with it. IIRC, ever since the GeForce 2, you've been able to get about as much performance from a reasonably sensiblyordered triangle array as from a sequence of strips.
The problem of needing multiple draw calls is a biggie  the call to DrawElements has a large overhead, regardless of how much you're drawing. On Mac OS X the overhead seems to be greater than on other platforms, too. With TRIANGLES, you issue a single DrawElements for the entire model. With TRIANGLE_STRIP, you need to issue one for each strip. That's a lot of extra overhead, almost certainly negating any tiny benefit you might get from the stripping.
(There is an NVidia extension NV_primitive_restart that avoids the overhead, but it's not available on the Mac or on ATI cards on the PC).
On top of that, optimal triangle stripping is, I believe, an NPcomplete problem, which makes it unwieldy to solve for any reasonablysized model. There are of course heuristics to take you to a merely very good solution in polynomial time.
The problem of needing multiple draw calls is a biggie  the call to DrawElements has a large overhead, regardless of how much you're drawing. On Mac OS X the overhead seems to be greater than on other platforms, too. With TRIANGLES, you issue a single DrawElements for the entire model. With TRIANGLE_STRIP, you need to issue one for each strip. That's a lot of extra overhead, almost certainly negating any tiny benefit you might get from the stripping.
(There is an NVidia extension NV_primitive_restart that avoids the overhead, but it's not available on the Mac or on ATI cards on the PC).
On top of that, optimal triangle stripping is, I believe, an NPcomplete problem, which makes it unwieldy to solve for any reasonablysized model. There are of course heuristics to take you to a merely very good solution in polynomial time.
I read a PDF from ATi (might've been nVidia) about optimal geometry submission, which stated that you can completely disregard how many triangles you push â€“*the only thing that counts is the number of submission calls, how many batches you send. While it might be drastic, it's something to keep in mind.
Oh wow, thanks guys!
I might consider dropping the triangle strip idea, since if it doesn't offer any advantage anymore, it's pointless trying to debug the code in its current broken state. This combines the previous thread I made and this one, but here's how bad it looks at the moment:
The important thing I noticed is that the triangle in the upperright corner of the head is smoothly interpolated, so that's a good sign. I might be better off dropping the whole triangle strip idea and just replacing it with a polygon array or something.
I might consider dropping the triangle strip idea, since if it doesn't offer any advantage anymore, it's pointless trying to debug the code in its current broken state. This combines the previous thread I made and this one, but here's how bad it looks at the moment:
The important thing I noticed is that the triangle in the upperright corner of the head is smoothly interpolated, so that's a good sign. I might be better off dropping the whole triangle strip idea and just replacing it with a polygon array or something.
The trick is to use degenerate triangles. 0area triangles that you use to jump...
Consider this vertex strip
0  1  2  2  3  3  4  5
Breaks into the following triangles
0  1  2
2  2  3
3  3  4
3  4  5
The second and third triangles have 2 identical vertices. This means that they have 0 area, and don't get rendered. Hence, you can restart your triangle strip without doing the extra draw call...
The speed difference is negligible, but for a 20000 poly terrain mesh, the VRAM usage can be quite a bit smaller.
EDIT: the speed difference mainly comes from vertex cache locality. Ordering the triangles so you access the same point many times in a row WILL give a speedup, as the GPU has cached the result of the vertex processing.
Most people (including Unity) don't really bother with writing their own tristripper. Just google for tristripper and pick the best one.
Consider this vertex strip
0  1  2  2  3  3  4  5
Breaks into the following triangles
0  1  2
2  2  3
3  3  4
3  4  5
The second and third triangles have 2 identical vertices. This means that they have 0 area, and don't get rendered. Hence, you can restart your triangle strip without doing the extra draw call...
The speed difference is negligible, but for a 20000 poly terrain mesh, the VRAM usage can be quite a bit smaller.
EDIT: the speed difference mainly comes from vertex cache locality. Ordering the triangles so you access the same point many times in a row WILL give a speedup, as the GPU has cached the result of the vertex processing.
Most people (including Unity) don't really bother with writing their own tristripper. Just google for tristripper and pick the best one.
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
OpenGL ES : Dynamic calculation of triangle indices  akademiks  0  5,167 
Sep 13, 2011 07:58 AM Last Post: akademiks 

How to zoom with a status bar strip  melobrien  2  3,623 
Oct 7, 2009 04:41 PM Last Post: melobrien 

Trying to make a square... there's a triangle!  TimMcD  4  5,116 
Jun 2, 2009 03:41 PM Last Post: AnotherJake 