The famous Separating Axis algorithm for determining intersection between arbitrary sf::Shapes:
bool intersect(const sf::Shape& shape_1, const sf::Shape& shape_2) {
if (existsSeparatingAxisForFirst(shape_1, shape_2))
return false;
return (!existsSeparatingAxisForFirst(shape_2, shape_1));
}
The functions it is implemented in terms of:
sf::Vector2f getPoint(const sf::Shape& shape, unsigned int index) {
return shape.getTransform().transformPoint(shape.getPoint(index));
}
sf::Vector2f projectShapeOn(const sf::Shape& shape, const sf::Vector2f& axis) {
auto point = getPoint(shape, 0);
auto initial = dotProduct(point, axis);
sf::Vector2f minmax(initial, initial);
for (unsigned int i=1; i<shape.getPointCount(); ++i){
auto point = getPoint(shape, i);
auto projected = dotProduct(point, axis);
if (projected < minmax.x)
minmax.x = projected;
if (projected > minmax.y)
minmax.y = projected;
}
return minmax;
}
bool existsSeparatingAxisForFirst(const sf::Shape& shape_1, const sf::Shape& shape_2) {
unsigned int pointCount = shape_1.getPointCount();
for (unsigned int i=0; i<pointCount; ++i){
unsigned int next_i = (i + 1) % pointCount;
auto side = getPoint(shape_1, next_i) - getPoint(shape_1, i);
auto perpendicular = unitVector(perpendicularVector(side));
auto minmax_1 = projectShapeOn(shape_1, perpendicular);
auto minmax_2 = projectShapeOn(shape_2, perpendicular);
if ((minmax_1.y < minmax_2.x) || (minmax_2.y < minmax_1.x))
return true;
}
return false;
}
A simple example:
Arrows to move current shape, W,A,S,D to rotate it, Q,E,Z,C to scale it.
Spacebar to cycle through shapes.
Shapes are red when they don't intersect with any other. They turn green if they intersect with at least one other shape.
Source for this example at:
https://gist.github.com/Kojirion/9635598(For convenience, vector math functions are included; they are similar to those provided by Thor)
A few notes, possibly to be addressed in the future:
- The algorithm can not be applied to sprites at the moment; it should be easy to accomplish this with a Facade.
- It is assumed the Shape is convex (as stated in the SFML docs), there are no checks that this is so.
- Points are transformed twice. Caching the results would likely improve performance.
Edit: Changed title from "Pixel perfect collision detection" so as not to imply this is a mask based algorithm.
