Re: [Algorithms] BSP-Primitive intersection testing

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

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