Moin!

Nachdem Separating Axis sehr einfach implementiert war, stellte sich grade raus, dass ich ja gar nicht immer konvexe Polygone habe

Genau gesagt ist eins der Polygone manchmal nichtkonvex, aber immer einfach (also nicht-selbst-schneidend). Das zweite ist immer konvex, genauer fast immer ein AxisAligned-Rechteck (es wäre möglich, immer mit einem Rechteck zu rechnen, wenn das hilft).

Es kann angenommen werden, das die Polygone "sortiert" sind, also die Punkte immer in Uhrzeigerrichtung angegeben sind.



Für später bräuchte ich das dann noch mit einem Kreis statt einem AA-Rechteck, aber da hab ich schon eine Idee (Distanz Mittelpunkt-Kante < Radius, Innen/Außen aus Vorzeichen).

Klar, die "einfache" Variante wäre alle Kanten mit allen Kanten zu schneiden und zu testen, ob ein Schnittpunkt existiert. Da das aber alles andere als performant ist, frag ich mal hier.

Grüße,
Martok

Warum zerlegst du nicht dein nicht-konvexes Polygon in konvexe Polygone (Triangulation)? Wenn du die peformant mit dem Seperating Axis Theorem lösen kannst (kenne den Algo nicht im Detail) sollte das doch kein Problem sein.

Einziges Problem könnte höchstens sein, wenn du neben Polygonen auch Linien hast, weil dann im richtigen Winkel die Linie vielleicht mit keinem der Teilpolygone kollidiert, weil es exakt die Schnittgerade trifft.

PS:
Guck mal hier narfation.org/alggeo/triangulation.pdf

PPS:
Noch eine Anmerkung: Wenn der Aufwand durch die vielen Dreiecke zu hoch wird, dann nimmt man normalerweise eine Bounding Box, also "ein minimal umschließendes Rechteck" deines Polygons (geht natürlich auch mit einer Kugel). Damit kannst du die Kollision einfach berechnen und falls die Bounding Box mit einem Objekt zusammenstößt, dann berechnest du die Kollision detailiert mit deinem aufwändigen Polygon. Es gibt auch noch räumliche Bäume, mit denen du vorher schon viele Kollisionspartner ausschließen kannst.

Hm ja, das ginge. Sweepline hatte ich schon beim Suchen vorbeifliegen sehen, aber so rein vom Gefühl her scheint das alles noch schlechter zu performen als das dumme O(n*m)-alle-mit-allen-schneiden. Das Gefühl hat sich mit dem Vortrag eher noch verschärft Wenn schon der Tesselation-Schritt länger dauert, kann da SAT auch nix mehr rausholen

@PPS: Ja, das passiert implizit sowieso schon, weil ich mir nur die Polys von den Feldern hole, bei denen eine Kollision theoretisch möglich ist. Und 2D sowieso, also brauch ich auch keine höherdimensionalen Bäume.

Tut, aber ist halt komisch: Klick. Und damit mein ich nicht mal den Check für die zweite Strecke, dass ich da einfach hätte umstellen können statt das nochmal vom Anfang zu ermitteln ist mir klar, war aber grad einfacher hergeleitet

Martok hat folgendes geschrieben :

Wenn schon der Tesselation-Schritt länger dauert, kann da SAT auch nix mehr rausholen

Man würde ja normal die Tesselation auch nur einmal machen. Wenn sich deine Polygone natürlich dynamisch in der Form verändern, dann ist das natürlich was andres.

Heyho,

ich werf das mal einfach so in Raum: www.realtimerenderin...m/intersections.html Vlt. findest du da ne Lösung für dein Problem.

MfG Bergmann.

Hi,
mir fällt dabei spontan eine Idee ein, welche das auch einigermaßen performant durchzuführt.
Einziges Problem bei der Sache: Wenn ein Polygon vollständig in einem anderen liegt, wird keine Kollision angezeigt.
Einfach überprüfen ob eine Linie des konkarven Polygons durch das Viereck geht, also kurzgesagt jede Linie des konkaven Polygons mit jeder Linie des anderen Polygons. Würde dann als auch mit konkarv, konkarv funktionieren.

Das geht mit Vektoren:

VektorPunktA + R * VektorRichtungA = VektorPunktB + S * VektorRichtungB
Auflösen auf R: R = (VektorPunktB - VektorPunktA + S * VektorRichtungB) / VektorRichtungA

Da s unbekannt ist zerlegen wir den Teil:

ReinesR = (VektorPunktB - VektorPunktA) / VektorRichtungA
STeilVonR = (VektorRichtungB) / VektorRichtungA

Für die Gleichungen nimmst du zum Beispiel die X-Koordiante der Vektoren.
Danach nimmst du die Gleichung für Y und rechnest weiter:

Allgemeine Gleichung ist:
AY + (ReinesR + STeilVonR) * ARichtungY = BY + S * BRichtungY
STeilVonR * BY - S * DY = CY + S * DY - AY - ReinesR * BY

Durch umstellen (wenn ich keinen Fehler gemacht hab):
S = (BY - AY - ReinesR * ARichtungY) / (STeilVonR * ARichtungY - BRichtungY);

Dann nur nor noch gucken ob (0 < R < 1) und (0 < S < 1). Wenn beide ja dann schneiden sie sich.

ODER:

Hab aber keine Lust das auch nochmal ganz auszuführen dürfte aber etwas leichter sein. Die Linien als Funktionen betrachten und schauen ob ihr Wert an den Eckpunkten des Rechtsecks innerhalb des Y bzw. X Rahmens des Rechtsecks liegen (Zum Beispiel: Ob f(x) zwischen 3|7 liegt wenn die obere linke ecke des Rechtsecks(2|7) und die untere rechte Ecke (6|3)). Geht aber nur bei Rechtecken die parallell zum Koordinaten System sind.

INSGESAMT:
Bei meinem ganzen Linien Berechnungs Zeugs. Ums performanten zu machen immer erst ne Boundary-Kollisionsüberprüfung machen und dann den Rest.

Wunderbar hergeleitet, aber ich hab eine schlechte Nachricht für dich: das ist genau das, was mein aktueller Code tut Ich hatte mir das allerdings von Mathematica auswürfeln lassen. Und nebenbei gelernt, wie Vektorrechnung/LGS da funktioniert.

Der Teil nach dem ODER ist allerdings eine gute Idee, das scheint mir eine schöne AABB-Optimierung des Ganzen zu sein Ich werd mir das auf jeden Fall warmhalten und bei Gelegenheit mal implementieren. Danke!

Wie gesagt mach das sowohl auf x als auch auf y bezogen, damit es auch funktioniert wenn eine Spitze des Polygons von unten bzw oben in das Rechteck reinragt, außer dir fällt was einfacheres dazu ein.

Vielleicht kann dir dieses Paper hier bei deinem Problem helfen.

Es bestünde noch die Möglichkeit, dein Polygon rekursiv von seiner konvexen Hülle zu "subtrahieren". Du würdest dann eine Art Tesselation der Teile erhalten, die deinem Polygon noch fehlen, um konvex zu sein. Diese Berechnungen sind nicht die schnellsten, lassen sich allerdings im vorraus durchführen. Hast du dies, so kannst du zunächst prüfen, ob die konvexe Hülle deines Polygons getroffen wurde. Falls nein, kannst du sofort abbrechen. Falls doch, prüfst du mit SAT, ob und wo dein Polygon eines der "Fehlteile" trifft (das geht ebenfalls hierarchisch, also nach dem "early-out"-Prinzip). Dies ist dann dein gesuchter Intersektionspunkt. Bin mir allerdings nicht sicher, wie gut das funktioniert.