I realize this has been asked before, but just to get some more clarification on the matter... I've been hearing that Octtrees are better for outdoor locations, and BSP trees are more apropriate for indoor areas. Is the reason behind this that outdoor areas generally use complex meshes of huge numbers of triangles to represent smooth hills etc. while and indoor 'room' could consist of as little triangles as is nessecary to create a box, thus an octree creates too much overhead for this type of map? So would a BSP tree be better for large outdoor areas that use a limited amount of polygons to represent the terrain?

BSP trees are used for indoor areas because alot of the geometry hides or "occludes" other geometry. A bsp tree is a map of these occlusions...basically.

Octrees on the other hand, break the world up into chunks. An octree starts at a root node (a large box that contains the entire world) this root node then has 8 children nodes (boxes) which in turn contain 8 children nodes of thier own and so on. Each node can also contain sets of geometry. Why oct trees are usefull is because you test each node against the view frustum. If that node is not visible, you stop there (ie. you do not test that nodes children). For example, say you are outside of the world and are facing away from it... the root note is being tested against the frustum but since it's not visible, none of it's children are tested thus none of the geometry in each note is rendered.

Read more about these topics. Quad trees may be a better start for you. Good luck.

Oh also... normally, if a room consists of a "box" and nothing else, you really do not have a bsp tree. Octrees can have a large overhead depending on how deep the tree goes (ie. root node, it's children....... great great great grandchildren...).

I don't really know much about bsp usage for outdoor areas, other then games such as halo use that approach. With that said, halo doesn't have large terrains that some games have (ie. marrowind and such).

Lod comes into play for large terrain sets. Lod incase you don't know, is level of detail which basically cause meshes which are far away from the camera to be rendered with fewer polygons.

well... of to bed for me... :)
~Jay

The normal BSP construction strategy is to choose the splitter plane from amoung the polygons the node is being constructed from. This works quite well for indoor locations and has the advantage that it's guaranteed to finish (i.e. it can't keep splitting forever because at least one polygon cannot be used as a splitter again each time). For outdoor locations however this choice is pretty hopeless because generally most terrain is fairly flat and therefore the plane of one polygon usually intersects a large number of polygons which are nowhere near it, unlike indoor locations where polygons have all sorts of orientations. The data for outdoor areas is also often a heightmap which is just a regular grid so quadtrees behave well and don't need to split any polygons in that case. However a BSP can be used to simulate a quadtree if you choose the splitter planes to be vertical instead of picking from amoung the polygons in the landscape. BSPs nodes/leaves can be culled in exactly the same way as octree and quadtree nodes since it's possible to calculate the bounding volume of each node. The only real performance advantage of octrees and quadtrees over BSPs is that node traversal is slightly faster since it only requires one comparison instead of performing a dot product - that is, if you're doing depth sorting. Otherwise I don't think there is any real advantage. BSPs do have the advantage for indoor areas that it's easier to calculate the potential visibility set or do portal based culling than with octrees, although I would've thought with octrees both were still possible if not as efficient.

So as far as static octrees/quadtrees and BSPs go I can't see any very big advantage in not using BSPs providing your splitter choice is appropriate as long as you aren't spending most of your time doing tree traversal or most of your memory on tree storage. However dynamic AABB trees which are similar to octrees do have a lot of advantages and using BSPs with arbitrary split planes for this purpose is totally impractical as far as I can see.

That's not to say quadtrees and octrees aren't useful for outdoor areas (well, particularly quadtrees). LOD algorithms use quadtrees to great effect and although you could probably simulate the same with a BSP you'd be wasting your time. The above discussion really applies to general static geometry without any LOD.

Quote:LOD algorithms use quadtrees to great effect and although you could probably simulate the same with a BSP you'd be wasting your time.

Binary trees are not BSPs and are used in LOD algorithms (such as ROAM) to great effect. A BSP is a special case of a binary tree, so the octree equivalent would be an OSP I guess. This thread seems to be comparing apples to oranges...

Quote:Original post by trippytarka
Binary trees are not BSPs and are used in LOD algorithms (such as ROAM) to great effect. A BSP is a special case of a binary tree, so the octree equivalent would be an OSP I guess. This thread seems to be comparing apples to oranges...

My point was more that a lot of people seem to confuse the BSP data structure with having to use the polygons in it for splitter planes, and that since most spatial partitioning schemes do partition subspaces by planes that BSPs lack of suitability for any particular task is more to do with their construction than the data structure itself, however specialised data structures can be more appropriate in more constrained circumstances.

ZQJ, my intention was to add to what you said, not contradict it.

Quote:Original post by Name_Unknown
You can encode an octree and quadtree in a BSP (Eberly). You can encode a terrain in a BSP, you don't do it the same way as you would in an indoor engine like Quake or Unreal... (Watts)

Where are you citing those references from? Searching for surname+keywords on Google isn't getting me anywhere.