Having just worked with BSP trees, Portals and so on, I had an idea I wanted to share.

The chief aim of a BSP Tree is to identify convex sets of faces.
You might think of these as walls which separate rooms.
If you're standing in a convex room, all the walls will face you, no matter which way you look.

What if we could cut the world up into convex sets without all the triangle-splitting and extra vertices that BSP suffers?

The algo:

Take each input Face, and shove it into a list / collection of faces which A) are connected to this face (share an edge) and B) are convex with all faces already in the collection.
If we can't find a collection that satisfies both of these constraints, shove it into a new list on its lonesome, and collect that list.

We end up with lists of both connected AND convex triangles, with zero splitting, and zero extra vertices required.

A bsp tree guarantees that sets of faces are convex, but does not guarantee that they are actually adjacent.

The adjacency data can then be used to find the geometry of Portals by determining which vertices of the faces in a convex list are shared by the faces in another convex list.
The resulting lists of vertices shared between the convex lists describe a complex polygon which may not necessarily be flat (planar), but it doesn't matter, since our visibility test for portals boils down to testing points against the view frustum planes :)


Posted on 2008-02-22 10:39:15 by Homer