Determining level connectivity

Question

Imagine you have a 3D level format consisting of an arbitrary number of convex polytope brushes (or we can simplify and consider just oriented-bounding boxes) and several point entities.

I want to find an algorithm to determine

1. If the level is water-tight. That is, the brushes are adjacent to each other and fit together to form a hull without gaps or holes.
2. If the level is disjoint, identify the set of brushes in each section.
3. If all entities are inside the water-tight level, and in which section (from (2)) they are in.

(1) isn't strictly necessary, but it seems necessary to ensure that (2) and (3) are well defined.

All engines I know that use this kind of level format (Doom, Quake, Source) seem to use a BSP algorithm for these tasks. However, they also use the resulting BSP tree as an acceleration structure for rendering, which I'm not interested in using.

Is anyone aware of any other possible alternative algorithms, or is BSP the only choice?

Answer 1

BSP is a classic for computational geometry tasks involving polygons. However, polygonal meshes are subject to a dismaying list of pathologies such as degenerate polygons, inconsistent winding order, T-junctions, coincident vertices, cracks or holes, self-intersecting geometry, loss of coplanarity or collinearity due to roundoff error, and other such things. Making computational geometry robust on arbitrary polygon meshes is Quite Difficult™.

It worked in Doom/Quake/Half-Life days because the base level geometry (made of brushes and constructed in a level editor, as opposed to a 3D modeling tool), was relatively simple, mostly axis-aligned, and all vertices were snapped to grids. More recently, the trend seems to be for level design seems to be done by creating mesh pieces in 3D modeling tools, then sticking together a bunch of instances of them to form a level. This kind of construction is a lot less friendly to BSP-type algorithms—especially as the geometric complexity rises.

An alternative approach for connectivity questions is voxelization. In short, you voxelize all your level geometry at some reasonably small resolution, like 10–30 cm per voxel or so. The voxelization wipes away any geometric errors smaller than the voxel size, and it gets rid of all those annoying pathologies mentioned earlier. You can use an octree or brickmap etc. to avoid voxelizing empty space.

Once you have the voxel representation of the level, you can then do all sorts of connectivity queries on it very easily because of the regular structure of the voxels. For instance, determining if a level is watertight or finding connected-components at the voxel level is basically a flood-fill. These kinds of algorithms can also be done hierarchically using the octree etc. to avoid the expense of a global flood-fill over a huge number of voxels.

For more reading, there was a 2011 SIGGRAPH talk Making Game Worlds From Polygon Soup, from some engineers at Bungie who used voxelization techniques on Halo Reach levels to build nav meshes, precompute visibility cells and portals, and so on.