Sign in to follow this  
Basiror

Triangle Stripification Algorithms

Recommended Posts

Basiror    241
Hi, I have to prepare a seminar about creating vertex cache friendly triangle strips. I don t ask for help, I just would like to know about other algorithms I have search a lot on google and there are basically 3 ways of doing this 1.) the bruteforce way (merge as many as you can and merge the rest of the strips) 2.) try a few times until you find the longest strips 3.) the tunneling algorithm working with the dual graph of a closed mesh What I wonder is, are there any other algorithms I should know of that are use a lot or is the tunneling algorithm the only one that delivers acceptable results with a minimum effort? thx in advance

Share this post


Link to post
Share on other sites
frob    44904
Quote:
Original post by Basiror
Hi, I have to prepare a seminar about creating vertex cache friendly triangle strips. I don t ask for help, I just would like to know about other algorithms

I have search a lot on google and there are basically 3 ways of doing this

1.) the bruteforce way (merge as many as you can and merge the rest of the strips)
2.) try a few times until you find the longest strips
3.) the tunneling algorithm working with the dual graph of a closed mesh


What I wonder is, are there any other algorithms I should know of that are use a lot or is the tunneling algorithm the only one that delivers acceptable results with a minimum effort?

thx in advance


4.) Outsource the work to a great program like stripe

frob.

Share this post


Link to post
Share on other sites
Basiror    241
the page doesn t seem to be up to date anymore

I ll have to see if I may publish the work and especially when


Anyone else who knows another algorithm? This can t be the only ones.

Share this post


Link to post
Share on other sites
Twon    145
Hi, you may find this reseach of some use, titled "Cache-Oblivious Mesh Layouts", it is from this years Siggraph conference, although it is aimed at very large scale meshes. You can find it at http://gamma.cs.unc.edu/COL/

Share this post


Link to post
Share on other sites
head_hunter    139
Greetings Basiror.

Since you are concerned about efficiency paired with decent results, I read in this article by Pierre Terdiman that :

Quote:

Choosing the first triangle


There are two standard ways of choosing the first triangle of a strip:



- the first method is the one from the SGI algorithm : pick the less connected faces first. Such faces, due to their lack of connections, are easily left isolated after some strips have been created. The idea is to take those faces first, in order to reduce the number of isolated triangles in the final mesh. This is just a heuristic method, but it works well in practice.



- The second method is just to take the first free face, i.e. the first face which doesn’t belong to a strip yet. This is what Chow does and according to him it’s just as good as the SGI way.



Both methods can be coded in a very similar way by using a precomputed insertion order, i.e. the order in which we’ll pick the faces to start creating a new strip. The insertion order for the second method is just the decimal one : we pick triangle 1 first, then triangle 2, and so on. For the SGI algorithm, we just have to sort the default list according to the number of connections of each triangle. The number of connections depends on the number of boundary edges, as defined in the previous paragraph, and we already have this information thanks to the adjacency structures. We just have to call the sort routine once more.



My own code takes one method or the other according to what the user wants.


Choosing an arbitrary triangle as the first is sure to give you a speed boost.

Share this post


Link to post
Share on other sites
Basiror    241
Quote:
Original post by superpig
NVTriStrip?


I am working on a seminar not a stripification implementation :)
but i will definitely implement this into my map editor once i am so far that it s worth it

@lightbringer: the link doesn t work :(
@head hunter: i think i have read this excerpt somewhere, is it from 3d programming gems?

the really seem to be only 3 common way( bruteforce, dual graph with tunneling operator and the SGI attempt to choose the less connected faces first


I gonna have to talk to my professor to make sure i am not missing something


thx for ya help :)

Share this post


Link to post
Share on other sites
lightbringer    1070
Aya, sorry, some code got appended to it somehow. The link is http://number-none.com/blow/slides/gdc_reception_korea2002_pieces_fit_together.ppt
Covers various topics and includes some skepticism and info about strips and caches. It probably won't be that useful to you, all I got out of it is that triangle strips are more trouble than they're worth. (And since I'm a beginner in 3d, I took it for face value ^_^ - and for me they certainly are overly complicated anyway)

Share this post


Link to post
Share on other sites
EvilDecl81    360
Quote:
Original post by Basiror
Hi, I have to prepare a seminar about creating vertex cache friendly triangle strips. I don t ask for help, I just would like to know about other algorithms

I have search a lot on google and there are basically 3 ways of doing this

1.) the bruteforce way (merge as many as you can and merge the rest of the strips)
2.) try a few times until you find the longest strips
3.) the tunneling algorithm working with the dual graph of a closed mesh


What I wonder is, are there any other algorithms I should know of that are use a lot or is the tunneling algorithm the only one that delivers acceptable results with a minimum effort?

thx in advance


Other then the fact you should probablly be using lists instead of strips (unless you're on Xbox), check out Hughes Hoppe's homepage.


Share this post


Link to post
Share on other sites
head_hunter    139
Quote:
Original post by Basiror
@head hunter: i think i have read this excerpt somewhere, is it from 3d programming gems?


I found it on the 'net. I don't really know where it is from.

Share this post


Link to post
Share on other sites
Basiror    241
thx for these links, that are some excellent resources and quite informative

however I can t really agree with the thesis of using indexed triangle lists instead of strips, huge hoppes show quite well that you can efficiently implement cache friendly strips and nvtristrip provides you a library that does all this for you

as for multi pass character skinning, the costs of shaders apply to the indexed lists as well plus you spend more bandwidth to submit vertex data if using indexed tri lists

the local cache optimization suggested by huge hoppes will counter this problem quite good i think


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this