PDA

View Full Version : the best way to build triangle strips



HamsterofDeath
12-31-2002, 05:38 AM
my idea :
try every triangle as a starting point (number of triangles), try every drawing order that is counter clockwise (3), remember the longest strip, kill all stripped polys, and go on until nothing is left.
per strip i would need triangles number*3 cycles.
is there a better (does not need to be faster) way ?

titan
01-03-2003, 08:59 AM
There are other things to keep in mind such as vertex cache sizes. Stripping info: http://www.ams.sunysb.edu/~xxiang/strip.html http://www.cs.sunysb.edu/~stripe/

Of course there is nvidia's tristripping library that is already written http://www.nvidia.com/view.asp?IO=nvtristrip_library
and this library as well (the one I use as I found it much better than nvidia's) http://users.pandora.be/tfautre/softdev/

GPSnoopy
01-05-2003, 01:32 PM
If I understand correctly, basically what you want to do is to build one strip at the time, building the longest possible strip at that moment.

The algorithm you describe isn't the most optimized to achieve this method. (it has a complexity of O(nē))
I already tried it when working on Tri Stripper (last url given by titan, thanks titan http://www.opengl.org/discussion_boards/ubb/wink.gif)

But you can optimize two big points to get a nice O(n.log(n)) algorithm:
- You don't have to try every possibility on every triangle, just a few of them. When building a strip you cover more than one triangle, so you could for example mark the triangles that are already part of a strip in a particular orientation (3 different orientations per triangle).
That is if you take a triangle and extend it in one direction; you can optimize a little further by extending in both directions but that's a little more complicated and gives 6 different orientations.

- When building a "final" strip you're eliminating a number of triangles and thus a number of previously possible candidate strips.
But other triangles and strips are left unmodified.
So what you can do is to find all possible longest strips using the method described above and put them in a priority queue (heap).
Then when building the longest strip of the moment you only have to re-organize the concerned strips in the heap; which is just, most of the time, splitting one strip into two strips because a triangle as been taken out.


I had a beta version of this algorithm up and running, and compared it against other algorithms. The conclusion is that it has a lot of disadvantages and not a lot of advantages:

It's hard to program. Not impossible but there are a lot of things to do if you want a fully optimized version.

A non-fully optimized version will be slow. My version was about 10 times slower than other algorithms I tried. But I think that if it's optimized correctly it should be nearly as fast. But is it worth the effort?

The gain in efficiency at the end is small compared to "dumber" but faster algorithms. Compared to an algorithm that randomly chooses the first triangle of the next strip I went from like 57fps to 63fps (the original un-striped model doing 30fps), which isn't such a great improvement.

The thing is that this greedy algorithm will give you the longest possible strip at each stage, but it won't give you the best overall solution and it can sometimes make things worse by isolating too many triangles.

Also it doesn't take into account the presence of a vertex cache. A vertex cache aware algorithm does give better results.


PS: Titan, it's nice to see people liking and using Tri Stripper. http://www.opengl.org/discussion_boards/ubb/smile.gif

chxfryer
01-05-2003, 03:15 PM
is it faster for tri-strips or vertex arrays?
or use the tri-strips for the vertex arrays?

jwatte
01-05-2003, 06:08 PM
Vertex arrays are orthogonal to tri strips.

You should, generally, submit your tri strips using the most efficient geometry submission API, which usually tends to be some flavour of vertex arrays.