2D SAT Collision Detection not working when using certain polygons (With example)

Posted by sFuller on Game Development See other posts from Game Development or by sFuller
Published on 2012-09-14T23:37:50Z Indexed on 2012/09/16 15:53 UTC
Read the original article Hit count: 275

Filed under:
|
|
|
|

My SAT algorithm falsely reports that collision is occurring when using certain polygons. I believe this happens when using a polygon that does not contain a right angle. Here is a simple diagram of what is going wrong:

problematic collision

Here is the problematic code:

std::vector<vec2> axesB = polygonB->GetAxes();
//loop over axes B
for(int i = 0; i < axesB.size(); i++)
{
    float minA,minB,maxA,maxB;
    polygonA->Project(axesB[i],&minA,&maxA);
    polygonB->Project(axesB[i],&minB,&maxB);

    float intervalDistance = polygonA->GetIntervalDistance(minA, maxA, minB, maxB);
    if(intervalDistance >= 0) return false; //Collision not occurring
}

This function retrieves axes from the polygon:

std::vector<vec2> Polygon::GetAxes()
{
    std::vector<vec2> axes;
    for(int i = 0; i < verts.size(); i++)
    {
        vec2 a = verts[i];
        vec2 b = verts[(i+1)%verts.size()];
        vec2 edge = b-a;
        axes.push_back(vec2(-edge.y,edge.x).GetNormailzed());
    }
    return axes;
}

This function returns the normalized vector:

vec2 vec2::GetNormailzed()
{
    float mag = sqrt( x*x + y*y );
    return *this/mag;
}

This function projects a polygon onto an axis:

void Polygon::Project(vec2* axis, float* min, float* max)
{
    float d = axis->DotProduct(&verts[0]);
    float _min = d;
    float _max = d;
    for(int i = 1; i < verts.size(); i++)
    {
        d = axis->DotProduct(&verts[i]);
        _min = std::min(_min,d);
        _max = std::max(_max,d);
    }
    *min = _min;
    *max = _max;
}

This function returns the dot product of the vector with another vector.

float vec2::DotProduct(vec2* other)
{
    return (x*other->x + y*other->y);
}

Could anyone give me a pointer in the right direction to what could be causing this bug?

Edit: I forgot this function, which gives me the interval distance:

float Polygon::GetIntervalDistance(float minA, float maxA, float minB, float maxB)
{
    float intervalDistance;
    if (minA < minB)
    {
        intervalDistance = minB - maxA;
    }
    else
    {
        intervalDistance = minA - maxB;
    }
    return intervalDistance; //A positive value indicates this axis can be separated.
}

Edit 2: I have recreated the problem in HTML5/Javascript: Demo

© Game Development or respective owner

Related posts about c++

Related posts about 2d