Last active
December 26, 2023 23:14
-
-
Save nyorain/dc5af42c6e83f7ac6d831a2cfd5fbece to your computer and use it in GitHub Desktop.
Small Separating Axis Theorem implementation in C++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <nytl/vec.hpp> | |
#include <nytl/vecOps.hpp> | |
#include <vector> | |
#include <limits> | |
using Polygon = std::vector<nytl::Vec2f>; | |
/// Returns whether the two given convex polygons intersect using the | |
/// separating axis theorem. The given polygons can be in clockwise or | |
/// counter-clockwise order (does not matter). | |
bool intersect(const Polygon& a, const Polygon& b) | |
{ | |
// loop over the vertices(-> edges -> axis) of the first polygon | |
for(auto i = 0u; i < a.size() + 0; ++i) { | |
// calculate the normal vector of the current edge | |
// this is the axis will we check in this loop | |
auto current = a[i]; | |
auto next = a[(i + 1) % a.size()]; | |
auto edge = next - current; | |
nytl::Vec2f axis {}; | |
axis[0] = -edge[1]; | |
axis[1] = edge[0]; | |
// loop over all vertices of both polygons and project them | |
// onto the axis. We are only interested in max/min projections | |
auto aMaxProj = -std::numeric_limits<float>::infinity(); | |
auto aMinProj = std::numeric_limits<float>::infinity(); | |
auto bMaxProj = -std::numeric_limits<float>::infinity(); | |
auto bMinProj = std::numeric_limits<float>::infinity(); | |
for(const auto& v : a) { | |
auto proj = nytl::vec::dot(axis, v); | |
if(proj < aMinProj) aMinProj = proj; | |
if(proj > aMaxProj) aMaxProj = proj; | |
} | |
for(const auto& v : b) { | |
auto proj = nytl::vec::dot(axis, v); | |
if(proj < bMinProj) bMinProj = proj; | |
if(proj > bMaxProj) bMaxProj = proj; | |
} | |
// now check if the intervals the both polygons projected on the | |
// axis overlap. If they don't, we have found an axis of separation and | |
// the given polygons cannot overlap | |
if(aMaxProj < bMinProj || aMinProj > bMaxProj) { | |
return true; | |
} | |
} | |
// at this point, we have checked all axis but found no separating axis | |
// which means that the polygons must intersect. | |
return false; | |
} |
@nyorain I was testing this code but it seems to give a false positive for certain edge cases. Is this because you are only projecting to the axis of only one of the polygons?
Edit: I think the pseudocode for a complete SAT should look like this.
Edit 2: Whatever, I just rewrote it. It's here if anyone wants to use it. It's in C++ as well.
@winstxnhdw yes that's correct, both shapes should be checked
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@bsabiston you're right, I updated it. Not sure anymore when or why i even dumped that code here, seems like i never needed it in the end.