I'd like to talk a little about an idea I've had today regarding BSP Trees.

There's two major algorithms for generating BSP trees, although the algorithms are known by several names.
I'll just call them A and B.

The key difference between the two algorithms is what happens to polygons when the dividing plane passes through them.

In algorithm A, we literally cut those polygons into new polygons, so the number of polygons gets bigger as the tree is being generated. If the fragment polygons have edges below a certain size, they cannot be used for collision detection - this causes small 'holes' in the map which people use to cheat in games, and which are a royal pain for game developers, as they continually patch their game maps as players discover new 'glitches' to abuse.

In algorithm B, we don't cut those polygons - instead, we put a reference pointer on each side of the dividing plane (ie, in both child nodes) - so as the tree is generated, we have to keep extensive lists of duplicate pointers.
These maps don't suffer from the 'glitches' mentioned above, but have a very large memory footprint, and rendering is more difficult as we must keep track of which polygons have already been rendered in neighbouring nodes, otherwise we are once more drawing more polygons than we have to... and the same problem for collision detection, we don't want to perform collision checking on the same polygon more than once.

My idea is quite simple - when a polygon is intersecting the dividing plane (or is coplanar with it), just leave it alone, don't try to send it down the tree anymore.
There's no good reason to want polygons to exist only in leaf nodes.
Now we have eliminated overdraw and 'glitches', no new vertices or polygons are generated, no extra memory is used, and collision detection and rendering code is not made more complex.

Rendering such a bsp tree is quite simple.
The revised algo for this would be:

-if the current node is a leaf, render the polygons in the current node
--Check what side of the current node's dividing plane the camera is positioned
--if its on the front side,
---recurse the back child
---render the polygons in the current node
---recurse the front child
---recurse the front child
---render the polygons in the current node
---recurse the back child

Posted on 2008-10-20 03:08:01 by Homer
Apart from the changes outlined in the previous post regarding BSP trees, I have some other ideas which can greatly speed up the generating process, especially in regards to portal generation.
In case you don't know, portals are imaginary transparent surfaces which lay apon the dividing planes that define each non-leaf node in the tree, and connect the subspaces - a simple example of these is windows and doorways.
Portals are used for two things - to generate a PVS for each subspace (potentially visible set of faces), and to allow us to track which subspace a player is in without having to walk the tree every frame.

Normally, we would generate a bsp tree, and then attempt to discover portals from the structure of the tree (the dividing planes), and the geometry it contains.
I'm thinking it might be far more efficient to treat the problem of bsp->portals backwards to everyone else.. rather than generating portals from a bsp tree, we would generate a bsp tree from its portals - its important to realize that portals always rest apon the dividing planes of the tree, and effectively define each bsp node.

Automatic generation of portals is NOT trivial, sometimes impossible, prone to error, and is never, ever as efficient as doing it by hand. Also, it is a recursion within a recursion, so the time it takes to find them automatically is exponentially greater than the time it takes to generate the tree by the usual means - if bsp generating WITHOUT portals is a major bottleneck to production times, imagine what the additional cost of automatic portal generation means to a production manager!

If I ask my artists to strategically place portal surfaces and tag them with a special material, I can then use this subset of surfaces to guide the generating of the bsptree in a fraction of the time it would normally take, and have total control over the placement of portals.

Of course the artists need to have it explained to them what portals are for, in order to place them strategically (to separate the subspaces of the game map into visible regions).

They need to be placed for example at bends in hallways, across doorways, above stair wells, they need to close off 'alcoves' and so on.

Another advantage is that we can use whatever 3D editor we are using to create game maps to do all the clipping of portals so they are perfectly clipped to the surrounding geometry and to each other.

Since game maps are generally much larger in recent years, I predict that it would take less time to place them by hand than it would take to generate them, and since we are using them to guide and optimize the bsp tree generator, recompiling of the tree due to map editing is no longer the huge production bottleneck that it otherwise may have been.

Another advantage of material-tagging portals in this way is that we can easily render that mesh subset using existing code to visually check that their placement is desirable.

Posted on 2008-10-21 00:24:53 by Homer
Once the tree has been generated, we still need to find the connectivity, which cannot be directly extracted from the tree.

The leaf nodes do indeed represent primal subspaces, but they are not necessarily convex, or even closed.
All the non-leaf nodes represent our predefined portals and their planes.
But the tree does not tell us anything about which leaves are connected via which portals.
To find that out, I am thinking about performing a 'stabbing test'.

Our goal is to build, for each leaf node, a list of portals which touch this subspace - ie, all the exits from this place to other places (there will often be more than one).
For each portal, we find its centroid, and then using the normal of the plane apon which it exists, we shift the centroid "very" slightly to each side of the plane, and then use the tree to figure out which leaf the point is now inside.
We just found out which two leaves are connected by this portal, and we can add that information to both leaves.

Now we have our bsp tree, our portals, and our connectivity information.
Using this, we can now go on to build a PVS for each leaf, if we really want it.
Also, we can use it to generate radiosity information for any number of fixed lightsources (a special form of lightmapping that adds enormously to the look of the virtual world - imagine roast beef with and without gravy and you'll understand how important radiosity is).
Posted on 2008-10-22 08:09:41 by Homer
I think that precalculated PVS is a really dumb idea, when compared to view-dependant realtime PVS (see Alan Baylis).

Precalculated PVS is something like this:
From a given subspace, name all the potentially visible faces in all the potentially visible adjacent subspaces, and render them, even if we cannot see them.
The benefit is that the cpu overhead is essentially zero, the cost is a larger memory footprint and a lot of triangles being thrown at the video card that are not visible.

Alan's concept is something like this:
If we can see a Portal on the screen, then we can see into the adjacent subspace, and so we must consider its surfaces... and if any of those happen to be another Portal, repeat that process.
The benefits are that there is no memory footprint and only visible triangles are sent to the video card, the cost is a very small amount of cpu overhead.

The cheapest triangle to render is the one you DON'T render, right?
Well, I think precalculated PVS takes the "avoid cpu work at all costs" ideology one step too far.
Maybe it was ok a decade ago before hardware-based shaders were available, but I'd rather spend my gpu cycles doing fancy special effects than culling offscreen triangles, thanks.

In my previous post I mentioned radiosity - please see http://freespace.virgin.net/hugo.elias/radiosity/radiosity.htm
Posted on 2008-10-22 10:29:02 by Homer
Resistance: Fall of Man  uses precomputed PVS bitfields (takes all night to compute by rendering + occlusion tests), and look at it churning out extremely vast and detailed levels :)

I'd put all my money on early-Z culling: draw the scene twice, first time with cheapest vtx-shader, cheapest frag-shader and disabled color-writes; then with the cheapest possible vtx-shader, but expensive frag-shader. The depth-pass must use memory-optimized arrays of vec3 for pos, instead of long strides.

But I still may use portals, with just an occlusion-test you get can get away with doing a thousand fewer draw-calls - if you sequence the test nicely.
Posted on 2008-10-26 21:17:47 by Ultrano
My goal is to create a cell-and-portal network from a loose bsp tree, and then discard the bsp tree.
Each Cell will have a list of Portals which lead to other Cells and a PVS.
I'll probably generate the PVS from within the radiosity loop.
The PVS will be stored in several chunks - one is associated with the Cell, and one is associated with each Portal.
This allows me to cull the potentially visible faces that are in adjacent cells (behind portals) whenever those portals are outside the view frustum.
I was thinking of unpacking the PVS into a VB whenever the player crosses a Portal plane.
I'd have all the PVS for the Cell and its Portals in there, always draw the Cell PVS, and only draw the Portal PVS's if a given Portal is visible.

Posted on 2008-10-26 21:55:16 by Homer