Kollision Dreieck - Kugel
-
Siehe Topic, hat da wer Ideen, Vorschläge?
Momentan habe ich erst einnmal einen Test, ob die Kugel die Ebene des Dreiecks schneidet. Wenn nein, kann man schonmal false zurück geben.
Falls ja, da haperts noch etwas. Mein Problem ist vor allem der Sonderfall, dass "die Kugel im Dreieck ist". Also riesiges Dreieck, kleine Kugel. Da wären alle Punkte des Dreiecks außerhalb der Kugel, also würde ein Test, ob min. einer der Punkte des Dreiecks in der Kugel ist nicht ausreichen, um alle Fälle abzudecken.
Tja falls der wer Hiwneise, Tipps hat, immer her damit
-
ich würde versuchen, folgendes für alle 3 seiten des dreiecks anzuwenden...
-
Pellaeon schrieb:
Falls ja, da haperts noch etwas. Mein Problem ist vor allem der Sonderfall, dass "die Kugel im Dreieck ist". Also riesiges Dreieck, kleine Kugel. Da wären alle Punkte des Dreiecks außerhalb der Kugel, also würde ein Test, ob min. einer der Punkte des Dreiecks in der Kugel ist nicht ausreichen, um alle Fälle abzudecken.
Allgemein: Die meisten Algorithmenbücher sind voll mit so einem Zeug (Geometrische Algorithmen), vielleicht leihst Du dir mal eins aus der Bibliothek aus.
-
Sunday schrieb:
ich würde versuchen, folgendes für alle 3 seiten des dreiecks anzuwenden...
Tja das deckt aber nicht alle Fälle ab. Die Kugel kann im Dreieck sein, ohne die Dreiecksseiten zu berühren.
-
Ich habe mir den link nicht angeschaut.
Mir fällt eine Lösung ein. Ich denke aber es gibt eine effizientere.
Du hast ein Dreieck gegeben durch 3 Punkte A,B,C und eine Kugel gegeben durch Radius r und den Mittelpunkt M.
Du kannst 3 Vektoren aufstellen: MA, MB, MC und testest ob der Winkel zwischen ihnen größer 180° ist. Dann liegt M innerhalb des Dreiecks. Jetzt stellst du 3 geraden auf, die das Dreieck ABC beschreiben. Dann ermittelst du den Abstand dieser Geraden zum Mittelpunkt und vergleichst ihn mit dem Radius. So sollte es funktionieren, habe nicht ausprobiert
-
matimatiker schrieb:
Ich habe mir den link nicht angeschaut.
Mir fällt eine Lösung ein. Ich denke aber es gibt eine effizientere.
Du hast ein Dreieck gegeben durch 3 Punkte A,B,C und eine Kugel gegeben durch Radius r und den Mittelpunkt M.
Du kannst 3 Vektoren aufstellen: MA, MB, MC und testest ob der Winkel zwischen ihnen größer 180° ist. Dann liegt M innerhalb des Dreiecks. Jetzt stellst du 3 geraden auf, die das Dreieck ABC beschreiben. Dann ermittelst du den Abstand dieser Geraden zum Mittelpunkt und vergleichst ihn mit dem Radius. So sollte es funktionieren, habe nicht ausprobiert
Mir fällt gerade ein
Das mit 180° stimmt nicht, die winkel sollten größer 90° sein.Wenn das auch nicht stimmt dann kannst Du weitere geraden aufstellen die durch die Punkte ABC gehen und sich in M schneiden. Dann testest Du mit denenen, die das dreick beschreiben, ob sie auch andere Schnittpunkte haben außer ABC. Denn dann liegt deine Kugel außerhalb des 3ecks
-
Vielleicht wäre auch die Projektion des Kugelmittelpunkts in die Ebene des Dreiecks interessant.
-
noch besser wäre natürlich gleich der kreis, der als schnittpunkt von dreiecksebene und kugel entsteht...
-
Der ist ja dann leicht zu berechnen:
Mittelpunkt ist der (orthogonal) projizierte Mittelpunkt, Radius ist sqrt(r^2 - d^2), dabei ist r der Radius der Kugel, d der Abstand des Mittelpunkts von der Dreiecksebene. (Zeichnung von der Seite machen, Pythagoras)
MfG Jester
-
Jester schrieb:
Vielleicht wäre auch die Projektion des Kugelmittelpunkts in die Ebene des Dreiecks interessant.
Habe ich auch schon überlegt. Ne Funktion die testet, ob ein Punkt in einem Dreieck liegt habe ich auch schon geschrieben. Allerdings deckt das auch nicht alle Fälle ab.
Und das mit den Winkel klingt mir zu aufwendig. Der Kollisionstest findet während einer Animation statt(mit OpenGL). Da möchte und unnötige sin, cos uns. sparen.Naja mal schauen ob mir noch was einfällt ... .
-
Wieso deckt das nicht alle Fälle ab?
Du berechnest zuerst den Abstand Kugel->Ebene. Ist der zu groß, biste schon fertig.
Jetzt schneidet entweder eine der 3 Seiten des Dreiecks die Kugel, oder das Dreieck liegt in der Kugel, oder die Kugel liegt "im Inneren des Dreiecks". Den ersten Fall kannste nachprüfen, der zweite Fall läßt sich mit einfacher Distanzberechung abhandeln und der letzte Fall dürfte auch leicht zu erkennen sein über Projektion + Abfrage ob Punkt im Dreieck.
-
Jetzt schneidet entweder eine der 3 Seiten des Dreiecks die Kugel, oder das Dreieck liegt in der Kugel, oder die Kugel liegt "im Inneren des Dreiecks".
deckt man nicht alle fälle ab, wenn man durch jede dreieckseite eine ebene orthogonal zur dreiecksebene legt, und die entfernung zum kreismittelpunkt berechnet? ist diese für jede der drei ebenen kleiner, als der "projizierte" radius, dann gibt es einen schnittpunkt, sonst nicht. die ebenen müssen natürlich alle nach innen oder außen gerichtet sein, damit das funktioniert.
-
Jester schrieb:
Wieso deckt das nicht alle Fälle ab?
Du berechnest zuerst den Abstand Kugel->Ebene. Ist der zu groß, biste schon fertig.
Jetzt schneidet entweder eine der 3 Seiten des Dreiecks die Kugel, oder das Dreieck liegt in der Kugel, oder die Kugel liegt "im Inneren des Dreiecks". Den ersten Fall kannste nachprüfen, der zweite Fall läßt sich mit einfacher Distanzberechung abhandeln und der letzte Fall dürfte auch leicht zu erkennen sein über Projektion + Abfrage ob Punkt im Dreieck.Jo ich dachte du meinst nur die Projektion als alleiniger Test.
So wie du es jetzt beschrieben hast, mache ich das jetzt auchMir fällt aber grad ein, der Fall mit dem Test der Punkte dürfte durch den Test Linie-Kugel schon mit abgedeckt sein
dk mdfpa kdk apt adsöf dm schrieb:
Jetzt schneidet entweder eine der 3 Seiten des Dreiecks die Kugel, oder das Dreieck liegt in der Kugel, oder die Kugel liegt "im Inneren des Dreiecks".
deckt man nicht alle fälle ab, wenn man durch jede dreieckseite eine ebene orthogonal zur dreiecksebene legt, und die entfernung zum kreismittelpunkt berechnet? ist diese für jede der drei ebenen kleiner, als der "projizierte" radius, dann gibt es einen schnittpunkt, sonst nicht. die ebenen müssen natürlich alle nach innen oder außen gerichtet sein, damit das funktioniert.
Ich weis jetzt nicht, was du mit projizierten Radius meinst, aber bei deiner Variante ist das wohl das Problem, wenn der KReis im Dreieck liegt, fehlt dieser Fall.
-
Naja bei einer paralellen Projekion sollte der Radius invariant sein oder irre ich mich ?