4
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ I can see a few explanations I think. For 3D we see that e.g. Bullet does not do anything terribly fancy here. My hunch is that the bottleneck simply isn't here at all in the 3D case... But 2D is actually the case that i am more interested in. What I do know is chipmunk gains speed over Box2d in certain scenarios via use of spatial grid partitioning and eschewing the dynamic AABB trees. But what I am wondering now is how things might change by making the dynamic tree much smarter. \$\endgroup\$ – Steven Lu Aug 3 '15 at 21:22
  • \$\begingroup\$ That GDC video you linked seems to contain the answer at 12:05 - "Dynamic objects doable / may eventually end up performing poorly". I don't think that is acceptable for anyone. \$\endgroup\$ – snake5 Aug 4 '15 at 4:48
  • \$\begingroup\$ R-trees are really just fancy AABB-trees —is that an advantage? What's the advantage? (Being “fancier” sounds like a disadvantage…) \$\endgroup\$ – Anko Aug 4 '15 at 9:42
  • 1
    \$\begingroup\$ @Anko they have cache friendlier behavior. See the gdc talk. Note how his graphs show terrible perf for the low branching factor cases (which are closer to what you get with e.g. binary AABB trees) \$\endgroup\$ – Steven Lu Aug 4 '15 at 15:54
  • \$\begingroup\$ Nice notes on this by same guy. \$\endgroup\$ – Engineer Nov 3 '15 at 23:47
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @StevenLu Thanks for the question! this is going to be key in something I'm presently working on. \$\endgroup\$ – Engineer Nov 4 '15 at 0:33
  • \$\begingroup\$ Cool. I kinda wish SE sites had PMs. I'll share with you what I'm working on if you do the same! \$\endgroup\$ – Steven Lu Nov 4 '15 at 0:35
  • \$\begingroup\$ Hey there, Sebastian's notes link seems to be dead now :( \$\endgroup\$ – Steven Lu Apr 30 at 14:51
  • \$\begingroup\$ @StevenLu I'll have a look at this when I have time. \$\endgroup\$ – Engineer May 2 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.