1

I'm having trouble implementing the Separating Axis Theorem - although the collision detection part works as it should, the minimum translation vector returned is wrong. If I try to use it to move the colliding polygon, it is placed either next to its previous location (sometimes intersecting the other polygon) or so far to the side it is no longer visible on the screen.

I tried to copy the code from here in an attempt to fix it, however, that did not work either. I'm not sure what is causing the problem, however, since I have rewritten everything several times now, there shouldn't be any typos.

I realise it's probably something obvious, but I have spent more than two days staring at this and I can't find it.

I apologise for the large amount of code - I have no idea where I messed up, so I can't really shorten it.

ETA: Fixed. Also, it seems that either there was an error in the original code or the coordinate system was different:

if (dotProduct(d, move_axis) < 0.0f) move_axis = -move_axis;

should actually be

if (dotProduct(d, move_axis) > 0.0f) move_axis = -move_axis;

void Polygon2d::calcEdges()
{
    sf::Vector2f v1, v2;
    edges.clear();

    for (unsigned int i = 0; i < vertices.size(); i++)
    {
        v1 = vertices[i];
        if ((i + 1) >= vertices.size()) v2 = vertices[0];
        else v2 = vertices[i + 1];

        edges.push_back(v2 - v1);
    }
}

void Polygon2d::calcCenter()
{
    float x = 0;
    float y = 0;

    for (unsigned int i = 0; i < vertices.size(); i++)
    {
        x += vertices[i].x;
        y += vertices[i].y;
    }

    center.x = x / vertices.size();
    center.y = y / vertices.size();
}

void Polygon2d::move(float x, float y)
{
    for (unsigned int i = 0; i < vertices.size(); i++)
    {
        vertices[i].x += x;
        vertices[i].y += y;
    }
    calcEdges();
    calcCenter();
}

The collision functions:

struct CollisionResult
{
    bool collision;
    sf::Vector2f move_axis;
};

void normalise(sf::Vector2f& v)
{
    float length = sqrt(v.x*v.x + v.y*v.y);

    if (length != 0.0f)
    {
        v.x /= length;
        v.y /= length;
    }
    else return;
}

float dotProduct(const sf::Vector2f a, const sf::Vector2f b)
{
    float dp = a.x*b.x + a.y*b.y;

    return dp;
}

void project(const sf::Vector2f axis, const Polygon2d& p, float& min, float& max)
{
    float dp = dotProduct(axis, p.vertices[0]);

    min = dp;
    max = dp;

    for (unsigned int i = 1; i < p.vertices.size(); i++)
    {
        dp = dotProduct(axis, p.vertices[i]);

        if (dp < min)
        {
            min = dp;
        }

        else if (dp > max)
        {
            max = dp;
        }
    }
}

float distance(float minA, float maxA, float minB, float maxB)
{
    if (minA < minB) return minB - maxA;
    else return minA - maxB;
}


CollisionResult collision(const Polygon2d& p1, const Polygon2d& p2)
{
    sf::Vector2f edge;
    sf::Vector2f move_axis(0,0);
    sf::Vector2f mtd(0,0);

    float min_dist = FLT_MAX;

    CollisionResult result;

    for (unsigned int i = 0; i < p1.vertices.size() + p2.vertices.size(); i++)
    {
        if (i < p1.vertices.size()) // or <=
        {
            edge = p1.edges[i];
        }
        else
        {
            edge = p2.edges[i - p1.vertices.size()];
        }

        sf::Vector2f axis(-edge.y, edge.x);
        normalise(axis);

        float minA = 0;
        float minB = 0;
        float maxA = 0;
        float maxB = 0;

        project(axis, p1, minA, maxA);
        project(axis, p2, minB, maxB);

        if (distance(minA, maxA, minB, maxB) > 0.0f)
        {
            result.collision = false;
            result.move_axis.x = 0.0f;
            result.move_axis.y = 0.0f;

            return result;
        }

        float dist = distance(minA, maxA, minB, maxB);

        abs(dist);

        if (dist < min_dist)
        {
            min_dist = dist;
            move_axis = axis;
        }
    }

    result.collision = true;

    sf::Vector2f d = p1.center - p2.center;
    if (dotProduct(d, move_axis) < 0.0f) move_axis = -move_axis;
    result.move_axis = move_axis * min_dist;

    return result;
}

1 Answer 1

0

It seems your condition result.collision is backward: if the distance for some axis is positive, the condition should be set to true, but in your code:

    if (distance(minA, maxA, minB, maxB) > 0.0f)
    {
        result.collision = false;
        result.move_axis.x = 0.0f;
        result.move_axis.y = 0.0f;

        return result;
    }

In addition, further in the code:

    abs(dist);

I guess it should be

    dist = abs(dist);

It's hard to judge though because of the previous problem (with the opposite logic).

2
  • dist = abs(dist); This fixed it. A bit odd, since I checked it earlier and it appeared to be working fine. Thank you for the help.
    – grue
    Apr 21, 2011 at 10:49
  • By the way, there is nothing wrong with the condition - if the distance is positive, there is a gap between the projections of the polygons and they cannot be overlapping.
    – grue
    Apr 21, 2011 at 11:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.