Sign in to follow this  
Magmatwister

Terrain Quadtree

Recommended Posts

My terrain will have largely varying heights and I need to be able to frustrum cull accurately with a Quad-tree that subdivides it. This creates a problem: The 2d bounding boxes. I've heard that an octree is another option, or I could simply create a "2.5D Quadtree", wherein the bounding boxes for each leaf or node has 3 dimensions instead of 2. Which one do you guys suggest???

Share this post


Link to post
Share on other sites
This depends on ur terrain and how u use it.
If u look from far 2d sounds good.

If ur terrain is detailed and ur running around in it, Octree might be good since u can easly check if u see the sky(top box) and so can skip the stuff behind. I really would use Octree since they arent much harder to code then 2d and should be much slower.


I dont know 2.5D sry ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by fenghus
If your terrain is based on a heightfield (ie. no overhangs) definately 2.5D - it's less data and should give better fitting bounding boxes.


Yea I plan to generate my terrain from a perlin noise heightmap. One more question though (I plan to use Quadtree for now based on the replies I've gotten), do I need to seriously watch how small my terrain leafs are? If all my terrain leaf's have bounding boxes, not only will many many frustrum test's need to be conducted (Despite all of the efficiency gained by ignoring large subsets of leafs), It could potentially use alot of memory. I plan to have a very large terrain (probably 10km * 10km). To save memory, shall I remove vertices that are very far away from the main terrain buffer and add them again later when they become visible (X, Y Co-Ordinates will be easy to generate and perlin noise height never changes), or Should I do that AND delete nodes/leafs out of my Quadtree? I know that optimisation Is going to be the key If I want this to run decently without losing a riddiculous amount of frame time.

Share this post


Link to post
Share on other sites
Hey,
why u dont use a moveable octree. Means it takes ur position
and if u move into another quadrant, u just transform the input of the requested data. So ur Octree will be fixed in size etc and
u can load/release quadrants into memory if they come into the octree dynamicly.

This way there should be a problem with huge maps, since u can have u map sized on a dimesion u want and jsut focus on some parts of it dynamicly.
If u size the octree together with max view distance u should be fine.

good luck

Share this post


Link to post
Share on other sites
Consider a sparse 3D uniform grid

Very cheap, very fast and they act like a modulo grid as you travel the terrain also

They can be faster to query than hierarchical index also:

- calculate frustum aabb rounded to grid cells
- enumerate each grid cell
- if passes frustum intersect *and* contains something - render

deleting cells is easy - no hierarchy to consider and you know the maximum no of cells required in advance ...

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