“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”

In the game, we have a very commonly used algorithm, collision detection, for the common game, such as aircraft, aircraft and aircraft collision, the bullet with the plane collision, with collision detection, for daily collision detection, rectangular, circular collision you may have already practice makes perfect, is also a basic skill, but if the polygon collision? Let’s say we need a hexagon colliding with a heptagon, how do we do that? With this GIF below, let’s enter the SAT world.

Concepts and conceptual analysis

Separation axis detection can be summarized in a simple and understandable sentence: if two objects do not collide, then there must be a line separating the two objects, we call this line the separation axis. As shown in the figure below:

It can be seen from the figure that the two rectangles on the left do not collide, but are separated by the separation axis in the middle, while the two rectangles on the right collide and no line can be found to divide them. So how should we judge these two cases?

Several coordinate points ABCD and EFGH are marked in different colors in the figure. These coordinate points are the projections of the coordinate points of each Angle of the rectangle on the X axis. It can be clearly seen that all the projections of the rectangle on the left can be divided into [A,D] in blue and [E,H] in red. For the left projection separated by the separation axis, the blue projection and the red projection have no intersection, that is, the intersection is empty and there is no same place. For the right projection of the two rectangles, the interval of [C,D] and [E,F] has a certain intersection, and the intersection is not empty set, then the two rectangles intersect.

SAT at the heart of the

To sum up, in fact, for SAT, the core is to find the separation axis, that is, to find the projection whose intersection is empty, so what we need to do is to find an axis that divides two convex polygons in two.

SAT core questions and raised

If we want to prove or solve the core idea of the SAT, we have two problems here

1. Where can we find this axis?

2. How can we tell that the projection on this axis has no empty set?

How do we find this axis

First, the first question,

If we want to find the true axis of separation, we need to first find all the potential axes, and then play the projection on each potential axis to detect the empty set. But for two irregular convex polygons, there are too many potential axes, I can draw any line, that’s called a potential axis. So one thing we need to know about this is the properties of convex polygons.

Let’s open the browser and check: Properties of convex polygons. We can see directly that the property of a convex polygon is —-.

If one of the sides of a convex polygon is extended indefinitely to form a straight line, all the other sides (angles) are on the same side of the line.

With this property, we can conclude that the potential axes we want to examine are the sides of two convex polygons

Now that we have solved the first problem, how do we detect the projection of the polygon on each side? This is where we introduce the concept of a normal vector

Eight line segments are numbered in the figure, 1-5 and 6-8 respectively. The blue line on the right is the projection axis of line segment 5, which is the normal vector of line segment 5, the potential axis of line segment 5, and the blue line is the projection axis of line segment 5.So how do we figure out the line segment and the projection axis?

We have two vertices of a line segment, P1 and P2, so we can represent a line segment as a vector

For segment P1, P2 can be obtained by subtracting P1 from P2. The code for

/ * * is presupposed * / 
static sub(v1: Vector, v2: Vector) { 
    return new Vector(v1.x - v2.x, v1.y - v2.y); 
}; 
Vector.sub(P1,P2);
Copy the code

Sub is a static method of vector subtraction. The line segment P1P2 can be obtained by passing in P1 and P2. The specific vector class can be viewed in the source code.

Now that we have this line segment, it’s a little bit easier to figure out our projection axis, which is actually our normal vector, so let’s just use the subtraction to figure out our normal vector

/** The normal vector */ 
normL() { 
    return new Vector(this.y, -this.x); 
} 
Vector.sub(P1,P2).normL();
Copy the code

NormL is the method of finding a normal Vector in Vector class.

A normal vector, as many of you know, is something that’s perpendicular to the original vector, and I’m not going to explain the properties of the normal vector too much.

Then we can obtain each side of a polygon and the normal vector of each side:

/** Obtain the sides of the polygon. Here we use the coordinates of the waypoints to find the vectors of the directed line segment. End point - start point */ 
getSides() { 
    let _path = this.path, 
    len = _path.length, 
    sides = [], 
    pre = _path[0] 
    if (len >= 3) { 
    for (let i = 1; i < len; i++) { 
        let cur = _path[i]; 
        sides.push(Vector.sub(cur, pre)); 
        pre = cur; 
    } 
    sides.push(Vector.sub(_path[0], _path[len - 1])); 
    } 
    return sides; 
} 
let sides = polygon1.getSides().concat(polygon2.getSides()); 
let axises = []; 
for (let j = 0, l = sides.length; j < l; j++) { 
    axises.push(sides[j].normL()); 
}
Copy the code

Path is the path set of polygons to be detected, namely the coordinate set of each vertex, as shown in the figure above, all edges and normal vectors.

So now to the second question,

How do we know that there is no empty set of projections on this axis

It’s actually quite simple, we can see that in both cases, we have Amin, Amax, Bmin, Bmax, and what that means is that all we have to do is say Amax to Amin plus Bmax to Bmin is less than Bmax to Amin and then we have an intersection of projections, and vice versa.

So how do we figure out the projection?

Based on the figure above we can start with the vector properties, the projection of vector B in the direction of vector A is

And we know that if a is equal to x1,y1, and b is equal to x2,y2, then a dot b is x1, x2 plus y1,y2, so we can figure out the projection ！！！！！！

Dot product / * * * /
static dot(v1: Vector, v2: Vector) {
     return v1.x * v2.x + v1.y * v2.y;
}

/** Get the current coordinate of each path */
getRootCoord() {
   let _path = this.path, readlPath = [];
   for (let i = 0; i < _path.length; i++) {
       readlPath.push(new Vector(_path[i].x + this.x, _path[i].y + this.y));
   }
   return readlPath;
}

/** Get projection */
getProjection(axis:Vector) {
    let path = this.getRootCoord(), min = null, max = null;
    for (let i = 0, l = path.length; i < l; i++) {
         let p = path[i];
         let pro = Vector.dot(p, axis) / axis.length();
         if (min === null || pro < min) {
             min = pro;
         }
         if (max === null|| pro > max) { max = pro; }}return { min: min, max: max };
}

Copy the code

And then it’s easy, we’ve got all the potential axes, all the projection axes of all the potential axes, all the projections, the maximum and minimum values of all the projections, so it’s a simple judgment

    /** ** ** ** ** ** * /
    isCollsion(proA, proB) {
        let min, max;
        if (proA.min < proB.min) min = proA.min;
        else min = proB.min;
        if (proA.max > proB.max) max = proA.max;
        else max = proB.max;
        return (proA.max - proA.min) + (proB.max - proB.min) < max - min;
    }

Copy the code

Well, the separation axis collision detection principle analysis is completed, I hope to be able to help you now or at some point in the future, if you have any suggestions or questions, welcome to discuss ~