What are the disadvantages of R-Trees in collision detection?

Question

I was poking around in SQLite and discovered R-trees. A little digging revealed that R-trees are really just fancy AABB-trees.

Then I realize that the state of the art in collision detection (often a perf-limiting sub-system for physics simulation) is dynamic trees (simple AABB trees).

So this is indicating to me that we can produce more efficient physics with this as a drop-in replacement.

Here is a pretty convincing argument for R-trees from half a decade ago. To really distill it to the core, R-trees were developed for databases to optimize disk access where getting the right data into RAM is the happy place, and now we can recycle the technique to optimize memory access where keeping the right data in cache is the happy place.

Sadly it seems that this has not caught on. I wonder what the reasons are?

I also found no reference to this BVH method in my Real-Time Collision Detection (Ericson) text (though, that book is a bit older than 2010).

Answer 1

R-trees and AABB-trees are two names for the same thing, so it doesn't make any sense to say one has an advantage over another.

Answer 2

From what I can see, when implemented in 2 or 3 dimesions it's just another name for a hierarchical AABB / BVH setup as noted. Searching on "r-tree GIS" gives a lot of info, and being an inherently spatial field has much similarity to game dev (graphs, computational geometry etc.).

The point on which R-trees really win out over spatial/geo hashes and N-ary trees like binary trees, quadtrees and octrees is their neat fitting to arbitrary features with minimal wasted (search) space.

Re cache performance... Here's what I found on cache-oblivious R-trees:

Memory layout. Even though our cache-oblivious R-tree is defined in terms of kd-nodes and line-based nodes [see fig. 1 in the linked paper], it is simply a tree of bounded height with nodes of degree at most four. We need to specify how to lay this tree out in memory in order to obtain an efficient query algorithm. Unlike most previous cache-oblivious structures we do not use a Van Emde Boas layout, but simply lay the tree out in depth-first order: to lay-out a tree Tv rooted in a node v , we define an ordering of the children v1, v2 ... vc of v and lay out the tree such that v is followed by a recursive layout of the tree Tv1 rooted in v1, followed by a recursive layout of Tv2 , and so on.

After reading this, my deduction from Sebastian's vague notes on his approach is simply that the data layout is extremely compact and avoids pointers altogether in favour of some 8- or (probably) 16-bit IDs use to access nearby nodes with impunity, many of which will already be in L2 at query time. I was surprised; I really thought that something like a 3D Z-curve would have been used to increase locality of reference but no, apparently it's just brute compactness - as noted in quote. I've seen quadtree and octree implementations like this as well - e.g. the original NVidia SVO paper.

Conclusion

What's clear from Sebastian's notes is first eliminating all that pointer dereferencing that is typical in naively-implemented graph-like structures. Again, we've seen this in the SVO paper ref'ed above.

Secondly, pack what you can into the smallest space possible. 1MB L2 cache on the author's XBox360 which he talked about at GDC may not seem like a lot - if you're not using it efficiently. Actually, R-trees don't need to be very large to accomplish a great deal of acceleration.