Oriented Collision Detection for HTML5 Games

Oriented Collision Detection gives you much better precision than circle or rectangle collision detection, but at a performance cost. If you have object that rotate in a game, it may be advisable to use oriented rectangles.

Rectangle and Oriented Rectangle Collision Detection

Vector Projection

When you take one vector and project it onto another, you make a 90 degree vector between some point on the vector you are projecting on to and the end point of the vector you are projecting. This creates a new vector along the vector that is being projected onto that has a different magnitude. Here are some visual examples.

In the above examples the blue vector is being projected onto the green vector. The new vector has the direction of the green vector with a different magnitude. The following code is in the cVector class, and projects one the vector onto a different vector.

public project = (onto: cVector): cVector => {
   var proj: cVector = this.duplicate();
   var d: number = onto.magSq();

   if (d != 0) {
      var mult: cVector = onto.duplicate();
      mult.multiply(proj.dot(onto) / d);
      return mult;
   }
   return onto;
}

The first thing we do we do is duplicate the vector we are working with so we don't modify the values. Then we verify that the vector that we are projecting onto has a magnitude greater than 0 (this won't work if it doesn't). Next we duplicate the vector we are projecting onto, and we change it's magnitude by multiplying it by the dot product between the two values divided by the magnitude squared of the vector we are projecting it onto.

Separating Axis Theorem

Detecting collisions between oriented rectangles requires us to use the Separating Axis Theorem (SAT). The basic idea is that if you can find a line that you can draw between two shapes (a separating axis), then the shapes do not collide. If you can't, they must collide.

If there is a separating axis, then there must be one parallel to one of the edges on one of our rectangles. For a polygon, we'll need to check all the edges on both polygons. However, for an oriented rectangle, there are some short cuts we can take.

class cRotRectangleCollider implements iCollider {
 public position: cVector = new cVector();
 public halfDimension: cVector = new cVector(1, 1);
 public rotation: number = 0;

 public axisOverlap = (axis: cLineCollider): boolean => {
  var topEdge: cLineCollider = this.GetEdge(0);
  var bottomEdge: cLineCollider = this.GetEdge(2);

  var direction: cVector = axis.position.duplicate();
  direction.subtract(axis.endPosition);
  direction.normalize();

  var axis_range: cRange = cRotRectangleCollider.ProjectLine(axis, direction);
  var range_0: cRange = cRotRectangleCollider.ProjectLine(topEdge, direction);
  var range_2: cRange = cRotRectangleCollider.ProjectLine(bottomEdge, direction);
  var projection: cRange = range_0.duplicate();
  projection = projection.combine(range_2);

  return axis_range.overlap(projection);
 }

 public static ProjectLine = (line: cLineCollider, onto: cVector): cRange => {
  var ontoNormalized: cVector = onto.duplicate();
  ontoNormalized.normalize();

  var range: cRange = new cRange();
  var dot1: number = ontoNormalized.dot(line.position);
  var dot2: number = ontoNormalized.dot(line.endPosition);

  if (dot2 > dot1) {
   range.min = dot1;
   range.max = dot2;
  }
  else {
   range.min = dot2;
   range.max = dot1;
  }

  return range;

 }

 private _a: cVector = new cVector();
 private _b: cVector = new cVector();

 public GetEdge = (edge_num: number): cLineCollider => {
  this._a.copy(this.halfDimension);
  this._b.copy(this.halfDimension);

  edge_num %= 4;
  // TOP
  if (edge_num == 0) {
   this._a.x = -this._a.x;
  }
  // RIGHT
  else if (edge_num == 1) {
   this._b.y = -this._b.y;
  }
  // BOTTOM
  else if (edge_num == 2) {
   this._a.y = -this._a.y;
   this._b.x = -this._b.x;
   this._b.y = -this._b.y;
  }
  // LEFT
  else if (edge_num == 3) {
   this._a.x = -this._a.x;
   this._a.y = -this._a.y;

   this._b.x = -this._b.x;
  }

  this._a.rotate(this.rotation);
  this._a.add(this.position);

  this._b.rotate(this.rotation);
  this._b.add(this.position);

  var edge: cLineCollider = new cLineCollider();
  edge.position.copy(this._a);
  edge.endPosition.copy(this._b);
  return edge;
 }

 public colliderType: COLLIDER = COLLIDER.ROTRECTANGLE;
}
class cRange {
 public min: number = 0;
 public max: number = 0;

 constructor(min: number = 0, max: number = 0) {
  this.min = min;
  this.max = max;
 }

 public overlap = (other: cRange): boolean => {
  return other.min <= this.max && this.min <= other.max;
 }

 public sort = (): void => {
  if (this.min > this.max) {
   var temp: number = this.min;
   this.min = this.max;
   this.max = temp;

  }
 }

 public copy = (range: cRange): void => {
  this.min = range.min;
  this.max = range.max;
 }

 public duplicate = (): cRange => {
  return new cRange(this.min, this.max);
 }

 public combine = (range: cRange): cRange => {
  var combined: cRange = new cRange();
  combined.min = this.min;
  combined.max = this.max;
  if (range.min < this.min) {
   combined.min = range.min;
  }

  if (range.max > this.max) {
   combined.max = range.max;
  }
  return combined;
 }

 public extend = (value: number): void => {
  if (value > this.max) {
   this.max = value;
  }
  else if (value < this.min) {
   this.min = value;
  }
 }

 public clamp = (value: number): number => {
  if (value < this.min) {
   return this.min;
  }
  if (value > this.max) {
   return this.max;
  }
  return value;
 }
}

We need to add more than one class to our program. First we need to put in a RotRectangle class that defines our rotated rectangle collider. We also need to have a range class. The range class will keep track of a minimum and a maximum value in a range and we provide several additional functions that are useful for tracking ranges. The Rotated Ractangle has a position, a halfDimension, and a rotation. The method "axisOverlap" checks to see if a line representing an axis overlaps with the rotated rectangle. That method uses the "ProjectLine" method which is a static method that returns a range. The range it returns represents a minimum and maximum value along the axis that the projected line takes up. We can use this value to see if multiple projections along the same axis have ranges that overlap with each other. There are some shortcuts taken by oriented rectangles that can not be taken by other polygons using the SAT. The reason for this is because any edge on an oriented rectangle has one other edge on the rectangle that is parallel to it and two edges that are orthogonal (perpendicular) with it. Because of this, we only need to test axis overlap between two adjacent adges on one rectangle and two parallel edges on the second.

Oriented Rectangle Collision Detection

Here is the static method that goes into our Collision class:

public static RotRectangleRotRectangle(a: cRotRectangleCollider, b: cRotRectangleCollider): boolean {
   var edge: cLineCollider = a.GetEdge(0);
   if (b.axisOverlap(edge) == false) {
      return false;
   }

   edge = a.GetEdge(1);
   if (b.axisOverlap(edge) == false) {
      return false;
   }

   edge = b.GetEdge(0);
   if (a.axisOverlap(edge) == false) {
      return false;
   }

   edge = b.GetEdge(1);
   return a.axisOverlap(edge);
}

Here is what it looks like in action. Hit the SPACEBAR to change the rectangles. Colliding rectangles will appear in red. Non-colliding rectangles will appear in blue.

Here's the full source code.

Next -> Part 5 - Polygon collision detection

Part 4 - Oriented rectangle collision detection

Part 3 - Line line collision detection

Part 2 - Rectangle collision detection

Part 1 - Circle circle collision detection