minkowski-vs-ray collision

collision.cpp

//NOTE: rayStart should be identical to *pos at the beginning of the function
static void collide_with_volumes(Vec2 rayStart, Vec2 rayDir, Vec2 * pos, Vec2 * vel,
                                 List<LineSegment> lines, List<Circle> circles,
                                 List<Vec2> * normals, float tick, float bounce)
{
    //NOTE: We do a discrete collision response step before the continuous collision step
    //      to fix a bug where the player could push themselves out of bounds when walking into
    //      corners less than 90 degrees due to floating point imprecision.

    Vec2 push = {};
    float distanceEpsilon = 0.05f;
    float pushEpsilon = 0.002f;
    for (LineSegment line : lines) {
        //project the player position onto the line
        float segmentDelta = dot(rayStart - line.a, noz(line.b - line.a));
        //check whether the projected point is within the bounds of the segment
        if (segmentDelta >= 0 && segmentDelta <= len(line.b - line.a)) {
            Vec2 closest = line.a + segmentDelta * noz(line.b - line.a);
            float distanceFromLine = len(closest - rayStart);
            if (distanceFromLine < distanceEpsilon) {
                Vec2 tangent = noz(line.b - line.a);
                Vec2 normal = vec2(-tangent.y, tangent.x);
                push += pushEpsilon * normal;
            }
        }
    }

    for (Circle circle : circles) {
        float distanceFromCenter = len(rayStart - circle.p);
        float distanceFromRadius = fabsf(circle.r - distanceFromCenter);
        if (distanceFromRadius < distanceEpsilon) {
            Vec2 normal = noz(rayStart - circle.p);
            push += pushEpsilon * normal;
        }
    }
    rayStart += push;



    //keep resolving one (nearest/first) collision at a time until we either run out of collisions
    //or run out of iterations, whichever happens first, then update position and velocity
    float timeRemaining = 1; //0 = no distance, 1 = full distance of rayDir
    bool stillColliding = true; //if we have not resolved all collisions by the end of the loop
    for (int iter = 0; iter < 4; ++iter) {
        float tmin = 1; //0 = no distance, 1 = full distance of rayDir
        Vec2 normal = {}; //the normal of the surface we first collide with
        for (LineSegment line : lines) {
            Vec2 segmentStart = line.a, segmentDir = line.b - line.a;
            //NOTE: algorithm adapted from https://stackoverflow.com/a/565282/3064745
            float divisor = cross(rayDir, segmentDir);
            if (divisor > 0) {
                Vec2 diff = segmentStart - rayStart;
                float t0 = cross(diff, segmentDir);
                if (t0 >= 0 && t0 <= divisor) {
                    float u0 = cross(diff, rayDir);
                    if (u0 >= 0 && u0 <= divisor) {
                        float t = t0 / divisor;
                        if (t < tmin) {
                            tmin = t;
                            Vec2 tangent = noz(line.b - line.a);
                            normal = vec2(-tangent.y, tangent.x);
                        }
                    }
                }
            }
        }

        for (Circle circle : circles) {
            //check if circle is in general direction of ray
            //NOTE: this prevents intersecting with a circle from the inside
            //      so we won't get stuck bouncing around inside a circle
            Vec2 AC = circle.p - rayStart;
            if (dot(rayDir, AC) > 0.0f) {
                //project circle center onto ray
                Vec2 R = nor(rayDir);
                Vec2 P = rayStart + R * dot(R, AC);
                //calculate distance between C and P
                float dist2 = len2(P - circle.p);
                if (dist2 < circle.r * circle.r) {
                    //solve the circle equation y = sqrt(r^2 - x^2) at x = dist
                    float solve = sqrtf(circle.r * circle.r - dist2);
                    //move backward along the ray from P to find the nearest intersection point
                    Vec2 intersect = P - solve * R;

                    //test if the intersection point is within the bounds of the ray
                    float t = len(intersect - rayStart) / len(rayDir);
                    if (t < tmin) {
                        normal = noz(intersect - circle.p);
                        tmin = t;
                    }
                }
            }
        }

        //early exit if no collision
        if (tmin >= 1) {
            stillColliding = false;
            break;
        }

        //resolve collision
        float epsilon = 0.001f; //the amount by which we push the collision point along the normal
                                //after calculating it, to avoid floating point problems
        rayStart = rayStart + rayDir * tmin + normal * epsilon;

        //calculate exit vector (by reflecting the leftover movement vector)
        Vec2 incoming = rayDir * (1 - tmin); //<- the leftover movement vector
        //blend between incoming and reflected movement vectors based on bounciness
        //bounciness: -1 = preserve velocity, 0 = fully plastic, 1 = fully elastic
        //TODO: allow bounciness < 0?
        //TODO: do we even need the tangent, or can we change this to use the normal directly?
        Vec2 tangent = { normal.y, -normal.x };
        rayDir = incoming + (bounce + 1) * (dot(incoming, tangent) * tangent - incoming);

        timeRemaining *= 1 - tmin;

        //optionally store a list of normals of all the surfaces we collided with
        //this is used for, for example, tracking whether the player is on the ground in a platformer
        if (normals) {
            normals->add(normal);
        }
    }

    //store back results of collision logic
    *vel = rayDir / (tick * timeRemaining);
    if (stillColliding) {
        *pos = rayStart;
    } else {
        *pos = rayStart + rayDir;
    }
}