Re: [Algorithms] Building BSPs Robustly

[Angel P. <ju...@bi...>]

> 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?).
Not yet, too busy right now. I hope to finish it next month.
 
> 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. 

If you just want to create a BSP from all convex polygons - then
first put all edge segments from all polygons in the root node of the
BSP.

Then pick a hyperplane from one of the stored edges (polys in 3D ) and move
all edges in front of the plane to node->Front and all edges behind the
plane to node->Back. If node->Front or node->Back is NULL and an
edge has to be put in it - then create that leaf.
Handling edges that lie on the plane depends on the kind of BSP tree
you want to do:
1. If it's a solid BSP with polygons(3D) in the BSP leaves forming solid convex
clumps then move the edge to node->Back.
2. If it's a solid BSP with polygons(3D) in the BSP leaves forming hollow convex
clumps then move the edge to node->Front, this kind of BSP
is used for automatic portalization.
3. If it's a classic BSP with polygons(3D) in the BSP nodes - then just store that
polygon there.
Recurse through node->Front and node->Back.


The approach you described is more suitable to CSG operations using BSP
trees (this is actually quite fast and can be done in realtime).

You can safely delete the clipped polygons which arive in
"IN" NULL leaf. See this picture:
http://thegeleto.tripod.com/bsp-figure1.jpg
This will clip away the polygons that are inside the current BSP.

For the edges that end in "OUT" NULL leaf - create a new
BSP leaf and store the edge and it's hyperplane in it.

For edges that arrive at a BSP node and lie on the separating
hyperplane  for that node - for now just store it there (although it's
not that simple, see below)

You have to clip the BSP line segments to the convex hull (or BSP if
the polygon is concave) of the polygon. Because clipping ALL BSP
line segments can be very slow you can use the bounding circle of the
polygon to visit only nodes that potentially intersect it.

The result will be a classic BSP with edges stored at nodes

There are two optimizations that can be done with this:
1. When all edges from a BSP node were clipped to the polygon
- this node can be safely removed from the BSP if either node->Front
or node->Back is NULL (the node that is not NULL replaces the
current node in the BSP and the current node is deleted). If that node
is a leaf - simply delete that leaf.
2. When the BSP edges are clipped to the BSPed polygon they may
get split quite a lot even if nothing is clipped away. You can keep a binary
tree with the split history of the edge and restore the unclipped parts from it.
This is quite beneficial in 3D where merging polygons can be tedious.

> 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.

In my explanation on doing CSG above I said that when the edge lies on
a node's hyperplane it should be stored in that node. This is partially
true except that before doing that you have to clip that edge to both
node->Front and node->Back. If you want to handle decals properly
this becomes quite complicated ( you have to be careful how you clip
the BSP segments to the polygon, etc )
 
> 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).

Calculate the planes for the original polygons and store them with
the polygon. When it is split - set the same plane for the splitted
polys. If you use EPSILON aware polygon splitting routine(see below)
you should not have such short segments.

> 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).

You should assume that a polygon/segment lies on a plane
if it's verts lie on less than some small (EPSILON = 0.001) distance
away from the plane. This hould not be a problem if your polygon
splitting routine is EPSILON aware.
Here is my one:

A few notes:
The CVertex class contains a fourth comonent called dist that stores the distance
of the point from the Plane. This is calculated in PlaneSide. So PlaneSplit can
be safely used only after PlaneSide was called for the polygon:

if( poly-->PlaneSide( plane )==SIDE_Intersect )
{
    CPolygon *frontPoly, *backPoly;
    poly->PlaneSplit( frontPoly, backPoly );
    .............
}

int CPolygon::PlaneSide( CPlane &P )
{
 vfloat d;
 bool vertexInFront=false, vertexBehind=false;
 for( int i=0; i<NumSides; i++ )
 {
  d = P.DistToVert( Verts[i] );
  if( d>EPSILON )
   vertexInFront=true;
  else
   if( d<-EPSILON )
    vertexBehind=true;
  Verts[i].dist = d;//will need it in PlanesSplit
 }
 if( vertexInFront )
 {
  if( vertexBehind )
   return SIDE_Intersect;
  else
   return SIDE_Front;
 }
 else
 {
  if( vertexBehind )
   return SIDE_Back;
  else
   return SIDE_OnPlane;
 }
}


void CPolygon::PlaneSplit( CPolygon *&FrontPoly, CPolygon *&BackPoly )
{
 int numFrontVerts=0, numBackVerts=0;
 vfloat d;
 vfloat prevd = Verts[NumSides-1].dist;
 for( int i=0; i<NumSides; i++ )
 {
  d = Verts[i].dist; //calculated in PlaneSide()
  if( myabs( d ) < EPSILON )
  {
   numBackVerts++;
   numFrontVerts++;
  }
  else
  {
   if( d < 0 )
   {
    if( prevd > EPSILON )
    {//intersection point
     numFrontVerts++;
     numBackVerts++;
    }
    numBackVerts++;
   }
   if( d > 0 )
   {
    if( prevd < -EPSILON )
    {//intersection point
     numFrontVerts++;
     numBackVerts++;
    }
    numFrontVerts++;
   }
  }
  prevd = d;
 }

 FrontPoly = new CPolygon( numFrontVerts, this );
 BackPoly = new CPolygon( numBackVerts, this );

 int backindex=0, frontindex=0;
 int previ = NumSides-1;
 prevd = Verts[previ].dist;//calculated in PlaneSide()
 for( i=0; i<NumSides; i++ )
 {
  d = Verts[i].dist;
  if( myabs( d ) < EPSILON )
  {
   FrontPoly->Verts[frontindex] = Verts[i];
   frontindex++;
   BackPoly->Verts[backindex] = Verts[i];
   backindex++;
  }
  else
  {
   if( d < 0 )
   {
    if( prevd > EPSILON )
    {//intersection point
     FrontPoly->Verts[frontindex].Interpolate( Verts[previ], Verts[i], prevd/(prevd-d) );
     BackPoly->Verts[backindex] = FrontPoly->Verts[frontindex];
     frontindex++;
     backindex++;
    }
    BackPoly->Verts[backindex] = Verts[i];
    backindex++;
   }
   if( d > 0 )
   {
    if( prevd < -EPSILON )
    {//intersection point
     FrontPoly->Verts[frontindex].Interpolate( Verts[previ], Verts[i], prevd/(prevd-d) );
     BackPoly->Verts[backindex] = FrontPoly->Verts[frontindex];
     frontindex++;
     backindex++;
    }
    FrontPoly->Verts[frontindex] = Verts[i];
    frontindex++;
   }
  }
  prevd = d;
  previ = i;
 }
}

> 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.

The above algho should take care of these cases.