# Cache friendliness of AABB-Tree: binary vs N>2

I found that state-of-the-art physics engines like Bullet and Box2D all use binary AABB-Tree for broad-phase collision detection.

I wonder, did anybody tested AABB-tree with >2 branches per node ?

I always had feeling that binary trees are extremely cache unfriendly, since you have to dereference pointers (resp. indexes) at each level, and whole your tree does not fit into cache. Since you have log_2(N) levels, I assume you have ~log_2(N) cache misses. Cost of cache miss can be ~100 CPU cycles. With N=4 base tree you would have just half cache misses (log_4(N) = log_2(N)/2), but you would need to do 2x more AABB comparisons at each level (yet you have less levels). Assuming AABB comparison cost less than 100 CPU cycles (especially using SIMD SSE/AVX ops ), using N=4 should be faster.

But I assume balancing N-tree is much more complex than binary tree, which deters people from implementation, and also can add runtime cost.

• What exactly is your question here? Binary trees aren't necessarily cache-unfriendly as you assume; there are mitigation techniques for memory layout issues for all kinds of trees. – user1430 Jul 24 '18 at 20:20
• Assuming that AABB comparison is the only thing that takes place each time may not be valid; some work has to be done as a result of a successful comparison; some work may need to be done on failed comparisons too. A binary tree does have the advatange that it allows you to exclude half of your objects with each test. Cache efficiency is not the sole arbiter of performance, and you may safely assume that the major middleware vendors do know, understand and implement performance optimization. – Maximus Minimus Jul 25 '18 at 8:48
• If you're interested in exploring alternative tree structures, this sounds like something you could experiment with and profile yourself. Have you given this a try? – DMGregory Jul 25 '18 at 10:58
• I'm trying to do it, but implementing non-Binary tree in 3D is quite complicated, so I'm asking if somebody tried that. For example - it is easy to split 3D-box to two halves, but it is not so obvious how to best split it N parts. Also it is not obvious how to optimally split set of M items to N subsets. – Prokop Hapala Jul 25 '18 at 11:51
• It's not just not obvious. I'm pretty sure it's NP-complete – Bálint Jul 25 '18 at 12:23