For example, depending on your camera position and orientation, a BSP Tree could concievably throw out HALF of your entire world on the top level and do nothing with it, because it's off screen. It could then concievably throw out half of the remaining half, and continues until it's left with the stuff that is onscreen and needs processing.

An Octree can concievably throw out 7/8 of a world at a time. The best way to envision an Octree is to take 8 building blocks and arrange them into a bigger cube. You have four blocks sitting on the ground and another four sitting on top. Now imagine each of these blocks is devided into eights the same way, and each of those divisions is broken up until you reach some finite minimum oct size.

You can use the tree(or any tree structure) to do alot of stuff. As already mentioned above, only draw the Octs that are in front of the camera and not too far away. You can put objects in the octs and only do collision detection with objects in the same oct instead of doing a distance test against every single item against every other one.

Octrees are only really practical if you're working in a truely 3-D environment. If your level is 500 feet wide by 500 feet long by only eight feet high, an octree is not going to be effective. You're basically going to have all kinds of nodes from eight feet high to 500 feet that contain absolutely nothing but still need to be eliminated when you traverse the tree. If you've got a game set in space, you can go in any direction so an Octree makes sense.

There are also quadtrees, which just devide a two-dimentional area into quadrants. These work pretty good if jumping onto a box is the only height-type issue you have to deal with. I prefer them to BSP trees. In C++, they're alot less abstract.

I think the reason BSP trees took such a hold was because they were based on Binary Trees(which already had all kinds of sorting/searching algos worked out) and were probably easier to deal with in straight C (where any one of the above options can get to look pretty abstract and ugly.) You can still find alot more pre-tested algo's for a BSP tree, though.

http://www.codecranker.com/members/steve/

Kevin