RE: [Algorithms] BSP-Primitive intersection testing

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

Hi Jay,

Hmm, you are of course correct that you can use separating-axis,
I'd never thought of that way; I think most of the people who
bevel their BSP's just put the planes in heuristically (that's
what Stan Melax describes, so far as I can tell).

Obviously, you don't want to treat your whole BSP as a bunch of
polyhedra and generate separating axes for all those polydra
against the axial planes.  Off the top of my head, it seems that
the correct local solution would be to bevel each vert by creating
new planes on the vertex, with many normals : three from the AABB,
and 3*n more from the axes of the AABB crossed with the normals
of the planes that define that vertex in the BSP.  I think you only
have to add planes which don't intersect the convex volume of the
leaf you are adding them to.

For OBB's I guess you could store the information necessary to compute
the extra planes in each leaf.  Then, after you descend the tree to
the leaf, the extra planes implicitly exist in the tree at that position,
and are created based on the orientation of the OBB.  The information
would need would be the vertices of the convex polyhedron which is the
leaf, and the planes coincident with those vertices (right?).  You could
probably get that information implictly from the BSP, but I'm not enough
of a BSP whiz to see how to do it quickly.

That is essentially equivalent to just sending the OBB to the leaf, and
then doing the normal OBB-polyhedron collision test, right?  The only
difference is that you know you don't need to check the separating axes
defined by the normals of the polyhedra, because those have already been
done by walking down the BSP.

At 05:03 PM 8/18/2000 -0700, you wrote:
>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.
>
>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?
>

--------------------------------------
Charles Bloom           www.cbloom.com