Sign in to follow this  
Stephen R

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by stro
Do 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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
This 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 this post


Link to post
Share on other sites
Quote:
Original post by SoDdit
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.


Brilliant [smile]

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this