5
\$\begingroup\$

I´ve been following this tutorial : http://www.dyn4j.org/2010/01/sat/ to help me understand and implement the SAT for collision detection in my games as I want to add a support for polygons. However, I´m facing troubles with the overlap function(to determine whether two projections overlap or not). Pieces of code:

class Polygon {
    public:
        std::vector<vec2> vertices;
        std::vector<vec2> edges;
        std::vector<vec2> axes;

        Polygon(){}

        Polygon(std::vector<vec2> list) :
            vertices(list)
        {
            init();
        }

        void init() {

            for (std::size_t i = 0; i < vertices.size(); i++) {

                vec2 edge = vertices[i] - vertices[i + 1 == vertices.size() ? 0 : i + 1];

                edges.push_back(edge);

                axes.push_back(edges.back().perp()); // its just (x,y) => (y,-x)
            }

        }

The projecting function:

    vec2 project(vec2& axis) {

        double min = axis.dot(vertices[0]);
        double max = min;

        for (std::size_t i = 1; i < vertices.size(); i++)
        {
            double p = axis.dot(vertices[i]);

            if (p < min)
                min = p;
            else if (p > max)
                max = p;
        }

        return vec2(min, max);
    }

And finally a function to determine if they collide or not:

bool collide(Polygon& poly1, Polygon& poly2)
{
    for (std::size_t i = 0; i < poly1.axes.size(); i++)
    {
        vec2 proj1 = poly1.project(poly1.axes[i]);
        vec2 proj2 = poly2.project(poly1.axes[i]);

        if (!proj1.overlap(proj2))
            return false;
    }

    for (std::size_t i = 0; i < poly2.axes.size(); i++)
    {
        vec2 proj1 = poly1.project(poly2.axes[i]);
        vec2 proj2 = poly2.project(poly2.axes[i]);

        if (!proj1.overlap(proj2))
            return false;
    }

    return true;
}

How would you implement the overlap function? I found someone elses solution using this overlap function :

bool overlap(const vec2& vector) {

    vec2 diffVector(x - vector.x, y - vector.y);

    if (diffVector.magnitude < magnitude)
        return true;
    else
        return false;
}

but its not working correctly. Is the error somewhere else or? Also im using for tets :

std::vector<cd::vec2> vertices{ {-2.0f,2.0f},{ -1.0f,0.0f },{ 2.0f,0.0f },{2.0f,2.0f },{ -1.0f,3.0f } };
cd::Polygon poly1(vertices);

std::vector<cd::vec2> vertices2{ { 0.0f,-2.0f },{ 0.0f,-3.0f },{ 2.0f,-3.0f },{ 2.0f,-2.0f },{ 1.0f,1.0f } };
cd::Polygon poly2(vertices2); And it ouputs me they don´t collide even when they should collide. Thanks!

Edit1 (due to the first answer) Adding a small screenshot showing a situation where green and red polygons just touch eachother, however the algorithm says they do not collide. enter image description here

\$\endgroup\$
3
\$\begingroup\$

Doing the overlap like that assumes the order of the overlaps.

If you instead try to find the smallest min and the biggest max and then compare those it should work;

bool overlap(const vec2& b) {
    double minA;
    double maxA;
    double minB;
    double maxB;
    if (x < b.x) {
        minA = x;
        maxA = y;
        minB = b.x;
        maxB = b.y;
    }
    else {
        minA = b.x;
        maxA = b.y;
        minB = x;
        maxB = y;
    }

    return !(maxA <= minB || minA >= maxB);
}

To find the depth of the penetration something like might do the trick;

float getOverlapDepth(const vec2& b) {
  float minA;
  float maxA;
  float minB;
  float maxB;
  if (x < b.x) {
    minA = x;
    maxA = y;
    minB = b.x;
    maxB = b.y;
  }
  else {
    minA = b.x;
    maxA = b.y;
    minB = x;
    maxB = y;       
  }

  if (maxA <= minB || minA >= maxB) {
    return 0.0f;
  }
  else {
    if (minB > minA && maxB < maxA) {
      return 100.0f; // Or some other high value to indicate complete overlap
    }
    else {
      return maxA - minB;
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ yay! it looks like it works now! (havent tried many different polygons yet). But I noticed one thing, if the two polygons only touch each other (i will edit question so you will see a screenshot describing the situation better) the algorithm says that they are colliding. However if I translate the top vertex of the green polygon for example vec(0.0f,0.01f) it says they collide. How would you fix that? Thanks. \$\endgroup\$ – Pins Jul 6 '17 at 11:52
  • 1
    \$\begingroup\$ @Pins You can measure the depth of the penetration and if it is very close to 0 you ignore the overlap. I'll knock up an example later if I find some time. \$\endgroup\$ – bornander Jul 6 '17 at 18:30

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.