Rendering a tesselated grid using indexed triangle strips

I don't use tristrips very often so I'm not sure about this, but I think you'll have to a) include degenerate triangles, or b) start a new strip at each row.

[Edit: Oops, didn't know about 'primitive restart' :-| ]

[Edited by - jyk on May 16, 2006 1:15:37 AM]

Take a look at the "restart index" technique. I think it does exactly what you want. I'm not sure how widely supported it is, but here is the Nvidia version:

http://oss.sgi.com/projects/ogl-sample/registry/NV/primitive_restart.txt

Hi,

Is pretty easy to do, i dont say its the best way to do it, but i do it like that using DirectX.
First, like jyk said you need to start a new strip each row.

This is your heightmap pixels.

1  2  3  4 5  6  7  89 10 11 12

The strips are form like this (put the vertex in this order into the VertexBuffer)
First Row: 5, 1, 6, 2, 7, 3, 8, 4
Second Row: 9, 5, 10, 6, 11, 7, 12, 8

Quote:

(0, 0), (0, 1), (1, 0), (1, 1) ... (m, 0), (m, 1) [this is for the first row of triangles]

Check up, they are not in the right order.

When drawing,

for(int x=0; x < heightMap.Height - 1; x++){   int startVertex = x * heightMap.width * 2;   int triCount = (heightMap.width - 1) * 2;   device.DrawPrimitives(PrimitiveType.TriangleStrip, startVertex, triCount);}

And voila a heightmapped terrain ;)

EDIT: Oups, i did an error in the vertex index...

Hopes this help,
Jonathan

Thanks for the very helpful answers everyone!

I went ahead with using a new tri-strip for every row, as I had suspected at first. It actually takes just a single draw call in OpenGL with glMultiDrawElements, so I'm happy with this for now.

deathkrush: Yes, NV_primitive_restart sounds like exactly what this kind of situation calls for. However, it isn't supported on the Nvidia 87.56 drivers on my Geforce 4 MX; and of course there's no hope on other platforms [wink].

Don't use 1 strip per row, except if your rows are extremely big. You'll completely waste the power of triangle strips by doing too much DIP calls !

Instead, use one big triangle strip for the whole grid. And insert degenerated (invisible) triangles to join 2 rows. For example :

0  1  2  34  5  6  78  9  10 1112 13 14 15

The index buffer would look like :

0, 4, 1, 5, 2, 6, 3, 7, 7, 4, 4, 8, 5, 9, 6, 10, 11, 11, 8, 8, 12, 9, 13, 10, 14, 11, 15.

The first part (0 to 7) is as always. After this first row, you have to duplicate the last index, and the first index of the next row, in order to create 2 degenerated triangles. This is the "7, 7, 4, 4" part. These triangles are invisible, and most modern GPU can get rid of those at early stage, so that it's almost free (and even if they are actually drawn, it's cheaper to draw 2 tris than to switch buffers to draw another row in another DIP call)

The point is to avoid having many too many DIP calls. In small patches (16x16 for example) you should only have 1 DIP call, instead of 16 ones.

Quote:

Original post by paic Don't use 1 strip per row, except if your rows are extremely big. You'll completely waste the power of triangle strips by doing too much DIP calls ! Instead, use one big triangle strip for the whole grid. And insert degenerated (invisible) triangles to join 2 rows. For example : 0 1 2 34 5 6 78 9 10 1112 13 14 15 The index buffer would look like : 0, 4, 1, 5, 2, 6, 3, 7, 7, 4, 4, 8, 5, 9, 6, 10, 11, 11, 8, 8, 12, 9, 13, 10, 14, 11, 15. The first part (0 to 7) is as always. After this first row, you have to duplicate the last index, and the first index of the next row, in order to create 2 degenerated triangles. This is the "7, 7, 4, 4" part. These triangles are invisible, and most modern GPU can get rid of those at early stage, so that it's almost free (and even if they are actually drawn, it's cheaper to draw 2 tris than to switch buffers to draw another row in another DIP call) The point is to avoid having many too many DIP calls. In small patches (16x16 for example) you should only have 1 DIP call, instead of 16 ones.

That's just what I was looking for, thanks! [smile]

What you are saying about performance makes sense to me, even though it in actual fact was negligible for tests with ~2000 to ~20000 triangles on my computer.

Read this thread: Rendering vertices for my Terrain. It contains a lot of useful information about rendering a grid. There are a few improvements you can make.

Can't you get away with no degenerate triangles by rendering the strip in an inwardly moving spiral?

Not a square grid. But a one which looks like a spiral, yes ^^

No, I mean a square spiral. Think back to the old 'Snake' game. Start in the top left corner, work across to the top right corner, then down to the bottom right, bottom left, top left 2nd level, across and so on.

Like this: (each number represents the strip direction (starting at 0).
-->
011111
->455552 |
| 488862 |
| 477762 v
333332
<--

No degenerate triangles...

Quote:

Original post by Maddibob No, I mean a square spiral. Think back to the old 'Snake' game. Start in the top left corner, work across to the top right corner, then down to the bottom right, bottom left, top left 2nd level, across and so on.

You can't do it because of the turns. Try it.

Quote:

Original post by JohnBolton Read this thread: Rendering vertices for my Terrain. It contains a lot of useful information about rendering a grid. There are a few improvements you can make.

Sorry for taking such a long time in replying - but thanks for the link. It does indeed contain very useful information.

edit: BTW, I just logged in once for a short period yesterday evening (my time, that would make it 19th morning US time) and there were a series of rating buttons below each post labelled -5 through +5?! I see they're gone now ...

edit2: ... and they're back! It's the attack of the ghostly rating buttons I tell you! Aarrrgh!

You can do spiral un-degenerate triangle grids. You just change the orientation of the triangles within each quad at the corner to make sure two vertices are available from the previous triangle for the next one.

I've never tried it but I'm sure it would work...

I am sorry but the things described in the thread you posted above about indexed triangle lists outperforming indexed triangle strips that are optimized for vertex cache efficiency aren t completely right.

There s another thread about this topic that was started ~ at the same time where I described why this isn t correct. I don t have the time to search for the thread right now but search the graphics programming forums at the end of january .

Here s the thread I was talking about

http://www.gamedev.net/community/forums/topic.asp?topic_id=385397

Quote:

Original post by deavik edit: BTW, I just logged in once for a short period yesterday evening (my time, that would make it 19th morning US time) and there were a series of rating buttons below each post labelled -5 through +5?! I see they're gone now ... edit2: ... and they're back! It's the attack of the ghostly rating buttons I tell you! Aarrrgh!

Do you use ...firefox? [smile]

And have you installed ...the GDNet Extension? [wink]

Cause that is one of the many useful features it adds to your whole GDNet experience [grin]

Quote:

Original post by ViLiO Quote: Original post by deavik edit: BTW, I just logged in once for a short period yesterday evening (my time, that would make it 19th morning US time) and there were a series of rating buttons below each post labelled -5 through +5?! I see they're gone now ... edit2: ... and they're back! It's the attack of the ghostly rating buttons I tell you! Aarrrgh! Do you use ...firefox? [smile] And have you installed ...the GDNet Extension? [wink] Cause that is one of the many useful features it adds to your whole GDNet experience [grin]

Aaaahhh, thank you! [smile] I must have downloaded it earlier in the day and forgotten about it [lol].