Help me please! I''m developing a game and I want to use Octrees for the outdoor scenes and BSP trees for the indoor levels. If this is possible, please tell me where to get more info on how to do this; if it isn''t, then just tell me to use BSP alone; and how to use it to design outdoor scenes!

Actually both ways are possible: you can simply create a BSP from the geometry in each octtree node (potentially cutting down on the maximal hierarchical depth of the tree, at the nodes you are going to use BSPs, to minimize face splitting). You could also create one huge BSP, and partition a part of it using an octtree, ignoring the BSP structure on those regions.

Or simply treat indoor geometry separately to outdoor geoemtry, BSP indoor faces, and create an octtree for outdoor faces.

OTOH, I would recommend to stay away from BSPs alltogether. They are outdated, and the only reason why commercial engines still use them, is because they have an existing codebase built on them. If you create a new engine from scratch, don''t use them. Use Occtrees (or similar) for indoor and outdoor geometry. You can still use portals, even with octtrees. You can''t use PVS anymore, but that''s no real problem, if your portal system is good. You could also throw in some occlusion culling, which renders even the portal system obsolete.

/ Yann

yann i have heard it 1000 times now
" don t use bsp anymore"

why not???

is it because of the tons of leafs you create?

someone told me to use octrees because of hierarchical culling
well in my opinion you can do the same with protals which is even more precise and on nowerdays machines it doesn t matter when you use portals with large polygon counts you can create a bounding cube and see if you trace line enters the cube at all if so you trace towards the portals to find out if they are visible or not

Note that when I refer to BSPs in this context, I mean the Quake style BSPs. There are other types as well, with their own benefits and drawbacks, the term BSP is somewhat ambiguous.

BSPs have been developed at a time, where rendering even a single face was very expensive (software rendering, early 3Dfx cards). The plan was to create a HSR algorithm that would return a theoretically perfect visibility set, every invisible face (or part of a face) is clipped away. The drawbacks were that the building and traversal is expensive (compared to other methods), and the clustering properties less than suboptimal (very high amount of leaves, poor localization, no range optimization possible, can't be used on dynamic geometry, no overgrowth capabilities, high number of splitted faces, etc). That was fine back then, but it's not today.

Things have changed. Scenes and levels have more and more faces, more and more complex state changes (eg. shaders), and tend to go away from the classical 'closed and easy portalizable underground dungeon' type of environment. And most important of all: drawing a single face is not expensive anymore. On modern hardware and 3D worlds, it is favorable to use a HSR algorithm that is fast, has no restrictions on the type of environment, offers good localization and low face splitting, but does only compute an approximate visible face set.

So what does all that means ? An occtree is faster in terms of traversal, offers better localization, and is indepedent of the environment. A more advanced structure, such as an OBB tree or a binary adaptive tree, offers further benefits: colume range optimization, overgrowth, and can handle fully dynamic geometry. In short: if you use BSPs, you are artificially limiting yourself.

Now about portals. I personally don't use them that often anymore, we have replaced almost all of them by occlusion culling. Simply because the type of scenes we use (many outdoor and very open environments) are the hell to portalize. If you use lots of indoor scenes, then portals are still a very good choice. They nicely work together with an octtree, OBB or ABT. But as mentioned above: instead of providing a perfect visibility set, they will only provide an approximate one. Which is no problem on modern hardware, and the upside is, that they are very fast (and can even be hardware accelerated on newer GPUs !).

Basically, Impossible is right: the easiest way to create sectors/portals in a non-BSP engine, is to ask the artist to tag all objects that belong to a certain sector. Note, that this contains no visibility information, just an attribution of objects to a sector. You could create an automatic process, but this again would impose limitations on the type of enviroment you use. Attributing objects to a sector is a job of a few minutes for an artist (even programmers can do that ), so it isn't really worth implementing a complex algorithm that might fail on certain scenes. In this context, a sector does not actually exist in the scene, it's a purely virtual concept: all objects attributed to a sector can only be seen through the portals that access the sector. There are no geometrical restrictions on the size or shape of those sectors, they can even be open, partially defined, and can overlap.

How to render a scene using such a structure ? Very simple, actually. First, traverse the hierarchical structure (octtree, OBB, ABT, whatever you used). For each node, check if it is in the frustum. If yes, then check to which sector it belongs to (a leaf will always belong to a single one, a node might belong to multiple sectors). It can also have a special case value (what we called the NPS , Non-Portalized Space), which simply denotes, that the goemtry contained in the node does not belong to any sector. If you found the sector it belongs to, run a visiblity check in projected screenspace against the recursive intersection of the screenspace portals from the current viewpoint. That's a bit like with standard BSP portals, but note that you don't need to clip anything, it's just a simple visibility check (and can be hardware accelerated (ab-)using the occlusion query of newer GPUs). If it's not visible, throw it away. Else, render it. Continue, until you walked through the entire tree (that's a gross simplification actually, as a more advanced engine will use a form of scenegraph that tightly interacts with the tree).

The result of all that is a render structure, that is more efficient as a BSP, while offering much higher flexibility. The portlization scheme is 'fluent', means that it will perfectly interact with an outdoor or open 3D world. There is no need to separate your scene in types of environments, you use a single highly optimized structure for everything.


OK, I just read that through again, it's a bit confusing... But it's 9 AM, and I haven't had my coffee yet, so if you have questions, just ask

/ Yann

[edited by - Yann L on November 11, 2002 3:49:59 AM]

quote:
Cool. What kind of occulsion culling are you doing? I geometric scheme seems the fastest (in absence of HW accelerated occulsion tests) but maybe I'm wrong.

Image space only. On complex scenes, geometric systems tend to be pretty inefficient and potentially unstable. We use HOMs in software, if hardware support is not available.

There was thread about different occlusion schemes a while back, can't find it anymore (damn search feature).

[edited by - Yann L on November 11, 2002 3:53:53 AM]

OK! since its possible, how do i do it? where can i find code or samples!? i just heard that unreal2 does it!