Spatial Hashing

Official forum for the Chipmunk2D Physics Library.
Post Reply
bronxbomber92
Posts: 8
Joined: Sat Dec 01, 2007 6:06 pm
Contact:

Spatial Hashing

Post by bronxbomber92 »

Hi,

I know Chipmunk uses a grid based spatial hashing broad-phase CD, and I was wondering what your (slembcke's) opinion on the spatial hashing technique presented here is - paper: http://www.eecs.ucf.edu/~hastings/papers/T-Collide.zip code: http://www.eecs.ucf.edu/~hastings/openg ... onDemo.zip ? To my knowledge it seems pretty close to the what you're doing. Do you think it'd be slower? What is the differences between this and yours?

I know this isn't exactly about Chipmunk, but Chipmunk is the only engine I know that uses a spatial hasing broad-phase, and I thought this could also provide some good discussion :)
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Spatial Hashing

Post by slembcke »

Minus the swept collision part, yes that is exactly what I'm doing.

The advantage of spatial hashing is that querying has a constant lower bound instead of a log(n) lower bound for sorting based and tree based broadphase. The downside is that it doesn't work as well when you have objects of wildly varying size as hashing a large object on a finely divided grid can be extremely expensive. For that reason I've started generalizing the spatial index code so that it will be possible to plug in a quadtree in the future.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
bronxbomber92
Posts: 8
Joined: Sat Dec 01, 2007 6:06 pm
Contact:

Re: Spatial Hashing

Post by bronxbomber92 »

Yes, the T-Collide paper states that the spatial hashing will decrease in performance when the object are larger than the cell sizes. Will you be using a conventional quadtree, or a loose quadtree?

Over the next few days (or weeks, pending on time) I'll be implementing this in 3D. I'll report back when I'm finished and post my results. I'd like to compare it to several forms of SAP broad-phase :)
electricutopia
Posts: 3
Joined: Sun Jun 28, 2009 7:17 am
Contact:

Re: Spatial Hashing

Post by electricutopia »

Hey, I'm going to write a spatial quadtree for chipmunk. Before I start, does anyone know if this has already been done (i.e. if I am wasting my time..)
electricutopia
Posts: 3
Joined: Sun Jun 28, 2009 7:17 am
Contact:

Re: Spatial Hashing

Post by electricutopia »

This is probably just me getting confused with the upside-down coordinate system, or something like that, but..

static inline int cpBBcontainsBB(const cpBB bb, const cpBB other)
{
return (bb.l < other.l && bb.r > other.r && bb.b < other.b && bb.t > other.t);
}

shouldn't this be:

static inline int cpBBcontainsBB(const cpBB bb, const cpBB other)
{
return (bb.l < other.l && bb.r > other.r && bb.t < other.t && bb.b > other.b);
}

all you have to say is "no, the way it is is correct". I will go back and stare at it some more, until it makes sense.. :)

cheers..
User avatar
Tam Toucan
Posts: 141
Joined: Tue Jun 23, 2009 4:26 pm
Contact:

Re: Spatial Hashing

Post by Tam Toucan »

no, the way it is is correct :)

If BB is 10x10 with bottom left corner at 0,0 then
BB.l = 0, BB.r = 10, BB.t=10, BB.b = 0
and other is 2x2 with bottom left corner at 2,2 then
other.l = 2, other.r = 4, other.t = 4, other.b = 2
So
0 < 2 and 10 > 4 and 0 < 2 and 10 > 4
So BB contains Other.
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Spatial Hashing

Post by slembcke »

Nope, it hasn't been done yet. I'd be interested to see how this turns out. I've been thinking I should implement hierarchical spatial hashes, as it can be built mostly on top of the spatial hash code I have now, but I haven't had time with the contracting work I've been doing. (Gotta pay the bills)
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
electricutopia
Posts: 3
Joined: Sun Jun 28, 2009 7:17 am
Contact:

Re: Spatial Hashing

Post by electricutopia »

Thanks Tam, I feel goofy. I'm new to an inverted Y axis (or I should say, a mathematically typical Y axis), I think this confused me a bit.

Slembcke, I'll give it a shot! Will let you know what happens.
Post Reply

Who is online

Users browsing this forum: No registered users and 15 guests