Not logged in, Join Here! or Log In Below:  
News Articles Search    

 Home / 3D Theory & Graphics / Transforming triangle lists to triangle fans Account Manager
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

April 11, 2005, 03:53 AM

Hello everybody, anybody knows if there's something similar to nvidia's NVTriStrip library but capable of transforming to fans instead of strips?
If it doesn't exist can anybody explain me any method to do that or where to find some info about it?



April 11, 2005, 06:48 AM

Well, NVIDIA once phrased it something like this: "If you think you need fans, you did something wrong".
Fans aren't very useful... there won't be any realistic situations where you have enough triangles in a single fan to get efficient batching (at least 500 triangles).
It's better to encode fans as lists, and then you can easily group all fans together in a single list, together with all other geometry, which allows you to make much larger batches.

I personally use lists only... If you sort the triangles so that they're stripped, and then attach the rest of the triangles that couldn't be stripped, you will get pretty much the same performance as with stripping (the vertexcache will be just as effective, you have slightly more indexbuffer traffic, but that is generally so low that it doesn't affect performance... ofcourse you should only be using 16 bit indices, 32 bit is not worth it. Most models can be encoded in just 1 or 2 16 bit batches, and you save lots of memory/bandwidth with it), but larger batches.

So in short, use only lists or strips... and don't use strips if you have too many small ones of them... converting them to a single list is better then.


April 12, 2005, 05:35 AM

Well, I've made this post because I'm interested in transforming the geometry of my models (which is made of triangles sets) to sets of star-shaped objects and I thought that a good way to do that was to transform them to triangle fans. The efficiency issue is secondary in this case because all will be precalculated and the final application probably won't use triangle fans. Any ideas?

Chad Austin

April 12, 2005, 06:19 AM

For what it's worth, my GLScry benchmark for various ways of doing regular (in a grid) triangle strips indicates that stitching strips with degenerate triangles is always faster than a triangle list, although not by much in most cases. Do you have a particular usage and card that shows otherwise? If so, I'd like to add that to the test.


April 13, 2005, 06:07 AM

I believe I read that newer cards are quite slow at degenerate triangles, so they should be avoided... I think it was in an NVIDIA presentation... I never put it to the test though.


April 13, 2005, 06:22 AM

Well, I suppose you just take a triangle, then look at the triangles that are connected at each edge. If there's a fan, then at least one of the neighbouring triangles should have a neighbouring triangle that shares a vertex with the original triangle. Then that vertex will be the center of your fan... Keep walking down the neighbours until you've found all triangles that share this vertex... Or something like that :)


April 13, 2005, 08:44 AM

If you like recursion, this is a perfect application!

Chad Austin

April 13, 2005, 08:53 AM

Interesting. Do you happen to remember where you saw it?



April 13, 2005, 10:46 AM

Well yea, technically things like finding optimum strip/fan/etc distributions are NP-complete problems ;)
But especially in the case of fans, I think it's not that much of an issue, since generally you'll not find all that many possible fans, so recursion won't be too deep. I wouldn't know of any better way to do it either.
Ofcourse you could always cut the recursion short and generate partial fans of a maximum of N triangles, or something like that :)


April 13, 2005, 11:06 AM

Not sure... all I can find so far is this:

If number of degenerate triangles is relatively high, it might be better to use strip ordered triangle lists. All TnL-capable ATI hardware has very efficient hardware implementation of triangle lists; so on any RADEON family hardware strip ordered triangle lists are just as good as triangle strips. Considering that triangle lists are much more flexible than triangle strips, in many cases they might be a preferred choice.

Chad Austin

April 13, 2005, 11:21 AM

Cool. Thanks for looking for me!


April 15, 2005, 03:52 AM

I've got the geometry grouped in small triangle sets, so probably NP-completeness won't be a big problem in my case, but It's good to know it anyway ;)


This thread contains 12 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.