Today we talked about three acceleration structures that are all similar:
1) Binary Space Partitions that divide the world into halves and sort all the objects in the world into one side or the other side
2) Quadtrees that split the world into quadrants and keeps subdividing until the number of objects in each region is below some threshold
3) Octrees that are Quadtrees but for 3D
If done right, they allow you to do things like pointcontents and traceline tests in O(logN) time instead of O(N), which is the kind of thing you want to hear when doing video games.
1