2D SAT Collision Detection not working when using certain polygons (With example)
- by sFuller
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:
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
