Jump to content
  • Advertisement
george7378

Optimization Deciding when to update my quadtree terrain

Recommended Posts

Hey everyone,

I'm designing a game which uses a quadtree system for creating and rendering terrain. There's nothing special about it - just create a single root tile covering the whole area, traverse the tree from the root and, using the camera position, split/merge cells to move the detail around where it's needed.

I'm happy with how it works, but I'm trying to come up with a better way to decide when I actually need to traverse the tree. Right now I'm using brute force and doing it every single frame, which seems like overkill as the camera isn't moving very quick. It seems like a waste of CPU time to force updates that regularly. I also tried doing the same thing but on a background thread, but this wasn't ideal either as it just seemed to lock up and I was only seeing the terrain update every 10 seconds or so. Plus I find that threading with more complicated stuff like this is a great way to take something that I understand, and turn it into a mess of hidden problems!

I guess I could put a timer on and update every ~second, possibly using a background thread to create a brand new terrain tree and swapping it out with the current one when it's ready (so I know for sure there aren't any conflicts with the terrain that I'm using and drawing), but that doesn't seem like a very intelligent way of doing it either.

Does anyone out there know a better way to decide when I should re-traverse and update my quadtree terrain?

Thanks for the help!

Share this post


Link to post
Share on other sites
Advertisement

I am not yet multi-threading. Atm i do the update every frame. It is not much work, just a view frustum check over the bounding boxes. Algorithm i use is cdlod. (Edit: i should say strongly based on ...) The quad tree is tile specific and is built while loading a tile. Only the selection of the nodes to draw is done every frame. CPU side is not the bottle neck.

Edited by Green_Baron

Share this post


Link to post
Share on other sites

Ah so you create/store every possible node when you begin, and just pick the ones to draw each frame? That's not a bad idea. I'll give that a go and see how much memory it uses for my game.

My algorithm is based on this paper, where each node is an N x N vertex grid and a bunch of pre-determined index buffers are used to fix cracks where different edges meet.

Share this post


Link to post
Share on other sites

I'm using kind of a chunk system. It's splits or merges chunks as you move around and also splits or merges all triangles in the those chunks to match.  A chunk is considered some point in the overall tree and everything under it. Each node in the tree has a bounding volume and as you go down the tree it calculates at what level a chunk should be, based on the square of the distance from the bounding volume to the camera.  Then there are rules......

For instance if you reach a point in the tree that should be the top of a chunk and it is in fact a chunk top, then you don't have to go further. If you reach a point where there is a chunk top but the chunk top should be further down in the tree based on the distance calculation, then you have to split the chunk into multiple chunks. Conversely if you reach a point where there should be a chunk top but you haven't encountered one yet on your way down the tree, you have to merge all chunks below that point into a new chunk that you create at that point in the tree. 

This way if you just move the camera just a little and nothing has changed, you only have to go down to the top of each chunk and not to each triangle within the chunk. You can see it in action in the first part of the video in my last blog entry. The system also works for voxels using an octree, but this one uses a quad-tree since it's dealing with height-mapped terrain albeit wrapped around a sphere. It's really just flat terrain here because it's a sun, but it would work for other terrain too.


 

Edited by Gnollrunner

Share this post


Link to post
Share on other sites

A thing i like about doing selection each frame is that one can for example change depth or field (far plane - near plane) on the fly and recalculate (within limits) the depths and transition areas for each lod level in between frames. So that the view to the horizon from a mountain top has different lod levels (provided the tiles with height data are loaded) than one needs when driving through a narrow valley.

A moon doesn't have graceful fog ....

Edited by Green_Baron

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

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!