Hallo,

das Problem ist nicht einfach darzustellen (3D), ich versuch's so gut wie möglich. Es geht um die Kollision einer Kugel mit einem Dreieck, aber nicht mit der Dreiecksfläche, das ist gelöst, sondern mit der Kante. So etwas wie eine "Streifkollision", aber nicht minder wichtig.
Folgende Situation: In meinem Testprogramm habe ich senkrecht ein Dreieck aufgespannt, dessen Unterkante aber ein wenig angehoben ist. Auf dieses Dreieck lasse ich schräg eine Kugel laufen, die so dick ist, dass sie so eben an der Unterkante des Dreiecks hängenbleiben muss. Dabei muss sie sich natürlich etwas unter das Dreieck schieben.

Irgendwo im Internet fand ich folgenden Lösungsvorschlag: Man berechnet den Intersektionspunkt mit der Dreiecksebene (B) und berechnet den nächstliegenden Punkt auf dem Umfang des Dreiecks (B'). Vor dort aus schickt man einen Strahl rückwärts zur Kugel und berechnet den Punkt auf der Oberfläche, der die Kante berühren wird. Mit dem resultierenen Vektor kann die Kugel dann an die gewünschte Stelle geschoben werden.

Doch die Sache hat einen Schönheitsfehler, eigentlich zwei. Bei schrägem Aufprall ist B' ja gar nicht der genaue Intersektionspunkt; mehr noch: Bei Abweichungen von mehr als 45° von der Ebenen-Normalen wird die Intersektion nicht mal erkannt, weil der "Rückwärtsschuss" an der Kugel vorbeigeht. Daraufhin bin ich dann vom Mittelpunkt der Kugel ausgegangen, was zu den beiden Punkten A und A' führt. Die Erkennung ist nun sicherer, aber so ganz genau scheint die Sache immer noch nicht zu sein. Der tatsächliche Intersektionspunkt müsste irgendwo zwischen A' und B' liegen, und nur wenn ich den genau kenne, kann ich doch ein exaktes "reverse intersection" durchführen, oder?

Hat jemand eine Idee, wie ich diesen Punkt auf der Dreieckskante genau berechnen kann?

Als erstes musst du den Punkt auf der Kante ermitteln, der dem Kugelmittelpunkt am nächsten ist. Das geht mit einer Lotpunktberechnung mit der Seite als Gerade und Kugelmittelpunkt als Punkt, duch den das Lot gehen soll. Infos hierzu gibts i diversen Matheforen und Tuts.
Der Vektor von diesem Punkt zum Kugelmittelpunkt ist dann die 'Flächennormale'. Hast Du diese Normale, lässt sich die Kollision wie eine normale Flächenkollision (Ausfall=Einfall) berechnen. Der einzige Unterschied ist quasi, dass die 'Flächennormale' nicht senkrecht auf der Fläche steht.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Dadurch würde ich also die Kollisionsfläche, die später im Kollisionspunkt Kugel-Kante sowieso berechnet werden muss, vorwegnehmen. Es geht übrigens um die sogenannte "sliding plane", denn die Kugel steht nur provisorisch für ein Objekt, das sauber auf dem Surface gleiten soll.
Das klingt zunächst plausibel, aber wie stelle ich nun fest, ob die Kugel die Kante auch schneidet? Folgendes Beispiel: Ich schiebe das Dreieck nach oben, so dass keine Kollision stattfinden kann. Die gedrehte Ebene, auf der die Kante liegt, wird aber irgendwo geschnitten, nur nicht auf der Geraden mit dem Kantenabschnitt.

Man berechnet den nahesten Punkt des Dreieckes zur Kugel.
Wenn dieser Punkt näher als der Radius der Kugel ist, schneidet sie das Dreieck.

Zuerst projiziert man den Mittelpunkt der Kugel in die Ebene des Dreiecks.
Mit baryzentrischen Koordinaten kann man testen, ob der Punkt im Dreieck liegt, dann ist er selber der naheste Punkt.
Ansonsten geben die Vorzeichen der baryzentrischen Koordinaten an, welche Ecke oder Seite am nächsten liegt.
Auf diese Seite kann man dann den nahesten Punkt durch durch Lotberechnung finden.
Man kann z.B. eine Ebene konstruieren, deren Normalvektor der Kante des Dreickes entspricht.

Hm, welches ist denn "der Nächste" aus der Sicht der Kugel? Dem unteren Pfeil nach bestimmt nicht der vordere Eckpunkt. Wenn überhaupt, wird der hintere berührt, oder irgendein Punkt auf der hinteren Kante, je nach Richtung der Kugel. Das Problem ist ja gerade, diesen Punkt ausfindig zu machen.

Vielleicht sollte ich das Ganze in einem Matheforum auch auf den mathematischen Kern bringen. Also eine vereinfachte Darstellung:


Gegeben ist eine Gerade, definiert durch 2 Punkte (oder Punkt + Vektor). Gegeben ist ferner eine Kugel mit dem Radius r an der Position xyz, die sich in Richtung xxyyzz bewegt.

1. Berühren bzw. schneiden sich Gerade und Kugel?
2. Falls ja, an welchem Punkt auf der Geraden findet die Erstberührung statt (an welchem Punkt ist die Gerade die Tangente an der Kugel) ?
3. Liegt dieser Punkt auf dem gekennzeichneten Streckenabschnitt?
4. Welcher Punkt auf der Kugeloberfläche wird berührt?

Wenn das alles klar ist, kann die Kugel exakt zum Intersektionspunkt bewegt werden. Außerdem lässt sich dann leicht die Normale der Intersektionsebene bestimmen.

Wenn man die baryzentrischen Koordinaten von p bezüglich eines Dreiecks A,B,C hat, kann man entscheiden auf welcher Kante oder Ecke der naheste Punkte liegt:
p soll dabei A*u+B*v+C*w sein

u>0,v>0,w>0: p selber (innerhalb des Dreiecks)
u>0,v>0,w<0: auf Kante AB
u>0,v<0,w>0: auf Kante CA
u>0,v<0,w<0: Ecke A
u<0,v>0,w>0: auf Kante BC
u<0,v>0,w<0: Ecke B
u<0,v<0,w>0: Ecke C

Den nahesten Punkt zwischen Liniensegment (a,b) und einem weiteren Punkt (p) berechnet man so:



Man kann anhand Lage des Punktes auch erkennen, ob eine Kollision mit einer Kante oder der Dreiecksfläche stattgefunden hat. Die Kugel kann dann in Richtung zwischen Mittelpunkt der Kugel und nahestem Punkt auf dem Dreieck entsprechend zurückgeschoben werden.

Die Vorteile der baryzentrischen Koordinaten werden deutlich, weil man damit den naheliegendsten Punkt des Dreieckes zu einem außerhalb der Ebene liegenden Punkt bestimmen kann. Bei dem Verfahren, das ich bisher ausprobiert habe, musste man den externen Punkt erst auf die Ebene projizieren. Das scheint mit barycentrischen C. offensichtlich eleganter und wahrscheinlich auch effizienter zu gehen.

Doch ein Problem bleibt immer noch. Die Kugel ist ja nicht vernachlässigbar klein, sie kann sogar größer sein als die Fläche. Der Mittelpunkt kann also nur gebraucht werden, um die Position der Kugel zu kontrollieren. Der Intersektionspunkt liegt aber irgendwo auf der Kugeloberfläche, und dieser Punkt muss den nahesten Dreieckspunkt auch wirklich berühren, wenn es zu einer Kollision kommt. Das war ja der Grund, warum ich im ersten Ansatz die ray-sphere Kollision eingebaut hatte.