Separation of axis theorem implementation

Question

I have been following the this guide to implement this. My current implementation is the following:

class SAT {

  SAT();

  bool collides(Rectangle rect1, Rectangle rect2){
    var axises = [
                  rect1.topRight-rect1.topLeft,
                  rect1.topRight-rect1.bottomRight,
                  rect2.topLeft-rect2.bottomLeft,
                  rect2.topLeft-rect2.topRight
                  ];

    for(var axis in axises){
      Projection p1 = project(axis,rect1); 
      Projection p2 = project(axis,rect2); 
      if(!overlap(p1,p2)){
        return false;
      }
    }
    return true;    
  }

  Projection project(Position axis, Rectangle rect){
    Position projection = getProjectionPosition(axis,rect);
    Collection<Position> corners = [rect.topLeft,rect.topRight,rect.bottomRight,rect.bottomLeft];
    num min = dot(projection,corners[0]);
    num max = min;
    for(var i = 1; i < corners.length; i++){
      num p = dot(projection,corners[i]);
      if(p < min){
        min = p;
      }else if(p > max){
        max = p;
      }
    }
    return new Projection(min,max);
  }

  bool overlap(Projection p1, Projection p2){
    return p1.max >= p2.min && p1.min <= p2.max;
  }

  num dot(Position projection, Position point){
    return projection.x*point.x + projection.y*point.y;  
  }

  Position getProjectionPosition(Position axis, Rectangle rect){
    num p = (rect.topRight.x*axis.x+rect.topRight.y*axis.y)/(Math.pow(axis.x, 2)+Math.pow(axis.y, 2));
    Position projected = new Position(p*axis.x,p*axis.y);
    return projected;
  }
}

However this doesn't seem to work. I think I might be a bit confused about the getProjectionPosition algorithm, as you can see I always use rect.topRight. But maybe I am supposed to loop trough all the corners of the rectangle? or should it just be the corner belonging to this axis? The guide wasn't very clear on this.

Any ideas on whats wrong? Or is there a reference implementation I could look at to see how my implementation differs?

Answer 1

I'm not sure what getProjectionPosition is trying to accomplish at all. To project a set of points on an axis, you can just dot them with the axis vector. (It implicitly uses the origin of coordinates as the origin of the axis, which is fine.) So I think you can leave out the whole getProjectionPosition function and just do dot(axis,corners[i]) in your project function.

On the other hand, I don't think that's where your problem is, since getProjectionPosition is just rescaling the axis vector by a number p, which shouldn't change the results of the overlap test; all the dot products will just be scaled by p as well. The rest of your code looks OK to me, though, so I'm not sure what's causing your test not to work correctly.

Answer 2

Solved it by changing the code a bit.

class SAT {

  SAT();

  bool collides(Rectangle a, Rectangle b){
    var axises = [
        a.topRight - a.topLeft,
        a.topRight - a.bottomRight,
        b.topLeft - b.bottomLeft,
        b.topLeft - b.topRight
    ];

    for(var axis in axises){
      Projection p1 = _project(axis,a);
      Projection p2 = _project(axis,b);
      if(!_overlap(p1,p2)){
        return false;
      }
    }
    return true;    
  }

  Projection _project(Point axis, Rectangle rect){
      Collection<Point> corners = [rect.topLeft, rect.topRight, rect.bottomRight, rect.bottomLeft];
      Point projection = _projectionPoint(axis, corners[0]);
      num min = _dot(projection, corners[0]);
      num max = min;
      for (var i = 1; i < corners.length; i++) {
          projection = _projectionPoint(axis, corners[i]);
          num p = _dot(projection, corners[i]);
          if (p < min) {
              min = p;
          } else if (p > max) {
              max = p;
          }
      }
      return new Projection(min, max);
  }

  bool _overlap(Projection p1, Projection p2){
    return p1.max >= p2.min && p1.min <= p2.max;
  }

  num _dot(Point projection, Point point){
    return projection.x*point.x + projection.y*point.y;
  }

  Point _projectionPoint(Point axis, Point vertice){
    num p = (vertice.x+vertice.y)/(axis.x+axis.y);
    return new Point(p*axis.x,p*axis.y);
  }
}

Basically i needed to change the implementation to check against the correct vertice of the rectangle. in my code above i only checked against the upper right corner of the first rectangle.