Open source Tri Stripper (vs NvTriStrip)

As I promised I would do in a previous post a few weeks ago, I just released the source of the triangle stripper I was working on.
http://users.pandora.be/tfautre/softdev/

You’ll find on that website the source and a test program.
There is also some explanations plus a comparison against the famous NvTriStrip.

Well, tell me what you think about it.

ahem

I like it. I wonder why nobody else does …

Good work.

very nice good to see.
sidenote - i recently decided to just draw everything with plain triangles (instead of the combination of strips + tris that i was using previously)
-reason being simplicity + not that much of a difference between the two.

Well, it looks extremely good - I found it complex to read the first time because I just dived straight into it and my STL is a little rusty, but on the whole, it seems to be a damn fine effort.

-Mezz

Great idea !

Your lib may save my life as I’ve just stumbled upon a model that makes NvTriStrips crash ! I’ll try it with your lib

I was wondering if you support 3-manifold (or more) geometry ?

Thanks,
Nicolas

To answer in the order:

zeckensack,
yep, I wonder why it doesn’t get more replies, 'cause there are often requests for triangle strippers on these forums (which always lead to NvTriStrip).
Thanks for your support.

zed,
thanks for your reply.
As you can see it depends of the model; I mean, with Tri Stripper using the skull model I get a 3 times increase in performance, but using a starship model I get almost no improvement.
But even if you only use triangles, re-ordering these while give better performance because of the vertex cache.

Mezz,
I heavily use the STL now, but actually it’s to make it more understandable.
You should have seen the very first version, using only pointers and arrays… brrrr… scary!
Thanks for your input.

Nicolas,

glad to hear my lib is saving lifes.

I’m not sure what you mean by “3-manifold geometry”… (excuse my not-so-complete English vocabulary, especially in math)
But Tri Stripper is designed to be stable and robust (it can handle a lot of complex cases: for example, it will accept that a triangle can have more than 3 neighbour triangles), so I hope it’ll work for you.

Anyway it’s the first version, 1.0 Beta 1, so if you find a problem please report it.

> it will accept that a triangle can have more than 3 neighbour triangles

That’s what I meant by 3-manifold geometry great !

By the way, your lib does not crash as NvTriStrip does great job, really great

By the way, I was wondering if there was a way to only generate triangle lists with improved vertex locality (and not strips) - that’s what I used from NvTriStrip ?

Thanks for the great work,
Nicolas

By the way, I was wondering if there was a way to only generate triangle lists with improved vertex locality (and not strips) - that’s what I used from NvTriStrip ?

Unfortunatly not, it currently outputs strips only.
Though a similar effect can be achieved by reconverting the strips back to triangles, which is fairly easy, while keeping the same order, but then I dunno how it compares in term of efficiency next to NvTriStrip in that case.

After all, it might just be what NvTriStrip is doing, but I haven’t got the time to really look into NvTriStrip code (which is not really readable by the way ).

Nice to hear it doesn’t crash.

[This message has been edited by GPSnoopy (edited 11-12-2002).]

Looks like a nice lib.

We had a couple problems with the nvstrip lib (ask for all strips shorter than 2 triangles to be put in a seperate list and give it two triangles you get an assert).

As I understand it the nv2x cards have a vertex cache of 24, NV1x/Parhelia/Xabre400 have 24, ATI R200 has 10, and ATI R100 has a vertex cache of just 6. nvstrip won’t optimize for the R100…

Looks great, we’ll probably switch to it for our next project.

i thought the cache for gf1/2 is effectively 10 not 24 (whatever it is its less than a tnt )

That is a typo, I meant to say they had a cache size of 16. With the GF1/2 it is effectively only 10 though.

I’m not sure how big the effective cache of the Parhelia, etc are compared to their real cache size.

AFAIK NvTriStrip can optimize for the R100, but it’s a bit tricky.

If you look into its source code you can see that NvTriStrip computes as follow:

Efficient_Cache_Size = Given_Cache_Size - 6;

So when you give it the cache size of a GF2 it’ll correctly get the efficient cache size (10 = 16 - 6).
But this formula only works with current NVIDIA GPUs and doesn’t work for other GPUs such as the R100 or maybe even future NVIDIA GPUs.

If you want to use NvTriStrip for an R100 I think you should give it a cache size of 12 (12 - 6 = 6), otherwise if you give it 6 it won’t work correctly. (6 - 6 = 0 oops )

Tri Stripper directly asks for the efficient cache size instead.

[This message has been edited by GPSnoopy (edited 11-27-2002).]

Hey, ive been looking for a good stripper… but i always have the same problem… Someone needs to explain things to me =P… For some reason, unless the code is Uber-simple, i cant look at it and see how to use it… Do you have any docs on how to use your library?

Originally posted by ImpactDNI:
Hey, ive been looking for a good stripper… but i always have the same problem… Someone needs to explain things to me =P… For some reason, unless the code is Uber-simple, i cant look at it and see how to use it… Do you have any docs on how to use your library?

The stripper class isn’t very complicated. It’s very easy to see how to use it. Try here: http://users.pandora.be/tfautre/softdev/tristripper/tristripper_manual.htm

-SirKnight

Indexed Triangles are really fast, I think that you should go to Strips ONLY if you have performances problems.

Thanks SirKnight

However I should point out that the interface described there is not up-to-date with the latest version (1.00 Beta 5) but it’s relatively the same.

There should be no problem if you know how to use std::vector (cf. C++ STL).

There is also a example program on the website that shows how to use it.

tri_stripper TriStripper(m_SubMeshes[0].Indices());
tri_stripper: rimitives_vector PrimitivesVector;

TriStripper.SetMinStripSize(2);
TriStripper.SetCacheSize(16);
TriStripper.Strip(&PrimitivesVector);

/* … */

Can it be any easier?

EDIT: LOL @ smileys in the code. I think that the CODE tags aren’t bug free

[This message has been edited by GPSnoopy (edited 01-12-2003).]

If vendors provided an extension for querying the optimal cache size to use, that would go great with libs like this.

I’m surprised it hasn’t been done yet.

Looks very useful! In browsing the code…

The singular form for “indicies” is “index”

Did you know that STL already has heap algorithms? Also, have you ever seen Boost Graph Library? An STL-like implementation of graphs that is quite powerful.

Good job. I think I’m going to find a use for this.

-Won

V-man, yep it would be useful. Knowing a little more about the cache mechanisms would be usefull too. (For the moment I assume that the cache is a simple FIFO structure, but it could be more complex than that in reality)

Won, thanks.

Sorry for that English mistake (and the others). My French confused me. (and it’s still confusing me by the way )

Yes the STL has some heap algorithms but because of the particular heap structure I need I can’t really use them efficiently.

I’ve originaly built the graph class for a university project, then I improved it for Tri Stripper.
It’s only later that I discovered the Boost library. (quite a nice library by the way )

There are still things that could be improved in the code structure, such as the parts extending and building strips, and also parts relative to the “cache simulator”.
However the current version seems to be working well, so I’m reluctant to modify it just to get a more aesthetic code.