top of page
Search
  • cedarcantab

Understanding Box2D-Lite in Javascript, Part 3.2: Clipping method

Updated: 19 hours ago

Contact Points using Clipping Method







In the previous post we delved into the code that checks for overlap between boxes. At the end of that code, we ended up with the collision normal (defined by Box2D-Lite as pointing away from the reference body).


In this post we tackle the contact point generation part of Box2D-Lite. Frankly, it is difficult. I have broken down my attempt at an explanation below.


  1. Objective of contact point generation

  2. Clipping method at a glance

  3. Special object to hold the Contact Point information

  4. Implementation of the clipping method


Objective


Contact point generation is (another) very important part of physics engine. There are lots of different ways of generating contact point(s) between two boxes. There exists relatively straightforward methods to generate a single contact point. However, things become quite considerably more complex if one wants to generate (up to) two good contact points.


Box2D-Lite uses something called the clipping method to generate either one or two contact points. I set out the main elements of this algorithm below.


The Clipping method at a glance


In really simple terms, the "clipping" method involves the following steps:


1. Identify the significant / colliding edges


When two boxes collide, there will be a pair of edges, one from each body, defining the penetration, ie the colliding edges. This pair of edges is often referred to as the significant edges.














2. Of the colliding edges, identify "reference edge" and the "incident edge"


There are various ways to distinguish between the reference edge and the incident edge, but one way is to define the reference edge as the face associated with the minimum separating axis


The incident edge is then the "other" colliding edge. The contact point(s) lie somewhere on this incident edge. Sometimes, the contact point would be the end vertices, but sometimes not. Finding the actual contact point is done by "clipping" the incident edge.




The "end" vertices of the incident edge are the starting points for clipping.












3. Clip the vertices of the incident edge by the reference edge


3.1. Clip the incident edge by the positive side of the reference edge


Clip the "positive side" or "positive" plane defined by the normal of the reference edge and one of its vertices.


Remember that a plane can be defined by a vector that is orthogonal to the plane and one point on the plane. In the below diagram, the "positive" clipping plane is one that "cuts" into the screen aligned to the right-hand side of the reference body, and if any part of the incident edge is "outside" this plane it would be clipped.


In the example below, the first clipping step as shown below does not result in the incident edge being clipped since the edge is entirely on the acceptable side of the plane.












3.2 Clip the incident edge by the negative side of the reference edge


Then clip the incident edge by the "negative side" or the "negative plane" of the reference body, which is the plane cutting into the screen aligned to the left-hand side of the reference body. In this case, the incident edge is clipped at point c2.


In this particular situation, points c1 and c2 would be the contact points.















4. Make sure the clipped points are on the "correct side" of the reference edge


In the above example, both the clipped points are on the correct side (ie "behind" the reference edge). However, you might have something like below. In this type of situation, of the clipped points remaining from steps 3.1 and 3.2, c2 is not a valid contact point since it is on the wrong side of the reference edge, so must be dropped.














5.Store the remaining clipped points in the Arbiter


The resulting clipped points (in the final example there is only one point remaining) is stored as appropriate.


Defining Contact Point


Ultimately, the contact point(s) are held in the Contact class. During the clipping process however, Box2D manipulates a class called ClipVertex. When the contact points have been identified, the important information is copied from ClipVertex to the Contact object.

At the most naive level, we are looking for the x/y coordinates of the contact contact point in world space.


For reasons that will become clearer when we come to implement warm starting, it is important to be able to "track" a contact point between frames. For example if a pair of bodies is colliding in this frame refresh, and it is identified that the same pair of bodies is colliding in the next frame, we need to be able to tell whether the contact point identified in the most recent frame is consistent with the contact point identified in the previous frame. There are different ways of tracking a contact point between frames:


  1. compare the contact point world space coordinates from one frame to the enxt

  2. contact point is at an intersection of two edges - compare the intersecting edges.

Box2D-Lite adopts the second approach. Whilst the theory is simple, implementation is not - and to make this process easier, there are several relevant classes, including (i) ClipVertex, (ii) FeaturePair, and (iii) Edges. During the clipping process the contact point is held in a special object called ClipVertex, which in turn holds a FeaturePair object, which in turn holds an Edges object, rather like below. Note however, that ultimately, the contact point ends up being held (together with other important contact constraint information in the Contact class).











Further details are set out below, but in summary:


  • inEdge2/outEdge2 define the contact point in terms of the edges of the incident box (think of a vertex as being the intersection of 2 edges).

  • inEdge1/outEdge1 define the associated edges of the reference box


Given that a contact point can be defined by two edges, it may seem odd to refer to 4 edges. However, this necessity is clear in cases such as below. The clipping process will start with v1 and v2, the end points of the incident edge. v1 will be clipped away by the "left" plane of the reference edge, leaving cp2. However, cp2 will clipped away in the final clipping operations since it is on the wrong side of the reference edge, leaving only cp1 = v2 as the contact point. This will be defined by the e2 of the incident box and the reference edge.



Thinking in terms of counterclockwise winding, a contact point is defined by an "inEdge", ie the edge that points towards the point, and an "outEdge", an edge that points away frmo the point. The edge may come from the incident box or the reference box.


ClipVertex class

class ClipVertex {
    
    constructor () {
        this.v = new Vector2()
        this.fp = new FeaturePair();
    }

}

Property v holds the "position" of the contact point as a 2d vector. However the object also has another property which itself is another object called FeaturePair, which in turn has two properties:


  1. property e which holds another object called Edges - this is a special class which, in a nutshell, holds information about the intersecting edges associated with the contact point

  2. property value which is used to hold a unique key value for this contact point based on the edges that "define" the contact point (see below for further explanation).


FeaturePair object

class FeaturePair {
    constructor() {
        this.e = new Edges();
        this.value = 0;
    }

    flip() {
        const edges = this.e;

        const tempIn = edges.inEdge1;
        const tempOut = edges.outEdge1;

        edges.inEdge1 = edges.inEdge2;
        edges.inEdge2 = tempIn;

        edges.outEdge1 = edges.outEdge2;
        edges.outEdge2 = tempOut;
    }

    getKey(){
		return this.e.inEdge1 + (this.e.outEdge1 << 8) + (this.e.inEdge2 << 16) + (this.e.outEdge2 << 24);
	};

    equals(fp) {
		return this.getKey() === fp.getKey();
	}
    
}

Edges class

The Edges class is shown below.


class Edges {

    constructor ()    {
        this.inEdge1 = EdgeNumber.NO_EDGE;
        this.outEdge1 = EdgeNumber.NO_EDGE;
        this.inEdge2 = EdgeNumber.NO_EDGE;
        this.outEdge2 = EdgeNumber.NO_EDGE;
    }
}

Edge references

It is useful to recall that Box2d defines the edges of a box as follows.












Implementation of the clipping method


Recall that the collision detection code of Box2D-Lite (separating axis theorem) identifies the following pieces of information:

  • collision normal

  • depth of penetration

  • separating axis (one of Axis.FACE_A_X, Axis.FACE_A_Y, Axis.FACE_B_X, Axis.FACE_B_Y)


..starting with the collision normal from the SAT step...

// Setup clipping plane data based on the separating axis
var frontNormal, sideNormal;
var incidentEdge = [new ClipVertex(), new ClipVertex()];
var front, negSide, posSide;
var negEdge, posEdge;

Working variables are set up as above, before the incident edge is calculated. Crucially, note that the incidentEdge variable consists of two ClipVertex objects (it is easy to think of incident edge being defined by an array of 2 end points).


As described in the summary earlier, at the heart of the clipping method:


  1. Identifying the incident edge which will be the edge that the contact points will lie on. At the start, the potential contact points are the end points of the incident edge, then

  2. "clip" the incident edge by the plane at the negative side of the reference edge

  3. "clip" the incident edge by the plane at the positive side of the reference edge

  4. finally check if any of the points remaining from the 2 above clipping steps lie on the "wrong" side of the reference edge itself


Identify and set-up the incident edge details

The code then goes into a switch statement with 4 case blocks of code dependent on the penetrating axis, that basically sets up the incident edge. Note that the tests performed by the 4 blocks are very similar. They key difference is that in the latter 2 relating to cases where the separating axis is from Box B, the normal is flipped before storing in frontNormal, which is the reference edge normal.


	// Compute the clipping lines and the line segment to be clipped.
	switch (axis) {
    
		case Axis.FACE_A_X:
		{
			frontNormal = normal.clone();
			front = posA.dot(frontNormal) + hA.x;
			sideNormal = RotA.col2.clone();
			var side = posA.dot(sideNormal);
			negSide = -side + hA.y;
			posSide =  side + hA.y;
			negEdge = EdgeNumber.EDGE3;
			posEdge = EdgeNumber.EDGE1;
			ComputeIncidentEdge(incidentEdge, hB, posB, RotB, frontNormal);
			break;
		}
		case Axis.FACE_A_Y:
		{
			frontNormal = normal.clone();
			front = posA.dot(frontNormal) + hA.y;
			sideNormal = RotA.col1.clone();
			var side = posA.dot(sideNormal);
			negSide = -side + hA.x;
			posSide =  side + hA.x;
			negEdge = EdgeNumber.EDGE2;
			posEdge = EdgeNumber.EDGE4;
			ComputeIncidentEdge(incidentEdge, hB, posB, RotB, frontNormal);
			break;

		}

		case Axis.FACE_B_X:
		{
			frontNormal = normal.clone().negate();
			front = posB.dot(frontNormal) + hB.x;
			sideNormal = RotB.col2.clone();
			var side = posB.dot(sideNormal);
			negSide = -side + hB.y;
			posSide =  side + hB.y;
			negEdge = EdgeNumber.EDGE3;
			posEdge = EdgeNumber.EDGE1;
			ComputeIncidentEdge(incidentEdge, hA, posA, RotA, frontNormal);
			break;
		}		

		case Axis.FACE_B_Y:
		{
			frontNormal = normal.clone().negate();
			front = posB.dot(frontNormal) + hB.y;
			sideNormal = RotB.col1.clone();
			var side = posB.dot(sideNormal);
			negSide = -side + hB.x;
			posSide =  side + hB.x;
			negEdge = EdgeNumber.EDGE2;
			posEdge = EdgeNumber.EDGE4;
			ComputeIncidentEdge(incidentEdge, hA, posA, RotA, frontNormal);
			break;
		}

	}

Example: First block of the switch statement

For example, the first block in the switch statement (in blue) sets up the incident edge in case the minimum penetration axis is face_A_X, and boxA is to the left of box B with the collision normal facing right.


Consider the below situation, where the "colliding edges" are EDGE4 of box A and EDGE2 of box B. One of these edges would be the incident edge.













To identify the incident edge, basic information about the state is set up, like so:


Then ComputeIncidentEdge method is called to identify and set up the actual incident edge details to be clipped in world space. More specifically, the end points of the incident edge are returned (incidentEdge is defined as an array of 2 clipVertex points).


ComputeIncidentEdge

My Javascript translation of the ComputeIncidentEdge method is shown in full below.


The parameters are:

  • c: variable to hold the details of the incident edge (ie an array of the 2 clipVertex objects)

  • h: halfWidth and halfHeight of the incident box

  • pos: position of the incident box

  • Rot: rotation matrix of the incident box

  • normal: outfacing normal of the reference edge

It is assumed that the normal is from the reference box.


function ComputeIncidentEdge(c, h, pos, Rot, normal) {

	// The normal is from the reference box. Convert it to the incident boxe's frame and flip sign.

	var RotT = Rot.transpose();
	//		var n = -(RotT * normal);
	var n = Mat22.MultMV(RotT, normal).negate(); // Vector2
	var nAbs = Vector2.Abs(n); // Vector2

	if (nAbs.x > nAbs.y) {
		if (Math.sign(n.x) > 0.0) {
			c[0].v.set(h.x, -h.y);
			c[0].fp.e.inEdge2 = EdgeNumber.EDGE3;
			c[0].fp.e.outEdge2 = EdgeNumber.EDGE4;

			c[1].v.set(h.x, h.y);
			c[1].fp.e.inEdge2 = EdgeNumber.EDGE4;
			c[1].fp.e.outEdge2 = EdgeNumber.EDGE1;
		}
		else
		{
			c[0].v.set(-h.x, h.y);
			c[0].fp.e.inEdge2 = EdgeNumber.EDGE1;
			c[0].fp.e.outEdge2 = EdgeNumber.EDGE2;

			c[1].v.set(-h.x, -h.y);
			c[1].fp.e.inEdge2 = EdgeNumber.EDGE2;
			c[1].fp.e.outEdge2 = EdgeNumber.EDGE3;
		}
	}
	else
	{
		if (Math.sign(n.y) > 0.0) {
			c[0].v.set(h.x, h.y);
			c[0].fp.e.inEdge2 = EdgeNumber.EDGE4;
			c[0].fp.e.outEdge2 = EdgeNumber.EDGE1;

			c[1].v.set(-h.x, h.y);
			c[1].fp.e.inEdge2 = EdgeNumber.EDGE1;
			c[1].fp.e.outEdge2 = EdgeNumber.EDGE2;
		}
		else
		{
			c[0].v.set(-h.x, -h.y);
			c[0].fp.e.inEdge2 = EdgeNumber.EDGE2;
			c[0].fp.e.outEdge2 = EdgeNumber.EDGE3;

			c[1].v.set(h.x, -h.y);
			c[1].fp.e.inEdge2 = EdgeNumber.EDGE3;
			c[1].fp.e.outEdge2 = EdgeNumber.EDGE4;
		}
	}
	c[0].v = Vector2.Add(pos, Mat22.MultMV(Rot, c[0].v));
	c[1].v = Vector2.Add(pos, Mat22.MultMV(Rot, c[1].v));

}

The first thing the code does is to take the normal from the reference edge, convert it to the incident box frame of reference, then flip the sign.


Then the switch statement assesses whether the resulting axis is more vertical or horizontal by comparing the x and y components of the vector.


If it is more horizontal, the incident edge will be one of the vertical edges. In order to detect which edge, you look at which way the normal is pointing.


Following through with the example where the reference box is on the left-hand side and the best axis has been identified as FACE_A_X such that the incident edge is shown in red, and the reference edge is as shown in blue below.














Once the incident edge details have been set up (see below - I've shifted Box B but otherwise same example), the green highlighted code maps the end points of the incident edge to world space, before the clipping process begins.

















Actual clipping

Having identified the incident edge, placeholders for the clipping operation is created to hold the clipped vertices (potential contact points).


	var clipPoints1 = [new ClipVertex(), new ClipVertex()]; // temp holder for 2 vertices to be clipped
	var clipPoints2 = [new ClipVertex(), new ClipVertex()];
	var np;

Clip against the "negative" side of the reference edge

First the vertices of the incident edge are clipped against the "negative side" of the reference edge. The resulting points are stored in array clipPoints1.


// Clip to box side 1
	np = ClipSegmentToLine(clipPoints1, incidentEdge, sideNormal.clone().negate(), negSide, negEdge);
	
	if (np < 2)
		return false;

Clip against the "positive side" of the reference edge

The points remaining from clipping above is taken and passed to the clipping operation against the "positive side" of the reference edge.


	// Clip to negative box side 1
	np = ClipSegmentToLine(clipPoints2, clipPoints1,  sideNormal, posSide, posEdge);

	if (np < 2)
		return false;

The algorithm then goes onto the final check to ensure that the clipped points are on the correct side of the reference edge. But before we delve into that part, let's look at the actual clipping method.


Clipping method

The Javascript translation of the actual clipping method ClipSegmentToLine is shown below. The parameters are:

  • vOut: to hold the clipped points

  • vIn: the points to be clipped (ie the ends of the incident edge)

  • normal: the outward facing normal from the edge

  • offset: the "side" plan against which to clip


function ClipSegmentToLine(vOut, vIn, normal, offset, clipEdge) {
		
	// Start with no output points
	var numOut = 0;

	// Calculate the distance of end points to the line
	var distance0 = normal.dot(vIn[0].v) - offset;
	var distance1 = normal.dot(vIn[1].v) - offset;

	// If the points are behind the plane
	if (distance0 <= 0.0) {
		vOut[numOut] = vIn[0];
		numOut++;
	};
	if (distance1 <= 0.0) {
		vOut[numOut] = vIn[1];
		numOut++;
	};

	// If the points are on different sides of the plane
	if (distance0 * distance1 < 0.0) {
		// Find intersection point of edge and plane
		var interp = distance0 / (distance0 - distance1);
	//	vOut[numOut] = new ClipVertex();
		vOut[numOut].v = Vector2.AddScaled(vIn[0].v, vIn[1].v.clone().subtract(vIn[0].v) , interp);
		if (distance0 > 0.0)		{
			vOut[numOut].fp = vIn[0].fp;
			vOut[numOut].fp.e.inEdge1 = clipEdge;
			vOut[numOut].fp.e.inEdge2 = EdgeNumber.NO_EDGE;
		}
		else
		{
			vOut[numOut].fp = vIn[1].fp;
			vOut[numOut].fp.e.outEdge1 = clipEdge;
			vOut[numOut].fp.e.outEdge2 = EdgeNumber.NO_EDGE;
		}
		numOut++;
	}

	return numOut;

}

In the blue highlighted code, the "offset" is compared against the distance of the vertex, and if the point falls on the wrong side of the offset, it is clipped (ie it is simply "removed", as it cannot be a contact point).


Updating the Edges object

In the red-highlighted code, the two ends of the incident edge to be clipped straddle the clipping plane, and hence the "intersection point" is returned as the clipped point. Notice how the Edges object property is amended here to EdgeNumber.NO_EDGE, to indicate that the contact point is not a vertex of the original box but is a point in the "middle" of the incident edge. The "other" associated edge is taken to be the "clipping" edge from the reference box.


Check which side of the reference edge the points lie on

Returning our attention to the overall clipping algorithm, having clipped against the negative side and the positive side of the reference edge, we now need to ensure that the clipped points lie on the correct side of the reference edge. To do that we simply take dot product between the contact point and the outfacing normal from the reference edge which we have made sure points in the correct direction in the above switch statement, stored in variable frontNormal


The "clipping" here is not performed by calling the clipSegmentToLine method above, although the process for clipping is similar. Instead, this final "clipping" is performed by the following piece of code.


The blue highlighted code is similar to what we have seen before. Take the dot product between the incident edge point against the reference edge normal, and subtract the "distance" to the reference edge plane (front), to see which side of the reference edge plane the point lies. If the "separation" is positive, if means the incident edge point is on the wrong side of the reference edge so we "discard" the point.


If the is negative, it means the point is on the correct side of the reference edge plane so we keep it. The red highlighted code copies the relevant details of the point to the contacts array (which already holds two blank Contact objects):


  • separation: note that we do not copy the penetration depth obtained as a result of the SAT; rather the separation just calculated is stored. In certain cases, the penetration depth will be the negative of the separation but in certain cases, it will not be the same because the edges may have been clipped in such a way that the penetration depths are different from that calculate during the separate axis test.

  • normal: this is the collision normal. the same normal is stored for each contact point (although I am sure you could store it just once per Arbiter)

  • feature: the featurepair (ie the edes that define the contact point) is stored


The purple highlighted code "shifts" the points on the incident edge to the reference edge.


Finally, if the separating axis was FACE_B_X or FACE_B_Y (ie the reference edge belongs to box B, as opposed to box A), the featurepair edges are swapped to ensure that inEdge1/outEdge1 vs inEdge2/outEdge2 are treated consistently (although frankly with the 9 demos provided, I could not any difference if this line was taken out).


	// Now clipPoints2 contains the clipping points.
	// Due to roundoff, it is possible that clipping removes all points.

	var numContacts = 0;

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

		let separation = frontNormal.dot(clipPoints2[i].v) - front;

		if (separation <= 0) {
			contacts[numContacts].separation = separation;
			contacts[numContacts].normal = normal.clone();			
			contacts[numContacts].feature = clipPoints2[i].fp;
			// slide contact point onto reference face (easy to cull)
			contacts[numContacts].position = Vector2.AddScaled(clipPoints2[i].v, frontNormal, -separation);
			if (axis == Axis.FACE_B_X || axis == Axis.FACE_B_Y) contacts[numContacts].feature.flip();
			numContacts++;
		}
	}
	
	return numOut;

Finally the number of contacts points (which may be 1 or 2) is returned. This is necessary since the array to hold the contact points has always 2 Contact objects (if there is only one contact point, the second Contact object will be "blank").


Calling the clipping operation from world step

All of the above is called from the step method of the world class, broadly as follows:


  for (let i = 0; i< this.bodies.length - 1; i++) {
      var bi = this.bodies[i];
      for (let j = i+1; j < this.bodies.length; j++) {
        var bj = this.bodies[j];
        var newArb = new Arbiter(bi, bj);
        if (newArb.numContacts>0) this.arbiters.push(newArb)
      }
    }

When the new Arbiter object is instantiated (in the red highlighted code above), an array of 2 Contact objects are created as a property of the arbiter object, and the collide method is called with the two bodies being tested and the contact objects array, by the constructor function.


	this.contacts = [new Contact(), new Contact()]; // hold up to 2 contact points
	this.numContacts = collide(this.contacts, this.body1, this.body2);;

The collide method then executes the SAT collision detection, and all of the clipping operations described above.


CodePen





Useful References






記事: Blog2_Post
bottom of page