基于SAT的凹多边形碰撞检测：计算误差问题排查与优化求助

我正在开发一款2D俯视角游戏的自定义工具，尝试实现基于**分离轴定理（SAT）**的凹多边形碰撞检测，但部分场景下检测结果和预期偏差很大（误判碰撞），有些场景却完全准确。我主要参考dyn4j的实现，猜测问题来自计算中的舍入误差，但不确定这种误差是否会导致这么大的问题。希望得到修改建议或排查方向。

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);

    //检查第一个形状的轴上的投影重叠
    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;
        }
    }
    //检查第二个形状的轴上的投影重叠
    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;
        }
    }
    //所有轴投影都重叠，判定碰撞
    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;
}

Vector类 #

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;
}

Triangle类（相关部分） #

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());
}

父类CollidableEntity（相关部分） #

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; 

}

1. SAT对凹多边形的本质限制 #

SAT仅原生支持凸多边形，直接用在凹多边形上必然出现误判。解决方法是先将凹多边形剖分为多个凸多边形（比如三角剖分），再对每一对凸多边形执行SAT检测，只要有一对凸多边形碰撞，就判定原凹多边形碰撞。

2. 浮点精度问题修复 #

浮点舍入误差确实会导致边界误判，可通过以下方式处理：

• 在overlap方法中引入极小值（epsilon），避免精度问题导致的边界误判：

  private static final double EPSILON = 1e-6;
  private static boolean overlap(double[] proj1, double[] proj2) {
      return !(proj1[1] + EPSILON < proj2[0] || proj2[1] + EPSILON < proj1[0]);
  }
  

• 修复Vector.normalize方法的逻辑错误：原代码跳过了分量为0的赋值，会导致归一化数组出现错误的0值，且未处理零向量的情况：

  public static double[] normalize(double[] axis) {
      double[] normalized = new double[axis.length];
      double magnitude = magnitude(axis);
      // 避免除以零向量
      if (magnitude < EPSILON) return axis.clone();
      for(int i = 0; i < axis.length; i++){
          normalized[i] = axis[i] / magnitude;
      }
      return normalized;
  }
  

3. 顶点坐标的精度损失修复 #

在CollidableEntity构造函数中，将缩放后的坐标强制转为int会丢失大量精度，尤其是scale非整数时：

// 原错误代码
hitboxPoints.get(i)[0] = (int)(hitboxPoints.get(i)[0]*scale);
hitboxPoints.get(i)[1] = (int)(hitboxPoints.get(i)[1]*scale);

修改为保留浮点值：

// 修改后
double scaledX = hitboxPoints.get(i)[0] * scale;
double scaledY = hitboxPoints.get(i)[1] * scale;
xPoints[i] = scaledX; 
yPoints[i] = scaledY;
verteces[i] = new Vector2D(scaledX, scaledY);
// 不要修改hitboxPoints中的Integer数组，或直接将hitboxPoints改为存储Double数组

4. 零向量轴的过滤 #

当多边形存在重合顶点时，会生成零向量的轴，导致后续计算出错。在getAxis方法中添加零向量检查，跳过无效轴：

private static double[][] getAxis(double[][] verteces){
    List<double[]> validAxes = new ArrayList<>();
    for(int i = 0; i < verteces.length; i++){
        int j = (i+1)%verteces.length;
        double[] p1 = verteces[i];
        double[] p2 = verteces[j];
        double[] edge = {p2[0] - p1[0], p2[1] - p1[1]};
        // 过滤零向量边
        if (Math.abs(edge[0]) < EPSILON && Math.abs(edge[1]) < EPSILON) {
            continue;
        }
        double[] normal = Vector.getNormal(p1, p2);
        validAxes.add(normal);
    }
    return validAxes.toArray(new double[validAxes.size()][2]);
}

5. 调试辅助 #

添加调试输出，定位具体误判的轴：

// 在checkCollision的轴检测循环中添加
double overlapAmount = Math.min(proj1[1], proj2[1]) - Math.max(proj1[0], proj2[0]);
System.out.printf("轴(%.2f, %.2f) | 投影1:[%.2f, %.2f], 投影2:[%.2f, %.2f] | 重叠量:%.2f%n",
    axis[0], axis[1], proj1[0], proj1[1], proj2[0], proj2[1], overlapAmount);

内容的提问来源于stack exchange，提问作者Péter Marschall