Triangle Stripification Algorithms
Author
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
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.
Author
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.
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.
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/
Greetings Basiror.
Since you are concerned about efficiency paired with decent results, I read in this article by Pierre Terdiman that :
Choosing an arbitrary triangle as the first is sure to give you a speed boost.
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.
This is probably too simple, but anyway: read this presentation, starting around slide 24, if you haven't yet, for some additional insights into the topic.
Author
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 :)
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)
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)
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
