• Advertisement
Sign in to follow this  

Terrain - Quadtrees

This topic is 4786 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 starting to optimise my terrain by firstly using a quadtree to cull some of the geometry. I understand the principle of quadtrees I just need some clarification on how to arrange and render my terrain data. Firstly say my terrain is 512x512 should I split it up into patches of say 16x16 or 32x32 for example then use these patches with the tree? Ive seen in a number of articles that they use a terrain of for example 513x513 instead of the 512x512, should I be doing this, if so how does this help? Then for rendering the terrain i`m using directX vertex and index buffers. Should I create a vertex and index buffer for every patch in the terrain and then only render the ones that are visible, using the quadtree? or is there a more optimal way of doing this? Thanks

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
My idea:
Use power of 2 sizes for the terrain.

1.
Make a large vertex buffer which holds all vertices of the terrain.

2.
Split terrain in 16x16 chunks or so -> this will be the leaves of the quad tree.

3.
each chunk has it own index buffer in the vertex buffer.

4.
Rendering:

procedure renderNode(Node n)
begin
if (n is visible)
begin
if (n is leaf)
begin
renderAttachedIndexBuffer();
end
else begin
for (each child node c)
begin
renderNode(c)
end
end
end
end


Just an idea...
cu Sebastian

Share this post


Link to post
Share on other sites
THe reason why you use 2^n+1 points is because when doing multiple levels of detail, you can use the same points.

*--*--*--*--*
| | | | |
*--*--*--*--*
| | | | |
*--*--*--*--*
| | | | |
*--*--*--*--*
| | | | |
*--*--*--*--*

can reduce to

*-----*-----*
| | |
| | |
| | |
*-----*-----*
| | |
| | |
| | |
*-----*-----*

If you do any other number, it wont break down as nicely into a lower lod. For your quadtree, you will also notice that your quadtree boundaries will fall on discreet points, rather than between two points as 64 points will cause.

Share this post


Link to post
Share on other sites
You can still use others, just thats why people do (2^n) + 1.

If you arrange your vertex data correctly, you can use the same index buffer for all the different subsets of data you break your data into. Then all you need to do is set up the index buffer, change the vertex/texture/normal data streams and keep rendering with the same index list.

Share this post


Link to post
Share on other sites
thanks for the replies, Just one more thing,

if I use one vertex buffer for the vertices of the terrain and then have different index buffers as sebastian suggested would this mean that all the vertices are processed but only the ones in the index buffer are drawn, or are only the vertices that the index buffer refers to processed and drawn. Not too sure how this works in the rendering pipeline.

If the first is the case then this wouldnt be a good way would it as all the vertices would still be being processed.

Think that makes sense. Thanks

Share this post


Link to post
Share on other sites
Upon changing my terrain from 256x256 to 257x257 my terrain is now all messed up. I have tracked down the problem to be someone in the index buffer creation.
My code is as follows:

// Now create our index buffer, large enough to hold the indices
if (FAILED(gDevice->CreateIndexBuffer(num_tris*3*2,D3DUSAGE_WRITEONLY,D3DFMT_INDEX16,D3DPOOL_MANAGED,&gIB, NULL)))
return FALSE;

// Lock the IB
if (FAILED(gIB->Lock( 0, 0, (void**)&indices, 0)))
return FALSE;

count=0;
for (i=0;i<255;i++)
{
for (j=0;j<cell_X-1;j++)
{
// create vertex index from co-ordinate
int id=(int)(j+(i*(cell_X)));

// tri 0
indices[count]=id;
indices[count+1]=id+(cell_X);
indices[count+2]=id+1+(cell_X);

count+=3;

// tri 1
indices[count]=id;
indices[count+1]=id+1+(cell_X);
indices[count+2]=id+1;

count+=3;
}
}
// and again remember to unlock the buffer
gIB->Unlock();







When the variable i in the loop is 254 or above I`m getting some odd results that I presume is causing my problem. An example of this is as follows:

indices[count]=id;
indices[count+1]=id+(cell_X);
indices[count+2]=id+1+(cell_X);

when count is = 390150, id = 65279 and Cell_X = 257 I get the following results from the above code:

indices[count]=65279
indices[count+1]= 0
indices[count+2]= 1

How can the last two results be possible. I`m thinking the problem must be something memory related. When the terrain is smaller, say 129x129 or 33x33 I get no problems and even at 256x256!

Does anyone have any ideas how to resolve this issue.

Share this post


Link to post
Share on other sites
I dont have any DX knowledge but it seems that you are using 16bit indices (D3DFMT_INDEX16) and with a terrainsize of 257*257 you need more than 2^16 values to index all of them. It works for 256 (and less) sized terrains because 256*256 = exactly 2^16.

Using 32bit indices should solve the problem.

Share this post


Link to post
Share on other sites
Yeah thats sorted it, didnt know about that, thanks alot Pancake!

Share this post


Link to post
Share on other sites
Ive kinda got the basics sorted now, I`m just not too sure on the data structure.

At the moment Ive got a node structure as follows:

struct node
{
---Data----

node *child; //Pointer to 4 children nodes
};

The problem with this is how I go about traversing the tree. The way Ive got it now I have to do it like this to refer to a specific node:

tree.child[0].child[1].child........

this proves real difficult to create a generic loop to traverse the entire tree and to check whether its in the view frustum.

Are there any other better methods of doing this, maybe using a list? or maybe theres an easier way using the method I`m already using?

Any thoughts? thanks.

Share this post


Link to post
Share on other sites
You *really* should look into recursion. Something like:

render( node n ) {
// ...render this node...

// recursive calls
if (child != null) {
for (int i=0;i<4;++i) render( n.child );
}
}

Share this post


Link to post
Share on other sites
oh yeah, am using recursion to create the tree, didnt think of using it in the rendering. Thanks

Share this post


Link to post
Share on other sites
Do people really use recursion when traversing trees in production software? Wouldn't it be faster to use your own stack instead of hacking the call stack? Or would it really make any difference?

Share this post


Link to post
Share on other sites
Yeah, I fear the call stack so I use my own stack when going through the quadtree. I heard no one uses recursion in released software so I stopped using it.

Share this post


Link to post
Share on other sites
If you're going to recurse a few levels, it's not a big deal. If your base chunk size is 17x17 on a 513x513 map, you're only going to recurse, what, 5 levels or so. That's fine. It's times when it may recurse dozens, hundreds or thousands of times that you should try to avoid it.

Share this post


Link to post
Share on other sites
no i dont think either recursion is something to be avoided here. its not THAT time critical is it?

id use recursion, just because its prettier/shorter to code.

Share this post


Link to post
Share on other sites
I have an odd question. I implemented a quadtree that from what I can test, doesnt care about the size being by 1 or 2. When I process my map I have it split the lowest nodes by dividing say 257 by 2. Which is 128.5 on both sides. If A triangle crosses that boundry either split it or render it depending on whatcha like. If your working with ints I can understand why it wouldnt work, but most terrain needs to be more exact than that doesnt it?

Paul7, I break my terrain up at compile time, and then send the triangles to the program with the size of the boundaries. so say the size is - 256 to 256, I simply cut at 0(the middle) at run time and walk the nodes (recursion) and place everything together. With vectors in the optimize compiler settings, it takes me roughly 5 seconds to load a large map. I dont think any1 would need it faster, but if so you can precompile every node then write your file output for that.

I upon compile time walk though the nodes and each triangle is linked to a index number(part of the structure) that is in the most child node. I simply say, if im at the child node, then it must be in view and add the vertex's index numbers to a dynamic index buffer. And continue through the nodes. Once this index is built I render the terrain. It might be slower than others, but again Its so damn fast for me I dont complain.

Share this post


Link to post
Share on other sites
Thanks for the help, Ive got all my boundaries defined now and in the tree but am just a bit stuck now as how to assosiate a chunk of terrain with each of the leaf nodes of the tree?

Also would it be better having a dynamic index buffer or a different index buffer for each leaf node? surely a dynamic one would be slower but lots of them will use more memory, dont no which is best!

Share this post


Link to post
Share on other sites
If you organize your vertex memory like this:


A1----A2----A3B1----B2----B3
| | | | |
| | | | |
| | | | |
A4----A5----A6B4-----B5----B6
| | | | |
| | | | |
| | | | |
A7C1--A8C2--A9C7----B8-----B9



WHere A, B, C, etc is each leaf node, then your index order will be the same for each leaf, so you can use one index list and just change the pointer. Point to A, render vertex 1,4,2,5,3,6 then point to B render vertex 1, 4, 2, 5, 3 6.... etc.


THen if oyu need to go back and implement LOD, you can create a new index list and it will work on all your leaf nodes again.

Share this post


Link to post
Share on other sites
Right so Ive got my quadtree all set up, if I draw all the leaf nodes I get the complete terrain which is what I want. I now have to implement frustum culling. The way ive got it is that each node of the quadtree defines a bounding box (2D) so I have to check the left, right, near and far clip clip planes of the view frustum again this, is this right? it shouldn't be 3D?

Anyone have any good resources on how to get the planes of the view frustum in DirectX?

Share this post


Link to post
Share on other sites
Well if your doing a quad-tree then no its 2d, if your doing an Oct tree then your spliting up the height too. For me its a waste of time to check height. But the other post had it dead on, just get new pointers, dont keep copying info itll take too long and waste space. Keep the verts the same but change the index. And hold pointers within the leaf nodes to the triangle's indecies.

check out here, this is by far the easiest method of doing culling on a quadtree. Very easy to understand, comparably that is.
right ive got the main code set up now but the problem is that it culls some of the terrain but not the right parts. Can anyone see anything wrong with the following code that I`m using to determine whether the quad tree nodes are within the frustum? The code might not be the most optimal but I just wanna get it working first.


void CGfxEntityTerrain::RenderTree(node *current_node, int level)
{
int cont = 0;
float minX = current_node->position[0].x, minZ = current_node->position[0].y;
float maxX = current_node->position[1].x, maxZ = current_node->position[1].y;
cont = CheckAgainstPlanes(minX, maxX, minZ, maxZ);

if(cont == 1)
{
if(current_node->node_type == ROOT || current_node->node_type == BRANCH)
{
for(int i = 0; i < 4; i++)
{
RenderTree(¤t_node->child, level+1);
}
}
//got to the leaf node so draw it
else
{
gDevice->SetIndices( current_node->index_buffer);
gDevice->DrawIndexedPrimitive( D3DPT_TRIANGLELIST,0,0,num_vert,0, num_tris);
}
}
}

int CGfxEntityTerrain::CheckAgainstPlanes(float minX, float maxX, float minZ, float maxZ)
{
int inplane;
float test;
D3DXPLANE *clip_planes = gCamera->m_frustum;
//0: Left 1: Right 2:Near 3:Far 4:Top 5:Bottom
D3DXVECTOR3 Quad[4];
//Bounding box of the trees node
Quad[0].x = minX; Quad[0].y = 0.0; Quad[0].z = minZ;
Quad[1].x = maxX; Quad[1].y = 0.0; Quad[1].z = minZ;
Quad[2].x = maxX; Quad[2].y = 0.0; Quad[2].z = maxZ;
Quad[3].x = minX; Quad[3].y = 0.0; Quad[3].z = maxZ;

//test against 4 clip planes LEFT, RIGHT, NEAR, FAR
for(int i=0; i<4; i++)
{
inplane = 0;
D3DXVECTOR3 plane_norm;
plane_norm.x = clip_planes.a; plane_norm.y = clip_planes.b; plane_norm.z = clip_planes.c;
//test 4 corners of bounding box
for(int j=0; j<4; j++)
{
test = D3DXVec3Dot(&Quad[j], &plane_norm) + clip_planes.d;

if (test>=0) inplane++;
}
//if none of the points are within this plane then its not within the frustum
if(inplane==0) return 0;
}
return 1;
}












Also I`m extracting my frutum using the method described in the article mr grinch provided. Am I right in using the view*projection matrix as my matrix to extract the planes from? (the combomatrix in the example code)

Thanks

*EDIT Just noticed that changing the y value of the quad for the quadtree makes it change, dont want this to be the case need it all in 2D, can I just drop the b component of the plane equation to make the plane normal in 2D?

[Edited by - Paul7 on January 11, 2005 11:21:56 AM]

Share this post


Link to post
Share on other sites
sorted it now just needed to swap the axis of the quadtrees bounding box around. works fine now apart from if I look up at a fairly steep angle I can see areas 'popping' in and out. Is this a drawback with doing it in 2D only.

I`m not getting that much of a frame rate increase either apart from when I move towards the edges of the terrain. If a turn off everything but the terrain it goes up from 30ish to about 100+ fps, could it be that my prob is more fillrate related? If this is the case whats the best way to sort this out?

Thanks

Share this post


Link to post
Share on other sites
You should NOT see popping at any angle in 2D checking. Thats the beauty of it. I would say you have something wrong with your checking. Rememberthe difference between radians and degrees. I know this sounds stupid but its an easy mistake to make if you havent messed with your terrain in awhile, I made this. Also try cutting out your box to box testing temporarily and use just sphere box testing, and visa-versa to find where the problem is. This is what I did and found my problem was within the box-box testing.

Like I said, not to say yer an idiot, I did these things, and they are very easy to do, you should not see any popping of any sort...

One other test, it might be the distance of your frustum? try extending the distance to a very FAR amount...

and your frame rates wont see muchof in increase untill you get ALOT of culling going on, so put in a HUGE terrain and you will notice a massive increase. And try optimizing the code...For instance in your draw routine try to add the indecies to a larger buffer instead of drawing each patch(leaf) seperate.... I love quadtrees as you can see :).

Enjoy, hope something works for ya here.

Share this post


Link to post
Share on other sites
i am wanting to do the same kinda thing. but since my data is about 10,000 X 5,000 X 3 i will have to use ROAM or something like that. i dont think chunks would work for me.. or would it?

i have looked at some ROAM source code and i understand the concept of splitting up triangles but implementing it is a totally different matter. it isnt trivial at all.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement