Hacker News Reader

Comment by convolvatron | Hacker News Reader

what else would you use for spacial subdivision? bsp trees?

Something adaptive. Maybe AABB trees depending on the context.

Why cant you use an N tree, what's special about 4?

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.

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.

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

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.

I'm a fan of spatial hash grids for most of the things I would consider quadtrees for.

It's simpler to reason about and there's no monkeying around with trees when you add an element or move one around.

Reply on news.ycombinator.com