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.