Separating Axis: Contact Point Generation

[cycloverid]

Hello, I've been working on a physics engine for a bit now. I'm on the final stretch, but I'm having trouble generating contact information for overlapping convex polygons.

The engine sweeps objects first to see if it can determine a collision at a t > 0, t < dt time. It creates the collision information perfectly in such a scenario, however when the sweep test fails and a collision is detected at t = 0, I can't figure out how to use SAT to generate the correct data for the collision, efficiently.

Let me describe my current algorithm, as I think there are problems with my logic in certain areas. First off, the vertex information for each polygon is generated per frame based on data from the rigid body, and the broad phase uses this information to detect collisions. (That means there are no local coordinates for collisions). That means when performing Dot( D, Vertex ) for min and max interval information for SAT, the origin of the vertex is not the center of the polygon. Would this potentially throw off my interval information for SAT as my intervals would be skewed?

When checking for an intersection of each axis of the polygon, my normal is not normalized as it is far more efficient to use unnormalized normals. This again skews the intervals for SAT. Again, the reason I chose to do this is based on efficiency, but if this is what is causing my problems I will rethink the algorithm.

Finally, when an axis is overlapping another axis I calculate t0=max1-min0 and t1=max0-min1. Let tn be the lesser of t0 and t1.
I store this value if it is less than all of the previous tn's, as well as store the correct edge information. When t0 < t1, I store object A's max index, and object B's min index, and vise-versa for t0 > t1.

Now comes the tricky part. Here's a novel method of determining contact information for a Vertex-Edge collision: Compute contact point using point projection from the overlapping vertex onto Edge E.


But how do I determine which object's vertex is overlapping the other's edge without searching through all the vertex data of the objects? And what happens when 2 vertices from one object overlap the other object's edge?


I know this question has been asked before, but I need a more thorough explanation as I think I understand most of the concepts yet I'm still having difficulty.

[Olivier_uk]

You can extract overlap information from the SAT. as you say, the calculations are not normalised, but you can work with squared distances really easy. Then you take the smallest overlap of all for your separation axis.

As for finding the contact points,

http://www.gamedev.net/community/forums ... _id=453179

same thing, wether you use continuous (linear) or overlap. once you have the axis of support, it's easy to find which points you need to consider. Then you have a few cases to parse.

[cycloverid]

Thanks for the response and the link. If this is Renault, thank you very much for the pollycolly demo, I have been using it as reference for my project. It's really cool that the physics community is so active in the forums.

I finally get it. So the minimum distance of overlap found turns out to be the object whose edge normal is the normal of the collision! I was confused about this until just now. So now all we need to do is dot the vertices of the other object against this normal to find the colliding vertices? Does this also yield the depth of the collision ( even if the polygon center is not at the origin? If so, that's very convenient.

EDIT:
So, upon testing the code, the correct contact data is generated in the event of overlap until approximately edge vs edge. For example, object A collided with object B, and object A pivots around its colliding vertex until it hits object B's edge with its edge. Now the min distance is calculated incorrectly. It reports that object B's vertex is now penetrating object A's edge ( dot product tests reveal that there is no edge vs edge collision ). So it tries to project B's vertex onto A's edge, which is not correct.

*If* correct MTD was being calculated, shouldn't ( in reference to the situation on the right ) object A's vertex be closer to object B's edge, rather than vise-versa? Could this be a result of squared distances? ... Or is this what should happen?

[Olivier_uk]

Thanks for the response and the link. If this is Renault, thank you very much for the pollycolly demo, I have been using it as reference for my project. It's really cool that the physics community is so active in the forums.

Yeah, the problem is, that demo is old and there is a better method.

. So the minimum distance of overlap found turns out to be the object whose edge normal is the normal of the collision! I was confused about this until just now. So now all we need to do is dot the vertices of the other object against this normal to find the colliding vertices? Does this also yield the depth of the collision ( even if the polygon center is not at the origin?

Well, when you scan the SAT axes, you end up with two projection intervals for the polygons / boxes. For each SAT axes, you have the information :
axis, [mina, maxa], [minb, maxb].

then, to find if the objects are separated, you check :
if (minb > maxa || mina > maxb) return false; // separated

Now, you can also extract some more information out of it. You can compute the amount of overlap for that SAT axis. it's either (maxb - mina) or (maxa - minb). During the calculations, these mina, max, minb, maxb are 'scaled' by the SAT vector length, since they are a product of the dot product of vertices against the SAT vector. So, you casn work with squared distance instead to avoid having to perform a square root (until the very end). Goes like this, for box / triangle.

Code: Select all

// calculate the projected interval of a triangle onto an axis
void SATTriangleInterval(Vector axis, Vector V[3], float& min, float& max)
{
    min  = max = V[0] * axis; // dot product
    for(int i = 1; i < 3; i ++)
    {
        float d = V[i] * axis;
        if (d < min) min = d; else if (d > max) max = d;
    }
}

// calculate the projected interval of a box onto an axis
void SATBoxInterval(Vector axis, Vector C, Vector R, Vector A[2], float& min, float& max)
{
    float p = C * axis;
    float e = R.x * fabs(A[0] * axis) + R.y * fabs(A[1] * axis);
    min = p - e;
    max = p + e;
}

// calculate the amount of overlap (signed) along an interval.
bool SATIntervalIntersect(float mina, float maxa, float minb, float maxb, float& depth)
{
     float d0 = maxa - minb;
     float d1 = maxb - mina;
     if(d0 < 0 || d1 < 0) return false;
     depth = (d0 < d1)? -d0 : d1;
     return true;
}

// resolve the calculation of the mtd.
// basically, find the minum of the combination of [axis, length] pairs, 
// and assign it to MTD.
// if mtd2 < -1, it means it's the first instance, and no comparaison is necessary.
void SATMTDResolve(Vector axis, float depth, Vector& MTD, float& mtd2)
{
    // depth was calculated projecting world vertices onto the axis vector.
    // as a result, depth is scaled by the length of axis.
    // to make comparaisons possible, we need to work with squared distances

    float a2 = axis.lengthSquared(); // squared length of axis
    float d2 = (depth / a2) * depth; // depth squared, in world coordiante (order of operations to minimise the floating point innacuracies)
    if(mtd2 < 0.0f || d2 < mtd2) // compare with current mtd length (squared)
    {
        // it's the minimum. Set the mtd to the [axis, depth] pair
        mtd2 = d2;
        MTD = axis * depth / a2;
    }
}

// V[3] : Triangle Vertices.
// C : Centre of the box.
// R : extents fo the box.
// A[2] : axes of the box, or orientation matrix.
// MTD : Minimum translation distance, or, a combination of the normal and depth of collision
bool SATIntersect(Vector V[3], Vector C, Vector R, Vector A[2], Vector& MTD)
{
    vector axis;
    float mina, max, minb, maxb;
    float depth; // depth relative to the axis intervals
    float mtd2=-1; // length of mtd squared (initialised to invalid value)

    for(int i = 0; i < 2; i ++)
    {
        axis = A[1];
        SATTriangleInterval(axis, V, mina, maxa);
        SATBoxInterval(axis, C, R, A, minb, maxb);
        if (!SATIntervalIntersect(mina, maxa, minb, maxb, depth)) return false;
        SATMTDResolve(axis, depth, MTD, mtd2);
    }

    for(int i = 0, j = 2; i < 3; j=i, i++)
    {
        Vector e = V[i] - V[j];
        axis = Vector(-e.y, e.x);
        SATTriangleInterval(axis, V, mina, maxa);
        SATBoxInterval(axis, C, R, A, minb, maxb);
        if (!SATIntervalIntersect(mina, maxa, minb, maxb, depth)) return false;
        SATMTDResolve(axis, depth, MTD, mtd2);
    }
    return true;
}

So, by running the SAT, you can calculate the MTD straight away. MTD is the minimum translation vector, and basically gives you the direction and depth of the intersection, in a vector form.

so that's two birds killed with one stone. SAT, direction of intersection, and depth.

second stage is to find the 'support' vertices on both objects, basically, the vertices that are likely to give you your support point. Think of a box on a table, the support vertices of the table would be its top two vertices, the vertices of the box would be its bottom vertices.

you will then end up with 3 possibilities.
1) support vertex vs support edge (box hitting table on a corner)
2) support edge vs support vertex (tilted box hitting table on the side).
3) support edge vs supoprt edge (box hitting table flat).

for each case, it's a matter of projecting the right things. Hence the code displayed in my link.

[cycloverid]

My problem was that I wasn't dividing by any edge length value. Now I understand what you mean by "squared distances." That fixed it, I am now getting correct results in that category.

Insofar as constructing the min,max interval with SAT, it doesn't matter where the two objects are located? I can work with world coordinates and still get an accurate MTD? ( I was wondering what MTD meant in your code for a while too, so I'm glad I got that cleared up finally! )

EDIT: Answered my own question with guess and check. No, it doesn't matter where the objects are oriented. Very cool! Thanks a ton for your help above. That makes answering depth queries very inexpensive, compared to finding the length between points of contact ( another sqrt ).

[Olivier_uk]

no worries.