Circle collision detection using Separating Axis Theorem
Where is the projection axis for a circle?
As we saw in the previous post, the idea behind the SAT is to project the vertices of one shape onto the edge normals of the other shape, and vice versa. However, if the shape is a circle, there are no vertices and no edges. So you might think that you cannot apply SAT to circles.
Circle vs Circle
Recall back to one of the earlier posts where we covered how to detect overlap between two circles. We could detect overlap by comparing the sum of the radii against the actual distance between the centers of the circles. This is, in fact the same as SAT, where the projection axis is the vector connecting the centers of the circles.
Polygon vs Circle
But what about polygon vs circle? Some clever folks figured out that you can apply SAT to polygon and a circle by projecting against the following axes:
normals of the polygon (as with polygon vs polygon)
axis connecting the center of the circle and the nearest vertex
Finding the closest vertex to the circle
I created the following crude method for the Polygon class to find the vertex that is closest to the position passed to the method as a parameter.
findClosestVertex(position) {
let result = null;
let vertices = this.points
let minDistance = Number.MAX_VALUE;
for (let i = 0; i < vertices.length; i++)
{
let distance = Phaser.Math.Distance.BetweenPoints(vertices[i], position);
if (distance < minDistance) {
minDistance = distance;
result = vertices[i];
}
}
return result;
}Once you have the nearest vertex, the axis is simply a vector that joins that vertex to the centre of the circle.
cp = shape2.findClosestVertex(shape1.position);
axes = [new Phaser.Math.Vector2(cp.x - shape1.position.x, cp.y - shape1.position.y).normalize()];Where are the "vertices" of the circle to project?
The vertices are points on the circumference that intersect the line joining the centre and the nearest vertex.
I created the following method for the Circle class to project its "vertices" onto the axis, and return the minimum and maximum projections (there are only 2 "vertices" to project so the bigger is the max and smaller one is the min).
I have coded it the way my brain worked. There is a much more compact way to code this. All you actually need to do is to project the circle's centre onto the axis, then add the radius and subtract the radius to get the minimum and maximum.
projectVertices(axis) {
let direction = new Phaser.Math.Vector2(axis.x, axis.y).normalize();
let directionAndRadius = new Phaser.Math.Vector2(direction.x * this.radius, direction.y * this.radius);
let p1 = new Phaser.Math.Vector2(this.x + directionAndRadius.x, this.y + directionAndRadius.y);
let p2 = new Phaser.Math.Vector2(this.x - directionAndRadius.x, this.y - directionAndRadius.y);
let min = p1.dot(axis);
let max = p2.dot(axis);
if (min > max) {
// swap the min and max values.
[min, max] = [max, min]
}
return {
min: min,
max: max,
};
}The Separating Axis Theorem code
Once you have figured out how to find the axis and vertices of a circle, then the rest is easy. The code is pretty much the same as the polygon example in the previous post, except the bit dealing with figuring out whether the shape being tested is a circle or a polygon, when getting the projection axes.
There is very definitely a much more compact way to code this. As you can see, the loop projecting the vertices onto the axes of shape 1 is the same as the loop projecting the vertices onto the vertices of shape 2. This can very definitely be made more compact - but for this post, I have kept it this way since it is easier to understand.
// Copes with shape1 = circle and shape2 = polygon, and vice versa
// Has not been coded to cope with shape1 = shape2 = circle, in the code to find the projection axes
sat(shape1, shape2, separation) {
let axes = [];
let cp;
// get the projection axes from shape 2
if (shape2 instanceof Polygon) {
axes = shape2.getAxes();
}
else
{
cp = shape1.findClosestVertex(shape2.position);
axes = [new Phaser.Math.Vector2(cp.x - shape2.position.x, cp.y - shape2.position.y).normalize()]
}
for (let i = 0; i < axes.length; i++)
{
const axis = axes[i];
// project each of the vertices onto the identified axis and get the min and max
const shape2_MinMax = shape2.projectVertices(axis)
//Do the same sort of thing for the shape1 (just 2 "vertices" at the sides)
const shape1_MinMax = shape1.projectVertices(axis)
if ((shape2_MinMax.min >= shape1_MinMax.max || shape1_MinMax.min >= shape2_MinMax.max))
{
return false
}
let axisDepth = Math.min(shape1_MinMax.max-shape2_MinMax.min, shape2_MinMax.max-shape1_MinMax.min);
if (axisDepth < separation.depth)
{
separation.depth = axisDepth;
separation.normal = axis;
}
}
// get the projection axes from shape 1
if (shape1 instanceof Polygon) {
axes = shape1.getAxes();
} else {
cp = shape2.findClosestVertex(shape1.position);
axes = [new Phaser.Math.Vector2(cp.x - shape1.position.x, cp.y - shape1.position.y).normalize()];
}
for (let i = 0; i < axes.length; i++)
{
const axis = axes[i];
const shape1_MinMax = shape1.projectVertices(axis);
const shape2_MinMax = shape2.projectVertices(axis);
if (shape2_MinMax.min >= shape1_MinMax.max || shape1_MinMax.min >= shape2_MinMax.max)
{
return false;
}
let axisDepth = Math.min(shape1_MinMax.max-shape2_MinMax.min, shape2_MinMax.max-shape1_MinMax.min);
if (axisDepth < separation.depth)
{
separation.depth = axisDepth;
separation.normal = axis;
}
}
return true;
}
Comments