[ODE] collision detection optimalizations for humanoid

[Erin Catto]

I see your point; I checked and ODE does compute bounding boxes for each
HashSpace. This would quickly cull the two humanoids if they are not
touching. Unfortunately, once the two HashSpace boxes overlap, the code
descends into an O(n^2) test. I think that overall this would be a loss
compared to using a single HashSpace, but I could be wrong because I have
not profiled the HashSpace (i.e. it might be slow).

My main experience with the n-body problem is with my own sweep-and-prune
code. Others have said, and I agree, that SAP can be much faster than
hashing. There are many tricks to getting an efficient SAP. Gino van den
Bergen's book is a good place to start.

Erin

-----Original Message-----
From: Jon Watte [mailto:hplus-ode at mindcontrol.org] 
Sent: Friday, January 07, 2005 9:19 AM
To: Erin Catto; 'Piotr Obrzut'; ode at q12.org
Subject: RE: Re[2]: [ODE] collision detection optimalizations for humanoid


Hmm, I thought the HashSpace actually did grid:grid overlap tests 
before descending to the objects, and thus is actually significantly 
better than N*M for all but degenerate cases (in which case any 
space would have the same problem). I could be remembering wrong, of 
course, but then, what's the point of HashSpace in the first place?

Using two hash spaces allows you to early-cull skeleton-to-skeleton 
intersections entirely, although this win might not be big (depending 
on your set-up).

I wasn't aware that we have an official sweep-and-prune space now. 
I can't find it in the check-out I have -- where is it?

Cheers,

			/ h+


-----Original Message-----
From: Erin Catto [mailto:erincatto at sbcglobal.net]
Sent: Thursday, January 06, 2005 11:25 PM
To: 'Jon Watte'; 'Piotr Obrzut'; ode at q12.org
Subject: RE: Re[2]: [ODE] collision detection optimalizations for
humanoid


I looked at the current implementation of collide2 for HashSpace and it's
O(n^2). Also, I don't understand how using two hash spaces could be more
efficient than having everything in one hash space, or better yet, in a
sweep-and-prune structure.

With temporal and spatial coherence, an efficient broad phase system should
record box overlaps with a cost proportional to the number of moving boxes.

Erin