[ODE] Hash Collision space in ODE!

[Anselm Hook]

On Tue, 2 Jul 2002, Nguyen Binh wrote:

> Hi ,
>
>    I had tried to read about the hash collsion space of ODE but
>    couldn't figure out what it is. Can anyone shed a light for me :
>    where is the document or some ideas about that?... I'm coding my
>    inhouse physics engine, I had implemented simple space but I'd
>    like to try a hash space like ODE.
>
>    Thanks very much,
>    Nguyen Binh
>    Software Engineer
>    Glass Egg Digital Media


Given a spatial region containing a collection of objects one needs a
strategy to quickly resolve which objects are potentially collidant. The
problem is usually decomposed into two parts; far-field collision
determination and near-field collision determination.  Far-field
strategies attempt to use inter-frame coherence to quickly resolve which
objects are potentially incident but to not actually resolve the fine
grained details of their collision.

Here we are interested in the far field strategy.

As a simpler example (not hash spaces) one far field strategy is to keep 3
sorted arrays, one for each of the x y and z axes.  Consider the problem
in one dimension only; objects get sorted into this array based on their
minimum and maximum extent in that axis.  Determining potential collisions
now is trivial, if in a sorted list of extents, an object has some other
objects extent in between its start and end extent, then that other object
is potentially incident.  When bringing the problem back up to 3d, one has
to make sure that the same objects are potentially incident in all 3
extents.

As you probably know, hashtables in general are a nice strategy for both
storing unevenly distributed inputs in a space of defined size, and for
fairly quickly search for and finding inputs once stored.  (I like to
think of hashtables as a kind of lens acting much in the way an optical
lens can compress sunlight).  If you're wondering what it is - as opposed
to how to use it - then the basic answer is that 1) it takes the extent of
each object in each of its dimensions 2) turns that into a hashkey, and 3)
uses that to check for hashkey space collisions against other objects.

In other words, it is exactly the kind of intuitive strategy that you or I
might invent when faced with a problem of needing to quickly detect
collisions; one more or less draws the "shadows" of the objects to a
coarser resolution memory and looks for collisions.

[ One neat thing is that it's a multidimensional hash; so big objects only
go into big cells, and smaller objects go into finer grained cells. ]

Here's a paper I dug up just to refresh myself on this issue - it seems
more or less on track with what Russ has in space.c.

http://www.cs.wisc.edu/~schenney/courses/cs638-f2001/lectures/cs638-23.ppt

-a