# Landscape partitioning

## Recommended Posts

Okay, I know this will be seem like, and probably is, an incredibly noobish question but I have no idea what the answer is. I have written 3d apps before but not anything that required any real efficiency. My current project is going to basically consist of sheep running over a mostly plain landscape. The landscape itself will be made of a regular grid on the xz plane and will be raised / lowered along y to create the hills / valleys. I have no idea how best to organize the data. I read about BSPs. They seemed to be mostly described using corridors as a model so I couldn't gauge their usefullness for terrain. I also couldn't find how to add moving objects into a BSP scene without having to reform the entire tree each frame. Octrees seemed too comlex for a this project. Should I use a BSP? If not, what? If someone could point me in the right direction I would greatly appreciate it.

##### Share on other sites
Quadtrees are your friends for terrains. you split the terrain recursivly on both the X and Z axis, starting from the root node (the whole terrain).

The split creates 4 subnodes for each node (thus then name quadtree). Here's a figure:

+------------+       +-----------+|            |       |     |     ||  Root      |       | 1   | 2   ||            |       |-----+-----||  Node      |       |     |     ||            |       | 3   | 4   |+------------+       +-----------+

You do this operation recursibly until you get to a set depth in the tree which gives best results for both the tree size and the size of the node (how many vertices it contains).

Use a terrain size of 2^n + 1 which creates 2^n quads (or pairs of triangles) so you can split the terrain in 2 for each axis at each step.

##### Share on other sites
Thanks. I'll look into quad trees.

##### Share on other sites
Terrain LOD techniques fit nicely with the quadtree too. I have implemented Chunked LOD which greatly takes advantage of a quadtree, and it performs *very* nicely! And then frustum culling, and everything else the tree gives you is readily available as well.

##### Share on other sites
Do you deal with objects on the terrain seperately or do you work thme into the quad tree?

##### Share on other sites
Quote:
 Original post by stroDo you deal with objects on the terrain seperately or do you work thme into the quad tree?

It's better to deal with them separately because they may be larger than the quadtree node so if you do frustum culling using the node's bounding boxes you might clip the objects when they are visible.

##### Share on other sites
Quote:
 It's better to deal with them separately because they may be larger than the quadtree node so if you do frustum culling using the node's bounding boxes you might clip the objects when they are visible.

This is only true if you only allow geometry in leaf nodes of the quadtree.

Any sensible implementation will allow geometry in the branches.

With this scheme geometry should be placed in the deepest node that it will still completely fit within, and then frustum culling will work properly.

One of the Game Programming Gems books describes "Loose Octtrees" which might be useful if you have a lot of inter-object spatial tests that need to be performed on moving objects, but that may be overkill for your problem. (Note that quadtrees are simply octtrees which ignore one of the dimensions)

##### Share on other sites
an irishman looking to partition a landscape???!! you know thats just going to lead to trouble.
NO SURRENDER and all that crap.

PS if any non (nothern)irish person gets this i will be quite surprised.

##### Share on other sites
Quote:
 Original post by Anonymous PosterThis is only true if you only allow geometry in leaf nodes of the quadtree.Any sensible implementation will allow geometry in the branches.

That sounds like a good ideea!

##### Share on other sites
Quote:
 Original post by SoDditan irishman looking to partition a landscape???!! you know thats just going to lead to trouble. NO SURRENDER and all that crap.PS if any non (nothern)irish person gets this i will be quite surprised.

Brilliant [smile]

##### Share on other sites
I don't see why it's not sensible to divide the diff types of geometry. If a lot of objects happen to span two child nodes to the root node (following a strict quadtree), then you'll see those objects all over the map. You could use loose boxes to avoid these splits, but then the terrain won't be as efficiently culled. Using separate trees will increase traversal time, but it will also make sure the types are handled correctly and in the best way possible. It's a matter of experimentation for your app, but for the general case, I'd go for two trees.

##### Share on other sites
>>an irishman looking to partition a landscape???!! you know thats just going to lead to trouble. <<

hehe though in that case i believe it was the english that doone the partition

##### Share on other sites
I think it should be feasible to store the geometry in the same tree, if the objects are all static meshes. If they're dynamic, use a different tree.

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627667
• Total Posts
2978533

• 10
• 10
• 12
• 22
• 13