An alternative to triangle strips and triangle fans

Triangle strips and triangle fans are very useful because they help reducing the number of vertices to send through the pipeline.
Rendering n triangles with GL_TRIANGLES requires 3*n vertices.
Rendering n triangles with GL_TRIANGLE_STRIP or GL_TRIANGLE_FAN requires n+2 vertices.

I think there could be an alternative to triangle strips or triangle fans that would also require n+2 vertices to render n triangles, but would pick vertices in a different order.

Let's call it "alternated triangle strip", using the token GL_TRIANGLE_STRIP_ALT. The name and token are subject to change.

An alternated triangles strip is the same as a triangle strip except the fact that the shared vertices are not always the last two processed vertices. They alternate between the "last two processed vertices (ie the last processed vertex with the second last processed vertex)" and "the last processed vertex with the third last processed vertex".


Example of processing :
glBegin(triangle_primitive);
glVertex(v1);
glVertex(v2);
glVertex(v3);
glVertex(v4);
glVertex(v5);
glVertex(v6);
glVertex(v7);
glVertex(v8);
glVertex(v9);
glEnd();

Triangles rendered with triangle_primitive == GL_TRIANGLES :
triangle1 = (v1 v2 v3)
triangle2 = (v4 v5 v6)
triangle3 = (v7 v8 v9)

Triangles rendered with triangle_primitive == GL_TRIANGLE_FAN :
triangle1 = (v1 v2 v3)
triangle2 = (v1 v3 v4)
triangle3 = (v1 v4 v5)
triangle4 = (v1 v5 v6)
triangle5 = (v1 v6 v7)
triangle6 = (v1 v7 v8)
triangle7 = (v1 v8 v9)

Triangles rendered with triangle_primitive == GL_TRIANGLE_STRIP :
triangle1 = (v1 v2 v3)
triangle2 = (v2 v3 v4)
triangle3 = (v3 v4 v5)
triangle4 = (v4 v5 v6)
triangle5 = (v5 v6 v7)
triangle6 = (v6 v7 v8)
triangle7 = (v7 v8 v9)

Triangles rendered with triangle_primitive == GL_TRIANGLE_STRIP_ALT :
triangle1 = (v1 v2 v3)
triangle2 = (v2 v3 v4)
triangle3 = (v2 v4 v5)
triangle4 = (v4 v5 v6)
triangle5 = (v4 v6 v7)
triangle6 = (v6 v7 v8)
triangle7 = (v6 v8 v9)


As a matter of usefulness, you can see that a torus can be rendered with a single "alternated triangle strip", which is obviously better (less vertices passed through the pipeline) than rendering a few adjacent quad strips.
Though, it is already possible to render a torus with a single _classic_ triangle strip.

Anyway, does any of you know how to render a cube with a single triangle fan, triangle strip or quad strip ? I don't (at least I don't think it's possible without degenerated polygons). In my opinion you need at least two triangle fans, two triangle strips or two quad strips to render a cube. But it is possible to render a cube with a single alternated triangle strip, quite easily.
Though, this time again it is already possible to render a cube with a single classic triangle strip. The difference between the triangle strip method and the alternated triangle strip method is that I find it much obvious to render a cube with a single alternated triangle strip than with a single classic triangle strip, although I know it's just a matter of preference.

If you want to render a cube with 4 faces -- 2 adjacent faces being holes -- it's still obvious to do it with an alternated triangle strip, but I don't know if it's possible to do it with a classic triangle strip (I'm convinced it's not possible, but I haven't studied this case enough to confirm what I'm saying).

All of that to tell that I can't prove that alternated triangle strip offer a unique rendering method (that is, I can't prove that there exists a mesh that can be rendered with a single alternated triangle strip and not with a single classic triangle strip) but I can affirm it offers a new dimension for rendering order.
In that sense, including GL_TRIANGLE_STRIP_ALT (or whatever its name) into OpenGL specifications (or an extension) would be no more no less useful/efficient than the primitive GL_QUAD_STRIP is, since I can admittedly affirm that everything rendered by quad strips can be rendered by classic triangle strips (with the same pipeline throughput).

As a final note, such processing could be extrapolated to GL_QUAD_STRIP_ALT.

(c) Vincent David 2002 - All rights reserved !

[This message has been edited by vincoof (edited 09-02-2002).]

don't studied all what you said, but it seems that you want to add another way to do a n+2 array for n triangles !!!

I think strip are already very more often used than fan, so, maybe it will be difficult to you to prove your veracity...

One way, I think would be to find (but it's still impossible), a simple algorithm that could hands N+2 vertices for N triangles.

Nice http://www.opengl.org/discussion_boards/ubb/smile.gif

multi_draw_arrays (or so ...) combined with clever post transform-caching will probably make it pointless, but it's still nice http://www.opengl.org/discussion_boards/ubb/biggrin.gif

Quote:

---

One way, I think would be to find (but it's still impossible), a simple algorithm that could hands N+2 vertices for N triangles.

---

That is what a triangle fan does, that is what a triangle strip does and that is what an alternated triangle strip does too.
Or maybe I misunderstood your sentence.

Just in order to explain what I mean by "I find it much obvious to render a cube with a single alternated triangle strip than with a single classic triangle strip", here's how a cube can be rendered with a single GL_TRIANGLE_STRIP_ALT :

Quote:

---

Code :

---

         (13)+----+(14)
             |\   |
             | \  |
             |  \ |
         (10)|   \|
     (9)+----+----+(12)
        |\   |\   |
        | \  | \  |
        |  \ |  \ |
     (6)|   \|   \|
(5)+----+----+----+(11)
   |\   |\   |(8)
   | \  | \  |
   |  \ |  \ |
   |   \|   \|
(2)+----+----+(7)
   |\   |(4)
   | \  |
   |  \ |
   |   \|
(1)+----+(3)

---

---

and here's how a cube can be rendered with a single GL_TRIANGLE_STRIP :

Quote:

---

Code :

---

                            +(14)
                           /|
                          / |
                         /  |
                    (12)/   |
              (10)+----+----+(13)
                 /|\   |   /
                / | \  |  /
               /  |  \ | /
              /   |   \|/
          (8)+----+----+(11)
             |\   |(9)
             | \  |
             |  \ |
          (6)|   \|
     (4)+----+----+(7)
       /|\   |   /
      / | \  |  /
     /  |  \ | /
    /   |   \|/
(2)+----+----+(5)
   |   /(3)
   |  /
   | /
   |/
(1)+

---

---

Still, it's a matter of preference, but I really think the first one is easier.

Dear reader,

Allthough this is an old thread, i like to comment since i think to have an improvement on the index buffer for both fans and strips.

In strips, there is always 3 ingredients in the buffer; 1 a sequence, 2 a degenerate triangle, and 3 a sequence that is sewn on to the first sequence.
I use to generate my buffers with matlab, and found out that it's alway the same riddle. I made a function that tells matlab the length of the sequence, and the number of sequences, and matlab generates the complete buffer. There is an exception when the surface needs different number of triangles in different lines (this can be dealt with, but i always create the surface from a (transformed) meshgrid, which does not have this problem)

In case of a fan, (i imagined this, i didn't try), you can make a complex fan from a spiral. All you need to know is when to switch to the next (hidden sequence). To explain, the sequence always starts like this ; {1 2 3 4 5 6 7 ... all those point are connected to point 1, so the interpreter would say "stay on one, dont go", now after 7, you have a nice fan and want 8 to connect to 2, so you say "go" to the interpreter. after you say go, the interpreter goes every new vertex. since the fan spirals outward, the triangles would get distorted more and more (inner points catch up with outer points), therefore, sometimes you have to tell the interpreter to 'stay'. The sequence would look like this: {1 2 3 4 5 6 7 'go' 8 9 10 11 12 13 'stay' 14 'go' 15 16 17 etc

in single triangles language, the thing would be like this:

1 2 3
1 3 4
1 4 5
1 5 6
1 6 7
1 7 8 << -- here you start walking
2 1 8
2 8 9
2 9 3
3 9 10
3 10 11
3 11 4
4 11 12
4 12 13
4 13 5 <<-- here you tell the sequence to stop. if you didnt, the triangle would be 4 13 14, which is a distorted triangle
5 13 14
5 14 6 <<-- here you start walking again. if you didnt, the triangle would be 5 14 15
6 14 15

if this was a left spiral, telling 'go' would be 'less curvature in the spiral, take the point that is on your right side', and 'stay' would be more spiralling, telling to take the next point on your path that is on the left side.

When you say go to the interpreter, the sequence is actually tat of a strip. in case of a tube with end caps, you can say go when you finished the cap, and then just keep going. Since this is the strip sequence, you only need one number, which is the length of the strip. So then you have a really compact index buffer

Since this sequence is so nice, it could even be incorporated in the vertex buffer, Since the position of the vertex in the list tells what to do, only the 'stop' and 'go' should be added to the vertex buffer (or create a 'stop and go' index buffer where each vertex only needs one extra bit that tells it to stop or go). I'm going to try this idea in software, which is slow due to the processing. But if it works, it maybe could be incorporated in the hardware.

Quote:

---

Allthough this is an old thread, i like to comment since i think to have an improvement on the index buffer for both fans and strips.

---

That's still not a good reason to unearth a ten year old thread.

Even worse, your proposal is nothing more than a poor-man's version of primitive restart, which is technology we have had for almost ten years. Even if you count by core specification and not NV_primitive_restart, that's still a good 3.5 years.

If you're going to suggest something for OpenGL, please:

1. Create a new thread.

2. Do some research and suggest something we don't already have a far superior version of.

I'm sorry. I was not aware of this. I'll do my research and look into the topics you suggest. I'm new to this topic, and 10 years ago I was still wearing my diapers.
Off course, that is no excuse for not doing my research. I was not aware of this, and I didn't know how to get awared. Is this functionality also available in opengles?

OpenGL ES 2.0 doesn't, but 3.0 does. Of course, 3.0 is not widely supported. Or at all, from what I can tell.