【算法漫谈】GJK 碰撞检测：几何空间的 “精准捕手”

import java.util.ArrayList;
import java.util.List;

// 三维向量类
class Vector3 {
    double x, y, z;

    public Vector3(double x, double y, double z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    // 向量加法
    public Vector3 add(Vector3 other) {
        return new Vector3(x + other.x, y + other.y, z + other.z);
    }

    // 向量减法
    public Vector3 subtract(Vector3 other) {
        return new Vector3(x - other.x, y - other.y, z - other.z);
    }

    // 向量点乘
    public double dot(Vector3 other) {
        return x * other.x + y * other.y + z * other.z;
    }

    // 向量长度
    public double magnitude() {
        return Math.sqrt(x * x + y * y + z * z);
    }

    // 归一化向量
    public Vector3 normalize() {
        double mag = magnitude();
        return new Vector3(x / mag, y / mag, z / mag);
    }
}

// 单纯形节点类
class SimplexNode {
    Vector3 a;
    Vector3 b;

    public SimplexNode(Vector3 a, Vector3 b) {
        this.a = a;
        this.b = b;
    }
}

// GJK算法类
class GJK {
    // 获取闵可夫斯基差集在某方向上的支持点
    private static Vector3 getSupportPoint(List<Vector3> shapeA, List<Vector3> shapeB, Vector3 direction) {
        Vector3 furthestA = null;
        double maxDotA = Double.NEGATIVE_INFINITY;
        for (Vector3 point : shapeA) {
            double dot = point.dot(direction);
            if (dot > maxDotA) {
                maxDotA = dot;
                furthestA = point;
            }
        }

        Vector3 furthestB = null;
        double maxDotB = Double.NEGATIVE_INFINITY;
        for (Vector3 point : shapeB) {
            double dot = point.dot(direction.negate());
            if (dot > maxDotB) {
                maxDotB = dot;
                furthestB = point;
            }
        }

        return furthestA.subtract(furthestB);
    }

    // 判断两个形状是否发生碰撞
    public static boolean gjkCollision(List<Vector3> shapeA, List<Vector3> shapeB) {
        List<SimplexNode> simplex = new ArrayList<>();
        Vector3 direction = new Vector3(1, 0, 0); // 初始方向

        Vector3 support = getSupportPoint(shapeA, shapeB, direction);
        if (support.dot(direction) <= 0) {
            return false; // 无碰撞
        }

        simplex.add(new SimplexNode(support, null));

        direction = support.negate();

        while (true) {
            support = getSupportPoint(shapeA, shapeB, direction);
            if (support.dot(direction) <= 0) {
                return false; // 无碰撞
            }

            simplex.add(new SimplexNode(support, null));

            if (simplex.size() == 2) {
                // 二维单纯形（线段）处理
                Vector3 ab = simplex.get(0).a.subtract(simplex.get(1).a);
                Vector3 ao = simplex.get(1).a.negate();

                double dotABAO = ab.dot(ao);
                if (dotABAO <= 0) {
                    // 原点在线段AB的A侧
                    simplex.remove(0);
                    direction = ao;
                } else {
                    // 原点在线段AB的B侧
                    Vector3 abNorm = ab.normalize();
                    double projLength = abNorm.dot(ao);
                    if (projLength <= ab.magnitude()) {
                        // 原点在线段AB上
                        direction = ao.subtract(abNorm.multiply(projLength));
                    } else {
                        // 原点在线段AB的B外侧
                        simplex.remove(1);
                        direction = ao;
                    }
                }
            } else if (simplex.size() == 3) {
                // 三维单纯形（三角形）处理，此处简化未完整实现
                // 需根据三角形与原点的位置关系更新单纯形和方向
                return true; // 假设三角形情况直接认为碰撞
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        List<Vector3> shapeA = new ArrayList<>();
        shapeA.add(new Vector3(0, 0, 0));
        shapeA.add(new Vector3(1, 0, 0));
        shapeA.add(new Vector3(0, 1, 0));

        List<Vector3> shapeB = new ArrayList<>();
        shapeB.add(new Vector3(0.5, 0.5, 0));
        shapeB.add(new Vector3(1.5, 0.5, 0));
        shapeB.add(new Vector3(0.5, 1.5, 0));

        boolean isColliding = GJK.gjkCollision(shapeA, shapeB);
        System.out.println("Are shapes colliding? " + isColliding);
    }
}