Wie finde ich 2D-Gitterzellen, die von einem sich bewegenden Kreis überstrichen werden?

9

Ich mache ein Spiel basierend auf einem 2D-Gitter, wobei einige Zellen passierbar sind und andere nicht. Dynamische Objekte können sich unabhängig vom Gitter kontinuierlich bewegen, müssen jedoch mit unpassierbaren Zellen kollidieren.

Ich habe einen Algorithmus geschrieben, um einen Strahl gegen das Gitter zu verfolgen, der mir alle Zellen gibt, die der Strahl schneidet. Das tatsächliche Objekt hat jedoch keine Punktgröße. Ich vertrete sie derzeit als Kreise. Aber ich kann keinen effektiven Algorithmus finden, um einen sich bewegenden Kreis zu verfolgen. Hier ist ein Bild von dem, was ich brauche: Geben Sie hier die Bildbeschreibung ein

Die Zahlen zeigen, in welcher Reihenfolge der Kreis mit Gitterzellen kollidiert. Kennt jemand den Algorithmus, um diese Kollisionen zu finden? Vorzugsweise in C #.

Aktualisieren Der Kreis kann größer als eine einzelne Gitterzelle sein.

Keine Ursache
quelle
mmh warum kollidieren 3 VOR 4?
FxIII
@FxIII Ich habe den Kreis im Bild tatsächlich verschoben und er hat 3 vor 4 getroffen. Nur knapp, aber immer noch vorher.
Nevermind

Antworten:

6

Ich denke, Ihre Zeichnung ist etwas irreführend, weil Sie Striche vom Punkt auf dem Kreis zeichnen, der Ihre Bewegungsrichtung tangiert. Ich kann sehen, dass die Kollisionen mit Ihren Gitterkanten auftreten, wenn die oberen und linken Punkte Ihres Kreises eine Kante berühren.

Sei C dein Zentrum und r der Radius, also P ' = C + ( r , 0) und P " = C + (0, r).

Wenn D Ihr Richtungsvektor (der Versor) ist, haben Sie zwei Linien:

R '= D · t + P' ,

R = D · t + P

Sie müssen einfach den Schnittpunkt dieser Linien mit den Gleichungslinien finden:

y = i und y = i , das sind die Kanten Ihres Gitters!

Die Lösung ist einfach, da Sie einfach die x- oder y-Komponente von R 'und R "berücksichtigen müssen. Sie finden den t s -Wert für jeden Einschnitt und die Punkte für diese t s. Sortieren Sie diese Punkte einfach nach t und Ihnen sind fertig.

Ich glaube, Sie können leicht sagen, welche Zelle getroffen wird, wenn Sie den Schnittpunkt kennen.

Dies funktioniert, wenn r <1 (die Zellenbreite und -höhe) ist.

Es funktioniert auch für die anderen Fälle, in denen einfach P ' und P " berücksichtigt werden . Wir wählen TOP und LEFT aufgrund der Richtung. BOTTOM und RIGHT sollten für die entgegengesetzte Richtung berücksichtigt werden. Sie verstehen, warum.

Schauen Sie sich nun dieses Bild an: großer Kreis

Der Kreis ist größer als eine einzelne Zelle und wir nehmen an, dass er in die gleiche Richtung wie Ihre Zeichnung verläuft. P1 ist der erste Punkt, der sich berührt, P2 ist der zweite, P3 ist nutzlos, weil er sich in der unteren Hälfte befindet. Was Sie tun müssen, ist, Strahlen von P1 und P2 wie zuvor gesehen zu werfen und dasselbe für die vertikalen Linien zu tun.

Im Allgemeinen haben Sie neben den oberen und linken Punkten andere Ausgangspunkte, von denen aus Sie Ihre Strahlen abschießen. Je größer Ihr Kreis ist, desto mehr Strahlen müssen geworfen werden.

Um ehrlich zu sein, können Sie es vermeiden, all diese Strahlen unter geometrischen Gesichtspunkten abzuschießen, aber das kann das Verständnis der Dinge erschweren.

FxIII
quelle
Ja, ich habe mir die P'- und P'-Punkte selbst ausgedacht, konnte aber nicht herausfinden, was zu tun ist, wenn der Kreis größer als eine einzelne Zelle ist. Zusätzliche Punkte sind wirklich sinnvoll (und ich muss natürlich nur Strahlen zwischen P 'und hinzufügen P ")
Nevermind
Es können geometrische Überlegungen angestellt werden, die die Berechnungen vereinfachen. Die Verwendung der Implementierung kann jedoch erfahrungsgemäß zu denselben Ergebnissen führen.
FxIII
Ist es klar, dass Sie getrennt auf horizontale und vertikale Gitterlinien testen müssen?
FxIII
Ich denke, Sie müssen auch überprüfen, wann der Kreis einen Gitterscheitelpunkt bedeckt, da der Kreis mit der diagonal benachbarten Zelle an seiner Ecke kollidiert, aber nicht unbedingt der obere / linke / untere / ganz rechte Punkt des Kreises ist, der ihn zuerst berührt (und Sie werden die Kollision zu früh erkennen.) Beispiel: Quadrate 3,4,5 im Beispieldiagramm in der Frage. Sie werden in der Reihenfolge getroffen (3, dann 4, dann 5), aber Ihr Algorithmus erkennt 4 und 5 gleichzeitig.
Finnw
@finnw sie berühren sich nur dann gleichzeitig, wenn sich der cicle genau in richtung der halbierenden bewegt.
FxIII
1

Wenn Sie Ihren Strahlenkollisionsalgorithmus verwenden möchten, können Sie acht Punkte auf jedem Kreis auswählen (in Schritten von 45 Grad, ausgerichtet an Ihrem quadratischen Gitter) und die Strahlenkollision zwischen entsprechenden Punkten verwenden (dh von oben auf einem Kreis nach oben). Die Vereinigung all dieser Strahlenkollisionen ist die gesamte Menge der durchschnittenen Zellen.

Sie könnten dies wahrscheinlich ein wenig verbessern - zum Beispiel, indem Sie das Liniensegment vom Mittelpunkt eines Kreises zum Mittelpunkt des anderen Kreises verwenden, das jedoch auf beiden Seiten um den Radius des Kreises sowie die parallelen Liniensegmente erweitert wird zu beiden Seiten an den Enden der Kreise.

TreDubZedd
quelle
8 Strahlen garantieren wahrscheinlich alle Kreuzungen, aber sie geben sie nicht in der richtigen Reihenfolge. Und für Kollisionen brauche ich Ordnung, nicht nur eine Liste von Zellen.
Nevermind
Erweitern Sie Ihren Strahlenkollisionsalgorithmus, um für jede Kollision einen t-Wert beizubehalten. Wenn Sie die Vereinigung von Zellen erhalten, können Sie nach dem t-Wert sortieren, um die richtige Reihenfolge zu erhalten.
TreDubZedd
Aber wie kann ich den t-Wert verschiedener Strahlen vergleichen?
Nevermind
Wenn Sie immer aus demselben Kreis stammen, sind Ihre Schnittpunkte Entfernungen von diesem Kreis. Wenn Sie zu einer Zelle kommen, die Sie bereits gesehen haben, verwenden Sie sie, wenn der t-Wert der aktuellen Kollision kleiner als der vorherige ist. Andernfalls verwerfen Sie den Schnittpunkt (behalten Sie das Original bei).
TreDubZedd
1
Möglicherweise können Sie mit nur zwei Strahlen an den Seiten des Kreises senkrecht zur Bewegung davonkommen. Dann können Sie sehen, welche Kacheln von den Strahlen getroffen werden, und Sie können den Rest überprüfen, um festzustellen, ob ihre Zentren zwischen den beiden Strahlen liegen. Das einzige, was fehlen sollte, wären Dinge, die am Anfangs- oder Endkreis kollidieren, aber das sind nur zwei Kreise und können leicht gehandhabt werden. Es kann etwas langsamer als acht Strahlen sein, ich bin nicht sicher; Sie müssten die Zahl jedoch nicht anhand der Größe des Kreises skalieren.
Lunin
1

Ich sage nicht, dass dies eine perfekte Analogie ist, aber Sie könnten über Bresenhams Linienalgorithmus nachdenken . Eine Änderung dieses Algorithmus oder einer seiner Erweiterungen kann hilfreich sein, insbesondere wenn Sie ihn mit einigen anderen Posts und Kommentaren koppeln. Normalerweise befasst sich dieser Algorithmus nicht mit der Bestellung, aber ich würde denken, dass Sie dies ziemlich trivial hinzufügen können.

Ryan
quelle
Ich habe auch darüber nachgedacht, aber meiner Meinung nach ist dies nicht der richtige Algorithmus. Bresenham wählt nur ein Pixel, er braucht alles. Und es wäre schwierig, Bresenham an einen Kreis mit nur einem Pixel anzupassen.
Zacharmarz
Der Ray Tracer, den ich benutze, basiert auf dem Bresenham-Algorithmus. Ich habe Probleme, es von einer dünnen Linie auf eine "fette" zu verallgemeinern, insbesondere von einem Kreis.
Nevermind