Hey guys!
Wanted to program a stripper today, but it keeps outputting the wrong data. I relooked into the MSDN definition of GL_TRIANGLE_STRIP and found that:
GL_TRIANGLE_STRIP
Draws a connected group of triangles. One triangle is defined for each vertex presented after the first two vertices. For odd n, vertices n, n + 1, and n + 2 define triangle n. For even n, vertices n + 1, n, and n + 2 define triangle n. N - 2 triangles are drawn.
If I take any triangle that is counter clockwise defined (you know what I mean…), the next (fourth) vertex will create a clockwise triangle. Or am I wrong?
I guess technically it would, yes… If the first one was CCW, the second one would be CW, CCW, CW and so on.
Maybe OpenGL turns those triangles in strips around internally, as far as the orientation is concerned?
Might be. Thnx.
But, wouldn’t that be idotic? Maybe I’m not getting it with greater n, but why not simply take the last two vertices and add the new one. That would be CCW and you don’t have to swap the face.
That is face n is vertices, n, n+1, n+2 for even and odd.
Actually, MSDN is right. They give the same information in the Red book. I’ve posted a couple responses about this in other threads as well. For instance if you have 6 vertices like so… (Excuse my terrible ASCII art)
1-3-5
|/|/|
2-4-6
And you send the vertex info in the order 1,2,3,4,5
It will be equivalent to rendering triangles using…
1 2 3
3 2 4
3 4 5
By doing this all the above triangles are in CCW winding order
If OpenGL were to intperet that as
1 2 3
2 3 4
3 4 5
The middle one would be CW and the other two would be CCW
Yeah… I forgot the 5 4 6 sequence for my example. I was originally going with a 5 vertex example then decided to add in an ASCII representation of the strips which looked better with 6 vertices.
Oh damnit!
I made a mistake when drawing that on a paper. Always me and my silly mistakes…
Sorry guys.
Yeah, MSDN was right! Uhm, the bug was in my stripper routine… As I could have guessed…
Anybody’s got an idea to make a fast stripping of a model that has 50000 poly’s?
It nearly took 10 minutes, although in debug configuration.
And I still don’t know how 3dsmax builds the normals of the 3ds model so fast. 3ds models only define vertices, faces and smoothing groups (that is, if a normal should be interpolated between 2 touching faces). It takes 20 secs for me and 3dsmax does it in 5 or so.
Is anybody used to 3ds files?
If you look in the Max SDK and the way in which they do their triangle strips, you’ll note that it’s very inefficient… That’s why they’re able to do it so quickly… In MAX, the normals have to be exactly equal for them to be stripped, so you won’t get a strip if you don’t have two polygons on the same plane, and facing the same direction with MAX.
One method you could look at for doing a triangle stripper would be a recursive “greedy” formula where you’d look for the longest possible strip. Then remove those polygons from your list and continue on with the next longest strip. One thing to note however is that all the normals in the strip have to be relatively close… otherwise when you texture your model, it will look really screwed up…
Good luck.
Kiyoshi
[This message has been edited by Kiyoshi (edited 11-16-2000).]
Oh, well, but I think that the normal of the face doesn’t have anything to do with it’s orientation, since there is still the aspect of smoothing groups, that enable gouraud shading.
What you mean is for me like this:
Find for any face all 3 possible strips (since a triangle has 3 edges) and take the longest strip of them all. Afterwards, go on with that.
I will probably implement it with a mode to disable it for large model.
My current algo only searches the longest strip of the three possible strips for the current face, and makes it the searched strip.
Maybe it would help me, if I would for example search the strips for the current face, and then combine them if at all possible.
I’ve got an algorithm I put together for creating triangle strips that seems to work pretty well. Not sure if it’s the most efficient, but it works well enough for me. If you want to look at the actual code, I can try to put together a project with just the stripping algorithm for you to look at.
Basically, my initial data is an array of vertices and an list of faces which are just indexes into the vertex array. I’ve also got an list of strips that I add each strip to. I don’t really have to do anything with the vertex array since only the indices need to change for the faces to create strips.
Anyway… the code works something like this.
Get the first face from the list and remove it from the list
Place the three indices of that face into a new triangle strip
Search through the list for a face that uses the last 2 indices of the previous face, being sure to only grab faces that have the correct winding order.
If a face is found in step three, remove that face from the list, add the new vertex to the current strip, then repeat step 3. If no faces are found continue to step 5.
Check if there are any single triangle strips in the current list of strips that we can add to this. If there are add it to the current strip and remove the single-triangle strip from the list
Check if the current strip can be pre-pended to any of the strips in the array of strips. You’ll need to make sure that pre-pending the list will not cause the winding orders to reverse. If there are, pre-pend the current strip to the strip in the list. Otherwise, just add the current strip to the end of the list as a new strip.
If there are still faces in the original face list, go back to step 1 and repeat.
Not sure how clear the above definition is. Like I said above, I can clean up a copy of my code to show you how I did the stripping algorithm, if you need it.
Yep, thanks.
That is exactly the way I’m going, with the difference, that I’m not using indexed modes. That is, only to have an array of vertices and a face array that indexes them. I don’t use it yet, not because it wouldn’t work (since I read the files from a 3ds file) but because I’m currently including smoothing groups. BUT, it is obvoiusly, that I can add a face to the strip if it’s in the same smoothing group with the last face in the strip. Most probably I will do that, although I still have an non-indexed vertex array, because I have to compute the face normals according to the smoothing groups before.
I think, that if one creates strips for any edge of a starting triangle, that one may combine two of the strips and also add the third strip. Might be more efficient, but I’m not too sure about it.
If one does, one also will probably not have to check if one can combine some strips, later, since they’re all already combined.
