A B-tree does in fact have >2 children for only a single dimension.

Right. But that is more to optimize cache/block reads, right? Been way too long since I've looked at many of those details. :)

Yeah pretty much, a node in a B-Tree is designed to fill a single page of memory

8 way trees are used for 3D, they’re called Octrees.

https://en.wikipedia.org/wiki/Octree?wprov=sfti1

I'm now super amused with myself for not looking for "oct." Which, yeah, would have been the obvious prefix to look for.

In ray-tracing, people debate back and forth between kd-trees, octrees, quad-AABB trees, oct-AABB trees, and I’m sure there are a few more.

I think quad-AABB has been the most popular option for a while now.

Generally the most popular is a BVH system between objects and a kd-Tree within objects, in my experience.

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.

Thanks!

So many things to read up on, now! :D Thanks for the pointers!

> My gut was more that it is 2^(number of dimensions) that is important here.

Yes, it's just binary search but applied to every dimension.

This was my thinking, exactly. I have not tried implementing one before.