自研2D物理引擎EPA算法计算接触法线时陷入无限循环求助

Hey there! Let's dig into your EPA infinite loop issue—this is a super common pitfall when rolling your own GJK/EPA implementation, so let's break down the likely culprits and fix them step by step.

Key Issues Causing the Infinite Loop #

Let's go through the code to spot the main problems:

1. Way Too High Tolerance Value

Your TOLERENCE = 2 is way too large for EPA. The algorithm relies on getting extremely close to the origin of the Minkowski difference (we're talking fractions of a unit, not whole numbers). A tolerance of 2 means you'll never reliably hit the termination condition, leading to endless cycles of adding vertices.

2. Incorrect Closest Edge Normal & Distance Calculation

In findClosestEdge, you're using absolute values for distance and possibly flipping the normal direction incorrectly. EPA needs the signed distance from the origin to the edge, and the normal must point directly toward the origin to ensure we're pulling support points closer to the collision contact.

3. No Duplicate Vertex Check

You're inserting new support points without verifying if they're already (almost) in the vertex list. This leads to redundant vertices being added over and over, keeping the loop running indefinitely.

Fixes to Apply #

Let's modify your code to address each issue:

1. Reduce the Tolerance

First, crank down the tolerance to a reasonable value for 2D physics:

private double TOLERENCE = 0.01; // Adjust based on your world scale, 0.01-0.001 works for most cases

2. Fix Closest Edge Calculation

Rewrite findClosestEdge to compute correct normals and signed distances:

private Edge findClosestEdge(List<Vector2> simplex) {
    Console.WriteLine("Finding closest edge");
    Edge closest = new Edge();
    closest.distance = Double.PositiveInfinity;
    
    for (int i = 0; i < simplex.Count; i++) {
        Console.WriteLine("i = " + i);
        int j = i + 1 == simplex.Count ? 0 : i + 1;
        Vector2 a = simplex[i];
        Vector2 b = simplex[j];
        Vector2 edge = b - a;
        
        // Calculate perpendicular vector to the edge
        Vector2 perp = new Vector2(-edge.y, edge.x).normalized();
        
        // Flip normal to point TOWARD the origin
        if (perp.dot(-a) < 0) {
            perp = -perp;
        }
        
        // Signed distance from origin to the edge (no absolute value!)
        double d = a.dot(perp);
        
        Console.WriteLine("distance from origin to edge = " + d);
        // Track the edge closest to the origin (smallest absolute distance)
        if (Math.Abs(d) < Math.Abs(closest.distance)) {
            closest.distance = d;
            closest.normal = perp;
            closest.index = j;
        }
    }
    Console.WriteLine("returing closest edge " + closest.index + " distance = " + closest.distance);
    return closest;
}

3. Add Duplicate Vertex Check & Refine EPA Termination

Update findContactDetails to stop if we're adding a redundant vertex, and tighten the termination logic:

private void findContactDetails() {
    while (true) {
        Edge closestEdge = findClosestEdge(vertices);
        Vector2 support = shape1.getSupportPoint(closestEdge.normal) - shape2.getSupportPoint(-closestEdge.normal);
        double distance = support.dot(closestEdge.normal);
        
        // Check if we're close enough OR if we're adding a duplicate vertex
        bool isCloseEnough = Math.Abs(distance - closestEdge.distance) < TOLERENCE;
        bool isDuplicate = false;
        foreach (var v in vertices) {
            if ((v - support).getMagnitude() < TOLERENCE) {
                isDuplicate = true;
                break;
            }
        }
        
        Console.WriteLine("difference between the two = " + (Math.Abs(distance - closestEdge.distance)) + " and it's " + isCloseEnough);
        if (isCloseEnough || isDuplicate) {
            Console.WriteLine("Contact details found");
            // Ensure normal points from shape2 to shape1 (adjust sign if needed for your physics)
            contactNormal = closestEdge.normal;
            penetrationDepth = Math.Abs(distance); // Penetration depth is always positive
            break;
        }
        
        Console.WriteLine("That was not the closest edge. adding the support to the vertices at index " + closestEdge.index);
        vertices.Insert(closestEdge.index, support);
        Console.WriteLine("The number of vertices now = " + vertices.Count);
        for (int i = 0; i < vertices.Count; i++) {
            Form1.dots.Add(vertices[i]);
        }
    }
}

4. Guard Against Zero Vectors in Perpendicular Calculation

Add a safety check in getPerpendicularUnitVectorTowards to avoid division by zero:

public Vector2 getPerpendicularUnitVectorTowards(Vector2 direction) {
    double mag = getMagnitude();
    if (mag < 0.0001) {
        return new Vector2(0, 0); // Avoid division by zero for near-zero vectors
    }
    Vector2 perp = new Vector2(-y, x) * (1 / mag);
    Console.WriteLine(perp);
    if (perp.dot(direction) < 0) {
        perp = -perp;
    }
    return perp;
}

Why These Fixes Work #

• The reduced tolerance ensures EPA stops when we're close enough to the true contact point.
• Correct normals and signed distances guarantee we're pulling support points toward the origin, not away from it.
• The duplicate check prevents adding redundant vertices that would keep the loop running forever.

Give these changes a shot—they should resolve the infinite loop and get your EPA working reliably!

内容的提问来源于stack exchange，提问作者Oshanath Rajawasam