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?

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.

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.

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

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.

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.

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.

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.