0
\$\begingroup\$

I am trying to implement Sweeping SAT like described here http://realtimecollisiondetection.net/files/levine_swept_sat.txt and I have already seen the answer to this question Finding the contact point with SAT which seems to have a sudo implementation to this very article.

The problem is I can't seem to fully understand how it works. Specifically if you have two 2D squares A and B. A has vertices {1,1 3,1 1,2 2,3} and B has vertices {4,1 5,2 4,4 5,4}.A's velocity is 2,0 and B is stationary. Clearly they should intersect in the future, however; If you use this algorithm then the maximum earliest future overlap seems to be 0 and the minimum latest overlap is -2 assuming the two axis you project onto are 1,0 and 0,1 which means no overlap?

Am I missing something fundamental here or does this just not work ? I have both tried it in code and via just pencil and paper as well. Both of which had the same result.

Here is my current implementation of it.

double minLatestFututreOverlapTime = std::numeric_limits<double>::infinity();
double maxEarliestFutureOverlapTime = -std::numeric_limits<double>::infinity();

Vec2D rV = other->GetPhysicsObject()->GetVelocity() - GetPhysicsObject()->GetVelocity();


for (int axes_index = 0; axes_index < 4; axes_index++)
{
    double mina = std::numeric_limits<double>::infinity();
    double maxa = -std::numeric_limits<double>::infinity();

    double minb = std::numeric_limits<double>::infinity();
    double maxb = -std::numeric_limits<double>::infinity();

    for (int point_index = 0; point_index < 4; point_index++)
    {
        double currenta = derivedPoints[point_index].dot(axis[axes_index]);
        double currentb = otherPoints[point_index].dot(axis[axes_index]);

        mina = min(currenta, mina);
        maxa = max(currenta, maxa);

        minb = min(currentb, minb);
        maxb = max(currentb, maxb);

    }

    double V = rV.dot(axis[axes_index]);

    if(V > 0)
    {
        if (maxa < minb)return false;
        else if (((mina <= minb) && (minb <= maxa)) || ((minb <= mina) && (mina <= maxb)))
        {
            minLatestFututreOverlapTime = min(minLatestFututreOverlapTime, (maxa - minb) / V);
            maxEarliestFutureOverlapTime = max(maxEarliestFutureOverlapTime, 0);


        }
        else if(maxb < mina)
        {
            minLatestFututreOverlapTime = min(minLatestFututreOverlapTime, (maxa - minb) / V);
            maxEarliestFutureOverlapTime = max(maxEarliestFutureOverlapTime, (mina - maxb) / V);


        }

    }
    else if (V < 0)
    {
        if (maxb < mina)return false;
        else if (((minb <= mina) && (mina <= maxb)) || ((mina <= minb) && (minb <= maxa)))
        {
            minLatestFututreOverlapTime = min(minLatestFututreOverlapTime, ((maxb - mina) / V));
            maxEarliestFutureOverlapTime = max(maxEarliestFutureOverlapTime, 0);


        }
        else if(maxa < minb)
        {
            minLatestFututreOverlapTime = min(minLatestFututreOverlapTime, ((maxb - mina) / V));
            maxEarliestFutureOverlapTime = max(maxEarliestFutureOverlapTime, ((minb - maxa) / V));


        }
    }
    else
    {
        if (minb < maxa && mina < maxb)
        {
            minLatestFututreOverlapTime = min(minLatestFututreOverlapTime, 0);
            maxEarliestFutureOverlapTime = max(maxEarliestFutureOverlapTime, 0);
        }
        else return false;
    }

}

if (maxEarliestFutureOverlapTime < minLatestFututreOverlapTime)
{
    response.CollisionResponse2D.collided = true;
    // not implemented yet
    //response.CollisionResponse2D.normal = axis[normal_index];
    response.CollisionResponse2D.objectBounds[0] = this;
    response.CollisionResponse2D.objectBounds[1] = other;
    response.CollisionResponse2D.collidedObjects[0] = GetPhysicsObject();
    response.CollisionResponse2D.collidedObjects[1] = other->GetPhysicsObject();

    response.timeHit = maxEarliestFutureOverlapTime / GetPhysicsObject()->GetCurrentDeltaTime();

    return true;
}
else return false;

Any help is greatly appreciated !

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.