Jump to content

  • Log In with Google      Sign In   
  • Create Account

help, vert array mesh with TRIANGLE_STRIP


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
18 replies to this topic

#1 skow   Members   -  Reputation: 248

Like
Likes
Like

Posted 21 February 2004 - 10:35 AM

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]

Sponsor:

#2 Enigma   Members   -  Reputation: 1402

Like
Likes
Like

Posted 23 February 2004 - 02:22 AM

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

#3 skow   Members   -  Reputation: 248

Like
Likes
Like

Posted 23 February 2004 - 11:10 AM

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!

#4 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 25 February 2004 - 11:42 AM

Awesome description!! I have one question though:

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


#5 Enigma   Members   -  Reputation: 1402

Like
Likes
Like

Posted 25 February 2004 - 01:17 PM

No, degenerate triangles are culled (very quickly these days) and do not add any pixels to the framebuffer.

Enigma

#6 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 25 February 2004 - 04:07 PM

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.

#7 skow   Members   -  Reputation: 248

Like
Likes
Like

Posted 25 February 2004 - 04:37 PM

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).

#8 Enigma   Members   -  Reputation: 1402

Like
Likes
Like

Posted 26 February 2004 - 03:00 AM

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

#9 skow   Members   -  Reputation: 248

Like
Likes
Like

Posted 26 February 2004 - 05:20 AM

Enigma, qeustion on #2:

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

#10 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 26 February 2004 - 05:26 AM

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.


#11 Enigma   Members   -  Reputation: 1402

Like
Likes
Like

Posted 26 February 2004 - 05:29 AM

In a display list the vertices are dereferenced at display list creation time and compiled. If you create a vertex array list, then create a display list from that array list and then change the data in the array list the display list will still contain the old data.

So whether you use array lists or immediate mode the vertices end up stored in the same manner in the display list. The only difference is the speed at which the lists are compiled (many function calls vs few function calls).

Enigma

#12 skow   Members   -  Reputation: 248

Like
Likes
Like

Posted 26 February 2004 - 05:36 AM

So VBO''s arn''t any faster at drawing than a vertex array? I coulda swore some one did some tests and got a huge prefomance increase when he put the vert arrays in dlists.

Sorry for basily asking the same question, I just don''t wana misunderstand.

#13 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 26 February 2004 - 05:36 AM

Enigma,

will a diplay list with:

for(i=0;i<something;++i)
{
glbegin(tri_strips);
//
//draw some verts
//
glend();
}

inside of it run as fast as a display list with:

glbegin(tri_strip);
draw_vertex_array(); // 1 tri long strip with deg. tri''s
glend();


??????


#14 skow   Members   -  Reputation: 248

Like
Likes
Like

Posted 26 February 2004 - 05:41 AM

AP, I hope that isn''t how you use vert arrays

#15 Enigma   Members   -  Reputation: 1402

Like
Likes
Like

Posted 26 February 2004 - 05:47 AM

AP: providing the vertices are exactly the same they should render at exactly the same speed (i.e both methods use 1 triangle strip with degenerate triangles). A caveat that I should have mentioned before is that the drivers may compile the data differently, in which case there may be a speed difference. I do not know whether there are any drivers that do this. Any speed difference will be entirely due to driver implentation though, there is no functional reason for a speed difference.

skow: Vertex Buffer Objects are different to array lists in display lists. Also see my caveat above. If you can find the source of those test I'd be interested to see. Simplest way to check for yourself is to try it. Just make sure you use a large data set though.

Enigma

EDIT: clarification

[edited by - Enigma on February 26, 2004 12:48:11 PM]

#16 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 26 February 2004 - 05:59 AM

skow,
I have never used vertex arrays before, but I assume that there are NOT multiple glbegin() & glend() calls in them, I assume you just call the gl_graw_vertex() function (or whatever its named) & pass it one long tri strip & it renders it all at once, versus say... that first method I showed above where I draw something using several glbegin() & glend() calls to draw the entity with several smaller tri strips. Instead of the one long tri strip for the vert array.

the point to the Q above was... is using one big vertex array in a display list better than just drawing several smaller tri strips (inside a loop).

#17 skow   Members   -  Reputation: 248

Like
Likes
Like

Posted 26 February 2004 - 06:42 AM

Enigma I'll try it out later and see if there is any diffrence. Right now the terrain I'm doing is much to large for displaylists (4.6+ milllion verts, broken down into 260,000 5X5 meshes). But when I have a chance I'll do so testing to be sure.

Thanks again.

[edited by - skow on February 26, 2004 1:43:10 PM]

#18 clutch   Members   -  Reputation: 122

Like
Likes
Like

Posted 26 February 2004 - 06:47 AM

Vertex arrays are used with glDrawElements and such.

Using Blender I have been able to pull out the vertex points AND ther index points AND the normals so I can draw any mesh I export from blender into opengl using a custom Python exporter in blender and my model loading code in Blender. Texturing should be easy, I have yet to do that part of it. My next goal is to see if I can pull out armature information from Blender and then have skeletally animated models for OpenGL from a free modeler. If anyone is interested in seeing the end result of this let me know.

Clutch

#19 Enigma   Members   -  Reputation: 1402

Like
Likes
Like

Posted 26 February 2004 - 09:19 AM

AP: I imagine there is likely to be some performance difference in favour of vertex arrays in that case, but it will be driver dependant as to how much of a difference.

Enigma.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS