Autor Beitrag
G-McKree
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 178



BeitragVerfasst: Mo 05.04.04 18:23 
Bevor die übliche Antwort kommt: ich hab von der Suchfunktion gebrauch gemacht und nix gefunden was mir was brächte

Also ich suche ne ganz algemeine Funtion zum Kollisions-check im 2D-Raum, wie das mit dem Kreis geht wissen wir ja alle, aber was is mir irgentwelchen bekloppten formen wie dummecke und alles unregelmäßiges Zeug?
Brainiac
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: Mo 05.04.04 21:26 
Ich gehe mal davon aus, dass du vektorisierte Objekte meinst.
Für Bitmaps gibts nur den PerPixel-check.

Grundprinzip bei allen Kollisionsalgorithmen zu beliebig geformten Polygonen ist, zu testen ob irgendeinen Eckpunkt des einem Objekts innerhalb des anderen zu finden ist.

Bei konvexen Objekten, also Objekten, bei denen alle Innenwinkel kleiner als 180° sind, gibt es den schnellen Test über das Vektorkreuzprodukt.
Damit kann man nämlich schnell bestimmen, ob drei in Reihenfolgende übergebene koordinaten im oder gegen den Urzeigersinn liegen.
Der Witz ist nun folgender:
Liegt ein Punkt in einem konvexen Objekt, dessen Randpunkte gegen den Urzeigersinn angeordnet sind, so drehen auch alle Dreiecke, die man aus je zwei benachbarten Randpunkten und dem Testpunkt bilden kann, gegen den Urzeigersinn.
Das muss man jetzt also für jeden Punkt des einen Objekts mit allen randlinien des anderen testen und umgekehrt.
Sobald man ein Dreieck findet, dass nicht gegen den Urzeigersinn dreht, kann man abbrechen.

Bei nicht-konvexen Objekten wird das ganze noch eine Nummer schwerer...
Hier ist die einfachste methode der Halbgeraden- oder Windungstest.
Dabei denkt man sich von dem Testpunkt aus eine Halbgerade, die nach oben ins Unendliche verläuft.
Jetzt prüft man, wie oft diese Habgerade die Außenlinien des Testobjektes schneidet. Oder besser, man prüft, wie oft zwei benachbarte Randpunkte nicht auf der gleichen Seite der X-Koordinade des Testpunktes liegen und falls das der Fall ist, ob der resulternde Schnittpunkt oberhalb dessen Y-Koordinate liegt. Problem sind dabei immer so Sachen wie senkrechte Linien etc... noch ein Grund möglichst nur konvexe Objekte zu nehmen.
Wenn die Anzahl der Schnitte ungerade ist, dann liegt der Punkt im Polygon.

Ich hab vor einiger Zeit mal an einer Physiksimulation gearbeitet, die beides verwendet.
ehome.compuserve.de/...Temp/PhysicsDemo.zip wenn du es dir ansehen willst.
Genau genommen wollte ich nochmal daran weiterarbeiten weil vereinzelt noch Bugs auftreten (siehe Drop-Off Szenario).
Wenn du willst, kann ich dir auf jeden Fall die Algorithmen für den Kreuzprodukt-Test und den Windungstest geben... oder zumindest Teile davon.
Brainiac
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: Mo 05.04.04 21:35 
Nebenbei... warum wird das jetzt eigentlich nicht verschoben, aber meine Matrizenmultiplikation schon? :?!?:
Hat doch auch nix mit Delphi zu tun, oder?
:nixweiss:
tommie-lie
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 4373

Ubuntu 7.10 "Gutsy Gibbon"

BeitragVerfasst: Mo 05.04.04 21:40 
Brainiac hat folgendes geschrieben:
Nebenbei... warum wird das jetzt eigentlich nicht verschoben, aber meine Matrizenmultiplikation schon? :?!?:
Hat doch auch nix mit Delphi zu tun, oder?
Es wird vermutlich vorrangig um eine Umsetzung in Delphi gehen, auch wenn der Algorithmus sich in beliebige Sprachen übersetzen ließe. Und da es eine Frage ist, die jeder Spiele-Programmierer mal haben wird, ist sie hier denke ich gut aufgehoben.
Deine Matrizen-Frage war IIRC eher allgemeiner und weniger mit der eigenltichen Implementierung in Delphi verbunden.

_________________
Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert