GJK -Algorithmus in C#(WinForms) für 2D -Kollision - Problem mit der Richtung für Simplexes ⇐ C#

[Anonymous]

As the title implies I have been trying to implement the GJK algorithm in 2D using C# mainly based off this blog:
https://blog.hamaluik.ca/posts/building ... detection/
We have two shapes, a square(ShapeA) and a Dreieck (ShapeB). Das Dreieck kann sich mit WASD bewegen. /> Dann kommt der GJK -Algorithmus und mein Problem. Der am weitesten in Shapea in die entgegengesetzte Richtung. Und der am weitesten verbreitete Punkt im minkowski -Unterschied in der Richtung senkrecht zur Linie, die von den ersten beiden Scheitelpunkten und dem Ursprung gebildet wird. Das Problem besteht darin, den dritten Scheitelpunkt zu erhalten. Wenn wir das Dreieck nach oben in das Quadrat bewegen, können wir sehen, dass der dritte Punkt, den ich gerade erhalten (der die Linie in Gelb bildet), nicht in Richtung des Ursprungs ist. Wenn Sie sich jedoch in die meisten anderen Richtungen bewegen, erscheint es in Ordnung. Um einfach ein neues Windows-Formulationsprojekt in C#zu kopieren und auszuführen, ersetzen Sie die Standardform1-Klasse durch Folgendes: < /p>

Code: Select all

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 ShapeA = new List();
List ShapeB = new List();

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

//Draw Shape A
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));

//Move Shape B
for (int i = 0; i < ShapeB.Count; i++)
{
ShapeB[i] += Direction;
}

//Draw Shape B
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));

//Offset origin to see minkowski difference points
g.TranslateTransform(900, 600);
g.FillEllipse(Brushes.Green, new Rectangle(-3, -3, 6, 6));

List MDifference = Minkowski(ShapeA, ShapeB);

//Draw minkowski difference points
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));
}

//Start of 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)); //Issue

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 Minkowski(List shape1, List shape2)
{
List MinkowskiDifferencePoints = new List();

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

return MinkowskiDifferencePoints;
}

public V2 SupportPoint(List 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();
}
}
< /code>
Fügen Sie dem Projekt "v2" eine neue Klasse hinzu und fügen Sie dies ein: < /p>
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); }
}

Sie können jetzt das Dreieck herum bewegen, den Minkowski -Unterschied beobachten und mir hoffentlich sagen, was ich falsch mache (irgendwo am Ende des Formulars.>