Landscape partitioning
Author
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.
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:
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.
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.
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.
Author
Do you deal with objects on the terrain seperately or do you work thme into the quad tree?
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.
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)
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.
NO SURRENDER and all that crap.
PS if any non (nothern)irish person gets this i will be quite surprised.
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!
Author
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement