This post deals with the subject of detecting collisions between a pair of bodies. Time is discretized in computer physics simulations; ie you step through time in small increments delta-t. As touched on in a previous post, bodies' positions are updated using Euler integration every screen refresh. If you have two bodies moving towards each other but not colliding at one point in time, those two bodies can end up overlapping in the next refresh.
In the real world, rigid bodies cannot overlap. Therefore, key function of a physics engine is to:
detect bodies that are overlapping
resolve the overlap; i.e. move the bodies apart so that the bodies are no longer overlapping but just touching = colliding
This post is about step (1) above, which is typically referred to as collision detection. Strictly speaking, you are detecting overlap. A collision detection algorithm must return some information about the collision that can be passed to step (2). Such a function, when passed two bodies, may return the following:
boolean to indicate whether the two bodies are touching or not,
collision normal
depth of overlap
There are lots of different algorithms that can be used to detect overlap between two shapes. The algorithm used by Box2D-Lite is the separating axis theorem, which is an efficient algorithm for detecting overlap between two convex polygons. The Box2D-Lite implementation is specifically customized to deal with boxes and is incredibly compact and elegant.
We will delve into the key implementation details below.
Customized to deal with only pair of boxes
Box2D-Lite only deals with boxes, and the version of SAT of Box2D-Lite is highly "tuned" to deal only with boxes, which are defined as follows. The vertices are assumed to be winding counter-clockwise order.
Recall that the separating axis theorem, in dealing with a pair of convex polygons, involves projecting the geometries against the face normals of both the geometries.
In the case of a rectangle, there are 4 face normals. However, 2 of them face the same direction as the other 2. Hence there are only 2 face normals x 2 boxes = 4 axes that you need to project onto.
The sheer compactness of Erin Catto's implementation is due to clever transformation of the normals into local space, thereby turning the problem into one of AABB overlap detection.
For 2 AABB's, you need to check whether there is overlap along BOTH the x-axis and the y-axis, then the boxes are colliding. If there is separation along either axis, then the boxes are not colliding.
Since there are only 4 axes to test, the code is implemented to check all 4 axes (rather than a more generic implementation which would loop through the face normals of body A, then the face normals of body B). As a direct result of the way it is implemented, we can keep track of which axes is the separating axis is interms of: (i) x or y-axis (in local space), and (ii) which body the axes belongs to. The 4 axes are fined as follows, making it easier to follow.
const Axis = {
FACE_A_X: 0,
FACE_A_Y: 1,
FACE_B_X: 2,
FACE_B_Y: 3
}
Turning the problem into an AABB collision test
To delve into the impelementation further, consider the following situation (remember that we are working in the local space of the repsective body so we are effectively working with AABB's).
Let's say we want to check whether there is overlap along the x-axis.
first calculate the absolute distance between the centers along the x-axis. In the above diagram, that would be dP.x.
most intuitive way to calculate the overlap would be compare dP.x with the sum of the "radii", ie hA.x + hB.x. If dPx is greater than this radii sum, then there is separation, or if dP.x is less than this radii sum, there is overlap, ie
Hence, there is separation if
dP.x > (hA.x + hB.x)
or
dP.x - hA.x - hB.x > 0
And you need to do the same test along the y-axis.
Of course, the boxes are not actually AABB's - they are oriented boxes. So the implementation involves a lot of clear transformation from one frame of reference to another, but the basic concept boils down to the above.
Preparing for the SAT / AABB test
First the code sets up a few key variables.
hA, hB - vector2's that hold the half width and half height magntudes
posA, posB - vector2's that hold the position of the body in world space
RotA, RotB, - rotation matrix for bodyA and bodyB
RotAT, RotBT - rotation matrix to rotate from world space to local space of bodyA and bodyB, respectively
var hA = new Vector2(bodyA.width*0.5, bodyA.height*0.5);
var hB = new Vector2(bodyB.width*0.5, bodyB.height*0.5);
var posA = bodyA.position.clone();
var posB = bodyB.position.clone();
var RotA = new Mat22(bodyA.rotation);
var RotB = new Mat22(bodyB.rotation);
var RotAT = RotA.transpose();
var RotBT = RotB.transpose();
Then the "distance" between body A and body B is calculated.
dp - vector that points from body A's center to body B's center, in world space
dA - the above, in A's local space
dB - the above, in B's local space
var dp = posB.clone().subtract(posA);
var dA = Mat22.MmultV(RotAT, dp);
var dB = Mat22.MmultV(RotBT, dp);
Then further matrices are set up before the actual identification of separating axis.
C - matrix that rotates from B's local space to A's local space
absC - matrix that takes the absolute
absCT - the opposite of the above
var C = Mat22.MmultM(RotAT, RotB);
var absC = Mat22.Abs(C);
var absCT = absC.transpose();
Actual separating axis test
With the above, we are now ready to perform the separating axis test.
The blue code checks against the face normals of box A. If faceA.x (x-axis) or faceA.y (y-axis) is positive, it means that there is a separating axis, and we can exit.
// Box A faces
var faceA = Vector2.Abs(dA).subtract(hA).subtract(Mat22.MmultV(absC, hB));
if (faceA.x > 0.0 || faceA.y > 0.0) {
return false
};
We do the same against B's x and y axes. If faceB.x or faceB.y is positive, there is separation along these axes, so we can exit.
// Box B faces
var faceB = Vector2.Abs(dB).subtract(Mat22.MmultV(absCT, hA)).subtract(hB);
if (faceB.x > 0.0 || faceB.y > 0.0) {
return false
};
If we get to the other side of the red highlighted code, it means that there is at least one penetrating axis, ie the boxes are overlapping.
Note that the faceA.x, faceA.y, faceB.x, faceB.y are indicating potential penetration. The depth of penetration is negative (or if the boxes the separated, the "overlap" is positive).
From here, we need to identify the "best" or the least penetrating axis. In principle, it means finding the axis where the penetration is least negative, ie numerically the"largest".
Finding the minimum penetrating axis
In order to find the least penetrating axis, the code basically compares each of the penetrating axis against each other to find the one with the "largest" (i.e. the least negative) penetration.
The code to find the best axis is reproduced below.
(JavaScript)
// Find best axis
var axis;
var separation;
var normal = new Vector2();
// Box A faces
axis = Axis.FACE_A_X;
separation = faceA.x;
normal = (dA.x > 0.0) ? RotA.col1.clone() : RotA.col1.clone().negate();
const relativeTol = 0.95;
const absoluteTol = 0.01;
if (faceA.y > relativeTol * separation + absoluteTol * hA.y) {
axis = Axis.FACE_A_Y;
separation = faceA.y;
normal = (dA.y > 0.0) ? RotA.col2.clone() : RotA.col2.clone().negate();
}
// Box B faces
if (faceB.x > relativeTol * separation + absoluteTol * hB.x) {
axis = Axis.FACE_B_X;
separation = faceB.x;
normal = (dB.x > 0.0) ? RotB.col1.clone() : RotB.col1.clone().negate();
}
if (faceB.y > relativeTol * separation + absoluteTol * hB.y) {
axis = Axis.FACE_B_Y;
separation = faceB.y;
normal = (dB.y > 0.0) ? RotB.col2.clone() : RotB.col2.clone().negate();
}
The code starts (highlighted in blue above) off by assuming that the minimum penetration axis is FACE_A_X, together with the separation being set to faceA.x, and the normal being set to the first column of RotA = the unit vector along x-axis in body A's local space rotated to world space.
Then proceeds to check for smaller penetration against the other potential axes.
The red highlighted code tests to see if FACE_A_Y is a better penetration axis. Naively, the test would be:
faceA.y > separation...then FACE_A_Y is a better axis
However, in Erin Catto's implementation, the test is as below:
if (faceA.y > relativeTol * separation + absoluteTol * hA.y)
It places biases to prefer one axis over the other. This is a trick improves coherence, ie if the depth of penetration along the x-axis and y-axis are very close, you do't necessarily want the contact point to be recognized as being different from frame to frame because of tiny movements. In the above implementation, the y-axis is given a slight preference.
The light green code similarly does a check to see if the box B x-axis is a better separating axis, and finally the code in black does a check to see if the box B y-axis is a better separating axis.
Being aware of the direction of the normal
Once the minimum penetrating axis has been determined, the collision normal would be either the x-axis or the y-axis of the relevant reference body, converted to world space.
Being consistent in the direction of the normal is critically important. In Box2D-Lite implementation, the collision normal points away from the reference body. The correct direction of the normal is ensured by the following ternary operator, which basically checks on which side of the penetrating axis the reference body is.
normal = (dA.x > 0.0) ? RotA.col1.clone() : RotA.col1.clone().negate();
For demonstration purposes...
For this post, I have added below to the Collide function so that it returns the separation and the collision normal.
I have added bits and pieces so that a box can be moved around the screen with the cursor keys to push another box, in order to demonstrate the SAT part of the Box2D-Lite code.