Collision detection and intersections

Introduction

This is going to be a brief tutorial on collision detection. Before we can dive in the intersection algorithms, let's look at some basic geometry operations.

Rectangle representations

Note that in any example involving rectangles, we will deal with several implementations because rectangles could be represented in a number of ways.


The same rectangle represented in three different ways

Box (center point with half-width and half-height extents)
One way to represent rectangles is as a center point (x, y) with half-width and half-height extents (hw, hh). This is very useful when programming games, because it's generally easier to work with the centers of collisions shapes. Also, it's easier to include rotation or other transformations to the rectangle when its origin is at the center.

AABB (left, top, right, bottom)
A second implementation treats rectangles as four numbers (l, t, r, b) where (l, t) is the top-left corner and (r, b) is the bottom-right corner.

Rect (top-left point with width and height dimensions)
The last example represent rectangles as a top-left corner point (x, y) with width and height dimensions (w, h).

Nearest point

Given an arbitrary position (P) outside of a shape, we want to find the nearest point (P2) on that shape. If P is already inside the area of the shape, the algorithms return the original point P. The nearest point algorithms can be used to solve more complicated intersection tests.

Nearest point on a segment

Given a line segment (x1, y1, x2, y2) we find the nearest point P2 on that segment from position P. The result is obtained using two dot products "cx*dx + cy*dy" and "dx*dx + dy*dy". One caveat is that if the segment is degenerate (has zero length) a division by zero will occur. That's why we need the check if "d == 0". One modification could be to remove the two if/else statements "if u < 0" and "elseif u > 1" and then the segment (x1, y1, x2, y2) will be treated as an infinite line. 

function pointOnSegment(px, py, x1, y1, x2, y2)
  local cx, cy = px - x1, py - y1
  local dx, dy = x2 - x1, y2 - y1
  local d = (dx*dx + dy*dy)
  if d == 0 then
    return x1, y1
  end
  local u = (cx*dx + cy*dy)/d
  if u < 0 then
    u = 0
  elseif u > 1 then
    u = 1
  end
  return x1 + u*dx, y1 + u*dy
end

Example 1: Nearest point on a line segment

Nearest point on a circle

Another common operation is finding the nearest point P2 in the circle area from an arbitrary position P. Note that the original point is returned if P is already inside the circle. 

function pointOnCircle(px, py, cx, cy, r)
  local dx, dy = px - cx, py - cy
  local d = math.sqrt(dx*dx + dy*dy)
  if d <= r then
    return px, py
  end
  return dx/d*r + cx, dy/d*r + cy
end

Example 2: Nearest point on a circle

Nearest point on a rectangle

Given an arbitrary point P the following function finds the nearest point P2 in the area of the rectangle. The code simply clamps the given point P to the extents of the rectangle. This example is designed for axis-aligned rectangles. For rotated rectangles, the point P needs to be translated relative to the center of the rectangle and then rotated.

Representation: 
function pointOnBox(px, py, x, y, hw, hh)
  local qx, qy = px - x, py - y
  if qx > hw then
    qx = hw
  elseif qx < -hw then
    qx = -hw
  end
  if qy > hh then
    qy = hh
  elseif qy < -hh then
    qy = -hh
  end
  return qx + x, qy + y
end

Example 3: Nearest point on a rectangle

Nearest point on a triangle

The following example finds the nearest point on a triangle using Barycentric coordinates. 
local function dot(ax, ay, bx, by)
  return ax*bx + ay*by
end
function pointOnTriangle(px, py, ax, ay, bx, by, cx, cy)
  local abx, aby = bx - ax, by - ay
  local acx, acy = cx - ax, cy - ay
  local apx, apy = px - ax, py - ay
  -- vertex region outside a
  local d1 = dot(abx, aby, apx, apy)
  local d2 = dot(acx, acy, apx, apy)
  if d1 <= 0 and d2 <= 0 then
    return ax, ay
  end
  -- vertex region outside b
  local bpx, bpy = px - bx, py - by
  local d3 = dot(abx, aby, bpx, bpy)
  local d4 = dot(acx, acy, bpx, bpy)
  if d3 >= 0 and d4 <= d3 then
    return bx, by
  end
  -- edge region ab
  if d1 >= 0 and d3 <= 0 and d1*d4 - d3*d2 <= 0 then
    local v = d1/(d1 - d3)
    return ax + abx*v, ay + aby*v
  end
  -- vertex region outside c
  local cpx, cpy = px - cx, py - cy
  local d5 = dot(abx, aby, cpx, cpy)
  local d6 = dot(acx, acy, cpx, cpy)
  if d6 >= 0 and d5 <= d6 then
    return cx, cy
  end
  -- edge region ac
  if d2 >= 0 and d6 <= 0 and d5*d2 - d1*d6 <= 0 then
    local w = d2/(d2 - d6)
    return ax + acx*w, ay + acy*w
  end
  -- edge region bc
  if d3*d6 - d5*d4 <= 0 then
    local d43 = d4 - d3
    local d56 = d5 - d6
    if d43 >= 0 and d56 >= 0 then
      local w = d43/(d43 + d56)
      return bx + (cx - bx)*w, by + (cy - by)*w
    end
  end
  -- inside face region
  return px, py
end

Example 4: Nearest point on a triangle

Point inside shape

Given an arbitrary point P we want to test if it lies inside the area of a given shape.

Point inside circle

Testing if a point is inside a circle is a two-step algorithm. First, we subtract the given point from the center of the circle. Next, we compare the length of the resulting vector to the radius of the circle. As an optimization, we avoid math.sqrt by comparing the square length and the square radius (r^2 or r*r). 

function pointInCircle(px, py, cx, cy, r)
  local dx, dy = px - cx, py - cy
  return dx*dx + dy*dy <= r*r
end

Example 5: Point vs circle
P: point being tested
C: circle center

Point inside rectangle

This is a relatively simple and inexpensive algorithm that checks each axis for overlap. Note that the second implementation (AABB) is the fastest and works entirely by comparing numbers.
Representation: 
function pointInBox(px, py, x, y, hw, hh)
  if math.abs(px - x) > hw then
    return false
  end
  if math.abs(py - y) > hh then
    return false
  end
  return true
end

Example 6: Point in rectangle

Point inside triangle

This simple algorithm is based on an example discussed by Christer Ericson in his book. The way the code works is by checking on which "side" the point P is located, in relation to each edge of the triangle. 
function pointInTriangle(px, py, x1, y1, x2, y2, x3, y3)
  local ax, ay = x1 - px, y1 - py
  local bx, by = x2 - px, y2 - py
  local cx, cy = x3 - px, y3 - py
  local sab = ax*by - ay*bx < 0
  if sab ~= (bx*cy - by*cx < 0) then
    return false
  end
  return sab == (cx*ay - cy*ax < 0)
end

Example 7: Point in triangle

Overlap checks

Given two shapes, we want to find if they intersect. For performance reasons, functions that detect if two shapes are intersecting should be programmed to return "false" as soon as possible.

Segment vs segment

The following function checks if two line segments (x1, y1, x2, y2 and x3, y3, x4, y4) are intersecting. The code uses two cross product "dx2*dy3 - dy2*dx3" and "dx1*dy3 - dy1*dx3" divided by a determinant (d). Note that the first check "if d == 0" returns false when the segments are either collinear or degenerate. 

function segmentVsSegment(x1, y1, x2, y2, x3, y3, x4, y4)
  local dx1, dy1 = x2 - x1, y2 - y1
  local dx2, dy2 = x4 - x3, y4 - y3
  local dx3, dy3 = x1 - x3, y1 - y3
  local d = dx1*dy2 - dy1*dx2
  if d == 0 then
    return false
  end
  local t1 = (dx2*dy3 - dy2*dx3)/d
  if t1 < 0 or t1 > 1 then
    return false
  end
  local t2 = (dx1*dy3 - dy1*dx3)/d
  if t2 < 0 or t2 > 1 then
    return false
  end
  -- point of intersection
  return true, x1 + t1*dx1, y1 + t1*dy1
end

Example 8: Segment vs segment

Segment vs circle

Given any line segment we want to find if it intersects a circle defined by a specific position and radius. 

local function segmentVsCircle(x1, y1, x2, y2, cx, cy, cr)
  local qx, qy = pointOnSegment(cx, cy, x1, y1, x2, y2)
  return pointInCircle(qx, qy, cx, cy, cr)
end
Expanded version that finds the points of intersection: 
function segmentVsCircle(x1, y1, x2, y2, cx, cy, cr)
  -- normalize segment
  local dx, dy = x2 - x1, y2 - y1
  local d = math.sqrt(dx*dx + dy*dy)
  if d == 0 then
    return false
  end
  local nx, ny = dx/d, dy/d
  local mx, my = x1 - cx, y1 - cy
  local b = mx*nx + my*ny
  local c = mx*mx + my*my - cr*cr
  if c > 0 and b > 0 then
    return false
  end
  local discr = b*b - c
  if discr < 0 then
    return false
  end
  discr = math.sqrt(discr)
  local tmin = math.max(-b - discr, 0)
  if tmin > d then
    return false
  end
  local tmax = math.min(discr - b, d)
  -- points of intersection
  -- first point
  local qx, qy = x1 + tmin*nx, y1 + tmin*ny
  if tmax == tmin then
    return true, qx, qy
  end
  -- second point
  return true, qx, qy, x1 + tmax*nx, y1 + tmax*ny
end

Example 9: Segment vs circle

Segment vs rectangle

Note that the following example works only for axis-aligned rectangles. 

function segmentVsAABB(x1, y1, x2, y2, l, t, r, b)
  -- normalize segment
  local dx, dy = x2 - x1, y2 - y1
  local d = math.sqrt(dx*dx + dy*dy)
  if d == 0 then
    return false
  end
  local nx, ny = dx/d, dy/d
  -- minimum and maximum intersection values
  local tmin, tmax = 0, d
  -- x-axis check
  if nx == 0 then
    if x1 < l or x1 > r then
      return false
    end
  else
    local t1, t2 = (l - x1)/nx, (r - x1)/nx
    if t1 > t2 then
      t1, t2 = t2, t1
    end
    tmin = math.max(tmin, t1)
    tmax = math.min(tmax, t2)
    if tmin > tmax then
      return false
    end
  end
  -- y-axis check
  if ny == 0 then
    if y1 < t or y1 > b then
      return false
    end
  else
    local t1, t2 = (t - y1)/ny, (b - y1)/ny
    if t1 > t2 then
      t1, t2 = t2, t1
    end
    tmin = math.max(tmin, t1)
    tmax = math.min(tmax, t2)
    if tmin > tmax then
      return false
    end
  end
  -- points of intersection
  -- one point
  local qx, qy = x1 + nx*tmin, y1 + ny*tmin
  if tmin == tmax then
    return true, qx, qy
  end
  -- two points
  return true, qx, qy, x1 + nx*tmax, y1 + ny*tmax
end

Example 10: Segment vs rectangle

Circle vs circle

By adding the radii of the two circles, we can treat one of the circles as a point. 

function circleVsCircle(cx, cy, r, cx2, cy2, r2)
  return pointInCircle(cx, cy, cx2, cy2, r + r2)
end
Expanded version: 
function circleVsCircle(cx, cy, r, cx2, cy2, r2)
  local sradii = r + r2
  local dx, dy = px - cx, py - cy
  return dx*dx + dy*dy <= sradii*sradii
end

Example 11: Circle vs circle
C1: center of the first circle
C2: center of the second circle
d: vector from the center of the first circle to the center of the second circle where d = C2 - C1. The two circles cannot overlap if the length of d is greater than the sum of the radii.

Circle vs rectangle

First, we find the nearest point on the rectangle to the circle center, then we compare the distance to the circle radius. Another way to describe the problem could be as finding if a point is inside a "rounded" rectangle.

Representation: 
function circleVsBox(cx, cy, cr, x, y, hw, hh)
  local qx, qy = pointOnBox(cx, cy, x, y, hw, hh)
  return pointInCircle(qx, qy, cx, cy, cr)
end
Expanded version: 
function circleVsBox(cx, cy, cr, x, y, hw, hh)
  local dx = math.abs(x - cx)
  local dy = math.abs(y - cy)
  dx = math.max(dx - hw, 0)
  dy = math.max(dy - hh, 0)
  return dx*dx + dy*dy <= cr*cr
end

Example 12: Rectangle vs circle
C: circle center
R: rectangle center
P: nearest point from C to the edges of the rectangle

Circle vs triangle

First, we project the center of the circle C to the edges of the triangle. Once we have found the projected point P, the rest of the code becomes trivial. 

function triangleVsCircle(ax, ay, bx, by, cx, cy, sx, sy, r)
  local qx, qy = pointOnTriangle(sx, sy, ax, ay, bx, by, cx, cy)
  return pointInCircle(qx, qy, sx, sy, r)
end

Example 13: Triangle vs circle
C: center of the circle
P: nearest point from the center of the circle to the edges of the triangle

Rectangle vs rectangle

The rectangle vs rectangle test checks each axis and returns false if there cannot be an intersection. Again, the second implementation (AABB) is the fastest although the parameters must be aligned so that: l < r and t < b and l2 < r2 and t2 < b2.

Representation: 
function boxVsBox(x, y, hw, hh, x2, y2, hw2, hh2)
  if math.abs(x - x2) > hw + hw2 then
    return false
  end
  if math.abs(y - y2) > hh + hh2 then
    return false
  end
  return true
end

Example 14: Rectangle vs rectangle
dx, dy: x-axis and y-axis distances from the center of the first rectangle (R1) to the center of the second rectangle (R2) where dx = R2.x - R1.x and dy = R2.y - R1.y. The two rectangles cannot overlap if abs(dx) is greater than the sum of the half-width extents (hw + hw2) or if abs(dy) is greater than the sum of the half-height extents (hh + hh2).

Triangle vs triangle

The following algorithm checks if all of the vertices of one triangle lie on the same side of any edge from the other triangle. If such edge exists, we know that the two triangles cannot overlap. 

local function cross2(x1,y1,x2,y2,x3,y3, ax,ay,bx,by,cx,cy) {
  local dXa, dYa = ax - x3, ay - y3
  local dXb, dYb = bx - x3, by - y3
  local dXc, dYc = cx - x3, cy - y3
  local x32, y23 = x3 - x2, y2 - y3
  local x13, y13 = x1 - x3, y1 - y3
  local D = y23*x13 + x32*y13
  local sa = y23*dXa + x32*dYa
  local sb = y23*dXb + x32*dYb
  local sc = y23*dXc + x32*dYc
  if D < 0 then
    if sa >= 0 and sb >= 0 and sc >= 0 then
      return true
    end
    local ta = x13*dYa - y13*dXa
    local tb = x13*dYb - y13*dXb
    local tc = x13*dYc - y13*dXc
    return (ta >= 0 and tb >= 0 and tc >= 0)
      or (sa+ta <= D and sb+tb <= D and sc+tc <= D))
  else
    if sa <= 0 and sb <= 0 and sc <= 0 then
      return true
    end
    local ta = x13*dYa - y13*dXa
    local tb = x13*dYb - y13*dXb
    local tc = x13*dYc - y13*dXc
    return (ta <= 0 and tb <= 0 and tc <= 0)
      or (sa+ta >= D and sb+tb >= D and sc+tc >= D)
  end
end

function triangleVsTriangle(x1,y1,x2,y2,x3,y3, ax,ay,bx,by,cx,cy)
  return not (cross2(x1,y1,x2,y2,x3,y3, ax,ay,bx,by,cx,cy) or
    cross2(ax,ay,bx,by,cx,cy, x1,y1,x2,y2,x3,y3))
end

Example 15: Triangle vs triangle