I am now able to discover all the convex subspaces, construct the portals as BFQ's and then 'shatter' them against one another.
However before I post the updated sourcecode, I need to eliminate a bunch of runtime tracing/debugging stuff that helped me track down the bugs, and I'd like to have a go at improving the heuristic for selection of splitting planes (in the bsp tree gen).
I will note here that this endeavor is pretty much redundant, since I do not intend to use the BSP tree structure at runtime (as such).
However I will for the sake of completion go on to explain what its about.
[subheading]Can we do better?[/subheading]
The current heuristic treats the input set of triangles as a 'point cloud', choosing the plane which most equally bisects the vertices for 'best balance', without considering the geometry - the shapes involved. It does not care how many triangles the plane passes through, and makes no attempt to avoid doing so. This generates an inordinately high number of fragment triangles during bsp tree generation, and for me it's going to mean more duplicate triangle references to either filter or pay for in terms of pixel overdraw.
.
Our heuristic for selecting splitting planes should attempt to fulfill two goals simultaneously: good balance (don't favor one side of the tree too much), and fewest possible splits (avoid generating too many extra triangles, leading to extra tree depth). These goals both seem to make the tree not be too deep.
Although not immediately obvious, these two goals are in fact mutually exclusive. That, however, does not prevent us from designing and implementing a heuristic which tries its best to meet both objectives.
What we can do is attribute a 'fitness score' to each potential splitting plane, based apon the number of vertices falling on either side of the plane being similar (good), and the number of triangles that are cut by the plane (bad). Then we'll just return the candidate whose score is 'best' (which is a subjective term, depends on how we calculate our fitness score, but will typically be 'highest' or 'lowest').
[subheading]What's Next?[/subheading]
Now we have our Portals (one per non-leaf node), which were constructed as big fat quad, each apon one of the unique 3D planes we used to construct our tree. Each Portal object is a container for a bunch of convex fragment polygons resulting from the shattering of the convex BFQ polygons. We will now 'march' all the fragment polygons down the tree starting right from the very top (root node) until they each have landed in a leaf node.
Important note about this process:
Since the fragments are, collectively, the result of splitting every BFQ against every possible splitting plane, we can never have a case of a fragment being split by a plane during its 'walk' down the tree. If we do, we did not shatter the BFQs correctly.
We can take advantage of this fact... it implies that ANY point in a polygon will return a point/plane result that is true for the WHOLE polygon.
There are two small exceptions - the first is when our test point returns a Coplanar result - we'll need to try another point (or points) until we get a definitive result. But the odds of us picking a valid point on the first try are very good.
The second exception occurs when all the points of the fragment turn out to be coplanar (with the current node's plane). The implication is that all OTHER fragments of this current portal will also be coplanar with this current plane. This case needs special handling.
If we detect a fragment is coplanar with the current plane:
For every fragment in the current portal, duplicate (clone) the fragment, send the original down to the front child, flip the cloned fragment's surface normal (ie, the x,y,z components of its plane), and send the clone down to the back child.
The reasoning behind this will become clear in the final step, where we seek to mate the matching 'sides' of each Portal (since a Portal has two sides, each facing into an adjacent subspace). We have just ensured that there are indeed two sides, and that they indeed face into the correct subspaces - the last part ensures that they survive our next step: Culling and Clipping our Portal Fragments.
So, for each fragment, get a polygon/plane result (whether the 'long way' or the shortcut I've suggested), and (excepting those special coplanars) send the fragment intact to the corresponding child node, and repeat, until we can't anymore.
We should end up with our portal fragments in a jumbled mess, neatly contained in a single list in each and every leaf node.
We expect that all leaf nodes will receive portal fragments. If they don't, it indicates a 'solid subspace' which is somewhere the player should never be. Anyway, so each leaf now has a list of portal fragments, each tagged with the identity of its 'owner' portal. And we have our list of portals, now completely empty of any portal fragments.
We will now clip and cull the fragments - many will not survive this process. Those that do are our 'true portals', and their shape represents the exact silhouette of the portal, the shape of the 'hole'. I'll talk about that more in my next post
