### Re: Collision problems

Posted:

**25 Jun 2018, 12:39**I finally fixed the last major bug in my personal 3d toy's movement solver, so I'll write it out in pseudocode here:

The first change this kind of movement solver would see if put into OpenMW is that the stair code should always run when hitting any kind of slope, not just unwalkable ones. The other change is the note about where to put "move outside the world" stuff for animated world collision bodies.

Another problem is that the detection for getting stuck in acute pits ("else if dot_a and dot_b are both acute") isn't very good, so running out of iterations happens if you run into certain kinds of acute pits, but the correct logic for pit detection is pretty elaborate and I can't figure it out. This doesn't affect the correctness of the movement solver, just its speed.

At any rate, this is the general right kind of design for a movement solver: detecting acute seams/crevices and gliding along them, and detecting acute pits and cancelling movement in them.

Code: Select all

```
safety margin: value something like 0.01
note: 90 degree angles are considered "acute"
check_world:
function that returns true if the body is intersecting with the world at its current location.
the movement solver doesn't use this to rectify anything. "finding contact" will never refer to this.
find_contact:
function that finds the distance and contact collision with the world from a particular position along a particular motion vector and has correct internal edge rejection.
"finding contact" or similar will always refer to this.
note: the returned distance HAS THE SAFETY MARGIN SUBTRACTED FROM IT. uses of this function run something like distance = max(0, distance) afterwards.
does not collide with collision surfaces that are facing the wrong direction
returned distance is always 0 if the body is touching the world at its origin position, regardless of internal edge rejection or collision surface direction
collider_throw:
keeps track of "touching" collision surfaces, but resets between calls (i.e. they belong to the function, not the body)
loop:
breaks if too many iterations have been run (16), or the motion is (0,0,0), or we're out of time/distance to travel
find contact with the world along our motion vector from our current position
if it finds contact:
if the collision was with a perfectly vertical wall or a too-steep-to-climb slope:
try to find a way to "climb stairs" (the algorithm for this is very similar to what OpenMW currently does,
if we did not manage to climb any stairs:
throw away any "touching" triangles that we are not (almost) touching (from the origin position of this iteration)
add the current collision triangle to "touching"
move to the point of contact
move away from the collision surface in the direction of its normal, by up to "safety" distance, using find_contact so we don't enter any other geometry
// FIXME: this should be aware of crevices and pits, but this is enough to not get stuck in the world from floating point rounding problems
// This is the core of the movement solver and what most custom 3d movement solvers don't do correctly
if "touching" contains one triangle:
vector-reject momentum from the collision surface
else if "touching" contains two triangles:
if they're relatively acute: // (via dot product of normals)
project momentum along the cross product of the two triangles' normals
else:
set "touching" to only the "current" triangle
vector-reject momentum from the collision surface
else if "touching" contains three triangles:
the "touching" triangles are herein A, B, and C, where C is the "current" one
dot_a = dot(C.normal, A.normal)
dot_b = dot(C.normal, B.normal)
if dot_a and dot_b are both obtuse:
set "touching" to only the "current" triangle
vector-reject momentum from the collision surface
else if dot_a and dot_b are both acute:
set motion to (0,0,0)
break out of loop
else if dot_a is obtuse:
set "touching" to only B and C
project momentum along the cross product of B and C's normals
else if dot_b is obtuse:
set "touching" to only A and C
project momentum along the cross product of A and C's normals
else:
something is horribly wrong and this should be an impossible condition the current way the movement solver is constructed
update remaining distance/time based on distance/time traveled
else if it doesn't find contact:
move to the desired point as though moving through the air
break loop
character motion:
check if we're on the floor using find_contact with a downwards vector and seeing if there's a collision surface and if it's normal is walkable
update inertia
if you want to move outside of contact objects to avoid passing through non-static world geometry, do it here (mine doesn't because all nonbody solids are static)
if we're not on the floor:
apply half gravity
collider_throw from current point along inertial vector
check if we're on the floor now
if we were on the floor before and now we're not:
if mapping the character downwards onto the ground would put it on walkable ground, with a limit on the distance based on how far the character is traveling horizontally:
do it
if we're not on the floor:
apply half gravity
```

Another problem is that the detection for getting stuck in acute pits ("else if dot_a and dot_b are both acute") isn't very good, so running out of iterations happens if you run into certain kinds of acute pits, but the correct logic for pit detection is pretty elaborate and I can't figure it out. This doesn't affect the correctness of the movement solver, just its speed.

At any rate, this is the general right kind of design for a movement solver: detecting acute seams/crevices and gliding along them, and detecting acute pits and cancelling movement in them.