Jump to content
  • Advertisement
Sign in to follow this  
Toolmaker

Little QuadTree issue...

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

I wrote a QuadTree class a while back, and I was going to use it for my current RPG project to cut up the collision detection and rendering zones to speed things up. However, when I use 64 as the minimal I have to use a power of 2 for the map size at the moment, or the quadtree keeps dividing itself until a stack overflow occurs. However, I don't want to use power of 2 for all my maps, especially inside maps. How would I go to solve this? Just check if both the height and width of the cell are smaller than the cellsize and then stop? Toolmaker

Share this post


Link to post
Share on other sites
Advertisement

You could just make your quadtree size the next power of two up from your map size and just leave the extra area empty. Easy. Your way would work too, though.

Share this post


Link to post
Share on other sites
Quote:
However, I don't want to use power of 2 for all my maps, especially inside maps. How would I go to solve this? Just check if both the height and width of the cell are smaller than the cellsize and then stop?


Spatial division does not require you to have dimensions power of two. It doesn't even require quads or rectangles. It can be done on arbitrary n-dimensional geometry.

You need to define basic operations
- Divisible( Geometry ) // Can the geometry be further divided
- Subdivide( Geometry ) // Divide geometry into sub-regions
- Full( Geometry ) // Can we insert into current geometry?
- Find( Geometry, Object ) // find which sub-geometry to insert the object into
- Attach( Geometry, Object ) // add Object to Geometry

Then your algorithm becomes something like:

Insert( Geometry, Object ) {
If Full( Geometry ) {
If ( Divisible( Geometry ) {
SubDivide( Geometry );
Insert( Find( Geometry, Object ), Object );
} else {
// we're full, we can't subdivide
// either fail, or overflow
}
} else {
Attach( Geometry, Object )
}
}



There's no need for power of two, rectangles, you can use spheres, triangles, hexagons, arbitrary dimensions, you can subdivide into n subregions, into 2, ....

There's a whole science studying optimal partitioning.

For quads, your new quads will be (assuming integers):
w = width / 2;
h = height / 2;
1 : ( w, h );
2 : ( width - w, h )
3 : ( w, height - h )
4 : ( width - w, height - h )

They won't always partition evenly (+/- 1), but they'll work, as long as the smallest width and height are larger than 1. At 1, you can't subdivide any further.

Share this post


Link to post
Share on other sites
Quite often, quadtrees (and octrees) get into grief when the planes they split the world up with cut through lots of objects. No matter how many times the quadtree cell subdivides itself and its children, those objects are stuck on the split plane get stuck high up in the tree.

When you were using a power of 2 map, you actually have a special case which is remarkably octree friendly. Most of the time, octree & quadtree implementations need to handle the more general case where objects do not fall nicely into a single quad.

So the first thing I would do is to modify my quadtree class to handle objects that cut across a split plane. Typically, there's some part of your code which says "if( numChildren > MAX_CHILDREN_IN_CELL) subidivide();" and somewhere around that the logic around this need to accept the fact that subidividing won't always reduce the number of children. Once a node is subdivided, you never try and subdivide it again. If objects are added to that cell after it has been subdivided, you first see if you can throw it into any children, and if not, you keep it up at the parent. The next thing is you can no longer expect that there are MAX_CHILDREN_IN_CELL entries in each cell - so if you're using a fixed size array to hold the objects in each cell, it's time to move to a dynamically resizeable structure.

These "straddled" objects will cost you a bit of access time when using the quadtree, as every query will have to test these objects, even if they're a long way from the coordinates you're actually querying.

One solution is to push "straddled" objects down the tree by duplicating them into all the child cells they overlap (and when I say duplicate, I mean, have multiple pointers to the object, not copy the object). This makes your queries very fast (as only the leaves of the tree will have objects in them), but you'll have to make all the code that uses the tree detect and remove duplicate objects when traversing the tree. Typically you can implement this in your tree traversal classes and forget about it. For my triangle octree, I just have a bit in the triangle object which tells me whether a given triangle has been duplicated, and only check for duplicates when the flag is on.

Another solution you could consider is a voxel grid. This is another type of tree where, instead of splitting each quad into 2 x 2 smaller quads, you split it into m x n children. You could then choose m and n based on your map dimensions (leaving a small number of empty cells to pad if you've got an indivisible map size).

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!