«

»

Jul 12

Beitrag drucken

Raytracing – Mathematische Herleitung

Hallo zusammen,

an dieser Stelle möchte ich kurz zeigen wie man eine Formel für Raytracing erstellt, welche man später in seinem Programm nutzen kann. Ich werde an dieser Stelle nicht erklären was Raytracing ist oder wie es funktioniert, hierfür wird es vermutlich später einen eigenen Post geben.

 

Aufgabenstellung

Schneidet ein Strahl eine(n) Kreis/Kugel?

Was ist ein Strahl?

Ein Strahl läuft von einem Urpsrung in eine bestimmte Richtung. Zur Veranschaulichung kann folgendes Bild, in dem die Gerade durch Vektoren beschrieben ist, dienen.

Durch Vektoren dargestellte Gerade

Durch Vektoren dargestellte Gerade

Wir benötigen also einen Vektor \vec{s} der auf den Anfang unserer Geraden zeigt. Der Vektor  \vec{d} gibt hier die Richtung unserer Geraden an. Einen Punkt auf dieser Geraden erhalten wir nun indem wir ein \alpha > 0 mit \vec{d} multiplizieren. Daraus ergibt sich  folgende Formel für unsere Geraden (bzw. unseres Strahls).

p = \vec{s} + \alpha \vec{d}

Was ist ein Kreis/Kugel?

Wenn wir wissen wollen ob ein Punkt auf der Oberfläche unserer Kugel liegt muss dieser Punkt \vec{p} den Abstand r zum Mittelpunkt unserer Kugel haben. Den Abstand eines Vektors von einem Mittelpunkt (Wenn der Mittelpunkt im Ursprung unseres Koordinaten Systems liegt) können wir durch seinen Betrag beschreiben. Dadurch können wir sagen, dass ein Punkt auf der Kugeloberfläche liegt, wenn |p| = r. Damit wir das Ganze auch nun mit Kreisen anstellen können, die nicht im Ursprung unseres Koordinatensystems liegen, müssen wir unseren Mittelpunkt der Kugel in unseren Koordinatenursprung bringen. Dies können wir erreichen indem wir jeden Punkt, den wir auf unserer Oberfläche haben, um die Position des Kugelmittelpunktes \vec{c}|; verschieben. Dadurch ergibt sich folgende Gleichung: |\vec{p}-\vec{c}|;

Das Problem mit dem Schneiden.

So nun wissen wir was unser Strahl und was unsere Kugel ist. Jetzt können wir anfangen zu überlegen wie wir unser Schnittproblem lösen können. Zum besseren Verständnis gehen wir hier davon aus, dass sich unser Kugelmittelpunkt in unserem Koordinatenursprung befindet.

Da unsere Kugelgleichung auf den Vektrobetrag angewiesen ist und dieser bekanntlich mit einer Wurzel berechnet wird ist unserer erster Schritt die Wurzel zu eliminieren.

|p| = r \Leftrightarrow \sqrt{<p,p>} = r\\<br /> \sqrt{p}^2 = r^2 \\<br /> <p,p> = r^2

In diese Gleichung können wir nun unsere Strahlgleichung einsetzen und nach \alpha hin auflösen. Als kleiner Tipp um die nachfolgenden Operationen besser zu Verstehen ist, dass wir hier auf eine Quadratische Gleichung hinarbeiten, die mehrere Lösungen haben kann:

0 Lösungen: Passante

1 Lösung: Tangente

2 Lösungen: Sekante

Nun kommen wir zur Berechnung selbst, an dieser Stelle sind mit Absicht alle Rechenschritte dargestellt, so kann jeder diese Rechnung verstehen.

r^2 = <\vec{p} , \vec{p}>\\<br /> = <\vec{s} + \alpha \vec{d} , \vec{s} + \alpha \vec{d}>\\<br /> = <\vec{s}, \vec{s} + \alpha \vec{d}> + <\alpha \vec{d}, \vec{s} + \alpha \vec{d}>\\<br /> = <\vec{s}, \vec{s}> + <\vec{s}, \alpha \vec{d}> + <\alpha \vec{d}, \vec{s}> + <\alpha \vec{d}, \alpha \vec{d}>\\<br /> = <\vec{s}, \vec{s}> + 2 * <\vec{s}, \alpha \vec{d}> + <\alpha \vec{d}, \alpha \vec{d}>\\<br /> = <\vec{s}, \vec{s}> + 2 * <\vec{s}, \vec{d}> * \alpha + <\alpha \vec{d}, \alpha \vec{d}>\\<br /> = <\vec{s}, \vec{s}> + 2 * <\vec{s}, \vec{d}> * \alpha + \alpha * <\vec{d}, \alpha \vec{d}>\\<br /> = <\vec{s}, \vec{s}> + 2 * <\vec{s}, \vec{d}> * \alpha + \alpha ^2 * <\vec{d},\vec{d}>\\<br /> = \vec{s}^2 + 2 * <\vec{s}, \vec{d}> * \alpha + \alpha ^2 * \vec{d}^2

Der aufmerksame Beobachter nach diesem langen Rumgeschiebe hat erkannt, dass wir unser Ergebnis auch wie folgt präsentieren können:

 <br /> c + b * x + x * a\\<br /> c = \vec{s}^2\\<br /> b = 2 * <\vec{s}, \vec{d}> \\<br /> a = \vec{d}^2\\<br /> x = \alpha \\<br />

Da unsere Gerade bekannt ist kennen wir unsere Vektoren s und d und somit haben wir hier eine Quadratische Gleichung. Diese können wir ganz einfach mit der Mitternachtsformel lösen.

\frac{-2 * <\vec{s}, \vec{d}> \pm \sqrt{4 * <\vec{s}, \vec{d}>^2 - 4 * <\vec{s}, \vec{s}> * <\vec{d}, \vec{d}>}}{2 * <\vec{d}, \vec{d}>}

Hiermit haben wir eine Formel mit der wir prüfen können, ob ein Strahl eine Kugel oder einen Kreis schneidet.

Dieser Beitrag wurde mit Hilfe von Vorlesungsunterlagen der FH-Trier und mit Hilfe von delphigl.com erstellt. Gerne darf dieser Beitrag geteilt werden, ich bitte aber um einen Verweis auf diesen Blog. Das Ganze kostete schließlich schon ein bissel Arbeit ;D. Sollte es Fragen zu dieser Lösung geben könnt ihr diese gerne in den Kommentaren stellen (Kommentieren erfodert ein Anmelden im Blog).

Über den Autor

Andreas

Fortgeschrittener Informatik Student mit der Spezialisierung auf Digitale Medien.

Permanentlink zu diesem Beitrag: http://blackdays.de/2012/07/raytracing-mathematische-herleitung/

Kommentar verfassen