Polygon vs polygon contact points madness

Started by
10 comments, last by Randy Gaul 9 years, 9 months ago

Its not working, i implemented it now in java and the contact points was generated like it was in my sample application from my last post.

BUT, this was all bullshit - nothing had work, boxes was falling through line segments, boxes was overlapping - the contact points was absolutely wrong.

So then i analyzed box2d lite a bit and the contact points generated there are completely different from my approach - now i am back to at the very start :-(

I searched a lot for a different approaches and found this: http://www.randygaul.net/2013/07/16/separating-axis-test-and-support-points-in-2d/

Seems to be very promising and of course i implemented the support point distance approach, because these was easier than projecting every vertex to the normal - and the sat-test itself works perfectly. But in some cases the used reference edge is on the back, not in the front - which results in support points which are on the back from the other as well - which are wrong.

I have 2 cases, one which works:

satsupport_correct.png

and one which are wrong:

satsupport_wrong.png

The red point are the support point on the incident body and the blue line with the numbers are the reference face.

As you can see, it should be just inverted, the reference face must be on the opposite side and the support point will be behind that face.

My code is brutally simple (There must be something missing!):


function findSupportPoint(body, normal) {
    var best = normal.dot(body.vertices[0]);
    var maxIndex = 0;
    for (var i = 1; i < body.vertices.length; i++) {
        var proj = normal.dot(body.vertices[i]);
        if (proj > best) {
            best = proj;
            maxIndex = i;
        }
    }
    return maxIndex;
}

function findLeastSeparation(bodyA, bodyB, relPos, result){
    var edgesA = [];

    // Get all the edges from bodyA - sometimes this edges are based on the closest point from the other bodies position
    addSATEdges(edgesA, bodyA, bodyB);

    // Loop through all edges of bodyA
    for (var i = 0; i < edgesA.length; i++) {
        var edge = edgesA[i];

        // Clone normal
        var n = new Vec2().setFrom(edge.eNormal);

        // Get point on edge (plane) with respect of the relative position of both bodies
        var p = new Vec2().setFrom(edge.v0).add(relPos);

        // Find support point for body B (Farthest vertex along negative normal)
        var supportPoint = bodyB.vertices[findSupportPoint(bodyB, new Vec2().setFrom(n).invert())];

        // Get distance from point to plane = d dot (p1 - p2)
        var d = n.dot(new Vec2().setFrom(supportPoint).sub(p));

        // Distance is positive - we have a separation
        if (d > 0) {
            return false;
        }

        // Record greatest negative distance (Least penetration)
        if (d > result.overlap) {
            result.overlap = d;
            result.referenceBody = bodyA;
            result.incidentBody = bodyB;
            result.referenceEdge = edge;
            result.normal.setFrom(n);
            result.support.setFrom(supportPoint);
        }
    }
    return true;
}

function supportSAT(body1, body2, result) {
    // Initialize result
    result.referenceBody = null;
    result.incidentBody = null;
    result.referenceEdge = null;
    result.overlap = Number.NEGATIVE_INFINITY;
    result.normal.zero();
    result.support.zero();

    // Get relative position
    var relPos = new Vec2().setFrom(body1.pos).sub(body2.pos);

    // Test faces of body 1 (A)
    if (!findLeastSeparation(body1, body2, relPos, result)) {
        return false;
    }
    // Test faces of body 2 (B)
    if (!findLeastSeparation(body2, body1, relPos, result)) {
        return false;
    }

    // Make sure the normal always is pushing away
    if (relPos.dot(result.normal) < 0) {
        result.normal.invert();
    }

    // We have a overlap
    return true;
}
Advertisement

Line 28 looks fishy. I'm not sure. I don't have time to debug the code, but you should try to make sure you space transformations are correct. Are you doing this in world space? In the space relative to the Reference OBB? Lastly, there exists code in both Box2D *Lite* for nearly the exact thing. The only difference is it's special case code for OBBs, but the math performed is doing the same SAT idea.

There's also an open source collision routine derived from Box2D Lite and Dirk's 2013 slides called "Impulse Engine" on Github. You can try looking at this for a reference.

We've all had silly bugs like this when implementing new things for the first time. It takes time to get rid of them, and they appear less often as time goes on and you understand math/concepts better :)

This topic is closed to new replies.

Advertisement