## Separating Axis Theorem Refinements and Expansion

##### intent

In this video, javidx9 explores two techniques for collision detection and static resolution for convex polygons. While his collision detection using the Separating Axis Theorem is just as robust as his diagonals approach, his static resolution for SAT is slightly naïve. His implementation assumes the smallest possible displacement to resolve the collision is along the vector between the centers of the colliding polygon and the collided polygon, with a magnitude of the smallest displacement. This assumption is not always correct, and can lead to incorrect resolution with large overlaps. The correct resolution vector is along the normal of the axis with the smallest overlap.
This article will explore my implementation of Separating Axis Theorem detection and resolution.

##### separating / separated axis theorem

The video above explains the Separating Axis Theorem quite well, I suggest you watch it if my explanation seems a bit muddled.

The Separating Axis Theorem states that two convex polygons overlap only if the projection of one polygon onto the every axis of another polygon overlaps with the projection of the latter onto the same axis.

##### implementation

My implementation relies on several objects:

vector2
```vector2 {
float x, y
float length => square_root(x * x + y * y)
float dot(vector2 other) => x * other.x + y * other.y;
vector2 normalized => this / length
vector2 normal => (y, -x).normalized
}```
polygon
``` polygon {
vector2 location;
point[] points;
side[] sides;

projection project(vector2 axis){
float min = axis.dot(points[0]);
float max = min;

for(int i = 1; i < points.length; i++){
float dot = axis.dot(points[i])
if     (dot < min) min = dot;
else if(dot > max) max = dot;
}

return new projection(min, max);
}
} ```
side
```side {
vector2 start, end;
vector2 normal => (end - start).normal;
}```
projection
``` projection {
float min, max;
bool overlap(projection other) =>
max > other.min &&
min < other.max;
float overlap(projection other) =>
minimum(max, other.max) -
maximum(min, other.min);
}```

With these, writing Separating Axis Theorem collision detection is quite simple:

```bool SAT(polygon a, polygon b){
// smallest overlap
float overlap = float.MaxValue;
// axis along which the smallest overlap occurred
vector2 oaxis = new vector2()

// pointers to each polygon so they can be swapped
polygon sa = a;
polygon sb = b;

// the same operations must be done on each shape
for(int shape = 0; shape < 2; shape++){
if(shape == 1)
swap(sa, sb);

vector2[] axes = new vector2[sa.sides.length);
for(int i = 0; i < axes.length; i++)
axes[i] = sa.sides[i].normal;

for(int i = 0; i < axes.length; i++){
vector2 axis = axes[i];
projection pa = sa.project(axis);
projection pb = sb.project(axis);

if(!pa.overlap(pb))
// no collision, no resolution
return false;
else{
float o = pa.overlap(pb);
if(o < overlap){
overlap = o;
oaxis = axis;
}
}
}
}

// if the smallest penetration normal
//     points into shape b,
//     flip it
if((b.location - a.location).dot(oaxis) < 0)
oaxis *= -1;

// now oaxis is the axis along which
//     the smallest penetration occurred
// the resolution vector is that axis normal
//     multiplied by the smallest
//     penetration amount
vector2 resolution = oaxis * overlap;
// translate the colliding shape to resolve the collision
a.location -= resolution;

// no collision because of static resolution
return false;
}```

The only meaningful difference between javidx9’s approach and mine is how the resolution vector is found.

##### references

javidx9, Convex Polygon Collisions #1 (video) published 2019-02-02 retrieved 2020-09-26
Wikipedia, Hyperplane Separation Theorem (article) retrieved 2020-09-26
Wikipedia, Euclidean Vector (article) retrieved 2020-09-26

##### Contact

discord: Fyre#0465
email: horace5413@gmail.com with “olc” in the subject line