Collision problems

Everything about development and the OpenMW source code.
User avatar
Posts: 319
Joined: 09 May 2015, 13:07

Re: Collision problems

Post by wareya » 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:

Code: Select all

safety margin: value something like 0.01
note: 90 degree angles are considered "acute"

    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.

    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

    keeps track of "touching" collision surfaces, but resets between calls (i.e. they belong to the function, not the body)
        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
                        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
                        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
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.
paying attention to #1751 #2473 #3609 #3862/#3929 #3807 #4297 #4623

User avatar
Posts: 319
Joined: 09 May 2015, 13:07

Re: Collision problems

Post by wareya » 03 Jul 2018, 17:05

There's a bug in the stair solving code that's actually a workaround for a problem where the capsule collision shape renders some steps that you're supposed to be able to walk up into steep slopes too wide to step over.

Cylinders are the only rotationally invariant primitive that Bullet provides that doesn't have that problem, but Bullet gives really bad collision normals with cylinders.

Also, with cylinders and a less buggy movement solver, the problem with the stairs in vivec is made obvious. The actual problem with the collision of the stairs in vivec is that the part at the bottom is too steep to be walkable. Vanilla handles it both of two ways:

- Walking into the short part that's too steep (more on that in a sec)
- Not registering that you're on something to steep to stand on until a fraction of a second after you've been standing on it

You can see the first point in vanilla with the beds in the ald'ruhn guild of mages. Walk up to their side, jump, glitch out, slide back down, end up further away from the bed than you walked into it. (Their sides are steep slopes)

The workaround that fixes capsules stepping up high-but-should-be-walkable steps also fixes the vivec thing, but it causes a lot of other problems, like skipping fast sideways when walking forwards tangentially into certain geometry. It has to go. sMinStep btw.

The right thing to do is to use a shape with flat tapers instead of a cylinder, but bullet doesn't have one, it would have to be a triangle mesh ¯\_(ツ)_/¯

Side note, Vanilla only rejects you from actors if you're inside of them, openmw does it even if you're standing on top of them. It also only happens in vanilla if you're aerial. In vanilla you can jump into the top half of their bodies for some reason, that's when you get rejected. Also, in vanilla, actors collide like AABBs with each other until they get too close, then they act like cylinders with a radius of the (half) distance between them. This is annoying because scripts (mods) can place you inside other actors.
paying attention to #1751 #2473 #3609 #3862/#3929 #3807 #4297 #4623

User avatar
Posts: 319
Joined: 09 May 2015, 13:07

Re: Collision problems

Post by wareya » 04 Jul 2018, 17:09

The actor-actor collision thing could be fixed by making overlapping actors not collide, and hacking the tracing function so that, when tracing towards an actor you're overlapping, it gives a normal pointing (on a flat horizontal plane) towards the moving actor from the actor that got traced into, and a distance of 0. Maybe.

Also the sMinStep hack could still be usable, it just has to only run if stairstepping is the very first iteration of the movement solving loop.
paying attention to #1751 #2473 #3609 #3862/#3929 #3807 #4297 #4623

User avatar
Posts: 319
Joined: 09 May 2015, 13:07

Re: Collision problems

Post by wareya » 07 Jul 2018, 03:53

I opened a new pull request:

It makes a lot of changes, so I'd like to get direct feedback.
paying attention to #1751 #2473 #3609 #3862/#3929 #3807 #4297 #4623

Post Reply