时间戳

首页 > 解决方案 > 在 Java 中实现 SAT 多边形碰撞检测时遇到问题

java - 在 Java 中实现 SAT 多边形碰撞检测时遇到问题

问题描述

我目前正在尝试在 java 中实现 SAT，但由于某种原因它不起作用。我已经多次重写了我的代码，仔细查看了它，看了很多教程，但找不到我的错误。在某些情况下，对于某些边缘，它可以部分正常工作，但否则它会在不碰撞时检测到碰撞。稍后我将添加 AABB 碰撞检测以获得更好的性能。以下是我的代码的相关部分：

SAT课：

public class SAT {
    public static boolean checkSAT(Polygon poly1, Polygon poly2) {
        Vector[] axes = new Vector[poly1.p.length + poly2.p.length];
        
        for (int i = 0; i < poly1.p.length + poly2.p.length; i++) {
            int a = i; if(i == poly1.p.length) a -= poly1.p.length;
            axes[i] = poly1.getEdge(a).getNormal().getNormalized();
            
        }
        
        double p1_min = Double.POSITIVE_INFINITY, p1_max = Double.NEGATIVE_INFINITY,
               p2_min = Double.POSITIVE_INFINITY, p2_max = Double.NEGATIVE_INFINITY;
        
        for (int i = 0; i < axes.length; i++) {
            for (int j = 0; j < poly1.p.length; j++) {
                double proj = axes[i].dotProduct(poly1.p[j]);
                if(proj < p1_min) p1_min = proj;
                if(proj > p1_max) p1_max = proj;
                
            }
            
            for (int j = 0; j < poly2.p.length; j++) {
                double proj = axes[i].dotProduct(poly2.p[j]);
                if(proj < p2_min) p2_min = proj;
                if(proj > p2_max) p2_max = proj;
                
            }
            
            if (p1_max < p2_min || p2_max < p1_min)
                return false;
            
        }
        
        return true;
        
    }
}

向量类：

public class Vector {
    public final double x;
    public final double y;
    
    public Vector(double x, double y) {
        this.x = x;
        this.y = y;
        
    }
    
    public Vector getNormal() {
        return new Vector(-y, x);
        
    }
    
    public double getLength() {
        return Math.sqrt(x*x + y*y);
        
    }
    
    public Vector getNormalized() {
        double l = getLength();
        
        return new Vector(x/l, y/l);
        
    }
    
    public double dotProduct(Vector vec) {
        return x * vec.x + y * vec.y;
    }
    
}

多边形类的相关部分：

public class Polygon {
    public Vector[] m; //"model" of the polygon
    public Vector[] p; //coordinates of the corners of the polygon in space
    
    public double posX;
    public double posY;
    
    public Polygon(Vector[] m) {
        this.m = m;
        
        p = new Vector[m.length];
        
        transform();
        
    }
    
    //later i'll add rotation
    public void transform() {
        for (int i = 0; i < m.length; i++) {
            p[i] = new Vector(m[i].x + posX, m[i].y + posY);
        }
        
    }
    
    public void setPosition(Vector pos) {
        posX = pos.x;
        posY = pos.y;
        
        transform();
        
    }
    
    public Vector getEdge(int i) {
        if(i >= p.length) i = 0;
        int j = i+1; if(j >= p.length) j = 0;
        return new Vector(p[j].x - p[i].x, p[j].y - p[i].y);
        
    }
    
}

标签： javacollision-detectionpolygongame-enginegame-physics

解决方案

更新：我发现了错误，这很愚蠢！最重要的是，我花了 5 个多小时才找到它！！！！！！！

        double p1_min = Double.POSITIVE_INFINITY, p1_max = Double.NEGATIVE_INFINITY, 
               p2_min = Double.POSITIVE_INFINITY, p2_max = Double.NEGATIVE_INFINITY;
        //those doubles should be declared inside the for loop

        for (int i = 0; i < axes.length; i++) {
            //right here

            for (int j = 0; j < poly1.p.length; j++) {
                double proj = axes[i].dotProduct(poly1.p[j]);
                if(proj < p1_min) p1_min = proj;
                if(proj > p1_max) p1_max = proj;
                
            }
            
            for (int j = 0; j < poly2.p.length; j++) {
                double proj = axes[i].dotProduct(poly2.p[j]);
                if(proj < p2_min) p2_min = proj;
                if(proj > p2_max) p2_max = proj;
                
            }
            
            if (p1_max < p2_min || p2_max < p1_min)
                return false;
            
        }

推荐阅读