Difference between revisions of "Physics:2D Physics Engine:Intersection Detection"
Silentmatt (Talk | contribs) 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 | ||
− | < | + | <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 | ||
− | </ | + | </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 | ||
− | < | + | <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 | ||
− | </ | + | </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. | ||
− | < | + | <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 | ||
− | </ | + | </syntaxhighlight> |
Latest revision as of 19:20, 3 July 2014
The following article is part of a series:
- Introduction
- Collision Detection
- Intersection Detection
- Collision Detection
- Resolving the Collision
- Rigid Bodies
- Extra 'stuff'
- Conclusion
Contents
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
- Look at the pictures. They are much easier to understand.
- For each edge vector of both polygons:
- Determine the separating axis. To compute the separating axis:
- Find the unit vector of the edge (vector of magnitude 1)
- Find the normal (perpendicular) of that unit vector
- For each polygon:
- Find the dot product between each point in that polygon and the separating axis
- The projection of that polygon onto the separating axis spans between the smallest of those projected points and the largest of them
- If the projections do not intersect, stop. That means the polygons are not intersecting.
- Determine the separating axis. To compute the separating axis:
- 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".