Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

skow

help, vert array mesh with TRIANGLE_STRIP

This topic is 5346 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm tiring to draw a terrain with vert arrays. Right now I have the vertices in a 2d array and draw them as follows with 2 for loops:
	for (int i = 0; i < (numVerts-1); i++)
	{
		for (int j = 0; j < (numVerts-1); j++)
		{
			glBegin(GL_TRIANGLE_STRIP);						// Build Quad From A Triangle Strip

				glTexCoord2d(0,0); glVertex3f(verts[i][j+1].x	,-3,	verts[i][j+1].z); // Bottom Left

				glTexCoord2d(1,0); glVertex3f(verts[i+1][j+1].x	,-3,	verts[i+1][j+1].z); // Bottom Right

				glTexCoord2d(0,1); glVertex3f(verts[i][j].x	,-3,	verts[i][j].z); // Top Left

				glTexCoord2d(1,1); glVertex3f(verts[i+1][j].x	,-3,	verts[i+1][j].z); // Top Right

			glEnd();


		}
	}
Now I want to convert this to a vert array method. I have no problem getting all the vertices in an array but I'm having a hard time figuring out how do the index array. With simple triangles it’s fairly easy, but this makes quads out of triangle strips. Here I'm not sure how to do this, do i have to now have 6 indices per quad? (3 per triangle strip). Any help is greatly appreciated. I’m using glDrawElements to draw. [edited by - skow on February 21, 2004 5:36:53 PM]

Share this post


Link to post
Share on other sites
Advertisement
Since you''re reusing your vertices from one strip to the next you can get much better performance with larger triangle strips. For example if you have a mesh like:
*----*----*----*----*----*
| 1 | 2 | 3 | 4 | 5 |
| | | | | |
*----*----*----*----*----*
| 6 | 7 | 8 | 9 | 10 |
| | | | | |
*----*----*----*----*----*
| 11 | 12 | 13 | 14 | 15 |
| | | | | |
*----*----*----*----*----*

Where each * is a vertex.

Currently for this mesh you would draw 15 triangle strips. A simple optimisation can reduce this to 3. A further optimisation an reduce this to just 1 triangle strip.

Image you draw the quads in numerical order. At the moment you are effectively doing:
glBegin(GL_TRIANGLE_STRIP);
// draw quad #1
glEnd();
glBegin(GL_TRIANGLE_STRIP);
// draw quad #2
glEnd();
// and continue for the rest


If we also number the vertices:
01----02----03----04----05----06
| | | | | |
| | | | | |
07----08----09----10----11----12
| | | | | |
| | | | | |
13----14----15----16----17----18
| | | | | |
| | | | | |
19----20----21----22----23----24

then your code equates to:
glBegin(GL_TRIANGLE_STRIP);
// draw vertex #7
// draw vertex #8
// draw vertex #1
// draw vertex #2
glEnd();
glBegin(GL_TRIANGLE_STRIP);
// draw vertex #8
// draw vertex #9
// draw vertex #2
// draw vertex #3
glEnd();
// and continue for the rest

If we reorder the vertices:
glBegin(GL_TRIANGLE_STRIP);
// draw vertex #1
// draw vertex #7
// draw vertex #2
// draw vertex #8
glEnd();
glBegin(GL_TRIANGLE_STRIP);
// draw vertex #2
// draw vertex #8
// draw vertex #3
// draw vertex #9
glEnd();
// and continue for the rest

You''ll see that the last two vertices of the first triangle strip are the same as the first two vertices of the second. This means we can combine them into a single triangle strip:
glBegin(GL_TRIANGLE_STRIP);
// draw vertex #1
// draw vertex #7
// draw vertex #2
// draw vertex #8
// draw vertex #3
// draw vertex #9
// and continue for the rest of the vertices up to #''s 6 and 12
glEnd();
// and continue for the rest of the strips

Now we are drawing each row in its own strip. Finally we can take advatage of degenerate triangles to stitch all the strips together. The area of the triangle (vertex #1, vertex #1, vertex #2) is zero, so the triangle is not drawn. This is a degenerate triangle. Our first triangle strip ends:
// previous vertices
// draw vertex #5
// draw vertex #11
// draw vertex #6
// draw vertex #12
glEnd();

And our second begins:
glBegin(GL_TRIANGLE_STRIP);
// draw vertex #7
// draw vertex #13
// draw vertex #8
// draw vertex #14
// more vertices

We can''t just combine these like we did before because the last vertices of the first strip are not the same as the first vertices of the second strip. Instead we use degenerate triangles:
// previous vertices
// draw vertex #5
// draw vertex #11
// draw vertex #6
// draw vertex #12
// draw vertex #12 (a degenerate triangle)
// draw vertex #7 (another degenerate triangle - 12, 12, 7)
// draw vertex #7 (and again - 12, 7, 7)
// draw vertex #13 (and one more - 7, 7, 13)
// draw vertex #8 (a real triangle again - the first of our second strip)
// draw vertex #14
// more vertices

Now to build an index array so we can render the mesh with a single glDrawElements call we just need to fill in the indices that we were using above. The number of indices can be calculated as:
The number of vertices in the first row
plus the number of vertices in the last row
plus two times the number of vertices inbetween
plus two times the number of rows of vertices inbetween.
So for this example the index array contains 40 elements and the indices are:
1, 7, 2, 8, 3, 9, 4, 10, 5, 11, 6, 12, 12, 7, 7, 13, 8, 14, 9, 15, 10, 16, 11, 17, 12, 18, 18, 13, 13, 19, 14, 20, 15, 21, 16, 22, 17, 23, 18, 24.

Hopefully you can see how to build index lists for meshes of different sizes.

Enigma

Share this post


Link to post
Share on other sites
Enigma thanks for taking the time to write all that.

I don''t know why it didn''t dawn on me to rearange the order i draw verts.

I don''t have time for a few days to work on it but this information will be here when I have time.

Thanks a bunch!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Awesome description!! I have one question though:

These "degenerate triangles" don''t show up or cause any funny looking effects?

Share this post


Link to post
Share on other sites
No, degenerate triangles are culled (very quickly these days) and do not add any pixels to the framebuffer.

Enigma

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
awesome, let me ask another. I have simple entities in this game I''m doing, they each can be described with 1 triangle strip (using degenerate triangles of course), & they each have a simple periodic motion (like wiggling as they move or something) & as I''m doing it now... all their vertice/normal info for every possible position (around 20 or so) is stored in a 2D array much like the one skow has for terrain. For each frame, depending on the entity, I only use part of the array to draw that entity & over a second or two, it looks pretty good as it moves because of the small periodic motion. Each entity takes approximately 250-400 polygons to render. Would it be a good idea to generate a vertex array (a real one) & use it in 20 or so display lists (each display list being a frame of animation) for each entity??? Would this speed things up? A half a dozen of these entities are likely to be on the screen at any given time. Thats around 2000 polys which aint too bad I guess, but still, thats just entities & none of the particles or "terrain" yet.

Share this post


Link to post
Share on other sites
The way this is drawn won''t effect the normals right so I can use the backface culling?

AP- You would only have to update the array of vertexes for each "frame" and you can recycle the same index array. Putting each "frame" drawn via vertex arrays would speed it up but would eat a lot of vram if you have a lot. (I cant used the display list as my terrain is freaking huge).

Share this post


Link to post
Share on other sites
The winding order is the same for all polygons, so backface culling can be used.

AP: I didn''t entirely get what you were saying but here are a few points I think might be useful:
1. 2000 polygons is absolutely nothing these days.
2. If you want to put your entities into a display list it does not matter if you use vertex arrays or immediate mode. The only difference will be the time it takes to compile the display lists.
3. If your motion is simple harmonic you might want to use a vertex program to animate the entities, rather than storing individual frames. This will have the added bonus that the animation can be made frame-rate independant.

Enigma

Share this post


Link to post
Share on other sites
Enigma, qeustion on #2:

Wouldn''t drawing the vertex''s via a vert array in a display list be faster (basicly a VBO)?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I''m interested in the answer to skow''s last question.

Also... thanks for the points, I did find them useful.

I probably am NOT going to learn about a vertex program, because I already have the code to make the entities move & animate (periodic motion) independent of frame-rate. Thanks.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!