JavaFX中3D GJK碰撞检测假阳性问题求助

我用JavaFX实现3D GJK碰撞检测，碰撞体实际碰撞或距离较远时功能正常，但特定朝向且近距离时会出现假阳性结果。推测问题出在单纯形（simplex）处理逻辑中，但无法定位具体问题，求帮忙。

Collider_3d类仅存储一组凸集点，已确认点集为凸集，需要的话可提供具体点数据。

原始代码 #

private static final double EPILSON = 0;

static private Point3D findSuppPoint(Collider_3d a, Collider_3d b, Point3D dir) {
    return a.findExtrema(dir).subtract(b.findExtrema(dir.multiply(-1)));
}

public static boolean Gilbert_Johnson_Keerthi_Collision(Collider_3d a, Collider_3d b) {
    Point3D dir = new Point3D(0,0,1);
    Point3D currPoint = findSuppPoint(a,b,dir);
    ArrayList<Point3D> simplex = new ArrayList<Point3D>();
    simplex.add(currPoint);
    
    dir = currPoint.multiply(-1); // 朝向原点的方向
    
    while(true) {
        currPoint = findSuppPoint(a,b,dir);
        if(currPoint.dotProduct(dir) < EPILSON) {
            return false;
        }
        simplex.add(currPoint);
        dir = calcSimplex(simplex, dir);
        if(dir == null){
            return true;
        }
    }
}

static private Point3D calcSimplex(ArrayList<Point3D> s, Point3D dir) {
    if(s.size() == 2) {
        return nextDir(s);
    }else if(s.size() == 3) {
        return triSimplex(s, dir);
    }else if(s.size() == 4){
        return tetraSimplex(s, dir);
    }
    return dir; // 理论上不会走到这里
}

static private Point3D tetraSimplex(ArrayList<Point3D> s, Point3D dir) {
    Point3D AB = s.get(2).subtract(s.get(3));
    Point3D AC = s.get(1).subtract(s.get(3));
    Point3D AD = s.get(0).subtract(s.get(3));
    Point3D AO = s.get(3).multiply(-1);
    
    Point3D ABCDir = AB.crossProduct(AC);
    Point3D ADBDir = AC.crossProduct(AD);
    Point3D ACDDir = AD.crossProduct(AB);
    
    if(ABCDir.dotProduct(AD) > 0) {
        ABCDir = ABCDir.multiply(-1);
    }else if(ADBDir.dotProduct(AC) > 0) {
        ADBDir = ADBDir.multiply(-1);
    }else if(ACDDir.dotProduct(AB) > 0) {
        ACDDir = ACDDir.multiply(-1);
    }
    
    if(ABCDir.dotProduct(AO) > 0) {
        s.remove(0);
        return ABCDir;
    }else if(ADBDir.dotProduct(AO) > 0) {
        s.remove(1);
        return ADBDir;
    }else if(ACDDir.dotProduct(AO) > 0) {
        s.remove(2);
        return ACDDir;
    }
    System.out.println("AHHHH");
    return null;
}

static private Point3D triSimplex(ArrayList<Point3D> s, Point3D dir) {
    Point3D AB = s.get(1).subtract(s.get(2));
    Point3D AC = s.get(0).subtract(s.get(2));
    Point3D AO = s.get(2).multiply(-1);
    Point3D ABDir = (AC.crossProduct(AB)).crossProduct(AB);
    Point3D ACDir = (AB.crossProduct(AC)).crossProduct(AC);
    if(ABDir.dotProduct(AO) > 0) {
        s.remove(0);
        return ABDir;
    }else if(ACDir.dotProduct(AO) > 0) {
        s.remove(1);
        return ACDir;
    }
    return dir;
}

static private Point3D nextDir(ArrayList<Point3D> s) {
    Point3D AB = s.get(0).subtract(s.get(1));
    Point3D AO = s.get(1).multiply(-1);
    return (AB.crossProduct(AO)).crossProduct(AB);
}

问题根源与修复方案 #

1. 浮点精度阈值设置错误 #

问题：EPILSON = 0，浮点运算存在精度误差，临界距离下的点积计算会因微小误差误判。
修复：设置极小正数阈值，避免精度问题导致的误判：

private static final double EPILSON = 1e-8;

2. 线段单纯形方向计算错误 #

问题：nextDir方法中方向向量未单位化，且向量推导逻辑未确保指向包含原点的半空间。
修复：

static private Point3D nextDir(ArrayList<Point3D> s) {
    Point3D A = s.get(0);
    Point3D B = s.get(1);
    Point3D AB = B.subtract(A);
    Point3D AO = A.multiply(-1);
    // 计算垂直于AB且指向原点的方向向量，并单位化
    Point3D perp = AB.crossProduct(AO).crossProduct(AB);
    return perp.normalize();
}

3. 三角形单纯形裁剪逻辑错误 #

问题：未正确判断原点是否在三角形平面的包含区域，且方向向量计算未确保指向原点。
修复：

static private Point3D triSimplex(ArrayList<Point3D> s, Point3D dir) {
    Point3D A = s.get(0);
    Point3D B = s.get(1);
    Point3D C = s.get(2);
    Point3D AB = B.subtract(A);
    Point3D AC = C.subtract(A);
    Point3D AO = A.multiply(-1);
    
    Point3D ABCNormal = AB.crossProduct(AC);
    // 确保法线朝向原点
    if (ABCNormal.dotProduct(AO) < 0) {
        ABCNormal = ABCNormal.multiply(-1);
    }
    
    // 检查原点是否在三角形平面外侧
    if (ABCNormal.dotProduct(AO) > EPILSON) {
        // 检查AB边区域
        Point3D ABPerp = AB.crossProduct(ABCNormal).crossProduct(AB);
        if (ABPerp.dotProduct(AO) > EPILSON) {
            s.remove(2);
            return ABPerp.normalize();
        }
        // 检查AC边区域
        Point3D ACPerp = AC.crossProduct(ABCNormal).crossProduct(AC);
        if (ACPerp.dotProduct(AO) > EPILSON) {
            s.remove(1);
            return ACPerp.normalize();
        }
        // 原点在三角形内部，判定碰撞
        return null;
    } else {
        // 原点在平面另一侧，裁剪为线段BC
        s.clear();
        s.add(B);
        s.add(C);
        return nextDir(s);
    }
}

4. 四面体单纯形面法线方向错误 #

问题：面法线方向修正逻辑错误，未确保法线指向原点所在的半空间，导致裁剪方向错误。
修复：

static private Point3D tetraSimplex(ArrayList<Point3D> s, Point3D dir) {
    Point3D A = s.get(0);
    Point3D B = s.get(1);
    Point3D C = s.get(2);
    Point3D D = s.get(3);
    
    Point3D AO = A.multiply(-1);
    Point3D BO = B.multiply(-1);
    
    // 计算四个面的法线，确保朝向原点
    Point3D ABCNormal = (B.subtract(A)).crossProduct(C.subtract(A));
    if (ABCNormal.dotProduct(AO) < 0) ABCNormal = ABCNormal.multiply(-1);
    
    Point3D ABDNormal = (B.subtract(A)).crossProduct(D.subtract(A));
    if (ABDNormal.dotProduct(AO) < 0) ABDNormal = ABDNormal.multiply(-1);
    
    Point3D ACDNormal = (C.subtract(A)).crossProduct(D.subtract(A));
    if (ACDNormal.dotProduct(AO) < 0) ACDNormal = ACDNormal.multiply(-1);
    
    Point3D BCDNormal = (C.subtract(B)).crossProduct(D.subtract(B));
    if (BCDNormal.dotProduct(BO) < 0) BCDNormal = BCDNormal.multiply(-1);
    
    // 检查原点是否在各面外侧，裁剪单纯形
    if (ABCNormal.dotProduct(AO) > EPILSON) {
        s.remove(3);
        return ABCNormal.normalize();
    }
    if (ABDNormal.dotProduct(AO) > EPILSON) {
        s.remove(2);
        return ABDNormal.normalize();
    }
    if (ACDNormal.dotProduct(AO) > EPILSON) {
        s.remove(1);
        return ACDNormal.normalize();
    }
    if (BCDNormal.dotProduct(BO) > EPILSON) {
        s.remove(0);
        return BCDNormal.normalize();
    }
    // 原点在四面体内部，判定碰撞
    return null;
}

核心修复总结 #

• 必须设置合理的浮点精度阈值，避免临界情况误判
• 所有方向向量计算后需单位化，确保后续点积计算的准确性
• 单纯形裁剪时，必须确保面法线/垂直方向指向包含原点的半空间，否则会导致错误的搜索方向
• 严格统一单纯形中点的顺序和索引引用，避免向量计算混乱

内容的提问来源于stack exchange，提问作者Glitchh