When a problem comes along, you must Clip it ;)
At this point, most of the BSP tree will no longer be of any use to us - our leaf nodes, which represent our convex subspaces, each contains a list of 'portal fragments', some of which are actually 'duds', which must die, and others need some cosmetic attention.
For each leaf node, we will clip its portal fragments to the planes of the visible geometry in that leaf.
We will discard any resulting fragments that are found to be 'back' ie 'behind the plane' since they are not inside this subspace. This may involve discarding entire polygons..if its point away from us, or its totally behind any plane of our hull, then its not part of this subspace.
The front parts and the coplanar parts we will keep. These are the parts that are within the bounds of the current subspace. Actually I expect not to get any front parts, but we'll see.
What we are doing is constraining the portal geometry to the exact shape of the voids in our otherwise closed convex subspace, without violating their geometric constraints, such as existing apon one of the planes that bounds the subspace's closed hull.
To be clear, our subspace is an open convex hull, which is closed by planes of its portals. So our subspace has visible, solid surfaces, and it has some 'holes' that lead to other places. We have just discovered the exact shape of these holes. All that remains is to determine where they lead to, and do something useful with that information.
OK Wait - there is one final tricky special case to handle, but it can wait for my next post.
[subheading]Planar Polygonal Mating Rituals[/subheading]
So, we have reduced our set of fragments per leaf to a relatively small number. As a matter of fact, the only remaining portal polygon fragments are those which fit inside the shape of the holes, on the planar surfaces of our subspaces, ie, collectively, they represent the shapes of all the holes that connect any two subspaces in our world.
Note that each fragment is tagged with the ID of the Portal that originally owned it.
Now we reach the moment of truth - Connectivity.
For each leaf, and for each unique portal ID in that leaf, find another leaf which contains a portal fragment with the same ID.
These two leaf nodes are connected by this portal! Only two leaf nodes can contain pieces of the same portal, due to the fact that our partitioning scheme is bi-fold.
Move all the portal fragments which bear that Portal ID back into the owner portal, discarding the fragments in the 'other' of the two leaves (since they're 'clones'), and add to each Leaf a reference to said owner portal, and tag the Portal with a reference to each Leaf it leads to.
End Loop.
Now, each leaf contains no portal fragments - just visible triangles once more.
Each leaf contains a list of Portals that lead to adjacent subspaces, and each Portal knows which two subspaces it connects, and the shape of the connecting hole as projected apon a unique 3d plane on the surface of both subspaces, with respect to the first of the two (order of discovery).
We now have everything we need to construct a cell and portal graph - in fact, we have already created it
