Re: [Algorithms] Broad-phase collision detection for dynamic objects

[Mark W. <Mwa...@to...>]

Stuart,
 
We're using a Dynamic Bounding Volume Tree (DBVT) similar to Bullet's
one. We're using this for graphics, physics and entities (3 different
trees) with great success.
I certainly recommend a pooled allocator of tree nodes if you go with
this scheme.
 
Cheers,
Mark
Torus Games


________________________________

	From: Stuart Golodetz [mailto:gda...@gx...] 
	Sent: Friday, 16 October 2009 2:28 AM
	To: Game Development Algorithms
	Subject: [Algorithms] Broad-phase collision detection for
dynamic objects
	
	
	Hi,
	
	Hope this is the right place to ask this. I'm considering a
broad-phase 
	collision detection scheme for the dynamic objects in my game
and was 
	wondering if I could have some thoughts please? (I'm a student
hobby 
	programmer right now and this isn't something I've tackled in
depth 
	before.) Basically I started out thinking about a hierarchical
grid-type 
	scheme (the sort you'd find in e.g. Christer Ericson's Real-Time

	Collision Detection book) but my understanding was that as
written it 
	works by looking only at the objects' positions at the point of 
	collision detection, and doesn't take account of their movements
over 
	the frame. (In other words, they're positioned in the hgrid in
the cells 
	where they end up after moving.)
	
	Since I'm using a *swept* version of XenoCollide/MPR 
	(www.xenocollide.com) for my narrow-phase collision detection,
this 
	seemed like an inappropriate approach for me to use for
broad-phase, 
	since it would cull a lot of potential collisions before they
got as far 
	as the narrow-phase detector (essentially, I'd be implementing a

	broad-phase algorithm which would erroneously generate a lot of
false 
	negatives - the narrow-phase detector might be able to detect
that a 
	bullet went through something, but it would never get the
chance).
	
	The alternative I'm considering is to adapt the scheme to take
into 
	account movement, essentially by doing a 3D Bresenham's
algorithm on the 
	hgrid. Normally, you might find an appropriate lowest level for
the 
	object based on object and grid sizes, and insert it in all the
levels 
	above and including that in the cells which it overlaps (this is
one of 
	the variations described in Ericson's book - I think due to
Mirtich). 
	What I'm thinking of doing is finding the appropriate lowest
level based 
	on the size of the moving object (i.e. taking into account both
its size 
	and its movement over the frame), doing the 3D Bresenham's on
this 
	lowest layer, then propagating the overlapped cells up to higher
layers 
	and inserting the object into the overlapped cells in each layer
as 
	before. The extent of the object isn't a problem - it's just
like 
	drawing a line with a 'fat' brush in a drawing package - so the
line 
	algorithm would only need to be run for the centre of each
object.
	
	Does this seem workable? I'm concerned that all the line drawing
might 
	be costly - though it's only one line per object - and I'm not
sure 
	about the trade-off between the cost of drawing the line on a
smaller 
	grid and the cost of potentially doing more narrow-phase
collision 
	detections if the line's drawn on a larger grid. Have people
done this 
	sort of thing before? (I'll keep Googling for it if so!) Also,
are there 
	any good alternatives people could recommend, please?
	
	Cheers,
	Stuart