How easy is it to extend k-d trees to deal with objects with finite size (vs. points)? Are there any libraries that do this? I might have to do something similar to this in the future, but I need nearest neighbors for 'spheres' in higher dimensions.
They’re great. Good perf, while being one of the simpler ways of accelerating spatial queries (compared to other types of trees, at least)
The catch with both is that you need to be careful with primitives that intersect split planes. You either need to introduce either additional bookkeeping to avoid testing the same primitive multiple times, or you need to split the primitives at each plane. Both are not really desirable properties. Also, primitives that lie exactly on a split plane will lead to unstable results as the tests involving the split plane and the primitive are usually bound to to give slightly different results.
A bounding volume hierarchy is generally easier to implement and more reliable. And people have optimised the heck out of algorithms to construct them.
Z-order combined with sorted array/tree/etc. generalizes to non-point objects quite easily. I think the Z-order NN algorithm will "just work" with non-point data.
A point is represented by a z-value at the resolution of space.
A non-point is approximated by multiple z-values, at varying resolutions. You can trade the accuracy of the approximation against the number of z-values.
I explained the NN algorithm in another comment on this thread. It shouldn't matter if some of the adjacent z-values are actually from the approximation of the same object.