I was learning about quad trees in 15418 as an efficient way to keep track of objects in a galaxy which may be clustered in some regions. It was interesting to learn about other data structures like KD trees and BVH trees and wonder if they may perform better. Specifically, it would be interesting to learn if these data structures are easy to update if objects move since that could be the case with what we are rendering and was the case with the galaxy simulation.
keenan
@potato Yep, people definitely use other structures like BVH for these kinds of n-body problems. Here's a fun example where a BVH is used to simulate "repulsive curves":
The advantages you point are exactly the right ones, e.g., ability to quickly "refit" geometry if it only changes slightly, rather than rebuilding the tree. Also, element partitioning scales well to higher dimensions (depends only on the number of elements), whereas spatial partitions like quadtrees scale badly (if you bisect each of $d$ dimensions, then you have $2^d$ children at each node).
I was learning about quad trees in 15418 as an efficient way to keep track of objects in a galaxy which may be clustered in some regions. It was interesting to learn about other data structures like KD trees and BVH trees and wonder if they may perform better. Specifically, it would be interesting to learn if these data structures are easy to update if objects move since that could be the case with what we are rendering and was the case with the galaxy simulation.
@potato Yep, people definitely use other structures like BVH for these kinds of n-body problems. Here's a fun example where a BVH is used to simulate "repulsive curves":
The advantages you point are exactly the right ones, e.g., ability to quickly "refit" geometry if it only changes slightly, rather than rebuilding the tree. Also, element partitioning scales well to higher dimensions (depends only on the number of elements), whereas spatial partitions like quadtrees scale badly (if you bisect each of $d$ dimensions, then you have $2^d$ children at each node).