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

------------------------------------------------------------------------------
Come build with us! The BlackBerry(R) Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and stay 
ahead of the curve. Join us from November 9 - 12, 2009. Register now!
http://p.sf.net/sfu/devconference

_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list