I'm having trouble implementing the Separating Axis Theorem - although the collision detection part works as it should, the minimum translation vector returned is wrong. If I try to use it to move the colliding polygon, it is placed either next to its previous location (sometimes intersecting the other polygon) or so far to the side it is no longer visible on the screen.
I tried to copy the code from here in an attempt to fix it, however, that did not work either. I'm not sure what is causing the problem, however, since I have rewritten everything several times now, there shouldn't be any typos.
I realise it's probably something obvious, but I have spent more than two days staring at this and I can't find it.
I apologise for the large amount of code - I have no idea where I messed up, so I can't really shorten it.
ETA: Fixed. Also, it seems that either there was an error in the original code or the coordinate system was different:
if (dotProduct(d, move_axis) < 0.0f) move_axis = -move_axis;
should actually be
if (dotProduct(d, move_axis) > 0.0f) move_axis = -move_axis;
void Polygon2d::calcEdges()
{
sf::Vector2f v1, v2;
edges.clear();
for (unsigned int i = 0; i < vertices.size(); i++)
{
v1 = vertices[i];
if ((i + 1) >= vertices.size()) v2 = vertices[0];
else v2 = vertices[i + 1];
edges.push_back(v2 - v1);
}
}
void Polygon2d::calcCenter()
{
float x = 0;
float y = 0;
for (unsigned int i = 0; i < vertices.size(); i++)
{
x += vertices[i].x;
y += vertices[i].y;
}
center.x = x / vertices.size();
center.y = y / vertices.size();
}
void Polygon2d::move(float x, float y)
{
for (unsigned int i = 0; i < vertices.size(); i++)
{
vertices[i].x += x;
vertices[i].y += y;
}
calcEdges();
calcCenter();
}
The collision functions:
struct CollisionResult
{
bool collision;
sf::Vector2f move_axis;
};
void normalise(sf::Vector2f& v)
{
float length = sqrt(v.x*v.x + v.y*v.y);
if (length != 0.0f)
{
v.x /= length;
v.y /= length;
}
else return;
}
float dotProduct(const sf::Vector2f a, const sf::Vector2f b)
{
float dp = a.x*b.x + a.y*b.y;
return dp;
}
void project(const sf::Vector2f axis, const Polygon2d& p, float& min, float& max)
{
float dp = dotProduct(axis, p.vertices[0]);
min = dp;
max = dp;
for (unsigned int i = 1; i < p.vertices.size(); i++)
{
dp = dotProduct(axis, p.vertices[i]);
if (dp < min)
{
min = dp;
}
else if (dp > max)
{
max = dp;
}
}
}
float distance(float minA, float maxA, float minB, float maxB)
{
if (minA < minB) return minB - maxA;
else return minA - maxB;
}
CollisionResult collision(const Polygon2d& p1, const Polygon2d& p2)
{
sf::Vector2f edge;
sf::Vector2f move_axis(0,0);
sf::Vector2f mtd(0,0);
float min_dist = FLT_MAX;
CollisionResult result;
for (unsigned int i = 0; i < p1.vertices.size() + p2.vertices.size(); i++)
{
if (i < p1.vertices.size()) // or <=
{
edge = p1.edges[i];
}
else
{
edge = p2.edges[i - p1.vertices.size()];
}
sf::Vector2f axis(-edge.y, edge.x);
normalise(axis);
float minA = 0;
float minB = 0;
float maxA = 0;
float maxB = 0;
project(axis, p1, minA, maxA);
project(axis, p2, minB, maxB);
if (distance(minA, maxA, minB, maxB) > 0.0f)
{
result.collision = false;
result.move_axis.x = 0.0f;
result.move_axis.y = 0.0f;
return result;
}
float dist = distance(minA, maxA, minB, maxB);
abs(dist);
if (dist < min_dist)
{
min_dist = dist;
move_axis = axis;
}
}
result.collision = true;
sf::Vector2f d = p1.center - p2.center;
if (dotProduct(d, move_axis) < 0.0f) move_axis = -move_axis;
result.move_axis = move_axis * min_dist;
return result;
}