[ODE] collision detection optimalizations for humanoid

[Erin Catto]

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

-----Original Message-----
From: ode-bounces at q12.org [mailto:ode-bounces at q12.org] On Behalf Of Jon
Watte
Sent: Thursday, January 06, 2005 5:09 PM
To: Piotr Obrzut; ode at q12.org
Subject: RE: Re[2]: [ODE] collision detection optimalizations for humanoid


> well the problems starts when 2 human models are going to collide
> mutually. I need to know about every collided box, so the pesimistic
> complexity is O(n^2) (which gives me 1600 collision checkings when
> models have 40 box colliders) - i've tested that doing collision
> detection so many times is VERY expensive.


Make sure that each of the humanoids are in their own dHashSpace 
space. HashSpace<->HashSpace collision is reasonably efficient, if 
you tweak the parameters right, because you won't ever get the O(n2) 
tests like you would if they're all in a single space, or each in 
a dSimpleSpace.

Cheers,

			/ h+


_______________________________________________
ODE mailing list
ODE at q12.org
http://q12.org/mailman/listinfo/ode