Jump to content
  • Advertisement
Sign in to follow this  
Stephen R

Landscape partitioning

This topic is 5056 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

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!