Hi, i have a really quick question, which probably would have a long answer... How do BSP trees compare to Octree''s (or similar space parititioning algs.), and why would someone choose BSP tree''s over them... thanks -jonnii ========= jon@voodooextreme.com www.voodooextreme.com

BSP''s are very good if you geometry is static, enclosed, and you want to be able to save the BSP data...

saving a octree or quadtree would be a nightmare... I have seen a 256x256 slab of terrain have a 3gb octree generated. Not good. but their performance probably beats a BSP. but they use more memory.

modifying data within a quadtree/octree is possible. whereas with BSP, you need to exclude geometry that may change.

ohh yeah. don''t automatically think you need a BSP/octree/quadtree system.

if you have a 1D terrainmap (eg, a heightmap) you can use a simple algorythm to find where you are because the data is constant.

I use a fixed grid of cells in my terrain engines... where if a cell has large verticle shift, it is split... I only use 10mb on a 512x512 terrain mesh... and average referencing about 6 triangles in any place. not to mention it''s parctically instant to work out what triangles are near by. (it also only takes 3 seconds to gen)
this beats a quadtree hands down. although if I had buildings, I''d have to re-work it.

quote:

---

Original post by jonnii
How do BSP trees compare to Octree''s (or similar space parititioning algs.), and why would someone choose BSP tree''s over them...

---

BSP Trees are far more general, they can also simulate quadtrees/octrees. BSP trees can partition space in an arbitrary way, where octrees/quadtrees have a set recursive way to partition space.


Mike

"The state is that great fiction by which everyone tries to live at the expense of everyone else." - Frederick Bastiat, The Law

also consider KD-trees... they''re kinda like a midway between an octree/quadtree and a bsp.

The main principle is that they have axis-aligned partioning planes like octrees/quadtrees, but you position these planes with regard to polygon distribution (ie position so that there are roughly an equal number of polys on each side of the plane).

They are very simple to implement, and give a nice shallow tree. The downside is that they don''t have the strict spatial distribution of nodes like an octree/quadtree. (sorry coulnd''t think of a better way to put that at the moment )

It simply depends on what you want to do.
For terrain engine, don''t consider BSP and Octree.
For indoor engine, both of them can be great.

I''ve heard of someone using an Octree containing BSP trees. I think it can be a very good idea if implented correctly. For example, it enables you to create a BSP tree on the fly without too much performance cost. The BSP is only generated with a few, select polygon. This way, you can surpasses the BSP moving geometry problem.

And for the Octree, you can generate it like you want. If it''s too big, just change the treshold. (eg. 20 poly/node instead of 5)