http://en.wikipedia.org/wiki/Bounding_volume_hierarchy
- With such a hierarchy in place, during collision testing, children do not have to be examined if their parent volumes are not intersected.
http://www.3dmuve.com/3dmblog/?p=182
- A brief tutorial on what BVH are and how to implement them
https://developer.nvidia.com/content/thinking-parallel-part-i-collision-detection-gpu
https://developer.nvidia.com/content/thinking-parallel-part-ii-tree-traversal-gpu
- The idea is to traverse the hierarchy in a top-down manner, starting from the root. For each node, we first check whether its bounding box overlaps with the query. If not, we know that none of the underlying leaf nodes will overlap it either, so we can skip the entire subtree. Otherwise, we check whether the node is a leaf or an internal node. If it is a leaf, we report a potential collision with the corresponding object. If it is an internal node, we proceed to test each of its children in a recursive fashion.
Instead of launching one thread per object, as we did previously, we are now launching one thread per leaf node. This does not affect the behavior of the kernel, since each object will still get processed exactly once. However, it changes the ordering of the threads to minimize both execution and data divergence. The total execution time is now 0.43 milliseconds?this trivial change improved the performance of our algorithm by another 2x!
HUH ?
https://developer.nvidia.com/content/thinking-parallel-part-iii-tree-construction-gpu
http://en.wikipedia.org/wiki/Z-order_curve (aka Morton order)
A function which maps multidimensional data to one dimension while preserving locality of the data points
The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree; because of its close connection with quadtrees, the Z-ordering can be used to efficiently construct quadtrees and related higher dimensional data structures.