• Announcements

Archived

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

Compiled Vertex Arrays and Octree

Recommended Posts

Spearhawk    145
Hi, I''m working on a terrain egine and right now I got a brutforce version up and runing (e.g. drawing every vertex, always). It''s a bit slow thought to I need to speed it up. I can see two ways of doing this, CVA and Octree. I got to beasic idea on how both work, but how make make them work together? In the octree example I have they simply store the vertexes in each node (well, end node) and then draws it using normal glVertex3f calls. I guess I could many CVAs, but wouldn''t that hurt performance? Is there a way to tell what parts of the CVA to draw, whitout needing to send it again? Or would it be better to just use normal vertex arrays? Thanks in advance Leon Ljunggren

Share on other sites
BlueCat    142
You just need to make four big arrays. One for vertices, colors, normals and texcoords (if you''re using all four). For each area you want to draw(each leaf node in a quad/octree) you will need an array of indices. Then for each node set up your indices to draw a ''square'' inside the large array.

You''ll need an array of indices:

if you use triangle strips, you would supply pairs of vertices

So the first index would be 0 (that''s the easy bit )

Next you would need an index for the vertex ''below'', on the next row. Normally in a single CVA this would be : 0 + n, where n is the width of each row, eg:

0, n, 1, 1+n, 2, 2+n, 3, 3+n

BUT, remember this will be INSIDE a bigger array so for the next row add the width of the larger array (be careful not to go beyond the edge of the large array)

When you have all the indices set up to render a square area, you will need to supply an address to the pointer functions.

Set all the pointers (glTexCoordPointer, glColorPointer, glNormalPointer, glVertexPointer) to the ''top-left corner'' address (they expect a memory location which is at the start of a vertex array) of the VA you want to draw.

glDrawElements also has a start address, use the same address as above

And there you go, you should now be able to draw any square(or rectangular!) area of an array.

This saves you setting up a separate array for each node when you implement your octree.

Hope at least some of that made sense, I know it works coz my engine does it this way.

Good luck

______________________________

Don''t ask me, I''m just the code monkey

Share on other sites
zedzeek    528
first before u do anything make sure u are geometry bound.
how to?
make the window small eg 200x100 does the framerate increase dramatically? if so youre fillrate bound and doing CVA,VAR whatever aint gonna help matters much.

http://uk.geocities.com/sloppyturds/kea/kea.html
http://uk.geocities.com/sloppyturds/gotterdammerung.html

Share on other sites
Spearhawk    145
zedzeek: Yes it's geometry, if I render every point of a 32x32 heightmap I get a fps of around 200, rendering every point of a 1024x1024 heightmap and I'm lucky if I get 0.5 fps.
But thanks for the tip, it could have been it.

BlueCat: Thanks, I think I understand the general pricipe (basicaly you make a CVA, then tell it which vertises to draw this time, correct?), but I don't really understand how to do it.
Lets say I wanted to render the trinagles in the picture. My vertex array would look something like this (3D, just happen to have y = 0): { {0,0,0}, {1,0,0}, {0,0,1}, {1,0,1}, {0,0,2}, {1,0,2}.... {1,0,6}, {2,0,6}, {1,0,5), {2,0,5}, {1,0,4}, {2,0,4}... etc

Now lets say I want to render the trinagles from the (3,3) and forward. How would I do that? I din't quite understand how that indices array was done. Did you mean that I would make a array like. {35, 49, 37, 47, 39, 66... etc?
How would I then pass it so that I can use it to read the corrent verteises from the CVA?
Wouldn't passing this array defete the point with a CVA? E.g wouldn't it be better just to use multiple CVs, one fore each node?

Thanks

[edited by - Spearhawk on October 23, 2002 6:57:55 PM]

Share on other sites
Digitalfragment    1504
My GOD - "rendering every point of a 1024x1024 heightmap" of course you are going to destroy your framerate.

Ever hear of a Binary Triangle Tree? I will cut down the polygons dramatically as well. It might help your problem a little. The doc for it is in the resources & articles section somewhere.

Share on other sites
BlueCat    142
OK, firstly I have tried both ways and one big array gave me much better performance. I too have a 1024x1024 heightmap with octree nodes approx 20x20x20 so that would be a lot of separate arrays! No reason not to try it yourself though

I wasn''t very clear about index arrays, the idea is that you have an array of vertices (you can also have arrays for normals, colors and texture coordinates but you should have at least a vertex array) which you fill with x,y,z values.

Make an array called myvertexarray, eg 9x9 = 81 vertices

The 1st X,Y and Z values would be at:

myvertexarray[0],myvertexarray[1],myvertexarray[2]

The X,Y and Z values at the start of the 2nd row would be at:

myvertexarray[27],myvertexarray[28],myvertexarray[29]

As an example, imagine you just wanted to draw one triangle, you could do it this way:

glBegin(GL_TRIANGLES);
glVertex3f(myvertexarray[0],myvertexarray[1],myvertexarray[2]);
glVertex3f(myvertexarray[3],myvertexarray[4],myvertexarray[5]);
glVertex3f(myvertexarray[27],myvertexarray[28],myvertexarray[29]);
glEnd;

or this way:

create an index array (let''s call it ''myindexarray''), fill it with these 3 values:

0, 1, 9

To render the triangle:

glVertexPointer(3, GL_FLOAT, 0, @myvertexarray); (Search the OpenGL docs if you want to know what all the parameters are)

glDrawElements(GL_TRIANGLES, 3, GL_UNSIGNED_INT, @myindexarray);

This will use the index array to look up the vertex data in the vertex array and send each one as though it were a glVertex call. Notice the ''GL_TRIANGLES'' which tells OpenGL to expect vertices 3 at a time.

To draw the entire array you would fill ''myindexarray'' sequentially with indices (3 at a time) to draw each triangle, you can also use GL_TRIANGLE_STRIP but wait until you have the triangles working

If you understood that bit, try this!

You should be able to see a red grid (4x4 vertices) at vertex 30. To render these you would need to put the following values in your index array:

30,31,39, 39,31,40, 31,32,40, 40,32,41, 32,33,41, 41,33,42,
39,40,48, 48,40,49, 40,41,49, 49,41,50, 41,42,50, 50,42,51,
48,49,57, 57,49,58, 49,50,58, 58,50,59, 50,51,59, 59,51,60

BUT what you actually need to do is use the address: myvertexarray + (30*3) in glVertexPointer and adjust your indices relative to that memory location

Like so:

0,1,9, 9,1,10, 1,2,10, 10,2,11, 2,3,11, 11,3,12,
9,10,18, 18,10,19, 10,11,19, 19,11,20, 11,12,20, 20,12,21,
18,19,27, 27,19,28, 19,20,28, 28,20,29, 20,21,29, 29,21,30

''WHY?'' I hear you ask, well there is a good reason. Those indices you put in your index array are OK when you only have 81 vertices, but your heightmap has 1048576 and indices are 16 bit values (You don''t really want to be using 32 bit indices now do you?).

So you can see, as I said in my previous post, you have to add the width of the larger vertex array (9) to reference the next row, you DON''T add the width of the smaller square (in this case 4)

Hope that helps

If I''ve made any stoopid mistakes, I''m sorry, it''s late

______________________________

Don''t ask me, I''m just the code monkey

Share on other sites
Spearhawk    145
quote:
Original post by BlueCat
Hope that helps

Ya, thanks! I wrote a small sample program to test it and it works like a charm. Now on to the reall challange, making it work with my egine.
Thanks once again, it was really usefull.

Share on other sites
zedzeek    528
>>zedzeek: Yes it''s geometry, if I render every point of a 32x32 heightmap I get a fps of around 200, rendering every point of a 1024x1024 heightmap and I''m lucky if I get 0.5 fps.
But thanks for the tip, it could have been it.<<

i said make the window smaller, not draw less points

http://uk.geocities.com/sloppyturds/kea/kea.html
http://uk.geocities.com/sloppyturds/gotterdammerung.html

Share on other sites
Spearhawk    145
Sorry, zedzeek. I misunderstood you post, when you siad fillrate I took it to mean the screen refresh rate. Which could be tested by drawing less points (e.g if it goes far faster than the screen fillrate, it''s not the refresh rate hindering it).
Anyway, rendering 1048576 vertises will requier an equal amount of function calls (twice or trice if color and texture). So eliminating as many of them as possible has to be good and even if it''s not, it''s much neater this way

Share on other sites
Basiror    241
id render such a terrain with triangle strip vertexarrays

Share on other sites
BlueCat    142
quote:
Original post by Basiror
id render such a terrain with triangle strip vertexarrays

Yeah that's how I do it, I just used triangles as an example as it's easier to follow.

To use triangle strips, you have to render across in one direction and then go to the next row and go back in the opposite direction and so on, with a redundant vertex at the end of each row. That way each 'patch' of terrain is rendered as a single strip. Of course, tri strips are MUCH faster than just plain old triangles

One thing to remember though, if you use an octree, you can't split a tri strip into separate triangles so you need to be careful where a strip crosses the boundary into other nodes or you might end up drawing each strip several times (think about it )

[EDIT]
This is a good reason to use a quadtree for a simple heightmap based terrain.
[/EDIT]

______________________________

Don't ask me, I'm just the code monkey

[edited by - BLUECAT on October 25, 2002 2:06:19 PM]

Share on other sites
zedzeek    528
>>Of course, tri strips are MUCH faster than just plain old triangles<<

true usually, though personally ive just ditched tri strips for plain old triangles for the terrain in my game

>>One thing to remember though, if you use an octree, you can''t split a tri strip into separate triangles so you need to be careful where a strip crosses the boundary into other nodes or you might end up drawing each strip several times (think about<<

make each node in your octree/quadtree contain one strip (no more no less)

http://uk.geocities.com/sloppyturds/kea/kea.html
http://uk.geocities.com/sloppyturds/gotterdammerung.html

Share on other sites
Spearhawk    145
I'm been trying to make my engine work with the vertex array using triangle strips, but I run into a problem that I can't understand why it appears.
It looks like it drawing to many trinagles. The first picture below is taken from above and the second from below.

Edit: Img no longer on the server
Edit: Img no longer on the server

(The rectangle in the middle and to the side is just part of the GUI).

I'm using GL_CULL_FACE GL_CCW.

Init code:

    // Create the vertex and texture cordinate arrayvertexArray = new float[mapWidth * mapWidth * 3];textArray	= new float[mapWidth * mapWidth * 2];// Init the vertex and texture coord arrayfor(y = 0; y < (unsigned)mapWidth; y++){	for(x = 0; x < (unsigned)mapWidth; x++)	{		// Calculate the vertex		vertexArray[j]	 = (float)x * scale;		vertexArray[j+1] = bitmap->Image((mapWidth * y) + x) * heightScale;		vertexArray[j+2] = (float)y * scale;		// Calculate the texture coordinte		textArray[i]   =  (float)x / (float)mapWidth;		textArray[i+1] = -(float)y / (float)mapWidth;		j += 3;		i += 2;	}}// Create the indices arrayindex = new unsigned short int[squareHeight * squareWidth * 2 + squareHeight + 1];j = 0;	// Reset the counter var// Init the indices arrayfor(y = 0; y < squareHeight; y++){	if(forward == true)	{		for(x = 0; x < squareWidth; x++)		{			index[j] = ((mapWidth * y) + x);			index[j+1] = ((mapWidth * y) + x) + mapWidth;			j += 2;		}	}	else	{		for(x = squareWidth; x > 0; x--)		{			index[j] = ((mapWidth * y) + x);			index[j+1] = ((mapWidth * y) + x) + mapWidth;			j += 2;		}	}	index[j] = ((mapWidth * y) + x);	j++;	forward = !forward;}index[j] = ((mapWidth * squareHeight) + x);  Drawing code:      glVertexPointer(3, GL_FLOAT, 0, vertexArray);glTexCoordPointer(2, GL_FLOAT, 0, textArray);glDrawElements(GL_TRIANGLE_STRIP, squareWidth * squareHeight * 2 + squareHeight + 1,			  GL_UNSIGNED_SHORT, index);

What am I doing wrong? To me it looks like the row isn't reversed, and thus it jumps down to 0 and stars drawing the tringale form there, but I am reversing it. I been trying to figure it out for a long time now but I just cna't seem to nail it donw. So any help would be greatly aprishiated.

Leon Ljunggren

[edited by - Spearhawk on December 11, 2002 4:43:54 PM]

Share on other sites
BlueCat    142
If you email me the whole thing I''ll see what I can do

I use Delphi usually but I can compare yours with my code and see what it does differently.

Can''t see anything obvious from the code you posted, it would be better if I could see it in action.

______________________________

Don''t ask me, I''m just the code monkey

Share on other sites
Spearhawk    145
quote:
Original post by BlueCat
If you email me the whole thing I''ll see what I can do

Hehe, thanks but i got it to work a while ago (well, actuly I didn''t get it to work but I found out that doing many tristrips was just as fast as a single one). I was just looking through old posts and notice that the imagines had been replaced by others so I edited the post, not realizing it would appear at the top again.

It look quite fine now actuly. I decided to go with a quadtree, as you recomended, and added frustum culling to that. So now I get a nice and stable fps on about 90. Now I''m only looking into using the GL_NV_vertex_array_range in order to speed it up some more.

Screenshot

Thanks for the help

BlueCat    142
You''re welcome!

Looks nice BTW