Add Me!Close Menu Navigation

Polygonal Collision Detection

We will use the Separating Axis theorem to deduce whether two convex polygons are overlapping or not and implement the desired algorithm in both C and Lua. Collision detection is primarily used within the game development industry, but practical uses outside of this industry are also quite common.

1. Table of Contents

2. Introduction

Detection of collision between two objects is a very common problem for game developers. One intuitive method may check for all vertices of a polygon and check whether the other polygon contains the said point, but the containment check is usually implemented very naively hence the overall collision detection procedure becomes highly inefficient. Now, we need collision detection to be efficient because oftentimes, the world that we are working with will be populated with thousands upon thousands of polygons. An iterative approach will increase the running time for collision detection exponentially with each additional object, hence, assuming that there are very few collisions at every instance of time, it becomes highly advantageous to develop an algorithm which can immediately detect whether two polygons are not colliding and break once it has made this decision. The separating axis theorem is one such algorithm.

Blatant plagiarism from wikipedia:

For objects lying in a plane (2-dimensional space), the separating axis theorem states that, given two convex shapes, there exists a line onto which their projections will be separate if and only if they are not intersecting. A line for which the objects have disjoint projections is called a separating axis. An equivalent way of stating the theorem is to say that two convex shapes in the plane are not intersecting if and only if a line can be placed with one shape to one side of the line and the other shape to the other side. Such a separating line will be perpendicular to a separating axis.

3. Starting off with the basics

A few simplified mathematical definitions first:

  • Vector – Imagine it as an arrow that points in some arbitrary direction in space. It also has a length that denotes its “strength”
  • Polygon – A closed shape consisting of no contours (only straight lines)
  • Convex polygon – for every line that intersects the polygon, this line can never hit more than 2 edges (meaning that there can’t be any indents)
  • Projection – Imagine that you shine a line on top of the polygon, you will see an outline/shadow of the shape on the ground. Now imagine doing the same in 2D, instead of a 2D shadow, you will just see a single line segment. This segment is the projection of a 2D polygon onto the ground (or y = 0 in normal cartesian coordinates). If we instead shift the ground to a 45 degree slant, we will still see a shadow, but it will be different. This new shadow is the projection of the polygon onto a line that is at a 45 degree slant.

The double sided arrow on the above image is the projection segment of the two objects onto the green line. Now the separating axis theorem asserts that if we are to project two objects onto a fixed line that we shall call the separating axis, then if we can find one such separating axis where a line perpendicular to it completely separates the two shapes, then we immediately conclude that the two objects do not intersect. In essence, this implies that if the projections of the two objects onto the separating axis do not overlap, then we can conclude that the two objects do not intersect. However, if the projections do overlap, then the test is inconclusive and we will have to try another axis.

From over here, this may look like a nonterminating algorithm because overlapping regions will continue checking new axes ad infinitum. There’s a second condition when applying the SAT (as we will call the theorem from now on) to convex polygons, namely that only axes that are perpendicular (normal) to the edges of both of the polygons need to be checked because we can only draw the separating line in regions beyond the edges.

4. At an abstract

An abstract representation of this algorithm looks something like this: (pseudocode)

bool sat(polygon a, polygon b){
    for (int i = 0; i < a.edges.length; i++){
        vector axis = a.edges[i].direction; // Get the direction vector of the edge
        axis = vec_normal(axis); // We need to find the normal of the axis vector.
        axis = vec_unit(axis); // We also need to "normalize" this vector, or make its length/magnitude equal to 1

        // Find the projection of the two polygons onto the axis
        segment proj_a = project(a, axis), proj_b = project(b, axis); 

        if(!seg_overlap(proj_a, proj_b)) return false; // If they do not overlap, then return false
    }
    ... // Same thing for polygon b
    // At this point, we know that there were always intersections, hence the two polygons must be colliding
    return true;
}


* No hippos were hurt during the production of this tutorial.

We of course need to define our datatypes first:

5. Vectors

A vector is essentially a point. It contains an x and a y coordinate. The magnitude of this vector is the distance of the point from the origin, and the direction the angle it makes with the X-axis. In this sense, it’s easy to implement, as it’s basically just two numbers (floats specifically)

C implementation:

typedef struct {float x, y;} vec;

vec v(float x, float y){
	vec a = {x, y}; // shorthand for declaration
	return a;
}

Lua implementation:

function vec(x,y)
	return {x,y} -- vectors are just lists/tables
end

v = vec -- shortcut

There are many different functions that we can implement in order to work with vectors, but for the sake of simplicity, we will only need a few:

  • Dot product – {a,b} dot {c,d} = a*b + b*d, the dot product is essentially what projection translates to quantitatively, so think of this as projection of a point onto a line/vector
  • Normalize – If the distance between {a,b} and {0,0} is sqrt(a^2 + b^2), then the normalization of {a,b} is 1/(sqrt(a^2+b^2)) * {a,b} (multiply to both a and b). The resulting vector will be of “unit length”, meaning that its distance to the origin will be exactly 1

By these definitions, the functions that we need are rather trivial:

Dot product, C implementation:

float dot(vec a, vec b){
	return a.x*b.x+a.y*b.y;
}

Dot product, Lua implementation:

function dot(v1, v2)
	return v1[1]*v2[1] + v1[2]*v2[2]
end

Normalize, C implementation:

#include <math.h>
vec normalize(vec v){
	float mag = sqrt(v.x*v.x + v.y*v.y);
	vec b = {v.x/mag, v.y/mag}; // vector b is only of distance 1 from the origin
	return b;
}

Normalize, Lua implementation:

function normalize(v)
	local mag = math.sqrt(v[1]^2 + v[2]^2)
	return vec(v[1]/mag, v[2]/mag)
end

We will also need to transpose the vector in order to find the perpendicular/normal vector. If you think about it, by flipping the x and y coordinates, and then negating the new y coordinate, the resulting vector will always be perpendicular to the original.

C:

vec perp(vec v){
    vec b = {v.y, -v.x};
    return b;
}

Lua:

function perp(v)
	return {v[1],-v[0]}
end

6. Segments

Oftentimes, the edges of a polygon are expressed as line segments with precise starting and ending points. While we don’t actually need to keep track of these during collision detection, other parts of the program may need to have the polygon keep the precise states of its edges (IE: drawing the polygon onto the screen), so we’ll also need a dummy datatype for segments. I’ll just provide a simple implementation.

Segments, C implementation:

typedef struct {vec p0, p1, dir;} seg;

seg segment(vec p0, vec p1){
    vec dir = {p1.x-p0.x, p1.y-p0.y};
    seg s = {p0, p1, dir};
    return s;
}

Segments, Lua implementation:

function segment(a, b)
	local obj = {a=a, b=b, dir={b[1] - a[1], b[2] - a[2]}}
	obj[1] = obj.dir[1]; obj[2] = obj.dir[2] -- seg[1] and seg[2] corresponds to its direction, for easy access
	return obj
end

7. Polygons

We will of course, also need to be able to define our polygons. Since we only need the vertices (corners) and the edges of the polygon, and since the edges can be calculated from the vertices, we can just construct our polygon from the set of vertices (points on the graph denoting where the corners are). An important (albeit subtle) issue arises here. If we define our polygon using the corners, how do we know which pairs of points will form edges? For example, what if we used {(0,0), (1,1),(0,1),(1,0)} to denote a box, how can we make the computer understand that we want the resulting region to be a box? The simple answer is that you cannot. Hence we must define the vertices in a specific order so that the edges are understood to be between consecutive vertices. Hence a box can be defined as either {(0,0), (0,1), (1,1), (1,0)} or {(0,0), (1,0), (1,1), (0,1)}. In the first case, we “wind” the edges around the shape like the hands of a clock would travel, and it is called a clockwise winding of the polygon, the latter being the counter-clockwise winding. In this tutorial and throughout this series, we will be using a CW winding to build our polygons. (while the direction of winding doesn’t impact the creation of the polygon much, it will matter when we begin working on our physics engine)

Polygons, C:

typedef struct {int n; vec *vertices; seg *edges;} polygon; // Assumption: Simply connected => chain vertices together

polygon new_polygon(int nvertices, vec *vertices){
	seg *edges = (seg*)malloc(sizeof(seg)*(nvertices));
	int i;
	for (i = 0; i < nvertices-1; i++){
		vec dir = {vertices[i+1].x-vertices[i].x, vertices[i+1].y-vertices[i].y};seg cur = {vertices[i], vertices[i+1], dir}; // We can also use the segment method here, but this is more explicit
		edges[i] = cur;
	}
	vec dir = {vertices[0].x-vertices[nvertices-1].x, vertices[0].y-vertices[nvertices-1].y};seg cur = {vertices[nvertices-1], vertices[0], dir};
	edges[nvertices-1] = cur; // The last edge is between the first vertex and the last vertex
	polygon shape = {nvertices, vertices, edges};
	return shape;
}

furthermore, a convenience function to create polygons without having to initialize the array for the vertices beforehand:

polygon Polygon(int nvertices, ...){
	va_list args;
	va_start(args, nvertices);
	vec *vertices = (vec*)malloc(sizeof(vec)*nvertices);
	int i;
	for (i = 0; i < nvertices; i++){
		vertices[i] = va_arg(args, vec);
	}
	va_end(args);
	return new_polygon(nvertices, vertices);
}

Polygons, Lua:

function polygon(vertices)
	local obj = {}
	obj.vertices = vertices
	obj.edges = {}
	for i=1,#vertices do
		table.insert(obj.edges, segment(vertices[i], vertices[1+i%(#vertices)]))
	end
	return obj
end

Example, C

polygon a = Polygon(4, v(0,0),v(0,3),v(3,3),v(3,0)), b = Polygon(4, v(4,4),v(4,6),v(6,6),v(6,4));

Example, Lua

a = polygon{v(0,0),v(0,1),v(1,1),v(1,0)}

8. Onto the Algorithm

First, we need to choose an axis and find the projection of the entire shape onto that line. What we’re really asking however isn’t so much the entire shadow, but whether it begins and where it ends. This can be simply expressed as an array or a vector. If we take the dot product of a point with a unit vector, it will give you the distance from the origin where the point will show up on the vector. While this may be an intangible location, since everything else is relative to that unit vector, this distance is sufficient to determine the min and max (begin, end) points of the polygon projection.

Projection, C

float* project(polygon a, vec axis){
	axis = normalize(axis);
	int i;
	float min = dot(a.vertices[0],axis); float max = min; // min and max are the start and finish points
	for (i=0;i<a.n;i++){
		float proj = dot(a.vertices[i],axis); // find the projection of every point on the polygon onto the line.
		if (proj < min) min = proj; if (proj > max) max = proj;
	}
	float* arr = (float*)malloc(2*sizeof(float));
	arr[0] = min; arr[1] = max;
	return arr;
}

Projection, Lua

-- We keep a running range (min and max) values of the projection, and then use that as our shadow

function project(a, axis)
	axis = normalize(axis)
	local min = dot(a.vertices[1],axis)
	local max = min
	for i,v in ipairs(a.vertices) do
		local proj =  dot(v, axis) -- projection
		if proj < min then min = proj end
		if proj > max then max = proj end
	end

	return {min, max}
end

9. Almost There…

Now, we need to find whether the two projections overlap. Since the projection is represented by two numbers, we need to only check if every one of the four numbers found in the two projections are in range of the other projection.

C:

int contains(float n, float* range){
	float a = range[0], b = range[1];
	if (b<a) {a = b; b = range[0];}
	return (n >= a && n <= b);
}

int overlap(float* a_, float* b_){
	if (contains(a_[0],b_)) return 1;
	if (contains(a_[1],b_)) return 1;
	if (contains(b_[0],a_)) return 1;
	if (contains(b_[1],a_)) return 1;
	return 0;
}

Lua:

function contains(n, range)
	local a, b = range[1], range[2]
	if b < a then a = b; b = range[1] end
	return n >= a and n <= b
end

function overlap(a_, b_)
	if contains(a_[1], b_) then return true
	elseif contains(a_[2], b_) then return true
	elseif contains(b_[1], a_) then return true
	elseif contains(b_[2], a_) then return true
	end
	return false
end

10. Putting it all together

Now that we have all of the necessary components, we can piece it all together into a single function.

SAT, C:

int sat(polygon a, polygon b){
	int i;
	for (i=0;i<a.n;i++){
		vec axis = a.edges[i].dir; // Get the direction vector
		axis = perp(axis); // Get the normal of the vector (90 degrees)
		float *a_ = project(a,axis), *b_ = project(b,axis); // Find the projection of a and b onto axis
		if (!overlap(a_,b_)) return 0; // If they do not overlap, then no collision
	}

	for (i=0;i<b.n;i++){ // repeat for b
		vec axis = b.edges[i].dir;
		axis = perp(axis);
		float *a_ = project(a,axis), *b_ = project(b,axis);
		if (!overlap(a_,b_)) return 0;
	}
	return 1;
}

SAT, Lua:

function sat(a, b)
	for i,v in ipairs(a.edges) do
		local axis = perp(v)
		local a_, b_ = project(a, axis), project(b, axis)
		if not overlap(a_, b_) then return false end
	end
	for i,v in ipairs(b.edges) do
		local axis = perp(v)
		local a_, b_ = project(a, axis), project(b, axis)
		if not overlap(a_, b_) then return false end
	end

	return true
end

Example usages, C:

polygon a = Polygon(4, v(0,0),v(0,3),v(3,3),v(3,0)), b = Polygon(4, v(4,4),v(4,6),v(6,6),v(6,4));
printf("%d\n", sat(a,b)); // false

a = Polygon(4, v(0,0),v(0,5),v(5,4),v(3,0));  b = Polygon(4, v(4,4),v(4,6),v(6,6),v(6,4));
printf("%d\n", sat(a,b)); // true

Example usage, Lua

a = polygon{v(0,0),v(0,5),v(5,4),v(3,0)}
b = polygon{v(4,4),v(4,6),v(6,6),v(6,4)}

print(sat(a,b)) -- true

11. Complete Code Listings

There we have it, a complete implementation of a convex polygonal collision detection algorithm that’s efficient in cases where the collision-to-polygon ration is relatively low. Here’s the full code listing:

C:

#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

// Separate Axis Theorem implemented via C99

typedef struct {float x, y;} vec;
typedef struct {vec p0, dir;} ray;
typedef struct {vec p0, p1, dir;} seg;
typedef struct {int n; vec *vertices; seg *edges;} polygon; // Assumption: Simply connected => chain vertices together

polygon new_polygon(int nvertices, vec *vertices){
	seg *edges = (seg*)malloc(sizeof(seg)*(nvertices));
	int i;
	for (i = 0; i < nvertices-1; i++){
		vec dir = {vertices[i+1].x-vertices[i].x, vertices[i+1].y-vertices[i].y};seg cur = {vertices[i], vertices[i+1], dir};
		edges[i] = cur;
	}
	vec dir = {vertices[0].x-vertices[nvertices-1].x, vertices[0].y-vertices[nvertices-1].y};seg cur = {vertices[nvertices-1], vertices[0], dir};
	edges[nvertices-1] = cur;
	polygon shape = {nvertices, vertices, edges};
	return shape;
}

vec v(float x, float y){
	vec a = {x, y};
	return a;
}

vec perp(vec v){
	vec b = {v.y, -v.x};
	return b;
}

seg segment(vec p0, vec p1){
	vec dir = {p1.x-p0.x, p1.y-p0.y};
	seg s = {p0, p1, dir};
	return s;
}

polygon Polygon(int nvertices, ...){
	va_list args;
	va_start(args, nvertices);
	vec *vertices = (vec*)malloc(sizeof(vec)*nvertices);
	int i;
	for (i = 0; i < nvertices; i++){
		vertices[i] = va_arg(args, vec);
	}
	va_end(args);
	return new_polygon(nvertices, vertices);
}

vec normalize(vec v){
	float mag = sqrt(v.x*v.x + v.y*v.y);
	vec b = {v.x/mag, v.y/mag};
	return b;
}

float dot(vec a, vec b){
	return a.x*b.x+a.y*b.y;
}

float* project(polygon a, vec axis){
	axis = normalize(axis);
	int i;
	float min = dot(a.vertices[0],axis); float max = min;
	for (i=0;i<a.n;i++){
		float proj = dot(a.vertices[i],axis);
		if (proj < min) min = proj; if (proj > max) max = proj;
	}
	float* arr = (float*)malloc(2*sizeof(float));
	arr[0] = min; arr[1] = max;
	return arr;
}

int contains(float n, float* range){
	float a = range[0], b = range[1];
	if (b<a) {a = b; b = range[0];}
	return (n >= a && n <= b);
}

int overlap(float* a_, float* b_){
	if (contains(a_[0],b_)) return 1;
	if (contains(a_[1],b_)) return 1;
	if (contains(b_[0],a_)) return 1;
	if (contains(b_[1],a_)) return 1;
	return 0;
}

int sat(polygon a, polygon b){
	int i;
	for (i=0;i<a.n;i++){
		vec axis = a.edges[i].dir;
		axis = perp(axis);
		float *a_ = project(a,axis), *b_ = project(b,axis);
		if (!overlap(a_,b_)) return 0;
	}
	for (i=0;i<b.n;i++){
		vec axis = b.edges[i].dir;
		axis = perp(axis);
		float *a_ = project(a,axis), *b_ = project(b,axis);
		if (!overlap(a_,b_)) return 0;
	}
	return 1;
}

Lua:

-- vectors are just lists
-- segments are tables: {start = vect, end = vect, dir = vect}
-- polygons includes {vertices = {vectors}, edge = {vectors}} 

function vec(x, y)
	return {x, y}
end

v = vec -- shortcut

function dot(v1, v2)
	return v1[1]*v2[1] + v1[2]*v2[2]
end

function normalize(v)
	local mag = math.sqrt(v[1]^2 + v[2]^2)
	return vec(v[1]/mag, v[2]/mag)
end

function perp(v)
	return {v[2],-v[1]}
end

function segment(a, b)
	local obj = {a=a, b=b, dir={b[1] - a[1], b[2] - a[2]}}
	obj[1] = obj.dir[1]; obj[2] = obj.dir[2]
	return obj
end

function polygon(vertices)
	local obj = {}
	obj.vertices = vertices
	obj.edges = {}
	for i=1,#vertices do
		table.insert(obj.edges, segment(vertices[i], vertices[1+i%(#vertices)]))
	end
	return obj
end

function project(a, axis)
	axis = normalize(axis)
	local min = dot(a.vertices[1],axis)
	local max = min
	for i,v in ipairs(a.vertices) do
		local proj =  dot(v, axis) -- projection
		if proj < min then min = proj end
		if proj > max then max = proj end
	end

	return {min, max}
end

function contains(n, range)
	local a, b = range[1], range[2]
	if b < a then a = b; b = range[1] end
	return n >= a and n <= b
end

function overlap(a_, b_)
	if contains(a_[1], b_) then return true
	elseif contains(a_[2], b_) then return true
	elseif contains(b_[1], a_) then return true
	elseif contains(b_[2], a_) then return true
	end
	return false
end


function sat(a, b)
	for i,v in ipairs(a.edges) do
		local axis = perp(v)
		local a_, b_ = project(a, axis), project(b, axis)
		if not overlap(a_, b_) then return false end
	end
	for i,v in ipairs(b.edges) do
		local axis = perp(v)
		local a_, b_ = project(a, axis), project(b, axis)
		if not overlap(a_, b_) then return false end
	end

	return true
end

12. Additional Reading

Posted By Lee

Woosh

  • 0failbit

    Great article, but I noticed a memory leak in the function sat. Simple fix though.

    [code]

    for (i=0;i<a.n;i++){
    vec axis = a.edges[i].dir; // Get the direction vector
    axis = perp(axis); // Get the normal of the vector (90 degrees)
    float *a_ = project(a,axis), *b_ = project(b,axis); // Find the projection of a and b onto axis
    int o = overlap(a_,b_); free(a_); free(b_); // free mem if ( !o ) return 0;
    }[/code]

  • Guest

    you are casting the return value of malloc, which is a bad idea, and you are missing the function keywords for the C functions?

  • Pingback: beat maker programs()

  • Max

    After you call these lines below, don’t you have to free the a and b vertices and edges? I tried this with the fix included by 0failbit and I was getting significant memory leaks when running this on thousands of polygons. You can’t forget to free memory after allocating it.

    polygon a = Polygon(4, v(0,0),v(0,3),v(3,3),v(3,0)), b = Polygon(4, v(4,4),v(4,6),v(6,6),v(6,4));
    sat(a,b));

    Do you need these lines after?
    free (a.vertices);
    free (a.edges);
    free (b.vertices);
    free (b.edges);

Recent Comments