Physics:2D Physics Engine:Intersection Detection

From GPWiki

The following article is part of a series:

• Introduction
• Collision Detection
  • Intersection Detection
  • Collision Detection
  • Resolving the Collision
• Rigid Bodies
  • Rotation
  • Contact Points
  • Rigid Body Dynamics
• Extra 'stuff'
  • Information Packets
  • Segment Collision Detection
  • Springs
  • Joints
• Conclusion

Intersection Detection versus Collision Detection

Before progressing any further I'd like to share the difference between intersection detection and collision detection. An intersection test will tell you if two shapes or objects are interpenetrating at a given time. On the other hand a collision test will tell you if two objects will collide over a period of time.

A common example of a wrongly-named collision detection algorithm is the case of two intersecting circles. The test is commonly described:

"Given two circles with a center at point P, with radius R, the circles are colliding if the sum of the radii are greater than the distance between the two circles."

This is actually an intersection test, because it tests of the two circles are intersecting at their given positions. If the circles were not intersecting, but were moving towards each other very quickly, then they would be colliding. However, this test will not tell us that.

Why is this important? It isn't, really. However, it is information that will keep you from wondering why somebodies 'collision test' doesn't work at high speeds.

The Separating Axis Theorem

The Separating Axis Theorem (referred to as SAT from now on) is a method to decide whether or not two convex polygons intersect.

The SAT involves projecting the two polygons onto every axis of both polygons. If these projections intersect on all axes, then the polygons are intersecting.

Procedure

Non-intersecting polygons

Intersecting polygons

1. Look at the pictures. They are much easier to understand.
2. For each edge vector of both polygons:
   1. Determine the separating axis. To compute the separating axis:
      1. Find the unit vector of the edge (vector of magnitude 1)
      2. Find the normal (perpendicular) of that unit vector
   2. For each polygon:
      1. Find the dot product between each point in that polygon and the separating axis
      2. The projection of that polygon onto the separating axis spans between the smallest of those projected points and the largest of them
   3. If the projections do not intersect, stop. That means the polygons are not intersecting.
3. If step 2 was completed, the polygons must be intersecting.

Implementation

The following code is written in Python, but should be readable for users of other languages as well. It may look daunting, but just take it step by step. You can probably skip over the Vector class (it's fairly standard), but it's there for completeness.

import math
class Vector:
	"""Basic vector implementation"""
	def __init__(self, x, y):
		self.x, self.y = x, y
	def dot(self, other):
		"""Returns the dot product of self and other (Vector)"""
		return self.x*other.x + self.y*other.y
	def __add__(self, other): # overloads vec1+vec2
		return Vector(self.x+other.x, self.y+other.y)
	def __neg__(self): # overloads -vec
		return Vector(-self.x, -self.y)
	def __sub__(self, other): # overloads vec1-vec2
		return -other + self
	def __mul__(self, scalar): # overloads vec*scalar
		return Vector(self.x*scalar, self.y*scalar)
	__rmul__ = __mul__ # overloads scalar*vec
	def __div__(self, scalar): # overloads vec/scalar
		return 1.0/scalar * self
	def magnitude(self):
		return math.sqrt(self.x*self.x + self.y*self.y)
	def normalize(self):
		"""Returns this vector's unit vector (vector of 
		magnitude 1 in the same direction)"""
		inverse_magnitude = 1.0/self.magnitude()
		return Vector(self.x*inverse_magnitude, self.y*inverse_magnitude)
	def perpendicular(self):
		"""Returns a vector perpendicular to self"""
		return Vector(-self.y, self.x)
 
class Projection:
	"""A projection (1d line segment)"""
	def __init__(self, min, max):
		self.min, self.max = min, max
	def intersects(self, other):
		"""returns whether or not self and other intersect"""
		return self.max > other.min and other.max > self.min
 
class Polygon:
	def __init__(self, points):
		"""points is a list of Vectors"""
		self.points = points
		
		# Build a list of the edge vectors
		self.edges = []
		for i in range(len(points)): # equal to Java's for(int i=0; i<points.length; i++)
			point = points[i]
			next_point = points[(i+1)%len(points)]
			self.edges.append(next_point - point)
	def project_to_axis(self, axis):
		"""axis is the unit vector (vector of magnitude 1) to project the polygon onto"""
		projected_points = []
		for point in self.points:
			# Project point onto axis using the dot operator
			projected_points.append(point.dot(axis))
		return Projection(min(projected_points), max(projected_points))
	def intersects(self, other):
		"""returns whether or not two polygons intersect"""
		# Create a list of both polygons' edges
		edges = []
		edges.extend(self.edges)
		edges.extend(other.edges)
		
		for edge in edges:
			axis = edge.normalize().perpendicular() # Create the separating axis (see diagrams)
			
			# Project each to the axis
			self_projection = self.project_to_axis(axis)
			other_projection = other.project_to_axis(axis)
			
			# If the projections don't intersect, the polygons don't intersect
			if not self_projection.intersects(other_projection):
				return False
		
		# The projections intersect on all axes, so the polygons are intersecting
		return True