Überprüfung, ob sich Rechtecke schneiden

[Nikolas]

Hallo

Ich bin gerade auf der Suche nach einer schnellen Lösung für folgendes Problem:

Ich habe ein ruhendes Rechteck, dessen Kanten parallel zu den Achsen liegen. Ein anderes Rechteck liegt irgendwie gedreht im Raum. Die Frage ist jetzt, ob sie sich beühren.

Eine Möglichkeit wäre natürlich alle Kanten des einen mit allen Kanten des anderen zu schneiden und auf schnittpunkt im richtigen Bereich zu testen. Nur ist das etwas aufwändig. Später soll das ganze in einem Spiel laufen, von da her Suche ich besonders nach einer perfomanten Lösung. Weiss da jemand etwas schnelleres?

Nikolas

[Robert Marquardt]

Game mit OpenGL bzw. DirectX? Wenn ja dann sollte es da passende Funktionen geben. Vierecke sind zwei aneinanderliegende Dreiecke. Dafuer gibt es bestimmt Schnitttestfunktionen.

[Nikolas]

Nein, Game mit C++ :)

Alles reine Handarbeit :mrgreen:

[DGL-luke]

Hallo,

projiziere die Rechtecke zuerst auf eine 2-dimensionale ebene (z.B. indem du sie "von oben" ansiehst, du kannst dann einfach die z-koords untern tisch fallen lassen).

Benutze dann IntersectRect. Wenn du damit keine Kollision erkennst, gibts auch keine. Wenn doch, musst du das ganze nochmal 3-dimensional prüfen, bzw. prüfen, ob es in einer der anderen ebenen (yz und xz) auch kollisionen gibt (bei einem rechteck mit höhe = 1 bzw. 0 kannst du dann davon ausgehen, dass eine kollision genau dann stattfindet, wenn du in allen drei ebenen eine erkennst, glaube ich... :gruebel: )

[shmia]

Zitat:

Zitat von DGL-luke

Benutze dann IntersectRect.

Hier werden aber Rechtecke erwartet, die rechtwinklig zum Koordinatensystem liegen. Zumindest ein Rechteck tut dies nicht.

@Nikolas oder Admin: bitte Thema ändern nach: Überprüfung, ob Quader sich schneiden.

[DGL-luke]

...trotzdem funktioniert mein ansatz. und ich denke, Nikolas spricht von Rechtecken.

[shmia]

Zitat:

Zitat von DGL-luke

und ich denke, Nikolas spricht von Rechtecken.

> Ein anderes Rechteck liegt irgendwie gedreht im Raum
"Gedreht im Raum" deutet für mich auf 3 Dimensionen hin. Er soll sich halt erklären, ob es 2 oder 3 Dimensionen sind.

[OregonGhost]

Zitat:

Später soll das ganze in einem Spiel laufen, von da her Suche ich besonders nach einer perfomanten Lösung.

Wenn es um Performance geht, kannst du auch einfach 99% aller Fälle abfangen, indem du zunächst prüfst, ob sich die Bounding Boxes (die parallel zu den Achsen ausgerichtet sind) überschneiden, und nur in dem Fall eine genaue Prüfung vornimmst (alternativ auch Bounding Circles, das könnte bei gedrehten Rechtecken sogar besser sein). Denk daran, dass es bei dem Gedanken der Performance-Optimierung nicht unbedingt immer darum geht, einen zeitaufwändigen Vorgang etwas schneller zu machen, sondern häufiger, ihn von vornherein zu vermeiden.

[DGL-luke]

auch ein rechteck kann im raum liegen, auch "gedreht"...

[Nikolas]

Es geht um den 2-Dimensionalen Raum, in dem sich mein Spiel bewegt. Entschuldigt bitte die Ungenauigkeit. (Wobei: Wer hat schon mal in einem Spiel Rechtecke in einem 3D-Raum gesehen, die geschnitten werden müssen? Klingt etwas nach Autoscooter mit fliegenden Teppichen :) )

Das mit dem Boundingcircle hört sich gut an. Als Vorprüfung werde ich das einführen. Eine schnelle Lösung dahinter wär aber auch gut