Kugel/Kreis prallt von Eck/Kante ab

[Florian H]

Hallo ihr Lieben,

ich entwickle grad ein Spiel, in dem eine Kugel (2D -> praktisch ein Kreis) durch ein Spielfeld rollt, das durch Blöcke gegeben und begrenzt ist.
Nun soll diese Kugel von den Blöcken abprallen. Das tut sie auch prima, sofern sie auf deren Seitenflächen trifft (da diese rechtwinklig sind ist ja einfach Einfalls- gleich Ausfallswinkel).
Aber wenn so eine Kugel auf ein Eck trifft, sieht es da mit dem Abprallen ganz und gar anders aus - ich frage mich nur schon seit einigen Stunden, wie das konkret ist bzw. vor allem, wie ich das in Delphi umsetzen kann.

Ich hab das mal illustriert:
http://klammcam.loseoase.de/host/ball_abprallen.png

Das ist ja schon relativ komplex, da es ja auf den Aufprallwinkel (s. 2 und 3) ankommt und auf die Verschiebung zur Kante (s. 1 und 3)..

Die Bewegung der Kugel wird über x- und y-Änderung angegeben, lässt sich also rel. einfach in irgendwas anderes umrechnen, falls nötig.

Also Kugel 1 bewegt sich z.B. mit [0;1] (nicht nach links/rechts, aber 1 nach unten), Kugel 2 mit [-1;-1] (eins nach links, eins nach oben) pro Zeiteinheit.


Viele Grüße
flo

[dino]

ich kanns dir sagen, aber nicht formulieren has versucht und es versteht ja doch keine sau

[Florian H]

Hm.. einen Versuch wärs wert (gewesen)?
:)

[dino]

1:strecke kante kreismittelpunkt
2:winkel Kreislaufahn
3:1 um 90grad drehen differenz und dann einfallswinkel =ausfallswinkel

[Dax]

Ich weiß nicht genau, wie es funktioniert, aber ich kann schätzen... Wünsch mir Glück ;)

Ich würde sagen, du ziehst eine imaginäre Gerade durch die Ecke, auf die der Kreis zufliegt und den Mittelpunkt des Kreises. Diese Linie rotierst du um 90 Grad und benutzt sie als virtuelle Kante, an der der Kreis abprallt.

Muss nicht stimmen ;)

edit: Kasten? :gruebel:

[Sidorion]

Bei Flächen gilt ja einfall=ausfall an der Flächennormalen.
Bei Kollision mit der Ecke wäre die 'Flächennormale' der Vektor von Ecke zur Kugelmitte. Dann gilt auch hier wieder einfall=ausfall.
Die einzige Schwierigkeit besteht nur darin, herauszubekommen, wann die Kugel nicht die Fläche, sondern die Kante berührt. Das kann man dann ermitteln, indem man schaut, ob der Fußpunkt der Flächennormalen durch den Kreismittelpunkt innerhalb oder ausserhalb der Fläche liegt.

[dino]

so jetzt haste 3 mal die selbe antwort: alle 3 zusammen müssten dein problem verständlich beantworten

ok neuerdiings sinds 4

[Nikolas]

Ds ist eigentlich nicht so schwer, würde ich mal sagen.

Wenn die Kugel auf die Ecke trifft, denkst du dir eine Gerade, die durch die Ecke geht und senkrecht auf die Verbindungslinie Ecke-Kreismittelpunkt steht. Dann lässt du die Kugel an dieser Geraden abprallen und dein Problem sollte gelöst sein.
An der Seitenfläche machst du eigentlich auch nichts anderes, du verbindest den Auftreffpunkt mit deinem Mittelpunkt und rechnst o.g. Gerade aus, die hier nur mit der Seitenkante des Rechtecks zusammenfällt. Also eigentlich nur ein Spezialfall der Ecke.
Zur Berechnung der neuen Geschwindigkeit könntest du z.B. Rotationsmatrizen benutzen.

// da war zwar ein Kasten, aber sagen wollte ich es trotzdem. :mrgreen:

[dino]

hab mich jetzt auch für dein problem begeistert und hab eine frage: wass passiert, wenn eine Kugel auf 2 Kanten gleichzeitig trifft?

zeichnung beispiele jeweils einfallswinkel =270grad (nach oben)


achja: wie findest du herraus, dass dein Kreis Kollidiert?

[3_of_8]

Du verbindest die beiden Punkte, konstruierst eine Tangente parralel zu der entstehenden Gerade und lässt die Kugel daran abprallen. ;)

[dino]

und wie findet man am besten herraus, ob man kolidiert?

[3_of_8]

Einfach mithilfe von Sinus/Cosinus und Radius ausrechnen.

[dino]

abstand von was zu was???

wenn ich wüsste welche Punkte ich mir angucken müsste wäre ich schon fertig

[3_of_8]

Also: Du hast eine Menge von Punkten P, bei denen du auf Kollision überprüfen willst.

Jetzt berechnest du für jeden Punkt Q aus P mithilfe des Hypotenusensatzes den Abstand PM wobei dein Kreis k(M;r) ist. Wenn PM<=r, dann war das eine Kollision.

[dino]

nun das sind aber sehr sehr viele Punkte...

[dino]

geht das auch anders?

[Sidorion]

Eine Kugel prallt NIE auf zwei Ecken gleichzeitig. Und wenn Doch, dann prallt sie halt auf eine zuerst. Sprich Du berechnest den Abprall von der einen Ecke und mit dem neuen Richtungsvektor dann den Abprall an der andern. Das ist dann genausogut, als wäre sie gleichzeitig an beiden abgeprallt, was sie ja eh NIE tut.

[dino]

und welche zuerst macht keinen unterschied?

Edit: mit der gerade fand ich schon gut, aber kann man die kollision nicht auch anhand anderer methoden testen?

[Nikolas]

Die Frage ist eben, ob du für den Kreis eine Bewegungsgleichung aufstellst und die dann mit den Punkten schneidest, oder ob du den Kreis immer ein kleines Stückchen verschiebst und dann auf Kollision testest.
Erste Methode ist dann sinnvoll, wenn du nur einen Kreis hast oder, wenn die Orte aller abprallrelevanter Punkte von Beginn der Simulation feststehen. Dann kannst du mit einer recht einfachen Rechung überprüfen, an welchen Punkt der Kreis als erstes kommt und auch, ob mehrere Punkte gleichzeitig getroffen werden.
Bei der zweiten Methode musst du nach jedem Umsetzen den Pythagoras benutzen (@Borg: wo hast du hier einen Hypothenusensatz?), bei dem du auch überprüfen kannst, welcher Punkt als erster getroffen wurde.

[Cöster]

Zitat:

Zitat von dino

und welche zuerst macht keinen unterschied?

Nö, wieso sollte es?

Zitat:

Zitat von dino

Edit: mit der gerade fand ich schon gut, aber kann man die kollision nicht auch anhand anderer methoden testen?

Wieso, die Gerade ist doch das Einfachste. Die andere Methode ist eben, sie nacheinander abprallen zu lassen.

Zitat:

Zitat von dino

und wie findet man am besten herraus, ob man kolidiert?

Wenn es sich bei den Körpern wie im Beispiel ganz oben um einfache Quadrate handelt, muss man sich NICHT etliche Punkte raussuchen und gucken, ob sie geschnitten werden:

Erstmal prüfen, ob eine der Kanten berührt wird. Das ist denke ich relativ einfach:

Delphi-Quellcode:

function CollidesWithEdge(const Circle: TCircle; Rect: TRect): Boolean;
begin
  result :=
    { vertikale Kanten }
    ((Circle.Center.X + Circle.Radius > Rect.Left) and
    (Circle.Center.X - Circle.Radius < Rect.Right) and
    (Circle.Center.Y > Rect.Top) and
    (Circle.Center.Y < Rect.Bottom)) or
    { horizontale Kanten }
    ((Circle.Center.Y + Circle.Radius > Rect.Top) and
    (Circle.Center.Y - Circle.Radius < Rect.Bottom) and
    (Circle.Center.X > Rect.Left) and
    (Circle.Center.X < Rect.Right));
end;

Dann die Kollisionsabfrage für jede der Ecken:

Delphi-Quellcode:

function CollidesWithVertex(const Circle: TCircle; Rect: TRect): Boolean;
begin
  result :=
    { obere linke Ecke }
    (Circle.Radius > Hypot(Circle.Center.X - Rect.Left, Circle.Center.Y - Rect.Top)) or
    { obere rechte Ecke }
    (Circle.Radius > Hypot(Circle.Center.X - Rect.Right, Circle.Center.Y - Rect.Top)) or
    { untere linke Ecke }
    (Circle.Radius > Hypot(Circle.Center.X - Rect.Left, Circle.Center.Y - Rect.Bottom)) or
    { untere rechte Ecke }
    (Circle.Radius > Hypot(Circle.Center.X - Rect.Right, Circle.Center.Y - Rect.Bottom));
end;

[dino]

nein ich möchte aber auch draufrumkritzeln dürfen, dass mein kreis sogar an ner Kurve abtitscht

dafür müsste er nur immer ne Pixelabfrage machen, ob er nen Punkte berührt, nur wie geht das?

[xZise]

Zitat:

Zitat von Florian H

Ich hab das mal illustriert:
http://klammcam.loseoase.de/host/ball_abprallen.png

eine Frage: Wie kommt die Kollision 1 zu stande, wenn es doch an sich das gleiche wie 3 ist?

[Corpsman]

Hi,

Dein Problem sieht ganz nach meinem Pinpong Sample aus das ich die Letzten Tage mal zusammengestellt habe.


DL Link ( inclusive Source )

Gruß Corpsman

[dino]

3 trifft mit einer anderen höhe auf das Rechteck
(1 müsste hierfür etwas weiter links und demnach auch etwas weiter runter gezeichnet sein)
sieht man zwar nicht, ist aber so

wie kann man denn nun diese PxelanPixel?-frage lösen?

[Sidorion]

genau so, wie mehrfach beschrieben.
Vektor Pixel-Kugelmitte=>Normale.
Winkel Einfall-Normale = Winkel Ausfall-Normale.
=> Ausfall = Einfall+2*(Winkel Einfall-Normale)
//Edit: Der Abprall an Linien geht übrigens genauso mit einer Ausnahme: Du berechnest vorher den Pixel der Line, den die Kugel berührt.

[dino]

auf welche frage war das die antwort???

[Sidorion]

Sorry..du wolltest woht wissen, ob und welchen Pixel die Kugel während ihrer Bewegung berührt...
Ob ist relativ einfach: alle, deren Abstand zur Strecke Iststandort-Sollstandort kleiner Radius der Kugel (wobei hier zu beachten ist, dass falls der kürzeste Abstand ausserhalb der Strecke (also hinter dem Zielpunkt) liegt, (Abstand Pixel-gerade)^2 + (Abstand Lotfußpunkt-Zielpunkt)^2 <=Radius^2 sein muss).
für alle diese Pukte berechnest Du nun den Abstand zum Startpunkt wie Folgt:
1. Berechnung Abstand LotFuß zum Startpunkt
2. hiervon ziehst Du ab: wurzel(Radius^2-(Abstand Punkt-gerade)^2).
Der kleinste Wert ist dann der Pixel, der zerst berührt.

Wenn Dir das zu kompliziert war, sag bescheid, dann zieh ich mir heute abend mal ne Zeichnung aus den Fingern.

[dino]

ich hab an eine Stelle geschrieben, dass ich auch auf die canvas der Form zeichnen will(per maus) und der Ball soll dann auch daran abtitschen

hier jeden Punkt zu speichern und immer wieder zu testen ist mir ein bisschen viel

der soll nur um sich gucken, ob da Pixel sind

also nur in die bewegungsrichtung zugewandte kreishälfte

[Sidorion]

Das ist doch das selbe...Der Canvas ist doch ein 2dim array wo die farbe gespeichert ist. Du liest einfach per readline die bitmap des canvas aus und da kannst du dann gucken, ob pixel gesetzt ist oder nicht. ReadPixel ginge auch, ist aber langsamer.
mit dem um sich gucken ginge auch, aber dann must Du gewährleisten, dass sich der Kreis je Schritt nur um einen Pixel bewegt.

[Cöster]

Zitat:

Zitat von Sidorion

Sorry..du wolltest woht wissen, ob und welchen Pixel die Kugel während ihrer Bewegung berührt...
Ob ist relativ einfach: alle, deren Abstand zur Strecke Iststandort-Sollstandort kleiner Radius der Kugel (wobei hier zu beachten ist, dass falls der kürzeste Abstand ausserhalb der Strecke (also hinter dem Zielpunkt) liegt, (Abstand Pixel-gerade)^2 + (Abstand Lotfußpunkt-Zielpunkt)^2 <=Radius^2 sein muss).
für alle diese Pukte berechnest Du nun den Abstand zum Startpunkt wie Folgt:
1. Berechnung Abstand LotFuß zum Startpunkt
2. hiervon ziehst Du ab: wurzel(Radius^2-(Abstand Punkt-gerade)^2).
Der kleinste Wert ist dann der Pixel, der zerst berührt.

Wenn Dir das zu kompliziert war, sag bescheid, dann zieh ich mir heute abend mal ne Zeichnung aus den Fingern.

Wenn du dich etwas genauer ausgedrückt hättest, könnte man es auch verstehen. Was meinst du mit Ist- und Sollstandort? der Mittelpunkt der Kugel vor und nach Bewegung? Wie errechnest du denn einen Abstand zwischen einem Punkt und einer Strecke? Was meinst du mit Zielpunkt und Startpunkt? Das gleiche wie der Sollstandort und Iststandort? Welche Gerade meinst du mit Gerade? Und außerdem kann man zu einer Gerade keinen Abstand messen. Was heißt Lotfußpunkt?

Prüfst du immer, ob sich der Ball dahin bewegen kann, wohin er sich bewegen will und bewegst ihn erst dann?

Zitat:

Zitat von Sidorion

Du liest einfach per readline die bitmap des canvas aus und da kannst du dann gucken, ob pixel gesetzt ist oder nicht. ReadPixel ginge auch, ist aber langsamer.

Du meinst wohl TBitmap.ScanLine und TCanvas.Pixels, oder?

Zitat:

Zitat von dino

der soll nur um sich gucken, ob da Pixel sind

Ja, das wär vielleicht gar nicht mal so schlecht. Dann bewegst du die Kugel aber nicht sofort um so viele Pixel, wie sie sich bewegen soll, sondern immer nur um einen. Kann man mit ner for-Schleife machen, wenn die Kugel eine Geschwindigkeit von 5 Pxs/Timeraufruf hat: for i := 1 to 5. In jedem Schleifendurchlauf prüfst du dann, ob sich auf den Pixels auf denen die Kugel jetzt ist und vorher nicht war, nicht zu überschreitende Pixels befinden. Wenn ja, berechnest du mit jedem dieser nicht zu überschreitenden Pixels nacheinander die neue Richtung. In diese bewegt sich die Kugel dann beim nächsten Schleifenaufruf um einen Pixel.

[Sidorion]

zu1:
Um den großen deutschen Philosophen Wiege zu zitieren: ich werd heute Abend mal ein Bild malen.
Den Abstand eines Punktes von einer Geraden kann man sehr wohl ermitteln: man fällt ein Lot vom Punkt auf die Gerade (sprich mann nimmt eine zweite Gerade, die senkrecht auf der ersten steht und durch den Punkt geht. Dann ermittelt man den Schnittpunkt der beiden Geraden). Der Schnittpunkt ist der Fußpunkt des Lots, also Lotfußpunkt. Jetzt kann ich bequem den Abstand des Lotfußpunktes zum Punkt berechnen.
Die besagte Gerade ist eine Gerade, die durch die Punkte M1 und M2 geht. (wobei M1 der Kreismittelpunkt vor der Bewegung, M2 der Kreismittelpunkt nach der Bewegung). Vektoriell ausgedrückt ist die Greade durch die Gleichung m1^+ m*(m2^-m1^), wobei bezeichner mit^ Vektoren darstellen und ohne ^ Skalare. Die Gleichung der Lotgeraden wäre dann P^+n*(1/m2^-1/m1^), wobei 1/Vektor in diesem Fall den Umkehrvektor bedeutet (x und y vertauscht).
Setzt man die beiden Geradengleichungen gleich, erhält man ein Gleichungssystem mit 2 Gleichungen und 2 Unbekannten, das man auf herkömmliche Weise löst. Das Ergebnis ist der Schnittpunkt oder Lotfußpunkt L. Abstandsberechnung wie oben.
Jetzt setzt man den Lotfußpunkt L in die erste Gleichung, erhält man ein ml (Abstand Lotfuß zu m1^). Ist dieses Negativ, legt der Lotfuß ausserhalb der Strecke M1M2, und zwar in Richtung M1.
Setzt man M2 in die erste Gleichung ein, erhält man ein m2, das die Länge der Strecke M1M2 darstellt.
Ist nun ml <= m2, ist der Lotfuß auf der Strecke M1M2 und wir können davon ausgehen, falls LP<=r(Radius des Kreises) wird der Kreis während seiner Bewegung den Punkt treffen.
Ist m2-m1>r, ist der Punkt P so weit weg, dass der Kreis den Punkt bis zum Ende seiner Bewegung nicht treffen wird.
kompliziert wird der dritte Fall: m2-m1<=r hier müssen wir die Eigenschaften eines jeden Dreiecks heranziehen. In diesem Fall wäre r die hypothenuse und LP und m2-m1 die Katheden. ist jetzt die Summe der Kathedenquadrate kleiner oder gleich dem Hypthenusenquardat wird der Kreis den Punkt treffen, andernfalls nicht.

zu2: ja andernfalls würde es keinen Sinn machen. Ich prüfe, wie weit sich der Kreis bewegen KANN und rechne dort den neuen Richtungsvektor aus. Ab da das gleiche Spiel, nur mit neuem Richtungsvektor und verringertem Weg.

zu3: ja meine ich, wusste aber nicht aus dem Kopf wie die funktione heissen

[Sidorion]

Hab grad ne schicke Zeichnung im Netzt gefunden: Abstand Punkt Gerade.
So kriegt man gleich alles raus, was man braucht: Abstand und Fußpunkt F.
Alle Punkte P, Deren Abstand d größer r fallen gleich weg.
Alle Punkte für die gilt FM1^=-m*M2M1^ {m | m e R+} fallen auch weg.
Alle Punkte, für die gilt |FM1^| > |M2M1^|+r fallen auch weg.
alle anderen fallen nur weg, wenn d^2+x^2<r^2, wobei x=|FM1^|-|M2M1^|.

Um nun rauszukriegen, mit welchem die Kugel zuerst kollidiert geht man wie folgt vor:

die Ergebnismenge wird nach |FM1^|-x aufsteigend sortiert, wobei x=sqrt(r^2-d^2).
Wenn man |FM1^|auch quadriert spart man sich hier das Wurzelziehn, wobei sich die Sache deutlich beschleunigt.
der erste in der Liste ist der Punkt mit dem die Kugel kollidiert.

Jetzt kann man den 'Kreismittelpunk zum Zeitpunkt der Kollision' M3 rauskriegen, indem man den Vektor M2M1^ durch seinen Betrag teilt, mit dem entsprechenden |FM1^|-x aus der Liste multipliziert und zu M1 addiert.

N^ (Normalenvektor des Punktes zur Kugel) errechnet sich dann durch P-M3.
neuer Richtungsvektor des Kreises bestimmt sich mit Ausfall=Einfall an diesem N^.
Betrag des neuen Richtungsvektor |M2M1^| - |FM1^|-x und das Spiel beginnt von neuem, solange bis im Weg der Kugel kein Hindernis mehr ist.

Zielpunkt des Kreises ist dann letzter Kollisionspunkt M3n+Letzter Richtungsvektor.

[dino]

die mathematik hab ich drauf, jedoch hab ich wiegesagt keine Liste an Pixel, die beobachtet werden müssen, darum würde ich gerne wissen, wie das mit dem readline gehen soll...
muss ich dafür nen neuen threat aufmachen?
dann könnt ihr hier die andere Lösung weiterdiskutieren

[Sidorion]

Der Canvas auf dem Du zeichnest hat ein Bitmap. dieses kannst du mit ScanLine abfragen. Scanline gibt dir die Farbinformationen der entsprechenden Zeile zurück. Jetzt kannst Du Pixel für Pixel gucken, ob Hintergrundfarbe oder Zeichenfarbe. Wenn der Pixel in der Zeichenfarbe ist, musst Du ihn(seine Position x und y) in die Liste der potentiellen Hindernisse aufnehmen.
Wobei Du wieder Performance sparen kannst, wenn du nur die Zeilen zwischen Startpunkt und potentiellem Endpunkt +-Kreisradius scannst. Beim Auswerten kommen auch nur die Spalten zwischen Start und Ende in Frage.

Alternativ kannst Du das ganze Bitmap nach jedem Zeichenvorgang scannen und das Ergebnis in ein Bitfeld eintragen. Dieses ist dann mui schneller zu durchwühlen als die Bitmap.

Ich würde Dir die zweite Variante trotz deiner Aversion gegen das doppelte Speichern der Information empfehlen, selbst wenn Du Dich für die pixelweise Bewegung entscheiden solltest, da ein Arrayelement auswerten um mehrere Zehnerpotenzen schneller ist, als Bitmaps auswerten und bei Bewegungen kommts auf Geschwindigkeit an.

[dino]

ich werde pixelschritte machen und wollte eigentlich die Pixel überprüfen, die von der Bewegungsrichtung zugewandten Seite ein Pixel in Bewegungsrichtung gehen, also so

[Sidorion]

Tja das ist dann mindestens genauso kompliziert.
-Als erstes musst du den neuen Kreismittelpunkt errechnen. Das geht über die Rasterisierung einer Strecke (algo gibts im Netz).
-Dann musst du die Menge aller Punkte ermitteln, die er zeichnen würde. Dafür gibt es einen Algorithmus, mit dem man einen Kreis rasterisieren kann (also am neuen Kreismittelpunkt). Muddu im Netz wühlen.
-Von diesen Punkten musst du gucken, ob das Kreuzprodukt zwischen Vektor M->Punkt und Richtungsvektor der Bewegung größer gleich null ist. Das sind dann die Punkte in Bewegungsrichtung.

Diese Algorithmen sind auch in jedem guten Computergraphik-einsteiger-buch zu finden.

Ich denke, die Methode, die ich Dir vorgeschlagen habe ist einfacher zu realisieren und wird vermutlich schneller sein, da man nicht jeden Pixel die Berechnungen durchführen muss.

p.s.: falls sich der Radius Deines Kreises nicht ändert kannst Du auch in nem Graphikprogramm den Kreis malen und dann die Positionen der Kreispunkte relativ zum Mittelpunkt ermitteln und Dir in einem Array speichern.

[dino]

die zu Beobachtenden Pixel vor dem Kreis, ändern sich mit dem Richtungsvektor, also könnte man 1. immer nur errechnen, wenn man den Richtungsvektor ändert und 2. für alle 360 Möglichkeiten irgendwo speichern

was haltet ihr davon?

[Sidorion]

Nichts, weil Du u.U. nicht alle 1° einen Pixel hast, sondern alle 0,576° oder alle 3,6678°, je nachdem wie groß Dein Kreisradius ist.
Bei Raduis 0 hast du 1 punkt, bei 1 sinds 4, bei 2 vielleicht 12 usw.
1. musst Du immer berechnen, weil sich der Kreis in eine der acht Haupt-und nebenachsen um 1 Pixel bewegt.
zu 2. die Menge der Pixel in der Abfragemenge geb ich Dir recht. die muss man nur bei Richtungsänderung neu berechnen.

[dino]

ich hab keine nachkommastellen bei Grad

[Sidorion]

Doch. Die heissen dann Minuten, Sekunden und so weiter. Im Bogenmaß sowieso.