   Falsely detected collisions when using Separation of Axis Theorum
  I have been writing my own physics engine based on the "Poly Colly" tuts released by Oli.The collision code is more or less copied straight from his tutorial, with a few minor adjustments to account for my own Vector and Polygon classes.When I test the program by moving around a polygon in relation to a static polygon, it will always correctly register a collision.However, it will also sometimes register a collision when certain vertices/edges are close to each other, but not touching.When the polygons to be tested against each other have only 2 verts (eg, lines) there will be a space the length of the static line, projected along the direction of the moving line, which if occupied by the moving line will incorrectly register a collision.Following is the code for the detection algorithm:// PolyColy.cpp: implementation of the CPolyColy class.////////////////////////////////////////////////////////////////////////#include "PolyColy.h"//////////////////////////////////////////////////////////////////////// Construction/Destruction//////////////////////////////////////////////////////////////////////CPolyColy::CPolyColy(){}CPolyColy::~CPolyColy(){}bool CPolyColy::Intersect(C2DPoly* A, C2DPoly* B){//loop through every edge of polygon A.for(int j = A->GetNumVerts()-1, i = 0; i < A->GetNumVerts()-1; j = i, i ++) { //create vector from two adjacent vertices    Vector2D E = (A->GetVertex(i)) - A->GetVertex(j); //find the normal of this vectorfloat negativey = 0 - E.y;    Vector2D N = Vector2D(E.x, negativey); //test if edge is a separation axis    if (AxisSeparatePolygons(N, A, B))    return false; }i = 0;for(j = B->GetNumVerts()-1; i < B->GetNumVerts()-1; j = i, i ++) {Vector2D E = (B->GetVertex(i)) - B->GetVertex(j); float negativey = 0 - E.y;    Vector2D N = Vector2D(E.x, negativey);if (AxisSeparatePolygons(N, A, B))    return false; }return true;}bool CPolyColy::AxisSeparatePolygons(Vector2D Axis, C2DPoly* A, C2DPoly* B){float mina, maxa;   //store the minimum and maximum projected values for each polygon    float minb, maxb; //project all vertices onto normal using dot productCalculateInterval(Axis, A, mina, maxa);CalculateInterval(Axis, B, minb, maxb); //test for overlap between intervals    if (mina > maxb || minb > maxa)    return true; return false;}void CPolyColy::CalculateInterval(Vector2D Axis, C2DPoly* P, float& min, float& max) { //project first vert onto axis using dot product    float d = Axis.dot(P->GetVertex(0)); //assign both min and max to d    min = max = d; //project each vert onto axis. Replace min or max if it is smaller or larger    for(int I = 0; I < P->GetNumVerts(); I ++){    float d = Axis.dot(P->GetVertex(I));   if (d < min)   min = d;    else    if(d > max)   max = d;} }I'm sure I must be missing something obvious. Any help is appreciated.   
  I didn't look any farther than this line, but this:Vector2D N = Vector2D(E.x, negativey);Should be either:Vector2D N = Vector2D(-E.y,E.x);Or:Vector2D N = Vector2D(E.y,-E.x);Also, don't forget to change it both times it occurs.   ;  My vector class places the x value first. This is consistent throughout, so it shouldn't be causing the problem.negativey was a workaround for a potential problem with the vector class. It was taken from nehe, and there is an operator which either returned a negative Vector2D, or reversed the current Vector2D. To be on the safe side I'm using this sloppy method until I deterimine if it will be a problem or not. You are correct though, it's not good practice.Also, the problem does not occur with two axis aligned boxes. Nor does it happen when a single box is rotated by 45 degrees. It does however occur when a single box is rotated by anything not divisable by 45.   ;Quote:Original post by CIJollyMy vector class places the x value first. This is consistent throughout, so it shouldn't be causing the problem.No, really, make the change that jyk is telling you to do!  The point is that given any 2D vector V = (x, y), the perpendicular vector to V is given by N = (-y, x) or, if you prefer, by N = (y, -x) as there are two choices of perpendicular vectors.  If this doesn't make sense, try graphing the vector (2, 1) on a piece of graph paper and you'll see that the two possible perpendiculars are (-1, 2) and (1, -2).So, the two lines you have that involve initializing N are wrong and should read just as jyk suggested.  There may be other errors, but those two lines are definitely wrong.;  Do'h! Right, now I get what you're saying. Sorry, I thought you were having me up on the format of my Vector Class, not how I calculated my normal.I'll just make that little change, and...Works like a charm, Thanks a bunch. I KNEW it would be some stupid little bug, and I was going through all my for loops and +/- signs with a fine tooth comb. Since it detected collisions some of the time, I figured the basic algorithm must have been working...ah well, you learn more from your mistakes.Thanks jyk and Christer, you just saved me (another) couple of days fruitless experimentation.   