Hi all. If anybody could help me with an algorithm for converting an object constructed of trianglepolygons into polygonstrips, I would be very grateful. I also suppose that this is quite an important issue in the more modern opengl implementation of games since polygon strips are faster than polygon triangles. Any exact code or pseudocode or just general tips on how to think would be much helpful. Best regards, Simpeman.

The best results I've seen so far are this.
There are very little information about his improved version.
Some source code (from another algorithm) can be found here.

Happy coding!

Quote:I also suppose that this is quite an important issue in the more modern opengl implementation of games since polygon strips are faster than polygon triangles

I dunno about opengl, but for the graphics hardware strips aren't that much faster than indexed triangle list, provided that your indices resides in the gpu's memory.
There's slightly more memory processed by the GPU compared to triangle strips, but i've reckon the overhead to be minimal (i.e < 1% slower).
Another benefit is that you don't need to send extra data to stitch together several strips.
I don't think that many commerical games use strips, the complexity of writing a good stripifier and the fact that many vertices aren't shared because of (often several layers) of texture coordinates etc makes in unfeasible (you get a lot of strips containing very few triangles).
Rather focus on writing a cache-aware optimizer for indexed triangle lists.

To hijack this thread, what algorithm do people use to optimize their inidices?
I've always used a simple brute force approach:
* Pick any triangle, store in index list.
* For every triangle that haven't been stored:
** Pick the triangle with most vertices in the cache (favour vertices that are close to being kicked out of the cache).
** Store in list
* Rearrange the actual vertices in order of appearance in the index list (to get more sequencial reads).

This doesn't give you that good results, however its alot better than not doing this at all.

With current hardware in PC there is not need to have strips anymore.
In fact cache optimized indexes triangle list are much faster than cache optimized index strips, in both OpeneGL and D3d
The reason for this is that must video card comes with at least 10 or 16 vertex cache registers that can be read randomly by the lru algorithm implemented in the driver.

A good index triangle list algorithm can do must better that one vertex per triangle, (sometime 0.8 vertex per triangle on large meshes) while the peak efficiency of a indexed triangle strip is asymptotically 1.0 (which is impossible)
These is easy to verify this with direct x 9 SDK and the optimize mesh demo programs.

However good stripping method are still useful on consoles like PS2, where there are only two FiFo register, so the more efficient method for rendering is vertex strips.

Unless you are doing this for a PS2 or for learning purpose, you will waste lots of time implementing good striping method and there will be not payoff.

Better to implement a cache friendly index triangle list with 10 or 16 lru.
This is a much easy algorithm, it come down to sorting the index list in a way that triangles are located based on the number of indices that are previously rendered.
These could be done with a 16 entry circular array where new vertices indices shift the array, and reused indices do not. The goal of the algorithm is to organize the index list such that triangle are rendered with the least amount of vertex shift of the vertex catch.

Hi all and thanks for the response!

I'm very surprised over the fact that a cache-aware indexed triangle list is faster than using strips. Is this a modern attribute? Because I think that the quake3 engine uses strips?

However, I guess I must go looking for a good indices optimisation algorithm.

Thanks again for all the help!

Quote:Original post by eq
The best results I've seen so far are this.
There are very little information about his improved version.

Unless opengl has changed I don't see that paper as being useful

it results in "generalized" strips, which the edge that the next face comes from doesn't necescarily alternate... so you could make a triangle fan with a triangle strip

... how would the graphics api know which edge the next face comes out of? [if all you send it is verticies...]


I'd suggest this page, but I've not completed any code like this before
http://www.codercorner.com/Strips.htm

Quote:Original post by _winterdyne_
Note they said 'with current hardware'.

I guess if you're playing with GF2 - GF3 you might still need to strip.

Harwared vertex register cache goes as far back as to nvidia TNT which had 16
the gforce 1 had 10,
most new cards do not even anounce it as a feature anymore.

I cache aware index triangle list and a cache aware index triangle strip in general will have the same performance on new hardware, unless the mesh is so bad that the index strip had to be patch a lot in which case the indexes triangle list will beat it.
This cases happens a lot with game level geometry were strip are so short that the extra overhead patching the mesh will make the index strip to underperformance even badly made triangle index strips.
I would not waste my time using strips unless the code is written for PS2.

These test can be verify wit the dx9 sampler demos, running the nut or any of the other meshes and comparing the performance.