Jump to content
  • Advertisement
Sign in to follow this  
Paul7

Terrain - Quadtrees

This topic is 5061 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
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
Sign in to follow this  

  • 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!