Hallo Leute, ich hab gerade ein mathematisches Problem... Ich arbeite gerade an einer Kollisionsabfrage, die den Tutorials von Suleco bzw. GameTutorials zu Grunde liegt. Das heißt, um zu prüfen, ob eine Strecke ein Face schneidet werden folgende Schritte abgearbeitet:

1. Zuerst wird geguckt ob die Strecke die Ebene des Faces schneidet. Dies ist trivial.
2. Danach wird der Schnittpunkt berechnet. Auch heir habe ich keine Probleme.
3. Nun muss zuletzt geguckt werden, ob dieser Schnittpunkt innerhalb dieses Polygons liegt und das bereitet mir Probleme.
Der Algorithmus in den Tutorials mag genial sein (er bildet immer Dreiecke aus den Eckpunkten und addiert die Winkel, bei 360 Grad liegt der Punkt im Polygon), aber er arbeitet nicht genau, was wohl auf Rundungsfehler zurück zu führen sein wird. Nun habe ich einen anderen Algorithmus gefunden der ebenso genial ist. Da sich keine Linien überschneiden (das Face besteht nur aus Aussenlinien) macht man einfach folgendes. Man nimm sich einen Punkt der 100pro ausserhalb des Polygons liegt und verbindet ihn mit dem zu prüfen Punkt. Nun geht man jeden Punkt des Polygons durch und bildet aus diesem Puntk und dem nächsten eine Strecke(ob die Punkte CW oder CCW angeordnet sind spielt keine Rolle). Nun prüft, ob diese beiden nun gebildeten Strecken sich schneiden. Wenn am Ende die Anzahl der geschnittenen Strecken des Polygons ungerade ist liegt der Punkt im Polygon, ansonsten ausserhalb. Auch dieser Algorithmus hat Schwachpunkte, z.B wenn die Gerade durch einen Eckpunkt des Polygons geht, aber sowas ließe sich evtl abfangen.

Um zu prüfen, ob die Strecken sich schneiden, muss ich nun erstmal prüfen, ob die Geraden dieser Strecken sich schneiden und hier liegt mein Problem: Die Berechnung des Schnittpunkts der Geraden im R³ ...

Vielleicht muss ich über eine Hilfsebene arbeiten? Würde mich freuen, wenn ihr mir weiter helfen könntet... THX!

Mfg
cHicHo

Man kann auch auf jede Kante des Polygons eine senkrechte Eben stellen. Wenn der Punkt dann in dem Polygon ist, liegt er auf der Vorder oder Rückseite, je nach Konstruktion, aller Ebenen.
Für Spielerbewegung eignet sich eine Gerade nicht zur Kollisionsprüfung. Da ist es sinnvoller man bewegt eine AABB.
Der Algorithmus, der prüft, ob die Summer aller Winkel 360° haben ist recht langsam, weil man für die Winkelberechnung eine Wurzel ziehen muß.

Ganz so genial ist der Algorithmus nicht, weil den/die Schnittpunkt(e) der Geraden zu berechnen recht kompliziert ist.
Wenn du die beiden Geradengleichungen hast, und die den Wert für s und t suchst, bei dem sie sich schneiden, musst du sie im Prinzip nur gleichsetzen:

(kursiv = Vektor!)

a0 + s * u = b0 + t * v

Da du im R3 bist hast du jetzt 3 Gleichungen und 2 Unbekannte. Wenn du für dieses Gleichungssystem eine Lösung findest, dann schneiden sich die Geraden. Bei mehr als einer sind sie parallel. Ansonsten sind sie windschief.
Aber lineare Gleichungssysteme mit mehreren Unbekannten lösen ist irgendwie nicht so toll.

_________________
Selber Denken macht klug!

ich weiß nicht, ob das hier von Bedeutung ist, aber wenn mehrere Lösungen vorhanden sind, dann sind die Geraden sogar identisch und wenn keine Lösung vorhanden ist können sie auch parallel sein

_________________
. . .

Jupp, das ist in sofern von Bedeutung, da ich was falsches geschrieben hab und das korrigiert gehört. Hast natürlich vollkommen recht!

-lith

_________________
Selber Denken macht klug!

Danke erstmal für eure schnellen Antworten.
Ich denke ich werde es mal versuchen über jeder Strecke eine Hilfsebene aufzuspannen. Denn selbst wenn ich mit AABBs arbeite, brauche ich doch einen Ray-Polygon-Collisions-Test, weil es ja nicht nur um Spielerbewegungen geht. In einem anderen Thread habe ich gelesen, dass AABB teilweise recht ungenau sind, und man beide Kollisionsverfahren kombinieren sollte? Gibt es irgendwo ein gutes Turorial oder Source für die Kollision von AABBs??[/quote]

Die AABB Kollision ist ungenau, wenn man die anderen Objekte als AABB vereinfacht, aber für den Spieler ist eine AABB optimal. In viele Q3 Level Viewer Tutorials wird das erklärt. Bei Quake gibt es nur eine Art der Kollision. Wenn nur eine Linie getestet werden soll, z.B. für Raketen, dann wird die Box eben auf die Gröe 0 verkleinert.

So, ich habe es über Hilsebenen lösen können... Ich poste mal meine Funktion, vllt hilft das jemandem der dasgleiche Problem wie ich es hatte


MfG
cHicHo