I've just finished implementing Nathan Whitaker's portal discovery algorithm.
Believe me, implementing it was awkward, involving deep recursions and lots of cutting of triangles, sorting between lists and creation of 'junk data' along the way, and the algorithm is, all said and done, a bit of a clunker.
So, we've generated a BSP Tree whose Leaves describe convex spaces which are bounded by the faces of the world, except for some holes in them, which we know just happen to lay on the 'cutting planes' that we found and used to construct the tree...
Really, we wish to 'close' the holes in our open hulls that surround our convex spaces, and we know that the 3D shape of each hole must be along one or more of our cutting planes.
We can use a 'hole-closing algorithm to find these shapes, accelerated by our knowledge that the vertices which form the edges of the hole all lie on our cutting planes. It will still be expensive, but nowhere near as expensive as the algorithm that cuts and sorts, cuts and sorts..
For a given leaf node, we'll be looking at the set of vertices which are used by its faces.. for each cutting plane, we will try to find three or more vertices that rest apon the plane - if we can find three or more, we have found a portal and its vertices (an n-sided planar polygon).
Now for the connectivity part.. for each portal, find the midpoint of its vertices... we know that it will be coplanar. Now using the surface normal, shove the point to each side of the plane, and use the tree to find out which 'other' leaf node it lands in... tadaa, connected.
Now we can write out the data for each Leaf node, and discard the tree.
What do you think?