[johtela]

> Broad phase collision detection usually involves three lists of the bounding boxes of the objects, ordered by X, Y, and Z.

Exactly. You first want to limit the set of objects that might collide as far as possible. A three-level interval tree [1] works great for finding overlapping bounding boxes. You need a three-level nested interval tree where the 1st level covers the x-direction, 2nd y-direction, 3rd z-direction. It also pays off to make sure that the interval trees are balanced. You can turn the interval tree into red black tree [2], for example, by adding the color flag in the interval node. Then you can balance the tree using rotations when inserting or deleting.

[1]: https://en.wikipedia.org/wiki/Interval_tree [2]: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree