RE: [Algorithms] BSP-Primitive intersection testing

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

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

Yeah, I just read his article.  That's definitely what Melax suggests.
Quake 2 definitely uses the same planes suggested by the separating axis
theorem.

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

The extra planes are the planes of the bounding box (unless the particular
leaf already has them) and the planes formed by the cross product of the
edges of each convex solid space and the edges of the AABB.  So the only
planes that bevel the verts are the axial aligned planes iff the solid
doesn't include those.  The other planes all bevel the edges (as the solid
is expanded).  I find it easier to visualize if I think of the BSP as a set
of discrete solid convex polyhedra.

If you computed the constructive planar solid of all of these planes (pushed
out for a particular AABB), it would be equivalent to the surface traced out
by the center of the AABB as you slide the AABB over the surface of the
convex solid - keeping the two in contact at all times.

> 
> 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 implicitly from the BSP, but I'm 
> not enough
> of a BSP whiz to see how to do it quickly.

The problem here is that you need the faces & edges of the convex BSP
solids.  The BSP itself implies these edges, but you'd have to go through a
process like CSG to compute them.  I've done quite a bit of work with BSPs
and I can't think of a reasonable way to get the information from a general
BSP (other than CSG).  Then you'd have to cross those edges with the edges
of the OBB to generate the separating plane normals.

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

This sounds correct, although intuitively it seems likely that you could use
information from the BSP about which faces/edges of the solid touch empty
space to optimize away some of the tests, and beat the more general case.


Jay