Kollision von Ellipsoiden

[3_of_8]

Morgen.

Ich habe gerade ein mathematisches Problem.

Angenommen ich habe zwei Kugeln. Ich kann sehr leicht feststellen, ob die Kugeln gerade kollidieren, und zwar indem ich teste, ob der Abstand der Mittelpunkte kleiner ist als die Summe der Radien der Kugeln.

Wenn ich jetzt aber zwei Ellipsoide habe, geht das nicht mehr so leicht. Die Ellipsoide können in alle 3 Achsen beliebig verformt und gedreht sein.

Wie bekomme ich jetzt eine allgemeine - und möglichst effiziente - Formel, um eine Kollision festzustellen?

[Logic]

Kannst du die beiden Formel nicht gleichsetzen und so den Schnitt bestimmen?

Ist doch wie mit 2 Ebenen im Raum die sich in einer Schnittgeraden schneiden.

[quendolineDD]

Hier ist es aber 3 dimensional

Eventuel hilft dir das hier weiter, ist aber englisch.
http://www.peroxide.dk/download/tuto.../pxdtut10.html

[Dax]

Das hindert aber nicht am Gleichsetzen. Bei Ellipsoiden dürfte das allerdings nicht mehr exakt gehen, in dem Fall müsste man auf Näherungsverfahren, zum Beispiel nach Newton, ausweichen.

[3_of_8]

@quendolineDD: Das ist schonmal sehr interessant, aber leider beschreibt es nur, wie man einen Ellipsoid mit Dreiecken kollidieren lässt und nicht mit anderen Ellipsoiden. Ich könnte den anderen einfach in viele Dreiecke aufteilen, aber wirklich effizient ist das leider nicht.

@Dax: Was genau ist das Newtonsche Näherungsverfahren?

[quendolineDD]

x n +1 = x n - (f(x n) / f'(x n))

[axelf98]

Eine Idee wäre, eine Vektorgerade zu basteln, die durch die Mittelpunkte der beiden Ellipsoiden geht. Diese Gerade verfolgt man jeweils und rechnet so den Abstand vom Mittelpunkt zur Hülle aus. Ist Abstand 1 + Abstand 2 größer als der Abstand der Mittelpunkte, so schneiden sich die Körper.
Leider habe ich zur Zeit keine Ahnung, ob das effizient genug ist...

[Dax]

Zitat:

Zitat von axelf98

Eine Idee wäre, eine Vektorgerade zu basteln, die durch die Mittelpunkte der beiden Ellipsoiden geht. Diese Gerade verfolgt man jeweils und rechnet so den Abstand vom Mittelpunkt zur Hülle aus. Ist Abstand 1 + Abstand 2 größer als der Abstand der Mittelpunkte, so schneiden sich die Körper.
Leider habe ich zur Zeit keine Ahnung, ob das effizient genug ist...

Falsch... Ellipsoide müssen sich nicht auf der Verbindungsgerade ihrer Mittelpunkte schneiden.

[3_of_8]

Zitat:

Zitat von quendolineDD

x n +1 = x n - (f(x n) / f'(x n))

Tut mir Leid, aber was mache ich jetzt mit dieser Gleichung? Was ist überhaupt x in diesem Fall? Und was ist f?

[sirius]

Näherungsverfahren sind iterativ.
Du nimmst dir einfach irgendein x (welches nah genug am Schnittpunkt liegt) und rechnest über die Formel
x - f(x)/f'(x), dein neues x aus. Und nach n Schritten liegst du dann sehr nah am Ergebnis. eine Abbruchbedingung wird dir sicherlich noch einfallen ;-)

f(x)...Die funktion zur Schnittpunktberechnung
f'(x).. deren 1. Ableitung

Edit: jetzt bruachst du "nur" noch die Funktion f(x), welche den Den Schnittpunkt bestimmt. (Was bei zwei Ellipsoiden eigentlich eine Ellipse ergeben sollte und damit nicht einfach f(x) :gruebel: )