Re: [Algorithms] BSP-Primitive intersection testing

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

You can just test the individual polygons of the mesh ( a low
LOD representation of your model ) against the BSP tree.
It's quite fast and very simple to do.

And there's fast and easy (although not quite trivial) way to find
the intersection shape and the normals at each vertex in that
shape of the 2 colliding objects. Tell me if you need more info
on this.

You can speed this algho by first doing a quick test just with the
vertices of the mesh.

Here's the code:

bool CBSPNode::PolygonColiides( CPolygon &P )
{
 CBSPNode *Node=this;
 while( 1 )
 {
  int side = P.PlaneSide( Node->SplitPlane );
  switch( side )
  {
  case SIDE_Front:
   {
    if( Node->Front==NULL )
     retrun false;//no collision
    Node=Node->Front;
   }
  case SIDE_Behind:
   {
    if( Node->Back==NULL )
     retrun true;//collision
    Node=Node->Back;
   }
  case SIDE_Intersect:
   {
    CPolygon FrontP, BackP;
    P.Split( Node->SplitPlane, FrontP, BackP );

    if( Node->Front!=NULL && Node->Front->PolygonCollides( FrontP ) )
      return true;//collision

    if( Node->Back==NULL || Node->Back->PolygonCollides( BackP ) )
      return true;//collision

    return false;//no collision
   }
  }
 }
}


> 
> Is there a fast and correct way to ask a BSP if it
> intersects with a primitive (AABB or sphere, for example) ?
> 
> The context of this question is the traditional hack
> which all the BSP-based games used.  They use a collision
> detection scheme where they take a primitive, and send it
> down the tree as if it were a point, but shift the BSP planes
> by the radius of the primitive in the direction of the
> plane's normal.  The problem with this test is that it just
> doesn't work near corners where planes intersect.  Many
> people are under the false impression that if you put
> extra "cap" planes on your leaves it will fix the problem,
> and while it certainly greatly decreases the error (because
> the error is roughly proportional to the angle difference
> of the joint, so adding more planes at a joint smooths out
> the error), the problem does remain.
> 
> Of course, you can test an AABB against a BSP exactly by sending
> the polygons of the AABB down the bsp tree and doing the full
> polygon clipping shish-poo-bah, but that seems a rather expensive
> way to an AABB-in-region test.
> 
> Using "cap planes" the error can be controlled, and you can
> make sure that the error is conservative (returns more
> intersections) so perhaps that's the best solution - be approximate.
> 
> --------------------------------------
> Charles Bloom           www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list