1
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .