RE: [Algorithms] BSP-Primitive intersection testing

[Jay S. <Ja...@va...>]

I'm not sure what errors you are talking about.  If you apply the separating
axis theorem, you can compute all of the necessary separating axes to
determine intersection.  As long as you "bevel" using the entire set of
planes, this will be as correct as the separating axis theorem.  Unless
there is something I misunderstand about this (I'd love to learn something
new), it's possible to exactly detect intersection between a BSP and an AABB
using this method.  Also, as long as all of your BSP doesn't rotate, and the
world axes are constant, it should be possible to precalcuate all of the
separating planes.  Obviously for OBBs or rotated BSPs, you'll have to
calculate the separating planes at runtime as they are dependent on the
coordinate systems involved.

NOTE: I haven't read the articles mentioned below, so when I say "this
method" I'm talking about the plane shifting method in general.  Also, this
doesn't apply to spheres because the manifold of collision (is there a term
for this?) does not have planar surfaces.

Charles, I don't understand your description of the "cap planes" problem
below.  To the best of my understanding, these "cap planes" or "bevels" must
coincide exactly with the planes given by the separating axis theorem -
since they are the surface of the manifold of collision.  After all, a
closed BSP tree is equivalent to a collection of convex polyhedra (each
solid leaf is one of these), and you can certainly use the separating axis
theorem to collide AABBs with those polyhedra treated as individual objects,
so why is this different?

Jay

> -----Original Message-----
> From: Charles Bloom [mailto:cb...@cb...]
> Sent: Friday, August 18, 2000 4:30 PM
> To: gda...@li...
> Subject: Re: [Algorithms] BSP-Primitive intersection testing
> 
> 
> 
> That's a good writeup of the approximate method which I describe,
> where the error can be limited by bevelling corners, but never
> eliminated.
> 
> For historical accuracy, I believe that method was known to Naylor
> and all the old-school BSP gurus.  I heard a story that Carmack came
> up with the plane-shifting trick for Quake and was delighted with
> himself, and then one of the old computer graphics guys pointed
> out that they'd been doing it for years...
> 
> At 04:04 PM 8/18/2000 -0700, you wrote:
> >This is a paper that supposedly deals with that issue (by 
> plane shifting;
> >you probably have seen it already), but I haven't read it thoroughly:
> >
> >http://www.cs.ualberta.ca/~melax/bsp/
> >
> >In a way, I'm dealing with the same problem, because I want 
> to do a full
> >simulation of rigid bodies in a bsp tree based world.  I 
> don't want to
> >pass every point down the bsp tree, but a spherical bounding 
> volume might
> >cull enough rigid bodies to make it okay.
> >
> >Will
> >
> >----
> >Will Portnoy
> >http://www.cs.washington.edu/homes/will
> >
> >On Fri, 18 Aug 2000, Charles Bloom wrote:
> >
> >> 
> >> 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
> >>