C# WinForms中2D碰撞检测GJK算法实现问题——单纯形方向错误

我最近一直在用C#结合WinForms实现2D版的GJK碰撞检测算法，参考了一篇讲解2D GJK的技术博客。目前的测试场景里有两个形状：一个正方形（ShapeA）和一个可通过WASD控制移动的三角形（ShapeB）。

为了调试方便，我做了可视化效果：

• 用绿色小椭圆代表偏移后的原点
• 红色点是minkowski差的所有顶点，当三角形移动时这些红点会同步更新，这部分逻辑是正常的
• 当原点处于红点构成的形状内部时，就代表正方形和三角形发生了碰撞

初始状态下，minkowski差的红点分布、原点位置以及两个形状的位置关系都符合预期。

接下来就到了GJK算法的核心部分，也是我遇到的问题：
2D版GJK需要在minkowski差中构造单纯形（这里是三角形），按照算法逻辑，初始的三个顶点应该满足：

• 第一个点：ShapeB移动方向上的最远点，与ShapeA相反方向上的最远点，两者构成的minkowski差点
• 第二个点：和第一个点方向相反的minkowski差支撑点
• 第三个点：垂直于前两点连线、指向原点方向的minkowski差最远点

目前前两个点的计算是对的，它们在minkowski差上构成的粉色线段符合预期，但第三个点的方向出了问题：当我把三角形向上移动进入正方形区域时，当前代码算出的第三个点（对应黄色线段）并没有指向原点，但在其他大多数移动方向下，这个点的方向是正常的。

下面是我当前的实现代码，你可以直接复制到WinForms项目里运行：

Form1 窗体类代码 #

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    bool up = false;
    bool down = false;
    bool left = false;
    bool right = false;

    V2 ShapeDirection = new V2();

    List<V2> ShapeA = new List<V2>();
    List<V2> ShapeB = new List<V2>();

    private void Form1_Paint(object sender, PaintEventArgs e)
    {
        Graphics g = e.Graphics;
        V2 Direction = ShapeDirection;

        //绘制正方形ShapeA
        for (int i = 0; i < ShapeA.Count - 1; i++)
        {
            g.DrawLine(new Pen(Brushes.Black, 2),
                new Point((int)ShapeA[i].X, (int)ShapeA[i].Y),
                new Point((int)ShapeA[i + 1].X, (int)ShapeA[i + 1].Y));
        }
        g.DrawLine(new Pen(Brushes.Black, 2),
            new Point((int)ShapeA[ShapeA.Count - 1].X, (int)ShapeA[ShapeA.Count - 1].Y),
            new Point((int)ShapeA[0].X, (int)ShapeA[0].Y));

        //移动三角形ShapeB
        for (int i = 0; i < ShapeB.Count; i++)
        {
            ShapeB[i] += Direction;
        }

        //绘制三角形ShapeB
        for (int i = 0; i < ShapeB.Count - 1; i++)
        {
            g.DrawLine(new Pen(Brushes.Blue, 2),
                new Point((int)ShapeB[i].X, (int)ShapeB[i].Y),
                new Point((int)ShapeB[i + 1].X, (int)ShapeB[i + 1].Y));
        }
        g.DrawLine(new Pen(Brushes.Blue, 2),
            new Point((int)ShapeB[ShapeB.Count - 1].X, (int)ShapeB[ShapeB.Count - 1].Y),
            new Point((int)ShapeB[0].X, (int)ShapeB[0].Y));

        //偏移原点以展示minkowski差
        g.TranslateTransform(900, 600);
        g.FillEllipse(Brushes.Green, new Rectangle(-3, -3, 6, 6));

        List<V2> MDifference = Minkowski(ShapeA, ShapeB);

        //绘制minkowski差的顶点
        for (int i = 0; i < MDifference.Count - 1; i++)
        {
            g.FillEllipse(Brushes.Red,
                new Rectangle((int)(MDifference[i].X - 3), (int)(MDifference[i].Y - 3), 6, 6));
        }

        //GJK算法开始
        V2 C = SupportPoint(ShapeA, Direction) - SupportPoint(ShapeB, Direction.Inverse());
        Direction = Direction.Inverse();
        V2 B = SupportPoint(ShapeA, Direction) - SupportPoint(ShapeB, Direction.Inverse());

        V2 Cline = B - C;
        V2 C0 = C.Inverse();

        Direction = V2.Cross(Cline, V2.Cross(C0, Cline)); //★这里是问题所在

        V2 A = SupportPoint(ShapeA, Direction) - SupportPoint(ShapeB, Direction.Inverse());

        g.DrawLine(new Pen(Brushes.Yellow, 2), new Point((int)A.X, (int)A.Y), new Point((int)B.X, (int)B.Y));
        g.DrawLine(new Pen(Brushes.Pink, 2), new Point((int)B.X, (int)B.Y), new Point((int)C.X, (int)C.Y));
        g.DrawLine(new Pen(Brushes.Yellow, 2), new Point((int)A.X, (int)A.Y), new Point((int)C.X, (int)C.Y));
    }

    private List<V2> Minkowski(List<V2> shape1, List<V2> shape2)
    {
        List<V2> MinkowskiDifferencePoints = new List<V2>();

        foreach (V2 VertexA in shape1)
        {
            foreach (V2 VertexB in shape2)
            {
                MinkowskiDifferencePoints.Add(VertexA - VertexB);
            }
        }

        return MinkowskiDifferencePoints;
    }

    public V2 SupportPoint(List<V2> shape, V2 direction)
    {
        float max = float.NegativeInfinity;
        int index = 0;

        for (int i = 0; i < shape.Count; i++)
        {
            float dot = V2.Dot(shape[i], direction);
            if (dot > max)
            {
                max = dot;
                index = i;
            }
        }

        return shape[index];
    }

    private void Form1_KeyDown(object sender, KeyEventArgs e)
    {
        if (e.KeyCode == Keys.A) { left = true; }
        if (e.KeyCode == Keys.D) { right = true; }
        if (e.KeyCode == Keys.W) { up = true; }
        if (e.KeyCode == Keys.S) { down = true; }
    }

    private void Form1_KeyUp(object sender, KeyEventArgs e)
    {
        if (e.KeyCode == Keys.A) { left = false; }
        if (e.KeyCode == Keys.D) { right = false; }
        if (e.KeyCode == Keys.W) { up = false; }
        if (e.KeyCode == Keys.S) { down = false; }
    }

    private void Form1_Load(object sender, EventArgs e)
    {
        System.Windows.Forms.Timer timer1 = new System.Windows.Forms.Timer();
        timer1.Interval = 1;
        timer1.Enabled = true;
        timer1.Tick += timer1_Tick;
        this.DoubleBuffered = true;
        this.Size = new Size(1200, 1000);
        this.StartPosition = FormStartPosition.CenterScreen;

        ShapeA.Add(new V2(300, 300));
        ShapeA.Add(new V2(350, 300));
        ShapeA.Add(new V2(350, 350));
        ShapeA.Add(new V2(300, 350));

        ShapeB.Add(new V2(600, 600));
        ShapeB.Add(new V2(650, 650));
        ShapeB.Add(new V2(550, 650));
    }

    private void timer1_Tick(object sender, EventArgs e)
    {
        ShapeDirection = new V2();

        if (left) { ShapeDirection.X = -1; }
        else if (right) { ShapeDirection.X = 1; }
        if (up) { ShapeDirection.Y = -1; }
        else if (down) { ShapeDirection.Y = 1; }

        this.Invalidate();
    }
}

V2 向量类代码 #

public class V2
{
    public float X { get; set; }
    public float Y { get; set; }
    public float Z { get; set; }

    public V2()
    { X = 0; Y = 0; Z = 0; }

    public V2(float x, float y)
    { X = x; Y = y; Z = 0; }

    public static V2 operator +(V2 VectorA, V2 VectorB)
    { return new V2(VectorA.X + VectorB.X, VectorA.Y + VectorB.Y); }
    public static V2 operator +(V2 Vector, float Scalar)
    { return new V2(Vector.X + Scalar, Vector.Y + Scalar); }

    public static V2 operator -(V2 VectorA, V2 VectorB)
    { return new V2(VectorA.X - VectorB.X, VectorA.Y - VectorB.Y); }
    public static V2 operator -(V2 Vector, float Scalar)
    { return new V2(Vector.X - Scalar, Vector.Y - Scalar); }

    public static V2 operator *(V2 VectorA, V2 VectorB)
    { return new V2(VectorA.X * VectorB.X, VectorA.Y * VectorB.Y); }
    public static V2 operator *(V2 Vector, float Scalar)
    { return new V2(Vector.X * Scalar, Vector.Y * Scalar); }

    public static V2 operator /(V2 VectorA, V2 VectorB)
    { return new V2(VectorA.X / VectorB.X, VectorA.Y / VectorB.Y); }
    public static V2 operator /(V2 Vector, float Scalar)
    { return new V2(Vector.X / Scalar, Vector.Y / Scalar); }

    public static float Dot(V2 VectorA, V2 VectorB)
    {
        return VectorA.X * VectorB.X + VectorA.Y * VectorB.Y;
    }

    public static float Length(V2 VectorA, V2 VectorB)
    {
        return (float)Math.Sqrt(Math.Pow((VectorB.X - VectorA.X), 2) + Math.Pow((VectorB.Y - VectorA.Y), 2));
    }

    public static V2 Cross(V2 VectorA, V2 VectorB)
    {
        V2 VtempRes = new V2();

        VtempRes.X = (VectorA.Y * VectorB.Z) - (VectorA.Z * VectorB.Y);
        VtempRes.Y = (VectorA.Z * VectorB.X) - (VectorA.X * VectorB.Z);
        VtempRes.Z = (VectorA.Z * VectorB.Y) - (VectorA.Y * VectorB.X);

        return VtempRes;
    }

    public V2 Inverse()
    { return new V2(-1 * X, -1 * Y); }
}

备注：内容来源于stack exchange，提问作者KBConsole