We are not going to use BSP in the traditional way (ie, for implementing painters algorithm during rendering).
Rather we will use BSP as an intermediate tool for generating our cell and portal graph.
We are interested in discovering a set of convex subspaces and the 'holes' that connect them - BSP is going to get us more than half way to our goal.
[subheading]Discovering Convex Subspaces[/subheading]
The first stage then is to generate a BSP tree from an input set of triangles.
And to be quite specific, it will be a 'leafy' tree, with all the polygons located in leaf nodes, and all other nodes recording a splitting plane (this will make more sense as we progress).
While building our BSP tree, it is desirable to attempt to create a well-balanced tree of minimal depth... this brings us to our first algorithm: given an input set of triangles, discover a triangle whose 3D Plane 'best' partitions the input triangles.
By 'best', we mean that Plane which produces the most even number of triangles in each of the resulting subsets, while simultaneously 'splitting' the least other triangles.
These two goals are mutually exclusive, this algorithm implements a simple heuristic which attempts to achieve our mutual goals.
The process of building the BSP tree is recursive - given the original input set of triangles, partition it into two subsets, and repeat.
When should we stop?
For our purposes, we should not stop until a triangle subset contains NO candidate splitting planes.
When this happens, we have discovered a CONVEX SUBSPACE whose CLOSED HULL is defined by the set of planes of the triangles in this subset (and the planes of its ancestor nodes). Furthermore, we know that the holes or portals which connect this subspace to other subspaces must exist on existing splitting planes, defined at non-leaf nodes in our tree.
At this stage, we have a complete leafy BSP tree describing our world... its leaf nodes represent convex subspaces or 'rooms' in our world, our next step is to discover the portals or 'holes' which connect the subspaces together.
