[Algorithms] Building BSPs Robustly

[Charles B. <cb...@cb...>]

A question for the BSP experts : what do you do to make
your BSP building robust (eg. numerically safe) ?
Is there an article on these issues? (still working on
that BSP article, Angel?).

Now for more detail.  Let me stick to two dimensions for
simplicity.  I'm building a 2d BSP from convex polygons.
To do that, you just take the polygon and send it down
the tree, clipping it against each plane in the tree.
Eventually you arrive at a leaf.  At that point I take
all the segments of the clipped polygon which arrives
at that leaf, and add them to the tree if and only if
the plane they create isn't already in the tree.  This
make it so that if you have a little empty leaf in
the tree and you add a polygon that covers it completely
you don't end up adding any planes, you just mark that
leaf is solid now.

Now, we run into robustness problems.  The first problem
is just with tiny segments.  Sometimes after clipping you
end up with very short segments in your leaves, that you
can't do a reliable cross product on to make a normal for
use in the plane.  I just throw out these short segments
(seems reasonable).

All of the remaining problems come from numerical errors
on the plane clipping.  This arises because when you take
a point, find the distance to a plane, and push it by
that distance, you don't end up with a point right on that
plane.

   d = plane.DistanceToPoint( point );
   point += d * plane.normal;
   d = plane.DistanceToPoint( point );

Now d is small, but not zero !  The point is slightly off
the plane in some direction.  This will always happen, no
matter how you do your plane clipping, and whether you
use floats or doubles (I use floats).

The result is that you can end up with non-convex polygons
in the leaves.  These can happen in 2 major ways (
see http://www.cbloom.com/bsp_problems.gif "):

1. "bend-ins".  This is when you have three verts that
are very nearly co-linear.  If the clipping had been perfect,
they would have been colinear.  Instead, the middle one fell
a bit to the inside of the other two, creating a very mild
star-trek-symbol shape.  I get rid of these by finding the
triangles that have very small areas and deleting their middle
vertex.

2. "fish-tails".  Take a triangle.  Duplicate one of the verts
to make it a quad with two verts right on top of eachother.
Take one of the duplicated verts and pull it across its twin
so that the segments of the quad intersect.  This makes a
segment with the wrong winding, two triangles with upside
down normals.  This is a big crisis for a BSP, because that
wrong-facing segment will make a plane facing the wrong way.
Most of the time, this will be fixed by deleting the very
short segments, but I still seem to get it once in a rare
while.  The rest of the time, I fix it by turning the segments
in to planes.  In my convention, proper planes will have
all the other verts of the polygon on its front side.  Thus,
any plane which has verts of the polygon on its back side
is simply tossed out, and its end-points are snapped together.

So, I find this all a bit scary (if I "fix" my leaf polygons
in the wrong way, I'll end up getting a BSP different than I
intended), and what's worse, I'm building these BSP's in real
time, and all this testing for convexity of the leaf polygons
is one of my biggest bottlenecks.  Help appreciated.

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com