[Algorithms] Building BSPs Robustly

[Bernd K. <bk...@lo...>]

Charles Bloom writes:
 > make your BSP building robust (eg. numerically safe) ?

Snapping the original vertices to a grid of integral 
coordinates? The split vertices won't be integral, but 
you might get a better error estimate.

If you can find an upper bound on the error, could you 
shift newly created vertices by that amount along the 
normal, by default? The deeper your tree, the more such 
changes you will accumulate, but if you find a sufficently 
low upper bound maybe you can make sure that you err on 
the right side without introducing a visible error?

Minimizing splits is a good start. Maybe reject splits 
too close to existing vertices, or splits that create 
to big an error (sign?) with respect to

   d = plane.DistanceToPoint( split_vertex );

Investing cycles into a good heuristic might come cheaper 
than checking correctness?

                                       b.



Side question: if you don't use the BSP for depth sorting 
(rendering) but just for hierarchical culling and collision 
detection, do you have to split polygons (i.e. create new 
vertices) at all? With respect to point-vs.-plane tests, 
isn't your leaf is essentially just a list of planes to 
test against, so does it matter whether a plane (that can 
cover all coplanar polygons) appears in more than one leaf 
(flip sign for orientation)?

I am not sure how big the penalty for a depth buffer clear 
and a more or less unsorted z read/write pass (as opposed 
to back-to-front z fill) is these days, especially as 
moving objects approach polygon budgets larger than the 
visible part of the scene.