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: )

[quendolineDD]

Diese Formel habe ich aus meinem Tafelwerk gestern noch schnell abgeschrieben.

F(x) ist dabei die Funktion des Graphen, bei dir musst du mal schauen, welche Funktion die Ellipsoiden haben, ich habe von solchen gar keine Ahnung (2. mal 12. Klasse Informatikgymnasium).

f'(x) ist deren 1. Ableitung, wie das geht müsstest du herausfinden / wissen können.

Grüße

[HERMES]

Newton Verfahren nur die auf Funktion der Elipsoiden anzuwenden hilft da auch nicht.

(Geometrische )Näherungen kannst du bestimmen, indem du deinen Ellipsoid in einen weniger komplexe Körper packst, zum Beispiel eine Kugel oder einen Quader. Und dann Kollisionen zwischen den umhüllenden Körpen prüfst. Wenn hier schon keine Kollision besteht (oder zumindest nicht bei beiden), hast du tatsächlich keine. Andernfalls musst du deine Näherung verbessern, indem du deinen Ellipsoid mit mit kleineren Kugeln "aussfüllst". Oder eine aufwendigeres exaktes Verfahren anwendest.

[3_of_8]

Aber es müsste doch irgendeine Formel geben, mit der man das exakt berechnen kann, oder? Ich kann mir irgendwie nicht vorstellen, dass man das nur so näherungsweise machen kann.

[sirius]

Bie bescheibst du denn deinen Ellipsoiden?

[3_of_8]

Durch Mittelpunkt und drei Radien. (Darf man da Radius sagen? Ich glaube schon)

Naja also ganz formal mathematisch wäre es wohl so:

E((xm, ym, zm), a, b, c):={(x, y, z)|((x-xm)/a)²+((y-ym)/b)²+((z-zm)/c)²=1}

Und ich beschreibe ihn eindeutig durch die Angabe eines Mittelpunkts m=(xm, ym, zm) und der drei Radien (oder wie sie auch heißen mögen) a, b und c.

[sirius]

Die fiel mir auch ein, aber kann damit ein Ellipsoid überhaupt schief liegen?

[HERMES]

Nein kann er nicht, dazu müsste man noch die richtung einer der 3 Achsen angeben.
Wenn du aber nur einen solchen Ellipsoid hast sollte sich die ganze Sache etwas einfacher darstellen.

Zitat:

Zitat von 3_of_8

Aber es müsste doch irgendeine Formel geben, mit der man das exakt berechnen kann, oder? Ich kann mir irgendwie nicht vorstellen, dass man das nur so näherungsweise machen kann.

Exakt wäre, wenn du die Mengen der beeinhalteteen Punkte berechnest und diese dann Schneidest. Ist der Schnitt leer liegt keine Kollision vor.

Da aber in einem Ellisoid unendlich viele Punkte liegen hätte dein Computer ein Problem, diese alle zu berechnen. Wenn du hier Punkte weg lässt hast auch wieder nur eine Näherung gemacht, bei der du allerdings viel "unnützes" berechnet hast.

[3_of_8]

Stimmt, ich habe noch 2 Drehungswinkel, pitch und yaw. Die habe ich vergessen.

[Nikolas]

Was willst du denn damit anstellen?
Ich hatte das Problem letztens auch, als ich eine kleine PhysikEngine für die Uni geschrieben habe. Analytisch wird das sehr groß (u.A. musst du ein Polynom dritten Grades lösen).
Erklär doch mal, was du später damit anstellen willst, vielleicht ist auch ein anderer Ansatz drin, wie z.B. ein PolygonGitter, mit dem man dann deutlich einfacher (und auch etwas ungenauer) wäre.

[axelf98]

Zitat:

Zitat von Dax

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

Stimmt, habe noch einmal darüber nachgedacht. Das Problem ist doch nicht so einfach, wie ich dachte.
http://home.arcor.de/fabianbuerger/Stuff/ellipsen.png

[Nikolas]

Das Problem lässt sich aber noch dahingehend vereinfachen, dass man über die Anwendung einer Rotationsmatrix wenigstens eine Ellipse dahingehend dreht, dass ihre Achsen parallel zu den Achsen des KS liegen.

[Dax]

Zitat:

Zitat von Nikolas

u.A. musst du ein Polynom dritten Grades lösen).

http://de.wikipedia.org/wiki/Cardani...dritten_Grades

[freak4fun]

Nur so eine Überlegung: Da die Berechnung anscheinend sehr kompliziert ist, könn man dann eine Vorberechnung machen. Zum Beispiel die Berechnung das einfachen Abstand, um zu prüfen, ob eine Kollsion überhaupt in Frage kommt.

MfG
freak

[Nikolas]

@Dax: Das es da eine Lösung gibt, ist doch nichts Neues. Nur: Wie lang brauchst du, um so was zu implementieren. Und auch dann ist es noch ordentlich Arbeit.

[3_of_8]

Ich werde einen schnellen Kollisionstest per Bounding Sphere als ungefähres Kollisionskriterium implementieren (3 Subtraktionen, 4 Multiplikationen, 2 Additionen, 1 Vergleich, also sehr schnell zu berechnen).

Also, jetzt dazu, wozu ich das alles brauche. Ich denke momentan vage daran, eine Art Weltraum-Spiel zu programmieren (mit OpenGL). Wenn ich jetzt einen Kollisionstest machen will, muss ich möglicherweise testen, ob 20-30 Schiffe mit jeweils einer Station kollidieren. Jetzt sind Schiffe u.U. nicht gerade klein und Stationen sind riesig. Auch bei Beschuss durch Raketen/Partikelwaffen ergibt sich dieses Problem. Da stellt sich natürlich die Frage, ob ein Dreiecks-Dreiecks-Test in allen Fällen das richtige ist, da der eine Komplexität von O(m*n) hat (wobei m die Dreiecksanzahl des Schiffes, n die der Station ist). Da Schiffe eher länglich sind, lässt sich ihre Form u.U. nicht sehr gut mit einer Kugel approximieren, jedoch sehr gut mit einem Ellipsoiden. Darüber hinaus sollen die Schiffe Schilde besitzen, die bei einem Treffer das Projektil abfangen. Diese Schilde sollen dann ellipsoid das Schiff umgeben, wodurch ich sogar noch eine optisch ansprechende und logisch einleuchtende Erklärung für diese Kollision habe. Der Ellipsoid-Test wird dadurch also eher selten, der Polygon-Test noch seltener verwendet, was sich ressourcensparend auswirkt - und Ressourcen sind bei einem 3D-Echtzeit-Spiel immer knapp.

[Nikolas]

Du könntest dir auch überlegen die langen Formel durch andere geometrische Formen anzunähern. z.B. erst eine Halbkugel, dann einen Kegelstumpf, einen Zylinder, einen Kegelstumpf und eine Halbkugel. Sieht recht ähnlich aus und sollte recht einfach zu schreiben sein.

Hat OpenGL nicht schon Kollisionserkennungen frei Haus? Oder willst du alles per Hand schreiben?

Wie suchst du nach Kollisionen? Suchst du nach jedem Frame nach einer Schnittmenge oder berechnest du den Kollisionszeitpunkt exakt?

[3_of_8]

OpenGL hat Kollisionserkennung? Das wäre mir neu.

Und ich berechne die Kollision nach jedem Frame.

[Nikolas]

War nur geraten, ich habe mich bei unserem Projekt überhaupt nicht um die Darstellung gekümmert.
Wenn du die Kollision erst am Ende eines Frames testest, was machst du dann mit schnellen Objekten wie z.B. Schüssen? Wenn du eine dünne Wand und ein schnelles Geschoß hast, könnte es dir passieren, dass das Teil einfach durchfliegt. Oder was machst du, wenn du merkst, dass zwei Objekte, die eigentlich aneinander abprallen sollten, plötzlich ineinander stecken?
Wir haben zu sechst ein Semester an dem Projekt gebaut und jeder hat mal eine kleine Nachtschicht eingebaut. Und das war 2D!
Ich würde also sagen, dass dein Ziel, das alleine in brauchbarer Zeit und in 3D zu bauen, kaum erreichbar ist, wenn du die Kollisionen und Physik selbst schreiben willst.
Schau dir doch mal OGRE oder sowas an, da hast du die ganze Physik schon drin. Das wär vielleicht etwas einfacher, wobei dir Gruppe, die damit gearbeitet hat, nicht fertig geworden ist.
Wenn du also nicht die nächsten Jahre nur damit beschäftigt sein willst, solltest du vielleicht etwas weniger planen.

[3_of_8]

Okay, dann werde ich wohl eventuell doch auf Newton oder so umsteigen müssen. Newton ist aber, wie ich schonmal gemerkt habe, nicht unbedingt sehr schnell.

[Nikolas]

Schau dir doch mal das Ogre an. So wie es aussieht ist das Teil sehr mächtig, und nach Auskunft des anderen Teams kann man sich da in 2Wochen genügend einarbeiten, um etwas damit anzustellen.