I've tried a few spatial partitioning schemes (bsp, quad/octree, kdtree etc) but all of them suffer from the same problem : they fracture the geometry at partition boundaries, producing more triangles than were originally present, and occasionally producing triangles with illegally-short edges which are then clipped, producing small 'holes' in your physical surface (gamers call these 'glitches', and use them to CHEAT).
So I was evaluating in my mind the process of building a BSP tree and it occurred to me that all we really wanted to do was find clusters of convex faces - ie, groups of triangles that all generally face toward one another.
It seems to me that it should be entirely possible to build an equivalent tree using a MUCH SIMPLER algorithm to select and reject candidate triangles, completely eliminating the Splitting of triangles.
The result wouldn't be a tree as such, but a network of connected nodes representing the connected convex subspaces ('rooms') that form our world.
The algorithm for selection of convex faces would be based on the connectivity information provided by the mesh at load-time in the form of "Edge Adjacency" data... given a starting triangle, we march the adjacent triangles, performing our planar select/reject test.
Selected triangles are added to the current List, and rejects are added to a Stack until we exhaust the current search.
Now we choose the first triangle on the reject stack as the first triangle for a new subset, and repeat the process.
At the end we have several lists of triangles, each representing a convex chunk of our world.
Now we can find the Portals between them, again using the Adjacency data to find the Edges of triangles in list A that are shared by triangles in list B.. each of these 'edge lists' represents the shape of a PORTAL (doorway/hole) that connects two convex subspaces.
With just a little more work we can describe the geometry of each Portal as a set of triangle-shaped holes rather than just some edges, so we can then perform collision detections against the portals, as well as use them at runtime for VISIBLE SURFACE DETERMINATION (VSD) because we know that if we can't 'see' a Portal on the screen, then we dont have to draw the 'room' it leads to.

Posted on 2008-06-14 23:34:43 by Homer