The goal: Detect collisions between 2 moving (rotating & translating) convex polygons.
When using a simulation that runs with a fixed timestep where polygons are moved based on their velocity and angular velocity each step; the simplest approach is to perform collision detection at the end of every step.
Performing collision detection on discrete timesteps means that checking if polygons are overlapping after they are moved. The algorithm selected to determine if two convex polygons are overlapping is the separating axis theorem. Which states: "Two closed convex objects are disjoint if there exists a line ("separating axis") onto which the two objects' projections are disjoint." [0]
i.e. if two convex polygons A and B are overlapping then the projections of A and B onto every possible axis will also be overlapping. If the projections of the polygons are not overlapping on any given axis then the two polygons are disjoint.
Consider the simpler example of determining if a point is contained within a polygon.
To do this:
1. pick an axis
2. project the polygon onto the axis
3. check if the point projected onto the axis is within the bounds of the projected polygon
if the point is outside of the polygon for any axis then we know that it is not within
the polygon.
It turns out that we only need check the normal of each edge of the polygon as a separating
axes. If the
projections are overlapping on every axis given by the normal of each edge then it is guaranteed that the point
intersects the polygon. (This can actually be done with only one axis for point +
polygon but thats irrelevant
for our end goal)
· White lines represent the axes we are checking
· Red lines are the projection of the polygon.
· Green/red dots show if the point is intersecting with the polygon/projection.
Note that the axes (white lines)
are shown centered on the edge that they are derived from, however the orientation of the axes is all that
matters as we are taking the projection of the polygon onto those axes.
Algorithm for determining if the projection of the point overlaps with the projection of the polygon for a
given axis:
1. Iterate over all the vertices of the polygon and compute their dot product with the axis.
2. Find the max and min values from the dot product results to defines the projection interval.
3. Perform the dot product of the point and the axis.
If the point's projection lies within the min/max bounds of the polygon's projection interval then they are
overlapping.
// get vectors perpendicular to edge
axes = []
for edge in polygon{
axes.add(normal(edge))
}
for axis in axes {
// compute the projection of the polygon onto the selected axis
poly_proj = []
for vertex in polygon{
vertex_proj = dot(axis, vertex)
poly_proj.add(vertex_proj)
}
// compute the projection of the point onto the selected axis
point_proj = dot(axis, point)
// check if the point is outside of the polygon projection
if(point_proj < min(poly_proj) or point_proj > fmax(poly_proj)){
// point is outside of polygon!
}
}
To determine if two convex polygons intersect there are two changes that must be made to the simplified
point-polygon algorithm shown above. Firstly, the axes given by the normals of both polygons must now be
checked as separating axes. Second, instead of checking whether the projection of the point lies within the
projection of the polygon, we must now check if the intervals given by the projections of the polygons
overlap.
· White lines represent the axes we are checking.
· Green lines are the projection of the polygon in the center.
· Blue lines are the projection of the polygon following the mouse.
· If the intervals given by projections are overlapping the axis becomes red
Our algorithm for determining if two polygons A & B overlap for a given axis is now as follows:
1. Iterate over all the vertices of polygon A and compute their dot product with the axis.
2. Find the max and min values from the dot product results to defines the projection interval.
3. Repeat 1. and 2. for polygon B
4. Given a_max_p as the max point of polygon A's projection, a_min_p as the min, and b_max_p, b_min_p for polygon B. Compute the amount of overlap with the following formula
overlap = min(a_max_p, b_max_p) - max(a_min_p, b_min_p)
5. If the computed overlap value <= 0 then the projections do not overlap.
In pseudo-code the full algorithm is as follows:
// get vectors perpendicular to edge
axes = []
for edge in polygon_A{
axes.add(normal(edge))
}
for edge in polygon_B{
axes.add(normal(edge))
}
for axis in axes {
// compute the projection of polygon A onto the selected axis
A_proj = []
for vertex in polygon_A{
vertex_proj = dot(axis, vertex)
A_proj.add(vertex_proj)
}
// compute the projection of polygon A onto the selected axis
B_proj = []
for vertex in polygon_B{
vertex_proj = dot(axis, vertex)
B_proj.add(vertex_proj)
}
// compute the overlap of the intervals given by the polygon projections
float overlap = min(max(A_proj), max(B_proj)) - max(min(A_proj), min(B_proj));
if(overlap <= 0){
// polygons do not intersect!
}
}