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

## Recommended Posts

Im 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 im 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 on other sites
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 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 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 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 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 Im 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. Im 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 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 on other sites
Yeah thats sorted it, didnt know about that, thanks alot Pancake!

##### Share on other sites
Ive kinda got the basics sorted now, Im 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 Im already using?

Any thoughts? thanks.

##### 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 );   }}

1. 1
Rutin
64
2. 2
3. 3
4. 4
5. 5

• 16
• 10
• 29
• 20
• 9
• ### Forum Statistics

• Total Topics
633413
• Total Posts
3011759
• ### Who's Online (See full list)

There are no registered users currently online

×