Re: [Algorithms] BSP-Primitive intersection testing

[Will P. <wi...@cs...>]

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
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>