## Triangle strip length

Member
Posts: 161
Joined: 2005.07
Post: #1
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:
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```
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.
Member
Posts: 161
Joined: 2005.07
Post: #2
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.
Moderator
Posts: 3,591
Joined: 2003.06
Post: #3
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 run-on sentence?
Luminary
Posts: 5,143
Joined: 2002.04
Post: #4
There's been a lot of fuss about triangle-stripping, 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 sensibly-ordered 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 NP-complete problem, which makes it unwieldy to solve for any reasonably-sized model. There are of course heuristics to take you to a merely very good solution in polynomial time.
Oldtimer
Posts: 834
Joined: 2002.09
Post: #5
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.
Member
Posts: 161
Joined: 2005.07
Post: #6
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 upper-right 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.
Member
Posts: 47
Joined: 2004.07
Post: #7
The trick is to use degenerate triangles. 0-area 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.

Nicholas Francis
http://www.otee.dk