Just some quick notes regarding the 'splitting' of geometry during BSP tree generation...
Traditionally, BSP Tree Generator algorithms will actually physically split polygons into two new polygons, placing one in each child subspace.
The problem with this is that it creates a large number of extra polygons and their associated costs, and the real danger of creating 'aberrations' - deformed, illegal polygons whose geometry might not be a problem for rendering but might certainly be problematic for things like collision responses.
We can easily avoid this: instead of directly passing polygons down the BSP tree during its construction, we will instead pass references to the original input set of polygons.
Now when we need to 'split' a polygon, we just duplicate the polygon's reference and send one down each side of the tree.
We'll end up with sets of polygon references in the leaf nodes instead of actual polygons.
There will be some duplication of references to polygons that are 'shared' by multiple subspaces, however these can easily be eradicated by collecting only unique references during the rendering step... or we can ignore them, and have some minor overdraw when those polygons are visible through onscreen portals.
Either way, the benefits of avoiding splitting polygons during BSP tree construction outweigh the costs and problems associated with 'perfect partitioning'.
We don't care if polygons overlap subspaces, only that we can identify those subspaces accurately.
[subheading]PORTALIZE ME[/subheading]
Now, the next exciting episode.
How do we automatically discover the portals which connect our subspaces?
[subheading]BIG FAT QUADS[/subheading]
We begin by observing the boundingbox of the original input set of polygons for the entire 'world'.
In fact, it would serve us well to calculate the boundingbox of the input set of polygons at each Node during tree construction.
Every non-leaf Node in the tree has recorded a splitting plane during the tree construction.
Our goal is to construct apon the splitting plane a rectangular polygon (eg a Quad, or two triangles) whose extents are those of the node's boundingbox.
So for the root node, we want to make a giant rectangle whose Surface Normal matches the splitting plane normal, and whose Vertices all exist apon the surface of the boundingbox (ie, the intersection of the plane and the box).
We will tag each of these special 'Portal polygons' with the ID of the node whose plane they were constructed apon.
This ID will be retained by any 'child fragments' resulting from the next step, where we 'smash' these 'giant windows', we will later use it to discover mating sides of each Portal.
[subheading]SHARDS OF PORTAL[/subheading]
Our next step is to 'Shatter' each of our Portal polygons: we attempt to Split each portal polygon with every splitting plane in the tree, with the exception of its own construction plane, keeping ALL the resulting fragments (both 'front' and 'back' of the splitting plane), tagging such fragments with the inherited ID of the input portal polygon fragment. We then pass each resulting fragment to the Root Node of the BSP tree, allowing it to 'fall' through the tree, classifying it against the splitting plane of each non leaf node, until it lands in a leaf node.
When a fragment reaches its own construction node, we should clone the ENTIRE fragment of the portal and send it down BOTH sides of the tree.
The reason is that a Portal has two sides - it lives in both of the subspaces that it connects, as we shall see momentarily.
Once we've finished doing that, we should have a whole bunch of portal polygon fragments in each of our leaf nodes, as well as the regular polygons from earlier.
NOTE: When passing Fragments down the tree, we should never need to Split them..
The reason is that these fragments have already been split against every single splitting plane in the BSP tree !!!
If we find that we need to Split them while passing them down the tree to the leaf nodes, we must have screwed up the Shattering step.
[subheading]CLIP ME AROUND THE EDGES[/subheading]
The next step is to Clip the Portal fragments against the planes of the regular polygons in the leaf nodes.
For each leaf node, clip the portal fragments in that leaf against the planes of the regular polygons in that same leaf.... literally we will split the portal fragment polygon against each clipping plane.
We want to keep the fragments that are 'inside the subspace' and throw away any parts that are behind any of the clipping planes.
We have now cut our portals into their exact shapes, any fragments which survived the clipping process are parts of our portals.
[subheading]MIRROR MIRROR - DISCOVERING CONNECTIVITY[/subheading]
Each fragment was tagged with the ID of its construction node, which contains its construction plane.
And each fragment has a mate in some other Leaf which bears the same ID.
Our goal is to match them - for each leaf, find all the portal fragments with the same ID and group them. Then for each group, find the Leaf containing a group with the same matching ID. We have now discovered the shape of each Portal and which two subspaces it connects. Note that it is perfectly legal for multiple coplanar Portals to connect the same two subspaces: for example, imagine a wall separating two rooms, with several windows and a doorway connecting them
Final steps could include welding the portal fragments into a single polygon (although its convexity cannot be guaranteed), and eliminating the second copy of the geometry for each portal. This step will involve finding and eliminating shared Edges in the portal fragment groups of each Leaf, and will lead to the discovery the individual shapes of multiple coplanar portals (ie unconnected portal fragment groups of the same construction id, as mentioned earlier).
Anyway, now we have found all the subspaces, and the portals that connect them, and the shapes of those portals.
We can now construct a Graph of connections between the subspaces, ie, a Cell and Portal Graph.
We're ready to write our structures to disk.
We no longer require the BSP Tree - just its Leaf nodes, or rather, the data they contain, since we can now track entities movements between subspaces via portals.
However its arguably useful to retain the BSP Tree for one simple reason: we can find out what subspace a given 3D point is in by simply passing it down the tree until it lands in a leaf node.... and finding out what subspace something began life in could be handy.
This wraps up the theory of Portalizing in a Polygon Soup, however there is much remaining discussion regarding correct utilization of the new cell and portal graph structure in terms of efficient rendering (to portal render or not to portal render), physical simulation (collision detection) and how to handle entities that are intersected by portals.
