rykounanba

Quad trees vs R-trees vs Spacial hashmaps

Recommended Posts

After some research on the internet I decided that I wanted to implement a broad phase collision detection in my private engine. Altough I found some structures that seem to be of good use for this I started wondering what the differences are between these structures. Up untill now I used spacial hashmapping but I got interested in Quad trees and R trees.

Could someone explain to me what the practical differences between them are and why some structures are used over others?

Share this post


Link to post
Share on other sites

I've only implemented quad trees and octrees. Here is what I like about them:
*They are easy to understand conceptually

*They don't take very long to implement (4-12 hours)

*They can be used recursively, which shortens code

*The runtime is O(LogN)

*Rather than trying to collide with objects directly, you collide with the object container first to cull out unneeded collision checks
 

Here's what I don't like:

*They can be a pain in the ass to debug. How many branches deep do you want to sift through in your IDE's debugger before you find your object?

*Generally, you just dump the tree and rebuild it every frame. What a waste of CPU time :(  (also, its a waste of programmer time to try to optimize it -- not because it can't be done, but because of all the bugs you'll probably introduce with the additional complexity)

 

I'm sure there are better solutions out there (maybe KD trees?). Today, I'd still implement a quadtree or octree (or maybe try a balanced KD tree).

Share this post


Link to post
Share on other sites

Better late than never.

I prefer R-Tree or R* Tree because it can adapt 2d or 3d scene.

By theory, they are faster when making an nearest object search because r-tree is balanced tree, with a little bit larger cost for insertion.

And you can even use it with 4d (spacetime model) scene for collision detection. Once the equation of the moving object is inserted and got indexed by the R-Tree, you won't need to refresh the tree any more.

Share this post


Link to post
Share on other sites

 

On 9/16/2014 at 4:25 AM, rykounanba said:

Could someone explain to me what the practical differences between them are and why some structures are used over others?

Spatial hash maps are similar to linear hash maps. Every position or range is converted to a bucket.  You can query for the items in the bucket. Finding an individual bucket is constant time, and so is placement and searching for a specific item. However, range searches beyond a specific location have geometric growth as hundreds or thousands of nodes need to be checked.

BSP trees partition the space based on how many things are within a region. They are time consuming to create and modify. Often when objects are changed (moved, added, deleted) it requires large modifications to the partition tree. Depending on how the partitions are oriented it can require significant math to navigate them. Search for a specific object is O(log n), but broad regional queries can be difficult or impossible with the structure.

R trees produce minimal bounding rectangle around objects. The boxes are irregularly shaped and are based on the current population of objects. Modifying the collection (moving, adding, or deleting) usually requires less work than a BSP tree, but can still require a significant amount of math. Creating an efficient tree requires enormous computational requirements.  Like the others, searching for a specific object is log n, but range searches require much more effort due to the irregular nature of the boxes.

KD trees break the world in to k dimensions, often a 2 dimensional irregular grid or a 3 dimensional irregular grid. Space required is O(n). Moving, adding, or deleting objects is always O(log n) by space. Searching areas of the map is also O(log n).  They have irregularly shaped areas, and dense areas filled with nodes can give very deep trees.

Quadtrees and octrees are a specialization on KD trees using regularly shaped areas. Depths can be computed easily on computers as they are all binary scale.  Loose quadtrees and loose octrees are a sub-variant where the boundaries of each layer are allowed to flow over halfway into their neighbor, or in different terms, are allowed to overflow by one layer deep in the tree.  Like DK trees the operations are all O(log n), but with much faster time because the subdivisions are powers of two rather than arbitrary. 

 

As for why (or why not) to use them...

Spatial hashes are a great fit if everything always fits into buckets, and you are only ever interested in a single bucket.  If you are interested in range searches (like everything within 10 units from a point) they quickly break down.

BSP trees and R trees are computationally expensive to build and maintain, so they are only a good fit if the world never/seldom changes. For range based searches a BSP is a nightmare when partitions are arbitrary, and are merely painful when partitions are axis aligned. For R trees a range based search can get to buckets with easy motion, but navigating the buckets requires processing irregular rectangles.

KD trees are inexpensive to build and maintain. There is little computational cost to build and maintain them. The big drawback is that dense areas on the map increase processing required, even though it is still log n the overhead is large.  Moving objects incurs the highest cost overhead when objects cross borders and must jump around the tree rather than moved through a simple tree node rotation.

Loose quadtrees and loose octrees are also inexpensive to build and maintain. There is even less computation cost than KD trees because edge points are always known as powers of two. The big drawback is that dense areas on the map tend to not be broken down, so a spatial querey in a dense area may yield many objects, but in practice this is extremely rare and can be completely avoided through design choices.

 

Most games with spatial trees use either a loose quadtree or loose octree unless the game has other specific needs that make a different structure easier to use.

Share this post


Link to post
Share on other sites

Similar discussion with some details (not sure about the difference between R-tree and BVH): https://www.gamedev.net/forums/topic/691015-spatial-sorting-in-3d/?tab=comments#comment-5350900

In short i'd suggest BVH with 8 children.

Advantage: Little work, very fast to build if you use just the center of the current box as the split point, refitable

Disadvantage in comparision to octree with neighbour pointers: Longer search time (but maintainig the pointers has probably a higher cost in most situations), node needs bounding box so more memory

 

Share this post


Link to post
Share on other sites

Unless I'm much mistaken, a quadtree or octree can be implemented as perfectly valid forms of bounding volume hierarchy, or BVH. 

The bounding volumes happen to be a regular grid, but they nonetheless are a spatial hierarchy around the individual objects.

Share this post


Link to post
Share on other sites
43 minutes ago, frob said:

Unless I'm much mistaken, a quadtree or octree can be implemented as perfectly valid forms of bounding volume hierarchy, or BVH. 

The bounding volumes happen to be a regular grid, but they nonetheless are a spatial hierarchy around the individual objects.

Agree, oc/quadtree is just a a special case of BVH, but BVH is more flexible:

BHV is not tied to a world grid. If an object moves outside the bounds of an Octree node, we have to move it to a new node that probably needs to be created first. With BVH you have the option to just refit the bounds, but keep the tree as is. E.g. for a large and complex moving object like a ship with interior we can precalculate the BVH tree once and only need to rebuild from the root of the ships tree upwards to connect it to the whole scene. Same for a character. Also it's possible to intersect character trees and ship tree without the need to merge them. So if we have a scene with 10 ships and 100 characters we build a tree for 110 nodes per frame. For an octree we need to build a tree for maybe 3000 nodes per frame. If we use spheres for the bounds, it's not even necessary to refit the precalculated radi, just update their positions.

Share this post


Link to post
Share on other sites

Yes, but if you have 10 ships and 100 characters you have no need for a spatial tree.  A simple linear search will be efficient enough.

Share this post


Link to post
Share on other sites

100 characters x 20 limbs + 10 ships x 100 walls = 3000 potential colliders, 3000^2 = 9 million potential collisions. 

Building a tree for 110 nodes takes almost zero time, so at this point it should be worth it already.

 

Edit: Of course in practice you can use a static tree for a ship and transform the characters relative to that, but i'm only giving an example to show advantages of not being bound to a world grid.

Edited by JoeJ

Share this post


Link to post
Share on other sites
19 hours ago, frob said:

KD trees are inexpensive to build and maintain.

 

19 hours ago, frob said:

BSP trees and R trees are computationally expensive to build and maintain

This is a contradiction. Kd-trees are axis-aligned BSP trees (a.k.a. rectilinear BSP trees) and as such are BSP trees.

Share this post


Link to post
Share on other sites

3D case

Regular grid:

  • spatial partitioning scheme
  • non-hierarchical
  • axis-aligned/non-axis-aligned voxels

Hierarchical regular grid:

  • spatial partitioning scheme
  • hierarchical
  • axis-aligned/non-axis-aligned voxels

Binary Space Partition (BSP):

  • spatial partitioning scheme
  • hierarchical
  • binary/n-ary tree (though the name becomes a bit fuzzy for the latter)
  • axis-aligned/non-axis-aligned voxels

Kd-tree:

  • spatial partitioning scheme
  • hierarchical
  • binary/n-ary tree
  • axis-aligned voxels

Octree:

  • spatial partitioning scheme
  • hierarchical
  • 8-ary tree
  • axis-aligned/non-axis-aligned voxels

Bounding Volume Hierarchy (BVH)

  • object partitioning scheme
  • hierarchical
  • binary/n-ary tree
  • axis-aligned/non-axis-aligned voxels

As one notices some variations are possible.

Edited by matt77hias

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