Polygon zwischen überschneidenden Vierecken

[Dooku]

Hi,

ich quäl mich schon etwas länger mit der Suche nach einem Algorithmus herum, der die überschneidende Fläche von zwei rotierten Rechtecken als Polygon zurückgibt. Einen Algorithmus für die Detektion einer Überschneidung zwischen den Rechtecken habe ich bereits: Überprüfen ob Viereck 1 eine der Ecken von Viereck 2 "beinhaltet" und das nochmal andersherum .

Auf die Schnittfläche übertragen würde das bedeuten, dass man die Fläche als Polygon definieren kann, wobei dessen Punkte aus allen "beinhalteten" Eckpunkten der Vierecke + den Schnittpunkten zwischen den Vierecken bestehen. Aber wie berechnet man diese Schnittpunkte? Gibts verlleicht irgendeine bessere Methode? Vlt existieren ja bereits Klassen (in Java) dazu,...

[flashpixx]

Baryzentrische Koordinaten

[Enno]

du musst doch "nur" die schnittpunkte der seiten berechnen.

von beiden Rechtecken sind doch immer die Koordinaten aller Ecken bekannt.

Rechteck 1 hat also die Ecken R1E1 bis R1E4 und Rechteck2 entsprechend R2E1 bis R2E4

einmal definiert und im Uhrzeigersinn nummeriert.

Dann brauchst du 4 Punkte um das Polygon zu erhalten:

R1Ex

R2Ey

(die beiden Ecken innerhalb des jeweils anderen Rechtecks)

Sowie die beiden Schnittpunkte der jeweils 2 Geraden

von R1Ex nach R1E(x-1) und von R2Ey nach R2E(y+1)

sowie von R1Ex nach R1E(X+1) und von R2Ey nach R2E(y-1)

verstanden was ich dir sagen will?

[Dooku]

Hmm ja... gar nicht mal soo einfach . Aber ich verstehe nicht ganz wie man damit die Schnittfläche berechnen soll, na gut ich hab das ganze Thema baryz. Koord. nicht wirklich verstanden . Kannst du nicht mal ein einfaches Beispiel dazu geben?

[Enno]

Berechnung des Schnittpunktes zweier Geraden

[Dooku]

du musst doch "nur" die schnittpunkte der seiten berechnen.

von beiden Rechtecken sind doch immer die Koordinaten aller Ecken bekannt.

Rechteck 1 hat also die Ecken R1E1 bis R1E4 und Rechteck2 entsprechend R2E1 bis R2E4

einmal definiert und im Uhrzeigersinn nummeriert.

Dann brauchst du 4 Punkte um das Polygon zu erhalten:

R1Ex

R2Ey

(die beiden Ecken innerhalb des jeweils anderen Rechtecks)

Sowie die beiden Schnittpunkte der jeweils 2 Geraden

von R1Ex nach R1E(x-1) und von R2Ey nach R2E(y+1)

sowie von R1Ex nach R1E(X+1) und von R2Ey nach R2E(y-1)

verstanden was ich dir sagen will?

Das funktioniert aber doch nur für normale (unrotierte) Rechtecke. Bei rotierten rechteck kann die Schnittfläche ein Polygon mit mindestens 3 und maximal 8 Ecken sein, wenn ich mich jetzt nicht irre.

[Enno]

aehm, ja. vergiss einfach was ich geschrieben habe!

[Dooku]

Um mal der Möglichkeiten mit den "eingeschlossenen Punkten" (die Eckpunkte die von den betrachteten Rechtecken eingeschlossen werden ) und Schnittpunkten nachzugehen : Wie kann man denn solche Schnittpunkte zwischen Vierecken bestimmen?

@flashpixx : Lassen sich diese baryzentrischen Koordinaten zur Detektion oder Schnittflächenbestimmung verwenden?

[flashpixx]

@flashpixx : Lassen sich diese baryzentrischen Koordinaten zur Detektion oder Schnittflächenbestimmung verwenden?

Nein nicht direkt. Die Fläche wird als Menge von Dreiecken beschrieben ( Polygonnetz ), diese Polygone werden dann in einer entsprechenden Datenstruktur verwaltet. Zu jedem Polygon wird die Normale ( Normalenvektor ) bestimmt und dann mit jedem Polygon des anderen Objektes der Schnittpunkt berechnet. Als Datenstrukturen für die Schnittberechnung kann man eine kd-Tree ( k-d-Baum ) oder Octree ( Octree ) verwenden.

Generell ist ist aber eine "Kollisionsdedektion" ( http://de.wikipedia.org/wiki/Kollisionserkennung_(Algorithmische_Geometrie) ) wozu man noch Boundvolumina ( Bounding Volume ) verwenden sollte. Ansonsten bitte einmal die Literatur zur Computergraphik durch sehen, dort finden sich genügend Ansätze für die Problemlösung

[Klotzkopp]

Einen Algorithmus für die Detektion einer Überschneidung zwischen den Rechtecken habe ich bereits: Überprüfen ob Viereck 1 eine der Ecken von Viereck 2 "beinhaltet" und das nochmal andersherum .

Nur als Anmerkung: Das funktioniert nicht.

[Gast runtimeterror]

Nur als Anmerkung: Das funktioniert nicht.

Weil ...

[Klotzkopp]

Weil ...

Kein Eckpunkt liegt innerhalb des anderen Rechtecks, trotzdem gibt es eine Überschneidung.

[Gast runtimeterror]

Da es sich bei den Rechtecken um konvexe Polygone handelt, kann man diese als Schnittmenge von vier Halbebenen darstellen. Die Schnittmenge der Halbebenen beider Rechtecke ergibt damit das gesuchte Polygon.

Den Flächeninhalt des Polygons bestimmt man z.B. mit der Gaußschen Trapezformel: Gaußsche Trapezformel

Oder: Man bestimmt den Schwerpunkt des Polygons und verbindet diesen mit allen Eckpunkten, wodurch dieser in mehrere Dreiecke zerlegt wird. Die Summe der Dreiecksflächeninhalte ist der Flächeninhalt des Polygons.

Schöne Grüße,

Kai

[Gast runtimeterror]

Recht hast du, den Fall hatte ich übersehen!

[flashpixx]

siehe http://de.wikipedia.org/wiki/Kollisionserkennung_(Algorithmische_Geometrie)

Kollision zweier konvexer Polyeder (z. B. durch V-Clip-Algorithmus),

Kollision n konvexer Polyeder (z. B. durch I-Collide-Algorithmus),

Kollision nicht-konvexer Polyeder (z. B. RAPID),

Ist doch alles angegeben.

[Dooku]

@Klotzkopp

ach verdammt^^ , da hast du leider recht

@runtimeerror

Sind Halbebenen nicht unendlich groß!? :confused:

Kennt jemand vlt ne Seite wo man die cpp, bzw. hpp Dateien des V-Clip Algorithmus' herbekommen kann, um sich dessen funktionsweise mal anzugucken.? Hab bei google so keine gefunden...

Mir ist übrigens noch etwas anderes in den Sinn gekommen,wobei ich nicht weiß wie es da mit der Performance ausschaut:

Man könnte doch vor dem Rendern eine Art Pseudo-FrameBuffer erstellen, in dem nach jedem gezeichnetem Element(die Vierecke) gespeichert wird, welche Pixel transparent oder gefüllt sind. Damit wäre es leicht eine Überschneidung pixel-perfekt zu erkennen. Dh ich bräuchte auch keine Schnittfläche mehr... Bleibt noch die Frage mit der Effektivität, im Vergleich zu anderen Algorithmen...

[flashpixx]

Man könnte doch vor dem Rendern eine Art Pseudo-FrameBuffer erstellen, in dem nach jedem gezeichnetem Element(die Vierecke) gespeichert wird, welche Pixel transparent oder gefüllt sind. Damit wäre es leicht eine Überschneidung pixel-perfekt zu erkennen. Dh ich bräuchte auch keine Schnittfläche mehr... Bleibt noch die Frage mit der Effektivität, im Vergleich zu anderen Algorithmen...

Das funktioniert nicht, wenn man transparente Körper zulässt, wenn Körper a und b auf x, y Achse identisch sind, aber nicht auf der z Achse, dann würde in diesem Fall eine Pixelüberschneidung statt finden, da man durch den ersten Körper hindurch auf den zweiten sehen kann, d.h. in 2D liegen sie übereinander, das wäre dann eine Kollision. Real in 3D liegt aber keine Kollision vor, ist letztendlich der gleiche Fall, den Klotzkopp schon geschilder hat.

Der erste Treffer liefert sogar ein Paper zu dem Algorithmus http://www.merl.com/reports/docs/TR97-05.pdf, das V steht für "Voronoi" siehe dazu auch http://en.wikipedia.org/wiki/Voronoi_diagram

Außerdem gibt es Bibliotheken (C++) die entsprechende Strukturen anteilig haben:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Optimisation/Chapter_main.html

Bearbeitet 17. Juli 2012 von flashpixx

[Dooku]

Da es sich aber um 2D-Objekte handelt, wäre eine andere Z-Ebene ja sehr leicht festzustellen.

[Gast runtimeterror]

Eine einzelne Halbebene ist unendlich groß, aber die Schnittmenge mehrerer Halbebenen kann einen konvexen Polygon beschreiben.

Falls das erste Rechteck R1 durch die Halbebenen A1, B1, C1, D1 beschrieben wird und das zweite R2 durch A2, B2, C2, D2, dann gilt das Folgende:

R1 = A1 ∩ B1 ∩ C1 ∩ D1

R2 = A2 ∩ B2 ∩ C2 ∩ D2

P = R1 ∩ R2 = A1 ∩ B1 ∩ C1 ∩ D1 ∩ A2 ∩ B2 ∩ C2 ∩ D2

P ist die Schnittfläche der beiden Rechtecke.

[Dooku]

Eine einzelne Halbebene ist unendlich groß, aber die Schnittmenge mehrerer Halbebenen kann einen konvexen Polygon beschreiben.

Falls das erste Rechteck R1 durch die Halbebenen A1, B1, C1, D1 beschrieben wird und das zweite R2 durch A2, B2, C2, D2, dann gilt das Folgende:

R1 = A1 ∩ B1 ∩ C1 ∩ D1

R2 = A2 ∩ B2 ∩ C2 ∩ D2

P = R1 ∩ R2 = A1 ∩ B1 ∩ C1 ∩ D1 ∩ A2 ∩ B2 ∩ C2 ∩ D2

P ist die Schnittfläche der beiden Rechtecke.

Eine Halbebene lässt sich ja durch eine Funktion ersten Grades (f(x) = ax + beschreiben...

Heißt das dann für die Schnittfläche von R1 und R2, dass diese gleich der Schnittfläche von acht verschiedenen Funktionen ist?

Das ist jetzt aber auch nicht gerade leicht umzusetzen ^^. Für zwei Funktionen ist die Schnittfläche die Differenz der beiden Stammfunktionen. Lässt sich das jetzt iwie auf acht übertragen?

[Gast runtimeterror]

Also das mit dem f(x)-Ansatz würde ich sein lassen. Damit lassen sich ja keine senkrechten Geraden darstellen.

Ich würde in deinem Spezialfall das erste Rechteck als Ausgangspolygon (Menge von Eckpunkten und den dazugehörigen Kanten) wählen und diesen dann nacheinander mit den Halbebenen schneiden. Hierbei können neue Eckpunkte und Kanten entstehen oder wegfallen. Das ist nicht schnell, aber funktioniert (auch in höheren Dimensionen).

Eine andere meiner Meinung nach elegantere (aber ungetestete) Methode wäre die konvexe Hülle beider Rechtecke zu bestimmen und diese zu triangulieren (bestehende Reckteckkanten und -eckpunkte müssten dabei erhalten bleiben). Alle Dreiecke deren Schwerpunkt sich innerhalb beider Rechtecke befinden bilden zusammen den gesuchten Schnittpolygon. Die Bestimmung der Fläche wäre dann trivial. Die Triangulation wäre dann der schwierigere Teil. Auch dieser Algorithmus lässt sich auf höhere Dimensionen extrapolieren.

Ein wirklich einfacher Ansatz (in Formel einsetzen und ausrechnen) fällt mir gerade nicht ein.

... nur so als Anregung

[flashpixx]

Eine andere meiner Meinung nach elegantere (aber ungetestete) Methode wäre die konvexe Hülle beider Rechtecke zu bestimmen und diese zu triangulieren (bestehende Reckteckkanten und -eckpunkte müssten dabei erhalten bleiben). Alle Dreiecke deren Schwerpunkt sich innerhalb beider Rechtecke befinden bilden zusammen den gesuchten Schnittpolygon. Die Bestimmung der Fläche wäre dann trivial. Die Triangulation wäre dann der schwierigere Teil. Auch dieser Algorithmus lässt sich auf höhere Dimensionen extrapolieren.

Es hat sich anscheinend niemand einmal das verlinket Paper unter http://www.merl.com/reports/docs/TR97-05.pdf durchgelesen, das ich in Post 17 verlinkt hatte, denn dort steht:

[...] This paper presents the Voronoi-clip, or V-clip, collision detection algorithm for polyhedral ob- jects specified by a boundary representation. V-clip tracks the closest pair of features between convex polyhedra, using an approach reminiscent of the Lin-Canny closest features algorithm. V-clip is an improvement over the latter in several respects. Coding complexity is reduced, and robustness is significantly improved; the implementation has no numerical tolerances and does not exhibit cycling problems. The algorithm also handles penetrating polyhedra, making it useful for nonconvex polyhedral collision detection. This paper presents the theoretical principles of V-clip, and gives a pseudocode description of the algorithm. It also documents various tests that compare V-clip, Lin-Canny, and the Enhanced Gilbert-Johnson-Keerthi algorithm, a simplex- based algorithm that is widely used for the same application.[...]

Alleine der Abstract liefert schon genügend Hinweise darauf.

Collision Detection ist ein komplexer Bereich und man sollte dazu eben auch die passenden mathematischen Kenntnisse besitzen, denn "mal schnell eben das codiert" klappt nicht