# Error in my Separating Axis Theorem collision code [closed]

EDIT 2: Made some more alterations, now the one area i'm still confused on is: how to work out the vector to project on the separation axes? My projectOnto(..) method has some huge gaps now and i know i need to use the dot product but i don't really understand how to. I left my old code in there commented out so you can see what i was trying to do following an article on SAT but i don't really understand how it works. Appreciate any help!

EDIT: Made several alterations thanks to suggestions below but the problem is still the very same.

The only collision experience i've had was with simple rectangles, i wanted to find something that would allow me to define polygonal areas for collision and have been trying to make sense of SAT using these two links

Though i'm a bit iffy with the math for the most part i feel like i understand the theory! Except my implementation somewhere down the line must be off as:

(excuse the hideous font) As mentioned above i have defined a CollisionPolygon class where most of my theory is implemented and then have a helper class called Vect which was meant to be for Vectors but has also been used to contain a vertex given that both just have two float values.

I've tried stepping through the function and inspecting the values to solve things but given so many axes and vectors and new math to work out as i go i'm struggling to find the erroneous calculation(s) and would really appreciate any help. Apologies if this is not suitable as a question!

CollisionPolygon.java:

package biz.hireholly.gameplay;

import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import biz.hireholly.gameplay.Types.Vect;

public class CollisionPolygon {

Paint paint;

private Vect[] vertices;
private Vect[] separationAxes;
int x; //actually the positions of the object that owns this CollisionPolygon
int y;

CollisionPolygon(Vect[] vertices){

this.vertices = vertices;
//compute edges and separations axes
separationAxes = new Vect[vertices.length];
for (int i = 0; i < vertices.length; i++) {
// get the current vertex
Vect p1 = vertices[i];
// get the next vertex
Vect p2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
// subtract the two to get the edge vector
Vect edge = p1.subtract(p2);
// get either perpendicular vector (my perp method returns (y, -x)
// then get a nomralized version
Vect normal = edge.perp().normalize();
separationAxes[i] = normal;
}

paint = new Paint();
paint.setColor(Color.RED);

}

public void draw(Canvas c){
if(x != 0 && y != 0){
for (int i = 0; i < vertices.length; i++) {
Vect v1 = vertices[i];
Vect v2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
c.drawLine(
x + v1.x,
y + v1.y,
x + v2.x,
y + v2.y,
paint);
}
}
}
public void update(int xPos, int yPos){
x = xPos;
y = yPos;
}

/* consider changing to a static function */
public boolean intersects(CollisionPolygon p){

// loop over this polygons separation exes
for (Vect axis : separationAxes) {
// project both shapes onto the axis
Vect proj1 = this.projectOnto(axis);
Vect proj2 = p.projectOnto(axis);
// do the projections overlap?
if (!proj1.overlap(proj2)) {
// then we can guarantee that the shapes do not overlap
return false;
}
}

// loop over the other polygons separation axes
Vect[] sepAxesOther = p.getSeparationAxes();
for (Vect axis : sepAxesOther) {
// project both shapes onto the axis
Vect proj1 = this.projectOnto(axis);
Vect proj2 = p.projectOnto(axis);
// do the projections overlap?
if (!proj1.overlap(proj2)) {
// then we can guarantee that the shapes do not overlap
return false;
}
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return true;
}

private Vect projectOnto(Vect axis) {
//When using the dot function we take into account the absolute position using the owning objects x & y
//   Not entirely certain if neccessary? appears to make no difference for the moment at least..

//TODO: need some sort of loop to figure out a vector that represents the max breadth of the polygon onto the current separation axes

//This is the simplified formula for projecting a vector onto a normalised vector (the axis)

/*
* OLD FUNCTIONLITY
float min = axis.dot(new Vect(vertices.x+x, vertices.y+y));
float max = min;
for (int i = 1; i < vertices.length; i++) {
float p = axis.dot(new Vect(vertices[i].x+x, vertices[i].y+y));
if (p < min) {
min = p;
}
else if (p > max) {
max = p;
}
}
Vect minMaxProj = new Vect(min, max);
return minMaxProj;*/

}

public Vect[] getSeparationAxes() {
return separationAxes;
}

public Vect[] getVertices() {
return vertices;
}

}


Vect.java:

    package biz.hireholly.gameplay.Types;

/* NOTE: Can also be used to hold vertices! Projections, coordinates ect */

public class Vect{
public float x;
public float y;

public Vect(float x, float y){
this.x = x;
this.y = y;
}

public Vect perp() {
return new Vect(y, -x);
}

public Vect subtract(Vect other) {
return new Vect(x - other.x, y - other.y);
}

public boolean overlap(Vect other) {
if(y > other.x && other.y > x){
return true;
}
return false;
}
/* used specifically for my SAT implementation which i'm figuring out as i go,
* references for later..
* http://www.gamedev.net/page/resources/_/technical/game-programming/2d-rotated-rectangle-collision-r2604
* http://www.codezealot.org/archives/55
*/
/* doing away with..
public float scalarDotProjection(Vect other) {
//multiplier = dot product / length^2
float multiplier = dot(other) / (x*x + y*y);
//to get the x/y of the projection vector multiply by x/y of axis
float projX = multiplier * x;
float projY = multiplier * y;
//we want to return the dot product of the projection, it's meaningless but useful in our SAT case
return dot(new Vect(projX,projY));

}*/
public float dot(Vect other){
return (other.x*x + other.y*y);
}
public float length(){
return (float)Math.sqrt((x*x + y*y));
}
public Vect normalize(){
return new Vect( x / length(), y / length());
}
public Vect multiplyByScalar(float s){
return new Vect(x*s, y*s);
}
}


## closed as too localized by Anko, MichaelHouse♦, bummzack, Trevor Powell, Josh♦May 2 '13 at 16:32

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

Your draw method takes two parameters xPos & yPos. is this the position of the object? If so then you also need to add xPos & yPos to your vertices when projecting on to an axis. If 'pos' is the position of the shape then you project as follows;

float p = axis.dot(new Vect(vertices[i].x+xPos, vertices[i].y+yPos);


float p = axis.dot(vertices[i]);


You need to project the absolute position of the vertex rather than the relative (to the centre) position of the vertex.

• One again thank you for taking the time to try and help me! But i'm afraid the results produced with those exact changes remain exactly the same as before! Since the axis was originally worked out using the vertices without taking into account the x/yPos of the object i don't think that they need to be taken into account during the projection either.. You make a good point with regards to absolute vs relative but i don't think thats the issue here? – Holly Oct 20 '12 at 19:35
• Yes, the axes are fine (unless there are any rotations), they are independent of object position (they are vectors). But when projecting vertices(points), you have to take into account the change of position of the objects. – Ken Oct 20 '12 at 19:40
• Right thanks, i guess that makes sense but i still have the same problem.. is xPos in you code above the xPos of the Object that owns the CollisionPolygon (as it is in the draw function)? Or is xPos above supposed to be the xPos of the CollisionPolygon? – Holly Oct 20 '12 at 19:50
• it's the position of the object that owns the polygon. Same as the xPos in your Draw method? – Ken Oct 20 '12 at 20:05
• Can we see the update method? – Ken Oct 20 '12 at 20:46

It looks like your overlap method isn't correct. I think it should be;

if(!(y<other.x || other.y < x))
return true;


or equivalently;

if(y > other.x && other.y > x)
return true;

• Thanks for taking a look! But your overlap condition produces the same results. I think its more likely to be the vector / projection math i've gone awry with somewhere.. – Holly Oct 20 '12 at 16:06
• hmmm, your overlap check is definitely wrong. It's returning true if the min of other is less than max, that can be true even if there is no overlap. – Ken Oct 20 '12 at 17:33
• Ah my bad you're absolutely right my check was wrong, i have updated my overlap method in the code above and believe it should now make sense (though it is different from yours) ? However my original problem posted above it still the same! – Holly Oct 20 '12 at 17:46
• You overlap check will still miss the case when 'this' range is completely inside the 'other' range. It only check if part of 'other' is inside 'this'. My overlap code assumes there is an overlap if both x's are less than both y's. – Ken Oct 20 '12 at 17:53
• Ah thank you for your patience i'm sorry, gotcha now and have replaced my code with yours! but as before the same problem as in the original question persists. – Holly Oct 20 '12 at 18:27

So there are a couple of problems I see right away. The first is that you are not actually normalizing the "normals" of your CollisionPolygon's faces. The second is that when you do your vector projections you want the projected vector, and not it's dot product with the vector you're projecting. So you might want to have a projection function that looks like this:

public Vect projectOnto(Vect other) {
float denominator = other.dot(other);
// Might want to check for denominator == 0
return other.scale((this.dot(other) / denominator);


You can use that to project the half-vectors of your polygons onto the separating axes.

The next problem I see is your overlap function in the Vect class. I'm not exactly sure what it's supposed to be checking; perhaps you can clarify? I interpret it to check if two vectors, being treated as lines, intersect. While it seems like those comparisons may be accurate, it will not actually acurately determine a line intersection, nor will it be useful for the Separating Axis Theorem.

The idea of SAT is that an axis separates two polygons if half the sum of the projected polygons onto that axis is greater than the length of the projection of the vector between them. I've found Metanet Software to provide the best explanation of SAT, for various shapes.

So, I think if you modify your intersection code to be doing length checks rather than line intersection checks, and also fix the normalization of your separating axes, your code should work. There may still be a few tweaks to make after that. The combination of bugs is what makes this difficult to debug.

Hope this helps :)

• sorry about the late reply! thank you very much for the helpful comments. I've gone through and altered it so my normals are now normalized for certain and i've also dug out the proper formula for projecting one vector onto another (i will update the code in my question in a mo). The one area i'm still confused on is: how to work out the vector to project on the separation axes? Perhaps you code snippet explains this but i'm afraid i couldn't make much sense of it! Could you possibly alter/comment upon your code above to explain how it works some more? – Holly Oct 25 '12 at 14:17
• for example what is the 'denominator' and how exactly does the dot product help us figure out the widest part of the polygon in relation to the separation axes we want to project onto? – Holly Oct 25 '12 at 14:17
• demonimator is just part of the projection calculation. That function isn't the bit which determines what vectors to project on to the axis, but merely handles the projection (you will call that function on the vector you want to project, and pass the axis). There are several ways you can figure out what vector(s) to project. One option is to project all of the edges and take the result that has the largest length. There's a quicker way to do it if you store your polygons with half-vectors describing their width and height. I'm not sure how that would work with 5+ sides though – kevintodisco Oct 26 '12 at 4:09

I'd like to propose a different method. Although I could see the dot-method working, it seems to require tracking a lot of data relative to each edge. I would argue that it might be simpler (this is really debatable) to use cross products. I'll downplay the difficulty in creating a new vector3 class...but on the plus side it really only needs a static cross() function, and possibly a few constructors:

When applied to flat (z = 0) 3-vectors, the cross product can tell you which side of a line contains a point by using the right-hand rule. In your case, if the point is on the right-hand side of every edge, then it must be inside the shape. So: if the cross product of every edge of the polygon with a new vector3 based on the colliding vertex all have a positive sign, then you have a collision. Psuedo-code for a collision detector function which examines polygons A and B:

bool isCollision = true

for(i = 1; i < A.vertices.count; i++) {
foreach (Vect bVert in B.verticies) {
// loop around the end of A.vertices ,

// as in your code, the edge vector
edge = A.vertex[i] - A.vertex[i - 1]

// 3-vector along the edge
edge3 = new Vector3(edge.x, edge.y, 0)

// 3-vector from leading point of edge to potential colliding vertex
vertvect = bVert - A.vertex[i]
vertvect3 = new Vector3(vertvec.x, vertvec.y, 0)

// get output 3-vector...
pointCross = Vector3::cross(edge3, vertvect3)
// ...and check to see if it points up or down
if (pointCross.z < 0) {  // it is on the left
// ergo the point is outside your shape
isCollision = false
// exit this double loop as early as possible
break foreach;
}
}
if (!isCollision){
break for;
}
}

return isCollision


When it comes time to implement a cross prodcut, that wikipedia page links to the involved math. :)

Here is the separation code I wrote for a project a while ago (it's in c++, but the logic is the important thing). The Separated method takes a normal vector (it doesn't have to be normalized for the SAT to work), and all the world coordinates for the two objects. This code is written for triangles, hence the loops to 3. But should world for any convex polygon. Hope it helps.

static bool CheckForCollisionSAT(Triangle* t1,Triangle* t2){ SATcount++; sf::Vector2f verts1; sf::Vector2f verts2; t1->GetVerts(verts1); t2->GetVerts(verts2);

    sf::Vector2f normals1;
sf::Vector2f normals2;
t1->GetNormals(normals1);
t2->GetNormals(normals2);

for(int i=0;i<3;i++){
bool sep;
sep=Separated(normals1[i],verts1,verts2);
if (sep) return false;//no collision
sep=Separated(normals2[i],verts1,verts2);
if (sep) return false;//no collision
}

return true;

}

bool static Separated(sf::Vector2f normal,sf::Vector2f verts1[],sf::Vector2f verts2[]){
float min1=FLT_MAX;
float min2=FLT_MAX;
float max1=-FLT_MAX;
float max2=-FLT_MAX;
for(int i=0;i<3;i++){//project t2 on to 1's normals
float d=Vector::dot(normal,verts2[i]);
if(d>max2) max2=d;
if(d<min2) min2=d;
}
for(int i=0;i<3;i++){//project t1 on to 1's normals
float d=Vector::dot(normal,verts1[i]);
if(d>max1) max1=d;
if(d<min1) min1=d;
}

if(max1<min2 || max2 <min1) //check for overlap
return true;

return false; //no separation on this normal
}