Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Your code suggests you're not using the axes from polygonA. You need to use all the uniques axes from polygonA and polygonB.

In your first example, polygonB has an appropriate axis to prove there is separation.

In your second example, polygonB does not have an appropriate axis to prove there is a seperation, but polygonA does.

Assuming polygonA is the square, anyway.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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