6 ms·
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.
by ShredKazoo 4y ago
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.
- taeric 4y agoI'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.
- EliasLittle 4y ago8 way trees are used for 3D, they’re called Octrees. https://en.wikipedia.org/wiki/Octree?wprov=sfti1 https://en.wikipedia.org/wiki/Octree?wprov=sfti1
- taeric 4y agoI'm now super amused with myself for not looking for "oct." Which, yeah, would have been the obvious prefix to look for.
- ShredKazoo 4y agoA B-tree does in fact have >2 children for only a single dimension.
- taeric 4y agoRight. But that is more to optimize cache/block reads, right? Been way too long since I've looked at many of those details. :)
- ShredKazoo 4y agoYeah pretty much, a node in a B-Tree is designed to fill a single page of memory
- corysama 4y agoIn 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.
- sudosysgen 4y agoGenerally the most popular is a BVH system between objects and a kd-Tree within objects, in my experience.
- boppo1 4y agoI'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'?
- sudosysgen 4y agoBVHes 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.
- boppo1 4y agoThanks!
- taeric 4y agoSo many things to read up on, now! :D Thanks for the pointers!
- misja111 4y ago> 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.
- taeric 4y agoThis was my thinking, exactly. I have not tried implementing one before.