Ich habe eine Kollsionserkennung für eine Gerade, oder besser gesagt Strecke, und mit einem Dreieck.
Diese funktionert wie folgt: Erst wird über den Abstand eines Punktes der Strecke zur Ebene und dem Richtungsvektor der Strecke, der Faktor bestimmt mit dem der Richtungvektor skaliert werden muss damit ich den Schnittpunkt mit der Ebene erhalte. Der Faktor wird dann auf 0>=Faktor>=1 überprüft, um zu testen ob die Ebene überhaupt geschnitten wird. Wenn der Test positiv ist wird getestet ob der Schnittpunkt vor allen Flächen des Dreiecks, die senkrecht auf den Kanten stehen, ist. Wenn ja, wird das Dreieck von der Strecke geschnitten, d.h. es kollidiert.

Mein Problem ist nun, wenn ich 2 Dreiecke teste, die sich eine Kante teilen, kann sich die Strecke sozusagen durchmogeln, wenn sie durch bzw fast genau durch die Kante verläuft. Wahrscheinlich wegen Ungenauigkeiten bei der Berechnung mit den Gleitkommazahlen.

Meine Frage ist nun: Wie kann ich das am besten Abstellen?

Wenn ich das Dreieck "ausdehne", also den Schnittpunkt nicht mit den senkrechten Ebenen auf eine Distanz größer Null teste, sondern Null+Konstante, kommt zwar nichts zwischen den Dreiecken durch, aber die "Richtung" der Kante wird umgedreht... Naja, weiß nicht wie man das nennt. Ich mein' so als würden die Ecken eines Raumes nach innen zeigen, wenn sich das überhaupt jemand vorstellen kann.
Auf jeden Fall kann ich dieses Verhalten auch nicht gebrauchen, womit meine Lösung nicht in Frage kommt.

Also ich habe das Problem jetzt wie folgt behoben:

Erst werden alle Dreiecke einzeln überprüft, dabei wird für jedes gespeichert ob das Dreieck überhaupt geschnitten werden kann, d.h. ob die Strecke lang genug ist oder ob das Dreieck vllt in die falsche Richtung zeigt (wird dann quasi gecullt). Wenn es geschnitten werden kann, wird der Schnittpunkt berechnet und gespeichert. Dann wird der Schnittpunkt wie gehabt mit den orthogonalen Ebenen auf den Kanten verglichen. Das Ergebnis (also vor oder hinter der Ebene) wird ebenfalls gespeichert.
Eigentlich ist das alles ganz normal wie oben auch schon genannt, bloß eben das die paar Werte für jedes Dreieck in einem Array gespeichert werden.
Wenn dann alle Dreiecke überprüft wurden schneidet die Strecke also entweder ein Dreieck und wurde erkannt, oder es wurde nicht erkannt oder es schneidet tatsächlich nicht.
Um nun herauszufinden ob tätsächlich keine Kollision vorhanden ist oder ob das wieder nur ein Fehler war, werden nun Dreieckpaare überprüft.
Also geht man wieder alle Dreiecke durch. Wenn ein Dreieck markiert wurde, dass es geschnitten werden kann (erster Wert der oben gespeichert wurde), wird für jedes angrenzende Dreiecke ebenfalls diese Eigenschaft geprüft. Wenn beide wahr sind, wird getestet ob der Test für die 4 Seiten, die die Dreiecke sich nicht teilen, jeweils auch wahr ist. Wenn ja geht die Gerade durch die Kante und schneidet ein oder beide Dreiecke. Der Schnittpunkt eines der Dreiecke (sollten beide fast gleich sein) kann dann als Ergebnis zurückgegeben werden, falls gewünscht.

Da ich sowieso die Nachbarn jedes Dreiecks gespeichert hatte, ist diese Lösung auch nicht viel langsamer, da nur recht simple Operationen dazukommen.
Natürlich ist der Test trotzdem nicht 100% sicher, da z.B. eine Gerade durch einen Eckpunkt an dem sich 3 oder mehr Dreiecke treffen, wahrscheinlich immernoch nicht erkannt wird, aber die Chance ist um einiges geringer als eine Kante zu treffen.

Hast du dir die 3 Kollisionstutorials mal angesehen?

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Nö, eigentlich nicht, höchstens mal die Bilder angeschaut.^^

Wenns 2D ist, kannst du dir auch das Separating Axis Theorem (auchn Tutorial hier) anschauen... Wobei ich mir nicht sicher bin, inwiefern das dann hilfreich ist.

Gruß Lord Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

also um ein Epsilon wirst du wahrscheinlich nicht rumkommen. Es gibt nunmal immer Rundungsfehler.

Bezüglich eines sehr schnellen Algos könnte ich den hier empfehlen: http://www.graphics.cornell.edu/pubs/1997/MT97.pdf

_________________
__________
"C++ is the best language for garbage collection principally because it creates less garbage." Bjarne Stroustrup

Separating Axis Theorem ist auch für 3D die Grundlage bzw. Octree und Boundingsphere Tests(vorab Test) sind auch hilfreich, wenn man mehr Performance raus holen muss.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Also erstmal danke für die Antworten.

Mein Problem bezog sich auf 3D.
Die Kollisionstutorials hab' ich erstmal überflogen, etwas neues ist mir dabei aber nicht aufgefallen, was dort anders gemacht wird. Kann aber auch sein ich habs überlesen.

@Pellaeon
Den Ansatz hab' ich auch schon mal in einem Forum gefunden, allerdings wusste ich nicht wie ich das umsetzen sollte. Muss ich mir mal die PDF genauer anschauen. Das Problem mit dem Epsilon war das die Gerade dann 2 Dreiecke schneidet, was sich wiederum nicht so gut mit meiner "Gleitpfadberechnung" vertragen hat. Vielleicht kann man da den Umkehrschluss meines Ansatzes oben verwenden: Wenn sich 2 Dreiecke eine Kante teilen kann nur eines geschnitten werden. Aber ob das dann schneller ist kann ich jetzt nicht sagen.

@TAK2004
Einen groben Vorabtest mach ich natürlich schon. Octrees hab ich noch nicht implementiert, weil ich mir nicht so sicher war in wiefern das bei bewegten Objekten zu verwirklichen ist. Separating Axis werd' ich mir auch mal anschauen.