Jump to content
  • Advertisement
Sign in to follow this  

Implementing quadtrees

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

Hi all, I’m currently trying to implement a quadtree system to my terrain engine and have encountered some problems. I am currently using the following article as a guide http://www.gamedev.net/reference/articles/article1303.asp but there are a few areas causing me trouble. I am currently at the stage where I have created classes for my QuadTree and QuadTreeNode featuring functions to split any quad into four smaller quads and storing all the bounding data. The thing I am unsure about is when creating my terrain and I am ready to store it in the quadtree im not sure how many times I need to split the current terrain? The article highlights this as the equation for the number of nodes (GridWidth)squared / LeafWidth but I really don’t understand what the author means by leafs, any ideas? Secondly I am unsure about how much terrain data needs storing in my quadtree? Currently I am under the impression that I can leave all my IndexBuffer and VertexBuffer as they are in my terrain class, but then how do I calculate what offset I need to use on my IndexBuffer when rendering? Thanks a lot for any help, Ben

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
about the 1st question:
you stop when you decide to stop :). Generally, you have a limit like: don't sub-divide this leaf if the number of objects inside of it is smaller than xpto.

Share this post

Link to post
Share on other sites
For your second question, the only way you can keep the index buffer out of the quadtree structure and use indexing is if your index buffer conforms with your quadtree.

By this I mean that all of the polygons for any given octree square are grouped together in your index buffer. Chances are they aren't. However, this is pretty simple to do.

All you have to do is clip your terrain to your quadtree and store small index arrays for each octree leaf. An octree leaf is the lowest level node of the tree and any node that isn't a leaf is a branch. Think of an actual tree.

Once you've done that use a simple recursive function that copies the data in to one index buffer. It'd probably look someat like this

CreateIndexBuffer (Quadtree, CurrentQuadtree, IndexBuffer)
If Quadtree[CurrentQuadtree].ChildCount = 0 then
IndexBuffer = IndexBuffer + Quadtree[CurrentQuadtree].IndexArray
Quadtree[CurrentQuadtree].IndexArray = 0
for i = 1 to 4
CreateIndexBuffer (Quadtree, _
Quadtree[CurrentQuadtree].Children, IndexBuffer)
next i
end if

Call the function with CurrentQuadtree as 1 (the node you started with before you started splitting). It then adds the node's index array to the index buffer if the current node's a leaf otherwise it goes through the node's children and calls the function for them.

Notice that, not only are the leaf polygons grouped together but so are all the other node polygons. This doesn't even change the size of the index buffer as long as your geometry splits perfectly along your quadtree structure - not always possible.

I hope some of that helps you out


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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!