Difference between revisions of "Physics:2D Physics Engine:Intersection Detection"

From GPWiki
Jump to: navigation, search
m (Rectangle intersection demo moved)
(s/code/syntaxhighlight/ for all code fragments)
 
Line 19: Line 19:
  
 
Here is a simple implementation written in Python
 
Here is a simple implementation written in Python
<code type="python">
+
<syntaxhighlight type="python">
 
import math
 
import math
  
Line 35: Line 35:
 
     # radii, then the circles must be overlapping
 
     # radii, then the circles must be overlapping
 
     return circleA.radius + circleB.radius > dist  
 
     return circleA.radius + circleB.radius > dist  
</code>
+
</syntaxhighlight>
  
 
== Separating Axis Theorem for Axis Aligned Rectangles ==
 
== Separating Axis Theorem for Axis Aligned Rectangles ==
 
A lot of games don't need complicated collision systems to find out whether two rectangles are intersecting. The code to find this is quite simple
 
A lot of games don't need complicated collision systems to find out whether two rectangles are intersecting. The code to find this is quite simple
  
<code type="python">
+
<syntaxhighlight type="python">
 
class Vect:
 
class Vect:
 
def __init__(self, x=0, y=0):
 
def __init__(self, x=0, y=0):
Line 59: Line 59:
 
     c4 = (a.y + a.h) > (b.y - b.h)
 
     c4 = (a.y + a.h) > (b.y - b.h)
 
     return c1 and c2 and c3 and c4
 
     return c1 and c2 and c3 and c4
</code>
+
</syntaxhighlight>
  
 
A good explanation of how this works can be found [http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other here] and a visual representation [http://silentmatt.com/rectangle-intersection/ here].
 
A good explanation of how this works can be found [http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other here] and a visual representation [http://silentmatt.com/rectangle-intersection/ here].
Line 94: Line 94:
 
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 is included for completeness.
 
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 is included for completeness.
  
<code type="python">
+
<syntaxhighlight type="python">
 
import math
 
import math
 
class Vector:
 
class Vector:
Line 171: Line 171:
 
# The projections intersect on all axes, so the polygons are intersecting
 
# The projections intersect on all axes, so the polygons are intersecting
 
return True
 
return True
</code>
+
</syntaxhighlight>
  
  

Latest revision as of 19:20, 3 July 2014

The following article is part of a series:

GUITutorial warn.gif This wiki page is under construction!

This page may be incomplete, missing information, or inaccurate!

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 if 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 someone's 'collision test' doesn't work at high speeds.

Circle Intersection

Firstly, the most simple shape to detect intersections between is the circle. You can think of a circle as a point and a radius. All you have to do to check whether two circles are intersecting, is to check whether the distance between the centers is greater than the radius. If it is, the two circles aren't touching.

Here is a simple implementation written in Python

import math
 
class Circle:
	def __init__(self, radius=1, x=0, y=0):
		self.radius = radius
        self.x = x
        self.y = y
 
def circle_intersect(circleA, circleB): # returns true if circles are overlapping
    dx = circleB.x - circleA.x # get change in x
    dy = circleB.y - circleA.y # get change in y
    dist = math.sqrt(dx * dx + dy * dy) # find distance between centers of circles
    # if the distance between the centers of the circles is less than the combined
    # radii, then the circles must be overlapping
    return circleA.radius + circleB.radius > dist

Separating Axis Theorem for Axis Aligned Rectangles

A lot of games don't need complicated collision systems to find out whether two rectangles are intersecting. The code to find this is quite simple

class Vect:
	def __init__(self, x=0, y=0):
		self.x = x
		self.y = y
 
class Rect(Vect):
	def __init__(self, w=0, h=0, x=0, y=0):
		self.x = x
		self.y = y
		self.w = w
		self.h = h
 
def rectangle_ovlbool(a, b):
    c1 = (a.x - a.w) < (b.x + b.w)
    c2 = (a.x + a.w) > (b.x - b.w)
    c3 = (a.y - a.h) < (b.y + b.h)
    c4 = (a.y + a.h) > (b.y - b.h)
    return c1 and c2 and c3 and c4

A good explanation of how this works can be found here and a visual representation here.

The Separating Axis Theorem

The Separating Axis Theorem (referred to as SAT from now on) is a method to quickly and efficiently 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. However, if any of the projections are not intersecting, the polygons are not 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 is included 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


[a note from thebluedragont] If you want to move out of intersection straight away, add to your position the inverse of one of the intersection axes multiplied by one of the overlaps: -axis * overlap.

If you want to move in a logical way (if you hit a wall you don't suddenly want to go upwards, do you?), add only the smallest overlap you got with the inverse of its axis.

For example, if you do a check against two AABBs and you get that they are intersecting, see what the overlaps are (I do it by regarding each Projection struct as a circle and do a simple circle-circle overlap test). Say you got that the overlap on the X axis is 10 and the overlap on the Y axis is 13 - you need to move your object -10 units on the X axis.

I also suggest reading this article http://www.metanetsoftware.com/technique/tutorialA.html . It explains in great detail about SAT and some common shapes, but doesn't really talk much about HOW to actually do everything. Thereof, it wouldn't be complete without this page, and Gman's other page (which I honestly think is better then this one) http://gpwiki.org/index.php/VB:Tutorials:Building_A_Physics_Engine:Basic_Intersection_Detection which explains more about the "HOW to do it".