[ODE] Pushing through collisions

[Konstantin Voloshin]

Hello

I have a working/tested piece of code which detects sliding direction given
the desired direction and a bunch of normals to contacted surfaces.
It:
    - takes O(n^3) time and O(1) storage, 'n' is number of normals
    - gives "correct" result in regard to precision
    - code is about 1 screen long

The idea:
1. Test desired direction vs. each surface.
    If no contradiction is found, return original direction.
    / O(n)
2. Project desired direction onto each normal-surface.
    Test projected direction vs. each other surface.
    If no contradiction is found, return projected direction.
    / O(n^2)
3. Intersect each pair of surfaces (gives us a line :)
    Project desired direction onto that line.
    Test projected direction vs. each other surface.
    If no contradiction is found, return projected direction
    / O(n^3)
4. Return zero

However, I don't understand what is Jon's idea about building a
3 vector basis. Is it better than the way I described above?

Konstantin


----- Original Message ----- 
From: "Jon Watte" <hplus-ode at mindcontrol.org>
To: "Colin Bonstead" <colin at cyan.com>; "ode" <ODE at q12.org>
Sent: Thursday, April 29, 2004 6:21 AM
Subject: RE: [ODE] Pushing through collisions


.....

> Anyway, what I'm trying right now is limiting the velocities I direct 
> into static, unclimbable objects.  Each frame I take all the collision 
> normals from unclimbable static geometry and add them together, then 
> normalize them.  Then I get the vector in between that one, and the 
> normalized velocity vector for the avatar.  I use that resulting vector, 

I don't think that's quite correct. You can imagine cases where 
the player gets wedged badly enough that he's between opposing 
faces. Adding perfectly opposing face normals together just gives 
you zero. If he's between three faces, no matter what the normal 
you end up with, it's going to point into one of the faces.

What I'm planning on testing is whether there is any direction 
you can move in without moving counter to any face normal. To do 
this, you just need three vectors to build a basis (and maybe a 
bit per basis vector to know whether you have also seen a face 
normal opposing the basis vector).

An alternate is to remove any component that will move into another 
vector from any normal vector that you consider, and if there's 
anything left at the end, that's a direction you can move in. Note 
that just iterating over all the vectors, removing the dot product 
projected amount, is not enough, as doing that will move the vector 
WRT other vectors you've already visited -- going down this path, 
you end up with either an LCP solver just for collision resolution, 
or the basis-building approach above.

.....