Combining Octrees and BSP trees... is it possible?

Of course it''s possible, Lithtech uses a combination of octrees and BSP trees. I think they basically generate the octree and the BSP all the geometry in the leaves (or maybe it''s the other way around) to get an octree of bsp trees. This lets you do fast frustum and occulsion culling for large outdoor areas, and portal or pvs type stuff and faster collision for indoor areas.

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?

Yann, I''m curious, how do you define sectors in your engine. Do you just have the artists select all the geometry that a given portal can see or is it some more complex than that. From what I''ve been reading lately, the nice thing about a BSP\portal system is that you can find out what cells a portal can see, even though I guess you could do something similar with an octree.

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]

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.

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!

Incidentally Yann, I''ve heard you mention Binary Adaptive Trees several times but I can''t seem to find any useful info on them. Do you have any links or would you mind elaborating? (something like k-d trees are they?)

Also, how do (did!) you go about generating the actual portals themselves? Just get the artists to draw them in, or develop some sort of hellishly complicated algo? (I think I just answered my own question)

quote:

---

Incidentally Yann, I''ve heard you mention Binary Adaptive Trees several times but I can''t seem to find any useful info on them. Do you have any links or would you mind elaborating? (something like k-d trees are they?)

---

I guess someone must have used them before, but I''m unfortunately not aware of any papers or tutorials covering them. The basic concept is actually pretty simple, the crticial point is to balance them. They are a hybrid approach combining the advantages of octtrees and BSPs, and adding some more options. They can also be used on fully dynamic geometry.

It''s not that easy to explain, I''ll post a more detailed overview tomorrow.

quote:

---

Also, how do (did!) you go about generating the actual portals themselves? Just get the artists to draw them in, or develop some sort of hellishly complicated algo? (I think I just answered my own question)

---

Heh, yeah, pretty much The artist draws them. We actually have a plugin for Maya that assists in semi-automatic portal creation.

/ Yann

quote:

---

It''s not that easy to explain, I''ll post a more detailed overview tomorrow.

---

That would be great!

quote:

---

We actually have a plugin for Maya that assists in semi-automatic portal creation.

---

Ahh, now why do I always forget I could use max to do this sort of thing, I''m always thinking I''ll have to write a custom editor, plugins rule.

What it is, and how to build them

The basic concept is similar to both octtrees and BSPs. The geometry is exclusively stored in the leaves, the inner tree nodes are just helper nodes used in hierarchical culling. The difference between Octtrees/BPSs and adaptive binary trees (ABT) is that each node of the former ones does always describe a totally distinct region in space, whereas an ABT node can describe overlapping clusters. An ABT leaf contains the geometry, where each face is unique to a leaf (ie. a face can never be attributed to more than a single leaf).

To build one, start with the root node: create an axis aligned bounding box around your whole scene. Start a recursive subdivision function on it: At each recursive step, the bounding box gets subdivided into two parts, where both children will again be AABBs (unlike BSP trees). The division continues until either the number of faces in a node goes under a threshold, or the depth gets too large. The last created node will then be declared as leaf and contains the renderable geometry.

All this is pretty straightforward, with one exception: how does the node gets divided into two children. This is where it becomes tricky. The division plane is always perpendicular to one of the three major axes. So a node is either split along his X, Y or Z axis, creating two new nodes (both axis aligned). The position of the division plane, as well as the axis, is mathematically a minimization of the following criterions (and their respective functions):

a) good localization of space. The largest axis of the resulting child AABB must be minimized (this will favor division along the largest axis of the parent AABB) ( f1(pos) = max(split_x_axis, split_y_axis, split_z_axis) )

b) the volume of both child nodes should be more or less equal ( f2(pos) = abs(volume_child_1 - volume_child_2) )

c) the number of faces on both sides should be more or less equal ( f3(pos) = abs(face_count_1 - face_count_2) )

d) The number of split faces should be kept at a minimum ( f4(pos) = total_number_of_split_faces )

To find an optimal subdivision axis and position, you need to minimize all the functions above. Note that function c) and d) exhibit both discreet behaviour, so they can have lots of local minima (depending on the topology of the geometry). Each function above is weighted by an importance factor, so the final equation to minimize is:

f(pos) = f1(pos)*w1 + f2(pos)*w2 + f3(pos)*w3 + f4(pos)*w4

The weight distribution depend on your engine: where are the bottlenecks, how should the tree be balanced to make use of the optimized paths, how is your scene structured, how is your scenegraph organized (if any), etc.

One can use several ways to minimize the equation. We use a neural net. A different approach could use successive approximation, or simply sampling a set of positions and taking the one with the lowest f(pos).

At this point, you have the position and orientation of your division plane. Now, if you divided all geometry contained in the parent node at that plane, you'll notice that even though you minimized equation (d), you'll still have a lot of split faces. That's not good, so let's introduce a new feature of ABTs: you can overgrow them. The idea is that an ABT node does not need to represent a distinct region of space, but an approximative one.

Consider one of the two child nodes. Atttribute to this node all faces, that have the largest part of their area in the node's bounding box. You have lots of small faces sticking out of one of the six sides of the box: the one created by the division plane. Those faces would normally need to be subdivided. Now make the box a little bit larger on that axis. Quickly, the number of subdivided faces will drop, as more and more faces will be contained in the AABB. Do the same thing with the other node. Note, that both AABBs will now slightly overlap in the middle. The more you overlap them, the less efficient will the hierarchy of your tree be, so the growth factor should be made a maximal percentage of the boxes volume. I use between 5% to 10%, which eliminates almost 90% of the critical faces. Some really big ones will still need to be subdivided, but in a reasonably tesselated environemnt, those faces will be the minority.

Now it's time to optimize the volume. Because of the property of an AABB to encompass the whole volume of an object along it's primary axes, the AABB of the parent node often has a much larger volume than the combined AABBs of both children nodes. Mathematically expressed:

AABB1 + AABB2 <= AABB1 UNION AABB2

In octtrees, that's a necessary evil, and can result in lots of empty (or almost empty) nodes. But we can do better: for both child nodes, recompute the optimal AABB for the geometry they contain.

Continue the recursive process on both children, by supplying the newly formed AABBs as parameter to the recursive function. Do that until the process has terminated, and all leaves have been created.

At this point, due to all the overgrowing and optimization, your original node hierarchy will be largely out of sync with the nodes themselves. So you need to rebuild it from the bottom to the top. For each leaf, walk up the tree, and recreate the bounding boxes for each node by unifying the child AABBs to the parent AABB. If everything went well, you'll end up with the same root AABB that you've started with. Your tree is now complete.

Rendering it
Very simple and extremely fast. Start at the root node. For each of the two child nodes, test their bounding boxes (those you recomputed in the last step of the tree creation) against the frustum. If they intersect, continue recursion along the branch. If you hit a leaf, render it.

Note that since a face has a unique leaf, you can directly store a vertex array/buffer in each leaf. So no array repopulation, no checking for doubles and already rendered faces, etc. Just a simple render vertex array/buffer call per leaf. You can't get faster than that (ignoring shader state changes of course, but they are very easy to integrate).

Making it dynamic
An ABT can be used on fully dynamic scenes. When an object moves, just move it's AABB along, and quickly reunify the AABBs of the nodes between the leaf and the root node. That's it. The problem is, that with time, when an object moves far away, the tree will slowly degenerate. It will still work, but it's culling efficiency will decrease. The sloution is to rebuild the degenarted parts of the tree on the fly, depending on degeneracy factors. But I won't go into details here, as it would double the lenght of this already very long post If there is enough interest, I could go into more detail here in another post.

/ Yann

[edited by - Yann L on November 14, 2002 7:56:25 AM]

That''s a brilliant description, thanks.

Now that I''ve seen the description, I realize it is the same as a technique I saw in a paper last year some time, although it didn''t have the abt name (I think). It didn''t explain the construction method, or much about dynamic recomputations.

Out of interest, do you incorporate atomic objects (like weapons or biscuits) as triangle sets, as bounding volumes, or just use a separate culling system?

I really like the system, it''s very neat. I know you can limit the tree size, do you have any statistics on what depth of tree is ''good''? I imagine on good hardware shallow trees work best, although if I wanted collision information I guess it will be better to have a deeper tree to cull more surfaces.. hmm.. Actually, now I come to remember it, I think that paper had a method whereby you order the faces by the tree, then you don''t need to recurse down to the leaves, you just pick a level and render all of the triangles in that level and lower. That way I could have a deeper collision tree without requiring a full traversal for rendering. Or maybe that doesn''t work..

I for one would be interested in the dynamic recomputation ideas.

Also, why haven''t you written a paper on this yet?

Yann, to reference back to something you said before:

Are you saying that with current hardware (or future for that matter) that the cost of drawing a polygon is almost less[i] than a large traversal algorithm to determine it''s visibility?

~Main

==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

quote:

---

Original post by duhroach

Are you saying that with current hardware (or future for that matter) that the cost of drawing a polygon is almost less than a large traversal algorithm to determine it''s visibility?

---

For a single polygon it has to be less. For lots of them it isn''t.

That would be an option, but it could destroy the locality. Say you have a large polygon sticking outside a box which contains a set of triangles which are nicely clumped together. If you just make the box bigger, you could waste a huge amount of space.

[edited by - JuNC on November 17, 2002 6:41:13 AM]

quote:

---

Now that I've seen the description, I realize it is the same as a technique I saw in a paper last year some time, although it didn't have the abt name (I think). It didn't explain the construction method, or much about dynamic recomputations.

---

Hmm, do you remember the title or author of that paper ? I haven't seen any descriptions of that system so far, so it would be interesting to compare it with a different implementation of the same idea.

quote:

---

Out of interest, do you incorporate atomic objects (like weapons or biscuits) as triangle sets, as bounding volumes, or just use a separate culling system?

---

No, they are part of the tree, just as other objects. Actually, dynamic objects are divided into two categories: full dynamic (can move everywhere) and stationary dynamic (can move/morph, but always stay in the same area. Eg. a door: it can move, but you'll rarely find a door travelling around your level... ). This can be used to optimize the runtime relocalization of the tree.

There was another thread a few months ago, where I described all that in more detail. Something about scenegraphs combined with octtrees. But well, you know, the search engine... I'll have to browse my bookmarks at work tomorrow.

quote:

---

Also, why haven't you written a paper on this yet?

---

Because I royally suck at writing papers... I have 3 unfinished papers lying around, and I just can't get them done. *ahem* Dave is still waiting for that paper about cloud rendering

quote:

---

Are you saying that with current hardware (or future for that matter) that the cost of drawing a polygon is almost less than a large traversal algorithm to determine it's visibility?

---

Yes. But there is a break-even point. It depends on the relative performances of your HSR system and your rendering pipeline. It can be anywhere between, say, 50 (for very optimized systems) to 2000+ faces (for very slow trees). Anything below 50 is going to be faster to simply render than to cull away using your tree (ignoring fillrate here), because it's under the break even point for a vertex array/buffer rendering call.

quote:

---

Thanks for that great description Yann. Forgive my naivete, but why do you need to go through the trouble of pushing out the faces of the leaf AABBs and splitting the triangles that lie on the boundaries? Why can't the intersecting triangles in question simply be members of both adjacent leaves?

---

This would also kill a major feature of that tree: the unique attribution of a face to a leaf. This ensures that every leaf is an independent entity, totally separate from any other leaf. That means, that a leaf AABB does always represent the combined axis aligned volume of all faces contained in it. Not more, not less. If the AABB is not visible, then you can safely discard all the geometry it contained, no other nodes have to be taken into account. This property allows for some very important performance optimizations:

* better leaf localization.

* leaf-local geometry pools. The geometry in each leaf is totally isolated. That is always true for face indices, and can be extended to vertices in highly optimized structures.

* If you render an independent leaf, then you can directly feed it's geometry pool to the 3D card. No other processing is involved. The geometry can also be stored directly in VRAM. That's not the case, if faces are shared among leaves: you either have to flag them as 'already rendered' (and this implies the CPU touching every face before rendering, which is a capital sin in high performance rendering), or you'll render a lot of faces multiple times (which is even worse).

* lower memory consumption. As each leaf has a separate node pool, and assuming that each leaf does not contain more than 65536 faces, you can use SHORTs to represent your index arrays, instead of the INTs typically required. Halves your index array memory consumption.

/ Yann

[edited by - Yann L on November 17, 2002 8:05:53 AM]

I''m to lazy to read all that text, but i don''t agree with your anti bsp/pvs propaganda. I think solid leaf bsp''s are still awesome for indoor scenes where there are surfaces that are translucent and for collision detection. And pvs and is still the fastest alternative for VSD in indoor scenes and unlike portals the artist does not need to mark them.