quote:
I am wondering if BSP is only useful in a 2D sense. I look at all the tutorials and they all explain it from a top-town 2D view. Does this mean that BSP would only be useful if I designed my maps in a way so that they are basically 2D?

No, BSPs can also be used for fully 3D scenes. Eg. the Quake engine does that. Instead of partitioning lines, you have partitioning planes.

quote:
If this is true, is Octree a better way to go?

For most scenes, octrees are in fact the better way. BSPs were designed at a time, when 3D hardware was far from what it is today. Octrees are better suited to make use of new hardware features, and they fit better into the way modern 3D cards works.

quote:
Exactly.
BSP (solid leafy) can describe exact underlying geometry (for collision det. ... etc.), octree can only partition it into hierarchical structure.
Because of that BSPs are very usefull for things like camera -> sector detection (*very* small BSP), collision, ...

Uh, no.

BSPs do not add any significant information about the underlying geometry. And by 'significant', I mean important for a modern engine, running on modern hardware. BSPs might be useful to auto-generate sectors, but this technology (BSP+PVS+indoor portals) is just as outdated as BSPs themselves. BSPs offer no advantage over other hierarchical data structures for collision detection. Well, assuming that we talk about remotely realistic 3D environments, and not this dungeon-type closed indoor stuff.

Stated in a different, perhaps less negative way: if you have highly restricted indoor environments, then BSPs can be used. In all other cases (outdoor or mixed environments) octrees will always be the better choice.

I really don't understand, why people still advocate the use of BSPs. They were nice at their time (fast sorting of faces, when renderers had no zbuffer), but 3D hardware has significantly advanced since then. Getting the less conservative face set possible, without false negatives, might be a nice feature, but it comes at a high computational cost, at level compile time, as well as at runtime. And modern 3D hardware doesn't care about that anymore: it's a lot faster to brute force conservative octtree node sets, than computing a perfect BSP face set.

And about collision detection being faster with BSPs than with octrees, now here we have a nice myth. Try it and compare (I did quite a few times). I *guarantee* you, that the octree version will be a lot faster on any reasonably complex scene.

Please don't take this personally if you are a BSP-lover (I'm a BSP-hater, in case you haven't noticed ), but it's funny how some people hang on old technologies, and try to deny by all means the fact that those technologies have reached the end of their life cycle. BSPs are a thing of the past, and have been replaced by better alternatives. Deal with it.

Oh, perhaps to clarify my point: I'm talking about the usefulness of BSPs in realtime object hierarchies, used for culling and collision. BSPs are still very useful in geometrical processing algorithms, such as boolean operations and CSG.

[edited by - Yann L on December 28, 2002 11:24:12 AM]

quote:
Outdated? All algorithms and DS-s has their use and purpose.

That's right. But the usefulness of what a certain algorithm accomplishes will always change. At the time when BSPs were first used, the rendering bottlenecks and performance profiles were totally different as on today's 3D hardware. BSPs were well suited to provide those old renderers with just the appropriate data to get optimal performance. But today, the typical data required to get this optimal performance is different - and so the algorithms that feed this data must be adapted. Perhaps the word 'outdated' wasn't well chosen, let's state it differently: BSPs don't fit the needs of modern 3D hardware anymore.

Example I already mentioned above: One of the biggest advantages of BSPs back in the early times, was the fact that they could magically sort the faces based on their depths. And they did (and still do) that pretty efficiently. But today, do we need that feature for standard geometry ? No, we have hardware zbuffering that is fast as hell. Can we use it alternatively ? Yes, we can use it for transparent faces, for example. But this is a special case, and that's the point: choose the best available algorithm for a specific task. For general opaque geometry, BSPs are not the best choice.

quote:
For example the camera -> sector query I mentioned before just cries for BSP, of course if we need it to be fast.

Yes, but this implies that you need a camera/sector query. If you drop the indoor portal idea altogether, then the question about the performance of such queries will become irrelevant - you won't need it anymore.

quote:
Octree suffer from that axis-aligned nature, as well as kd-tree.

OBB octrees, should the AABB's really be a problem (they are mostly not).

quote:
i'm not necessarily a bsp lover, i'm just saying that the only way *i know how* to detect if you are outside the level even though you aren't intersecting anything is a bsp.

I wasn't referring to you by the 'BSP-lover' term And you are right, BSPs are a good way to detect this situation. But on the other hand, ask yourself if you really need to detect that. Other algorithms exist, that do not need such a query, and might be better suited for visibility culling (well, rethorical question of course, you won't recode your whole engine if it is already based on BSP, obviously. But that's more a fundamental question to ask, when starting to design a new engine).


[edited by - Yann L on December 28, 2002 12:02:30 PM]