Question

Collision detection for concave polygons with SAT, round/off error optimization

Basically I want to create my own tools for developing a 2D top-down game and when it comes to collision detection I'm trying to implement the SAT method, but somehow my calculations seem to be way off from expected in certain situation (see picture below). Collision Detector returns true And at other times they are super accurate (2nd picture) returns false, which is correct

I mostly followed dyn4j's implementation and even tho only sub-optimally, but it seems to be working. So ultimately my guess is that it's some sort of rounding error in the calculations, but I'm not sure if it should/could be this big. If you have any suggestions on how to modify my methods, or where else to look for issues it'd be much appreciated!

The classes mainly concerned with the checks and calculations are CollisionDetector:

public static boolean checkCollision(Collidable e1, Collidable e2){

    double[][] shape1 = e1.getVerteces();
    double[][] shape2 = e2.getVerteces();
    
    double[][] axis1 = getAxis(shape1);
    double[][] axis2 = getAxis(shape2);

    //Check for overlap on 1st shape's axis
    for(int i=0; i<axis1.length; i++){
        double[] axis = axis1[i];

        double[] proj1 = project(shape1, axis);
        double[] proj2 = project(shape2, axis);
        if(!overlap(proj1, proj2)){
            return false;
        }
    }
    //Check for overlap on 2nd shape's axis
    for(int i=0; i<axis2.length; i++){
        double[] axis = axis2[i];

        double[] proj1 = project(shape1, axis);
        double[] proj2 = project(shape2, axis);
        if(!overlap(proj1, proj2)){
            return false;
        }
    }
    //Everything overlaps so return true
    return true;
    
}

private static boolean overlap(double[] proj1, double[] proj2) {
    return !(proj1[1] < proj2[0] || proj2[1] < proj1[0]);
}

private static double[] project(double[][] hitboxPoints, double[] axis) {
    
    double min = Double.MAX_VALUE;
    double max = Double.MIN_VALUE;
    double[] normalizedAxis = Vector.normalize(axis);

    for(int i = 0; i < hitboxPoints.length; i++){
        double[] point = {hitboxPoints[i][0], hitboxPoints[i][1]};
        double projection = Vector.dotProduct(point, normalizedAxis);
        if(projection < min){
            min = projection;
        }
        if(projection > max){
            max = projection;
        }
    }
    return new double[]{min, max};
}

private static double[][] getAxis(double[][] verteces){
    double[][] axis = new double[verteces.length][2];
    for(int i = 0; i < verteces.length; i++){
        int j = (i+1)%verteces.length;

        double[] p1 = {verteces[i][0], verteces[i][1]};
        double[] p2 = {verteces[j][0], verteces[j][1]};
        double[] normal = Vector.getNormal(p1, p2);
        axis[i][0] = normal[0];
        axis[i][1] = normal[1];
    }
    return axis;
}

and my Vector class for vector math:

public static double[] normalize(double[] axis) {
    double[] normalized = new double[axis.length];
    double magnitude = magnitude(axis);
    for(int i = 0; i < axis.length; i++){
        if(axis[i] != 0){
            normalized[i] = (axis[i]/magnitude);
        }
    }
    return normalized;
}

public static double magnitude(double[] axis) {
    
    double sum = 0;
    for(int i = 0; i < axis.length; i++){
        sum += axis[i]*axis[i];
    }
    return Math.sqrt(sum);
}

public static double[] getNormal(double[] p1, double[] p2) {
    
    double[] edge = {p2[0] - p1[0], p2[1] - p1[1]};
    double[] normal = {edge[1], -edge[0]};
    return normal;
}

public static double dotProduct(double[] point, double[] normalizedAxis) {
    
    double sum = 0;
    for(int i = 0; i < point.length; i++){
        sum += point[i]*normalizedAxis[i];
    }

    return sum;
}

Possibly relevant parts of my Triangle class:

double screenX;
double screenY;
double moveSpeed;
public void update() {

    if(keyH.isPressed("RIGHT")) {
        direction = "right";
        screenX += moveSpeed;
        screenPos.add(new Vector2D(moveSpeed, 0));
    } else if(keyH.isPressed("LEFT")) {
        direction = "left";
        screenX -= moveSpeed;
        screenPos.add(new Vector2D(-moveSpeed, 0));
    } else if(keyH.isPressed("UP")) {
        direction = "up";
        screenY -= moveSpeed;
        screenPos.add(new Vector2D(0, -moveSpeed));
    } else if(keyH.isPressed("DOWN")) {
        direction = "down";
        screenY += moveSpeed;
        screenPos.add(new Vector2D(0, moveSpeed));
    }

    for(int i = 0; i < hitboxPoints.size(); i++){
        xPoints[i] = hitboxPoints.get(i)[0] + screenX;
        yPoints[i] = hitboxPoints.get(i)[1] + screenY;
    }
}

public void draw(GraphicsContext gc) {
    gc.setStroke(Color.BLUE);
    gc.strokePolygon(xPoints, yPoints, hitboxPoints.size());
}

and it's parent class:

protected List<Integer[]> hitboxPoints;
protected double[] xPoints, yPoints;
protected boolean collision = false;


public CollidableEntity(List<Integer[]> points, double scale) {
    this.hitboxPoints = points;
    this.xPoints = new double[hitboxPoints.size()];
    this.yPoints = new double[hitboxPoints.size()];
    this.verteces = new Vector2D[hitboxPoints.size()];
    for(int i = 0; i < hitboxPoints.size(); i++){
        hitboxPoints.get(i)[0] = (int)(hitboxPoints.get(i)[0]*scale);
        hitboxPoints.get(i)[1] = (int)(hitboxPoints.get(i)[1]*scale);
        xPoints[i] = hitboxPoints.get(i)[0]; 
        yPoints[i] = hitboxPoints.get(i)[1];
        verteces[i] = new Vector2D(xPoints[i], yPoints[i]);
    }
}

public double[][] getVerteces(){

    double[][] verteces = new double[xPoints.length][2];
    for(int i = 0; i < hitboxPoints.size(); i++){
        verteces[i][0] = xPoints[i];
        verteces[i][1] = yPoints[i];
    }
    
    return verteces; 

}

edit: links removed from post to stay in line with site rules

2 34 2

1 Jan 1970