PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : effizienter Algorithmus gesucht


Gast
2007-06-11, 08:45:58
Ich möchte innerhalb eines C-Programms folgendes Problem lösen. Ich habe zum einen einen Ellipsoid gegeben, der an den drei Raumachsen ausgerichtet ist (er liegt also nicht "schräg" im 3D-Raum). Zusätzlich habe ich eine Ebene. Nun möchte ich zuerst effizient und schnell testen, ob sich die beiden überhaupt schneiden. Udn nur wenn sie sich schneiden möchte ich den Schnittkreis oder die Schnittellipse ausrechnen. Wie gehe ich da am besten vor, welche Darstellungsform ist am geeignetsten für eine schnelle Berechnung (Parameterdarstellung?).

micki
2007-06-11, 10:28:11
fuer die ebene waere die normalisierte normale und w gut. dann teilst du die einzelnen elemente der normale durch die skalierung des elipsoiden (kannst dir ja die inverse merken) und dann berechnest du simpel den abstand ebene-mittelpunkt vom elipsoid, falls <1.f gibt es einen schnittpunkt.


ich hab es zwar nicht ausprobiert, aber muesste eigentlich so gehen :)

Silpion
2007-06-11, 12:17:56
Jup, einfach den Raum verzerren, so dass aus dem Ellipsoid eine Kugel mit Radius 1 und Mittelpunkt im Ursprung wird.

Eine weitere Möglichkeit wäre, vorher mit einer Bounding-Box zu testen, aber das oben genannte sollte ebenfalls sehr schnell gehen.

Der Schnittkreis sollte sich ebenfalls recht problemlos ausrechnen lassen, wenn ich mich recht erinnere war das bei mir eine Abituraufgabe. Da die Rücktransformation des Raumes nur eine Skalierung ist, kommt man auch relativ einfach zur Schnittellipse.

Vom Programm her benötigst du höchstens Matrixoperationen, im wesentlichen kommt es darauf an, was du in dem Bereich als Vorwissen hast.