Octtree vs. bsp

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

BSPs aren't used just for occlusions. You can use them for collision detection, and back in the day they were used extensively for back-to-front rendering, back before we had z-buffers.

BSPs really aren't suitable for terrains because the amount of splits would get ridiculous. Kind of difficult to explain in a single paragraph, but theres a bit of info out there you can read.

http://www.gamedev.net/reference/articles/article657.asp

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...

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)

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.

Quote:

Original post by trippytarka 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.

3d Game Engine Design (Eberly)
3d games real time rendering (Watts and Policarpo)

Note: they are books, if you want I will look in them and see if they have any references to further resources.

Quote:

Original post by PorkBag 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.

What type of bsp tree do you mean? if you mean Quake style bsp tree, that is a polygon aligned bsp tree, you are right. But, nothing can prevent you to use a polygon aligned bsp tree for indoor scenes and axis aligned bsp tree for out door scene linked together with a portal system (like doom 3).
For indoor scene try to read this paper to optmize the creation of internal bsp tree rooms:

http://artis.imag.fr/Publications/2003/LH03/lefebvre-hornus-portals.pdf



Bye
Davide

Quote:

Original post by PorkBag 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.

What type of bsp tree do you mean? if you mean Quake style bsp tree, that is a polygon aligned bsp tree, you are right. But, nothing can prevent you to use a polygon aligned bsp tree for indoor scenes and axis aligned bsp tree for out door scene linked together with a portal system (like doom 3).
For indoor scene try to read this paper to optmize the creation of internal bsp tree rooms:

http://artis.imag.fr/Publications/2003/LH03/lefebvre-hornus-portals.pdf



Bye
Davide

Quote:

Original post by Name_Unknown 3d Game Engine Design (Eberly) 3d games real time rendering (Watts and Policarpo) Note: they are books, if you want I will look in them and see if they have any references to further resources.

Thanks. I'll try to get hold of those books. Just to be sure, when you said:

Quote:

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)

Did you mean they encode terrain in a BSP, or that they describe BSP use for indoor engines?

Quote:

Original post by trippytarka Quote: Original post by Name_Unknown 3d Game Engine Design (Eberly) 3d games real time rendering (Watts and Policarpo) Note: they are books, if you want I will look in them and see if they have any references to further resources. Thanks. I'll try to get hold of those books. Just to be sure, when you said: Quote: 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) Did you mean they encode terrain in a BSP, or that they describe BSP use for indoor engines?

Basically, Watts describes how to use a 2D Bsp for a terrain and a grid. I never used it though, and don't know if it is really very useful for anything, it is like making a BSP that acts like a quadtree.