RE: [Algorithms] BSP-Primitive intersection testing

[Feltman, H. <Fe...@se...>]

You're right, the BSP itself can't be used for AABB using the
plane expansion method because during expansion, the
planes would intersect and cause all kinds of problems.

Quake1 used pre-expanded "hulls"; take all the brushes,
expand the planes according to the current AABBox size,
add axial planes which aren't in the brush already (you refer
to these as "cap-planes"?) , and re-compile a BSP. Quake1
only had 3 hull sizes: one for the players bbox, one for large
monsters, and the BSP itself used for bullets (lines).
To trace an AABB through this new world only requires tracing a
line so you can see how fast this method really is.

Quake2 stores the brushes themselves for real-time expansion
(any AABB size is accommodated).

The current project I'm working on uses realtime-expanded-
rotated-convex-brush-collision-detection, It's definitely a very
simple and fast method.

-Hamilton

Hamilton Feltman
SEGA[WOW/ARCADE]
www.sega.com/alienfront

> -----Original Message-----
> From:	Charles Bloom [SMTP:cb...@cb...]
> Sent:	Friday, August 18, 2000 3:44 PM
> To:	gda...@li...
> Subject:	[Algorithms] BSP-Primitive intersection testing
> 
> 
> 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