Polygon-Circle Collision Algorithm not working

Question

EDIT: Updated code and video

I've been working on one of the last pieces of my collision detection system for my game, a polygon-circle collision method. I'm almost there with it, but there's a few minor issues that seem to pop up with it. I'll explain the few things I'm seeing, but it's probably easier just to watch the short video I have below:

https://1drv.ms/v/s!AjUDP95TjAMqje8AVA0LpPfeszVYoA

There are the three things I'm seeing:

• Little bit of bumpiness when going down a slope vs up (I'm guessing I just need to smooth out the movement adjustment a little bit
• When going around certain corners, the adjustment distance gets computed incorrectly, which results in either:
  • A small bit of excess distance
  • A large amount of excess distance

Below are the major components of my code, happy to update the post and add any other relevant code chunks that made be needed. Any assistance with this would be appreciated. Thanks!

Physics World Update Method:

IEnumerable<PhysicsFixtureBase> results = this.physicsTree.Query(fixture);
foreach (PhysicsFixtureBase otherFixture in results)
{
    Vector3 adjustment = Vector3.Zero;
    if (fixture.Body != otherFixture.Body && fixture.Intersects(otherFixture, out adjustment))
    {
        this.OnContact(fixture, otherFixture);
        body.SetVelocity(Vector3.Zero);
        body.MovePosition3D(adjustment);
    }
}

Main Intersection Method:

public static bool Intersects(PhysicsCircleFixture circle, PhysicsPolygonFixture otherPolygon, out Vector3 adjustment)
{
    bool result = PhysicsCollisionHandler.Intersects(otherPolygon, circle, out adjustment);
    adjustment *= -1;
    return result;
}

public static bool Intersects(PhysicsPolygonFixture polygon, PhysicsCircleFixture otherCircle, out Vector3 adjustment)
{
    adjustment = Vector3.Zero;

    Vector2 circleCenter = otherCircle.GetPosition2D();
    float circleRadius = otherCircle.GetSize2D().X;

    Vector2 closestPoint = Vector2.Zero;
    float closestDistance = float.MaxValue;

    foreach (Vector2 point in polygon.Points)
    {
        float distance = circleCenter.Distance(point);
        if (distance < closestDistance)
        {
            closestDistance = distance;
            closestPoint = point;
        }
    }

    Vector2 previousPoint = polygon.Points[polygon.Points.Count - 1];
    foreach (Vector2 currentPoint in polygon.Points)
    {
        Vector2 edge = currentPoint - previousPoint;
        float interp = edge.DotProduct(circleCenter - previousPoint) / edge.DotProduct(edge);
        if (0.0f < interp && interp < 1.0f)
        {
            Vector2 point = previousPoint + edge * interp;
            float distance = circleCenter.Distance(point);

            if (distance < closestDistance)
            {
                closestDistance = distance;
                closestPoint = point;
            }
        }
        previousPoint = currentPoint;
    }

    if (closestDistance < circleRadius)
    {
        float penetrationDistance = circleRadius - closestDistance;
        Vector2 normalizedVector = (closestPoint - circleCenter) / closestDistance;
        adjustment = (normalizedVector * penetrationDistance).To3DVector3();
    }

    return (adjustment != Vector3.Zero);
}

Helper Code:

public static Vector2 Normal(this Vector2 vector) { return new Vector2(-vector.Y, vector.X); }

public class Range
{
    public float Min { get; set; }

    public float Max { get; set; }

    public Range(float min, float max)
    {
        this.Min = min;
        this.Max = max;
    }

    public float Length() { return this.Max - this.Min; }

    public Range Intersects(Range other)
    {
        Range longestDistance = new Range(Math.Min(this.Min, other.Min), Math.Max(this.Max, other.Max));
        if (longestDistance.Length() < (this.Length() + other.Length()))
        {
            return new Range(Math.Max(this.Min, other.Min), Math.Min(this.Max, other.Max));
        }
        return null;
    }
}

public Range PhysicsPolygonFixture.ProjectOnAxis(Vector2 axis)
{
    Range range = new Range(float.MaxValue, float.MinValue);
    foreach (Vector2 point in this.Points)
    {
        float projection = point.DotProduct(axis);
        if (projection < range.Min)
        {
            range.Min = projection;
        }
        if (projection > range.Max)
        {
            range.Max = projection;
        }
    }
    return range;
}

public Range PhysicsCircleFixture.ProjectOnAxis(Vector2 axis)
{
    float circleCenterProjection = this.GetPosition2D().DotProduct(axis);
    float circleRadius = this.GetSize2D().X;
    return new Range(circleCenterProjection - circleRadius, circleCenterProjection + circleRadius);
}

Answer 1

The code that checks for edge collisions is definitely causing the problems you're seeing. Since it's also a little more complex than necessary, I think the right solution is to rewrite it completely.

Remove the entire foreach (Vector2 edge in polygon.Edges) loop, and add the following code above the line if (closestDistance < circleRadius):

Vector2 pointPrev = polygon.Points[polygon.Points.Length - 1];
foreach (Vector2 pointCur in polygon.Points)
{
    Vector2 edge = pointCur - pointPrev;

    float interp = edge.DotProduct(circleCenter - pointPrev) / edge.DotProduct(edge);

    if (interp > 0.0f && interp < 1.0f)
    {
        Vector2 point = pointPrev + edge * interp;
        float distance = circleCenter.Distance(point);

        if (distance < closestDistance) 
        {
            closestDistance = distance;
            closestPoint = point;
        }
    }

    pointPrev = pointCur;
}

Note 1

I tried to use your function and type names. The only thing I didn't have a reference for was whether polygon.Points is an array or a list.

Note 2

The only tricky bit there is the calculation of interp; it combines two calculations into one to avoid a square root. It normalizes the edge vector and also divides the projection of the circle's center onto the edge by the length of the edge vector.