is an octree the same as a bsp?

# is an octree the same as a bsp?

No, but they are similiar concepts. The bsp generally recursively subdivides space into two sub-spaces (then each of those get split into two and so on) until all subspaces are convex. BSP’s typically can use arbitrary planes to do the splitting. Though most use some heuristic in choosing the best splitting plane for a given set of subspaces.

Oct-trees also recursively split space, but they split a space into 8 subspaces by using 3 perpendicular (and usually axis-aligned and centered) planes (just like the x-z, y-z, and x-y planes split space into 8 octants). Here some heuristic has to be used to gauge when enough subdividing has been done as well. But it is generally different as all the subspaces (regardless of what level in the tree you are at) are already convex. Oct-trees generally provide a mechanism to simplify collision detection (you only have to check the polys that occupy your subspace(s)) but they generally don’t provide gross solidity information unless the geometry of the world is constructed of axis aligned right angles which takes us back to the days of Wolfenstein 3D (which did not use an oct-tree since it was a 2D maze rendered in 3D perspective. A quad-tree is more suitable for that).

The bsp also simplifies collision detection as you only have to test against the polys in the colliding object’s leaf. The bsp can provide gross solidity information very easily as well. The convex regions (which can add up to arbitrary complex regions) can be solid or not and simply marked as such.

Getting visibility info from these structures (bsp or octree) is time consuming however so you need to augment them with some kind of VSD or PVSD.

For those that want to argue the technical point, yes, an oct-tree is also just a special case bsp tree.

[This message has been edited by DFrey (edited 01-07-2001).]

thanks alot.