Kugel/Kreis prallt von Eck/Kante ab

[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.