Maybe having the struct size be constant allows for better space locality in memory? You never have to reallocate nodes, you can pack everything into an array.
I'm now very curious on this. My gut was more that it is 2^(number of dimensions) that is important here. As such, for a single dimensional storage of data, standard binary tree. Add in another dimension, but still want to halve the search space with every comparison, add another branch factor to the tree.
That said, this implies that for 3d space, you would want 8 way trees? But, I don't think I've ever heard of that being done/used.
I'm a noob to DS&A, but I'm writing a little add-on for Blender and have come up against BVH and kd-trees. What makes one more popular for 'within objects' and the other for 'between'?
BVHes handle sparsity and very large scenes with variable density very well, so they are good to be able to see which objects you might intersect. kd-Trees are much better for objects because they handle the high density of geometry very well and are thus very effective if you want to test against a million triangles in close proximity, for example.
