[ODE] collision detection optimalizations for humanoid

Jon Watte hplus-ode at mindcontrol.org
Fri Jan 7 09:19:19 MST 2005


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





More information about the ODE mailing list