I have been studying the logged output of my tree generator, and using that information to step through the same process in the 3D modelling tool originally used to construct the current test model ('Box In A Box').
Attached are some screen shots.
My implementation chooses to make the first cut through +Z side of the inner box.
This results in 16 triangles on the 'front' side of the plane, and 24 on the 'back' side, when I perform this step in my modeller, the result is the same.
My impl. next chooses to cut through the -X side of the inner box.
The results this time are 13 to the front, and 20 to the back, again this agrees with my modeller.
My impl. then chooses to cut through the +Y side of the inner box.
The results now are 13 to the front, and 16 to the back.. My modeller disagrees, it does a better job than me of triangulating the polygons - My triangle code does not attempt to optimize/simplify the tesselation.
Its results are 11 to the front, and 16 to the back. Not bad though.
This goes on, until 5 of the 6 planes of the inner box have been used as splitting planes.
Anyway, the problem I currently have is related to the very last subspace we discover, and is due to the fact that my model contains a CLOSED SUBSPACE which is SOLID, ie UNREACHABLE (we think!)
Consider this last face of the inner box, surrounded by four of the five used splitting planes.
As we used each splitting plane to carve away at our model, we 'stole' a face of the inner box.
These faces are now in the other leaf nodes.. leaving only this one unused face, plus a bit of the outer box, in the last leaf node, parallel faces pointing at each other. This is actually a convex set, we can't choose either of these two planes to split the set. The problem is that our node thinks that it includes all the space INSIDE the inner box, as well as the remaining space outside of it.
It is worth noting that this problem subspace is a BACK LEAF, and in this example, happens to be the last and only back leaf.
One possible solution I am considering is to impose a constraint that states all back-facing leaf nodes must be EMPTY of polygons - if a leaf node is discovered which is found to be the back leaf of its parent, we will shove the faces down one node further, forcing selection of a splitting plane from those available. This means that only FRONT leaf nodes represent OPEN subspaces where the player can go, and BACK leaf nodes represent illegal void subspaces.
This solution seems perfectly viable until we reconsider our example, and note that we don't actually have any way to determine which plane from a convex set is actually valuable to us !! We know that it can't have been already used as a splitting plane, but otherwise, our plane selection algorithm doesn't know how to choose among these convex faces which plane to use in this final step.
Of course we know that a face which is part of the world's outer boundary is a VERY POOR CHOICE - this will always be true.
But there are bound to be cases where simply choosing the face closest to the world bounds will be the wrong choice.
Actually, it might be more appropriate to make my constraint even more forceful.... I might stipulate that every face in a subset must exist on a used splitting plane. This will absolutely guarantee that all potentially problematic closed subspaces are indeed fully closed in the bsp sense (unreachable subspaces will not be reachable by the point-in-open-leaf test), at the cost of unnecessary (but minor) tree depth due to the mindless inclusion of planes on the world's outer bounds - however I can think of lots of reasons FOR including these planes, so I am happy to go along with this as the final solution unless anyone has a better idea.
I would love to hear your thoughts, people!
