Studying Box2D-Lite in Javascript, Part 3: Collision Detection - Polygon vs Polygon

Over the course of the next couple of posts, we will look into the code involved in:

1. checking for overlap between two polygons using separating axis theorem (SAT), and

2. identifying the contact points using clipping method

The basic logic is similar to the Lite implementation (except of course, Lite code was specifically for boxes - Box2D code caters for n-gons).

The main entry to collision detection is the CollidePolygons method. The parameters for this method are:

• manifold object to be populated with the contact point information

• polyA and polyB - the polygons that need to be checked

• xfA and xfB - the transform objects of the relevant parent bodies

Separating Axis Theorem

CollidePolygons uses SAT to check overlap between two polygons.

As a reminder, SAT works on the premise that the two objects are NOT colliding if a line (ie a separating axis) can be drawn between them. We have delved into this in quite some detail when looking at Lite implementation, so we will only touch on the key points of the Box2D implementation.

Shown below is part of the CollidePolygons code that deals with SAT (this is not the complete method - we will look at the clipping method part in the next post).

In Box2D implementation, the existence of a separating axis is checked by calling FindMaxSeparation method. This method, given two polygons poly1 and poly2:

• for every edge normal of poly1,

• look for the "deepest" vertex of poly2 along that normal (i.e. look for the support point of poly2 against every edge normal of poly1 with the biggest separation)

If the separation is postiive, then we have found a separating axis. So we do the same test for the normals of poly1 and poly2. We can exit early if a separating axis is found.

// Find edge normal of max separation on A - return if separating axis is found
// Find edge normal of max separation on B - return if separation axis is found
// Choose reference edge as min(minA, minB)
// Find incident edge
// Clip

// The normal points from 1 to 2
function b2CollidePolygons(manifold, polyA, xfA, polyB, xfB)  {
	
	manifold.pointCount = 0;

	let totalRadius = polyA.m_radius + polyB.m_radius;

	let separationA = {separation: 0, edgeIndex: 0}
	b2FindMaxSeparation(separationA, polyA, xfA, polyB, xfB);

	if (separationA.separation > totalRadius)
		return false;

	let separationB = {separation: 0, edgeIndex: 0}
	b2FindMaxSeparation(separationB,  polyB, xfB, polyA, xfA);
	//console.log("separataionB=", separationB)
	if (separationB.separation > totalRadius)
		return false;  
	


}

FindMaxSeparation

// Find the max separation between poly1 and poly2 using edge normals from poly1.
function b2FindMaxSeparation(separation, poly1, xf1, poly2, xf2) {

	var count1 = poly1.m_count;
	var count2 = poly2.m_count;
	const n1s = poly1.m_normals;
	const v1s = poly1.m_vertices;
	const v2s = poly2.m_vertices;
	
	var xf = b2MulT(xf2, xf1);

	let bestIndex = 0;
	let maxSeparation = Number.NEGATIVE_INFINITY;

	for (let i = 0; i < count1; i++) {

		// Get poly1 normal in frame2.
		var n = Rot.MulQV(xf.q, n1s[i]);
		var v1 = b2Mul(xf, v1s[i]);

		// Find deepest point for normal i.
		let si = Number.MAX_VALUE;
		for (let j = 0; j < count2; ++j) {
			let sij = Vec2.b2Dot(n, Vec2.Subtract(v2s[j], v1));
			if (sij < si) {
				si = sij;
			}
		}

		if (si > maxSeparation)		{
			maxSeparation = si;
			bestIndex = i;
		}

	}

	//edgeIndex = bestIndex;
	separation.separation = maxSeparation;
	separation.edgeIndex = bestIndex;
	//return {separation: maxSeparation, edgeIndex: bestIndex};

}

Sample Code