3D Kugelkollision mit anderen Kugeln

Foxx90

Hallo, ich habe ein drigendes Problem:

Ich hab vor einiger Zeit in Delphi einen Algorithmus geschrieben geschrieben,
der die Kollision von 2D Kugeln berechnet. Kein großes Ding.. Aber nun versuch ich mich wieder reinzulesen, da ich ihn iwie umcoden will damit er im 3D-Bereich klappt. Mir ist klar, dass das hier das Matheforum ist, aber damit ihr die Funktionsweise versteht, poste ich mal den Delphicode, dürfte ansich einfach zu durchschauen sein...

procedure TBallChris_Mathias.CalcHit(CalcBall: TBallChris_Mathias);
var
  Vec1, Vec2, SpeedVec, DistanceVector, { TMP } OtherVpos, OtherVspeed, tmp { TMP }: TVector; //Die beiden Geschwindigkeitsvektoren der Bälle, der TVector der die neuen Geschwindigkeiten enthält, die Distanzen zwischen den Bällen...
  RelaCos, RelaSin: extended; //Die Relationen, mit denen die Achsen gedreht werden müssen...
begin
  if(CalcBall <> NIL) then
  begin
    { Variablen füllen }
    OtherVpos := CalcBall.GetPosVector();
    OtherVspeed := CalcBall.GetSpeedVector();

    { Entfernung der beiden Bälle errechnen }
    DistanceVector := OtherVpos.Minus( m_Vpos );

    { Cos, Sin ohne Winkel berechnen... }
    RelaCos := DistanceVector.x / DistanceVector.Track();
    RelaSin := DistanceVector.y / DistanceVector.Track();

    { Drehen der Vektoren, um einen relativen "zentralen" Stoß zu berechnen... }
    Vec1 := TVector.Create( (m_Vspeed.x *  RelaCos + m_Vspeed.y * RelaSin) ,
                            (m_Vspeed.x * -RelaSin + m_Vspeed.y * RelaCos) );

    Vec2 := TVector.Create( (OtherVspeed.x *  RelaCos + OtherVspeed.y * RelaSin) ,
                            (OtherVspeed.x * -RelaSin + OtherVspeed.y * RelaCos) );
    { Fertig }

    { Ok, wenn die linke Geschwindigkeit kleiner ist, als die recht, dann dürfen wir nicht weiter rechnen }
    if (Vec1.x - Vec2.x > 0) then
    begin
      { Nun wird der zentrale Stoß berechnet... }
      //SpeedVec.x ist die neue Geschwindigkeit des ersten Balls, und y des 2ten
      SpeedVec := CalcCentralHit(Vec1.x, Vec2.x, GetMass(), CalcBall.GetMass());
      { Fertig }

      //m_Vspeed ist der Speedvektor des ersten Ball
      { Zurückdrehen der Vektoren, um relative Vektoren zu berechnen... }
      m_Vspeed.Equal( (SpeedVec.x * RelaCos + Vec1.y * -RelaSin) ,
                      (SpeedVec.x * RelaSin + Vec1.y *  RelaCos) );

      tmp := TVector.Create( (SpeedVec.y * RelaCos + Vec2.y * -RelaSin) ,
                             (SpeedVec.y * RelaSin + Vec2.y *  RelaCos) );

      //Speedvektor des 2ten Balls
      CalcBall.SetSpeedVector(tmp);
      { Fertig }

      { Aufräumen }
      SpeedVec.Free();
      tmp.Free();
      { Fertig }
    end;

    { Aufräumen }
    OtherVpos.Free();
    OtherVspeed.Free();
    DistanceVector.Free();
    Vec1.Free();
    Vec2.Free();
    { Fertig }
  end; //Hoffentlich nicht NIL   
end;

So, jetzt bräuchte ich mal ein paar Tips um das ganze in 3D umzusetzen...
Natürlich kein Code!

Also meine erste Idee war: Nicht nur um die z-Achse drehen sondern vorher um die y-Matrix drehen. (Rotationsmatrix)

So, aber iwie klappte das bei mir nicht Was mache ich falsch ?

Gruß Chris

.filmor

Ich hab's mir nicht so richtig angeschaut, aber mein Vorgehen zum kollidieren von zwei Kugeln in beliebigen Dimensionen wäre folgendes:
Seien x_1 und x_2 Vektoren der Mittelpunkte der Kugeln, r_1 und r_2 die Radien. Dann ist d = |x_2 - x_1| der Abstand der Mittelpunkte. Die beiden Kugeln haben sich also genau dann getroffen, wenn d - r_1 - r_2 < 0 ist.

/edit: Aha, du willst sie wirklich aneinander dotzen lassen. Hätte mir vielleicht doch den Code durchlesen sollen

Foxx90

Danke schonmal, die Kollisionserkennung hab ich schon ganz gut gelöst, ähnlich wie deine Idee. Aber es ging mir grad nur um die Berechnuung der neuen Geschwindigkeitsvektoren. Sprich bei einem Hit in einer 3D-Umgebung ihre neuen Richtungen.

Danke.

Gruß Chris

EDIT: Die Lösung für die Erkennung ist wie folgt:
Jede Kugel bekommt eine lineare Gleichung, die dann gleichgesetzt werden, jedoch enthält diese megagleichung dann noch ein b, das Werte >= 0 <= 1 annehmen kann, und im Prinzip die den Faktor repräsentiert, womit die Geschwindigkeit multipliziert werden muss, damit man GENAU vor die andere Kugel gesetzt wird...

Chuck

Abend.

Für die Neuberechnung der Geschwindigkeiten wendest du einen Kraftstoß an.

- Kugeln a und b bestehen aus Mittelpunkt p, Radius r und Masse m
- n = a.p - b.p

- |n| bestimmen
- wenn (|n| > a.r + b.r), dann Abbruch, sonst n = n / |n| (Normierung)

- vrel = n * (a.v - b.v) (Skalarprodukt)
- wenn (vrel < 0), dann ist ein Kraftsroß von Nöten, damit keine Durchdringung
stattfindet, sonst Abbruch

- j = -(1 + eps) * vrel / (1 / a.m + 1 / b.m)
- J = j * n (Vektor mit Skalar multiplizieren)

- a.v = a.v + J / a.m
- b.v = b.v - J / b.m

Die Längenbestimmung |n| nur 1 Mal, wegen der ineffizienten Wurzelbestimmung.
4 Divisionen (auch zeitfressende Operationen) kannst du dir auch sparen, indem
du die inversen Massen speicherst, anstatt der bzw. zusätzlich zu den normalen
Massen.

/edit:
Die Kollisionserkennung kannst du auch verbessern, indem du statt
|n| = sqrt(n.x² + n.y² + n.z²) mit der Summe der Radien, die quadratische Länge |n|² = n.x² + n.y² + n.z² mit der quadratischen Summe der beiden Radien (a.r + b.r)², vergleichst.

So und nun wirklich gute Nacht.

Foxx90

Erstmal wieder vielen DANK!!
So, die Kollisionserkennung klappt hervorragend die ich bereits hab. Grade was Speed > Durchmesser einer anderen Kugel angeht, und das daurch unausweichliche "Durchfliegen". So aber es ging mir jetzt speziell um die berechnung der neuen Richtungsvektoren, oder ist in deinem Beitrag bereits drin und ich bin nur zu doof um das zu erkennen zu dieser späten Stunde. Was meisnt du mit "eps" ??
Und genau enthält j bzw J hinterher ?

Danke für deinen ausführlichen Tipp

Gruß Chris

Chuck

Morgen.

Ja, das ist eigentlich ein Rundum-Programm: Kollisionserkennung und -behandlung

Ich sehe ich hab, vergessen zu erwähnen, dass v die Richtungsvektoren sein
sollen. Naja war spät.
Und wie du siehst wird ganz am Ende a.v und b.v neu berechnet.

Das eps ist eine Stoßkonstante mit 0 <= eps <= 1.
0 bedeutet maximaler Energieverlust
1 bedeutet kein Energieverlust

j ist eine positive reelle Zahl, die die Stärke des Kraftstoßes angibt.
n ist die Richtung des Kraftstoßes

J ist der Vektor des Kraftstoßes (also j * n)

Und am Ende wird eben dann der Kraftstoß auf die Kugeln übertragen. Einmal
+ auf Kugel a und einmal - auf die Kugel b.
Damit bleibt die relative tangentielle Geschwindigkeit erhalten. Nur die
Geschwindigkeit parallel zu n muss verändert werden, da nur sie eine
Durchdringung hervorruft.

Du hast Recht. Da hab ich gar nicht mehr dran gedacht, dass sich diese beiden Kugeln durchfliegen können ohne Durchdringung. Aber der naive Ansatz geht auch bei normalen Simulationen, wie Snooker oder ähnliches.

Foxx90

Alles klar... Ich drehe die Impulsvektoren im moment mit der Y bzw Z Rotationsmatrix, damit ich die Komponenten haben, die wirklich zur Richtungsänderung beitragen, mein Problem war, dass bei 3D (Nicht bei 2D, da klappte alles wunderbar) anscheined iwie die MAtrixrotation falsch läuft was natürlcih eine Fehlberechnung der Impulsvektoren zur Folge hat. Ich werde es iwie schon hinkriegen, danke aber für die Ansätze!!

Gruß Chris

Chuck

Ganz schön kompliziert und ineffizient, wenn du mit Matrizen arbeitest in
diesen Bereich.
Mein Ansatz kickt viele von diesen Redundanzen raus. Aber das musst du selbst
entscheiden.

Übung macht den Meister

Foxx90

Ehrlich gesagt bin ich etwas deprimiert, dass du das ohne kannst Ich dachte immer man bräuchte für die berechnet des Impulses ne Matrize !!

Chuck

Naja, siehst du in meinem Vorschlag eine Matrix, die kein Vektor ist?

Foxx90

Also deine Idee klappt hervorragend, nur eine Sache is mir aufgefallen war (Ich will nicht sagen falsch, aber wenn ich sie aßer Acht lassen, klappt alles)

Du hast diese gepostet:
- vrel = n * (a.v - b.v) (Skalarprodukt)
- wenn (vrel < 0), dann ist ein Kraftsroß von Nöten, damit keine Durchdringung
stattfindet, sonst Abbruch

Ich habe den Betrag von vrel geprüft, (Ich hoffe das Meintest du damit), und dann klappte es nicht , wenn ich bei >= 0 aus meiner Funktion sprang.

Hier der Code

public static void betweenBalls(Ball tori, Ball uke)
	{	
		if(tori == null || uke == null)
			return;

		//Wir berechnen zuerst die Entfernung der beiden Bälle
		Vector dist = tori.getPosition().sub(uke.getPosition()).unitVector();

		Vector vrel = dist.mul( tori.getSpeed().sub(uke.getSpeed()) );

		//if(!(vrel.track() < 0))
			//return;

		double j = vrel.mul(-(1 + 1)).div( 1 / tori.getMass() + 1 / uke.getMass() ).track();

		Vector J = dist.mul(j);

		tori.setSpeed( tori.getSpeed().add(J.div(tori.getMass()) ) );
		uke.setSpeed( uke.getSpeed().sub(J.div(uke.getMass())) );
	}

Damit scheint es zu funktionieren. Einfach genial, und ich hantiere da mit MAtrizen rum, was auch geklappt hat, aber deines ist genialer Naja danke !!

Gruß Chris

Chuck

Zeile 9 : vrel ist kein Vektor sondern eine reelle Zahl(deswegen Skalarprodukt)

Und diese vielleicht negative Zahl zeigt an, ob sich die beiden Kugeln im
nächsten Zeitschritt durchdringen.

Foxx90

Sry, habs übersehen, aber als Vektor klappts auch :D^^ Ok, danke für alles! Dank dir hab ich ne neue Sicht der Dinge

Gruß Chris

Chuck

Klar klappt's damit^^ du brauchst ja bloß den Betrag. Das Vorzeichen soll aber
noch andere Informationen liefern. Aber wenn's geht, kann ich ja beruhigt
Einkaufen fahren.