Tutorial Raytracing - Grundlagen I: Unterschied zwischen den Versionen

Aus DGL Wiki
Wechseln zu: Navigation, Suche
K (Quadratische Gleichungen: fhler in dateiname)
K (Vorschau: Kategorie hinzugefügt)
 
(22 dazwischenliegende Versionen von 7 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Offline}}
 
 
= Tutorial Raytracing - Grundlagen I =
 
= Tutorial Raytracing - Grundlagen I =
 
[[Bild:Tutorial_RaytracingI_teaser.jpg|center]]
 
[[Bild:Tutorial_RaytracingI_teaser.jpg|center]]
 
== Einführung ==
 
== Einführung ==
Soso. Da melde ich mich mal wieder zurück mit einem kleinen Tutorial bezüglich Raytracing. Ihr sollt ja auch gelegentlich was neues lernen. Es ist zwar etwas schade, daß nur noch selten Tutorias aus der Community kommen - ich hoffe ja immernoch, daß sich das irgendwann wieder ändern wird. Nunja. Was hat es also mit dem Raytracing auf sich? Und warum heisst dieses Tutorial Grundlagen I? Ich will es euch erklären. Beim Raytracing verfolgt man im Gegensatz zum Rastern wie es etwa OpenGl oder Direct3D machen, einen anderen Ansatz. Statt Objekte in Polygone zu zerschneiden und sie dann auf den Bildschirm per Z-Buffer zu projezieren, wirf die Kamera Strahlen in die Szenerie und auf jedem Strahl prüft man, ob sich ein Objekt mit dem Strahl schneidet. Man verliert dadurch sehr deutlich geschwindigkeit: die wenigsten Raytracer sind so schnell, daß man Interaktiv damit arbeiten kann. Wozu also ist dann Raytracing gut? Man kann im Raytracer hoch realistisch wirkende Bilder erzeugen und auch Verfahren verwenden, die im Rasterizer nich oder kaum nachzubauen sind - die gute alte Grafikkarte muss dabei aber nicht völlig unnütz werden: Diese besitzen sehr flotte und massiv parallele Geometrie-Einheiten, die auch im Raytracer Verwendung finden können - dies ist aber viel zu speziell für unser kleines Tutorial. Was sich im Bereich interaktiver Grafik allerdings anbietet, ist Raytracer ein wenig umzumodeln und mit ihnen statische Lightmaps erzeugen oder sie zur Selection missbrauchen. Das einzige Problem welches wir dabei haben: Wir müssen alles von Grund auf zusammenbasteln - nicht so schön, wie bei OpenGl wo man nach ein paar Stunden schöne Bilder zeichnen kann. Wir werden da wohl etwas länger brauchen, aber ewig wird es auch nicht dauern ;-)
+
Da melde ich mich mal wieder zurück mit einem kleinen Tutorial bezüglich Raytracing. Ihr sollt ja gelegentlich was neues lernen. Es ist zwar etwas schade, dass nur noch selten Tutorials aus der Community kommen - ich hoffe immer noch, dass sich das irgendwann wieder ändern wird. Und alle die bislang Tutorials geschrieben haben, mussten ja irgendwann ihr erstes schreiben - also nur Mut (mein allererstes war im Übrigen das 1. Tutorial aus der Terrain-Reihe). Nunja. Was hat es also mit dem Raytracing auf sich? Und warum heißt dieses Tutorial Grundlagen I? Ich will es euch erklären. Beim Raytracing verfolgt man im Gegensatz zum Rastern wie es etwa OpenGL oder Direct3D machen, einen anderen Ansatz. Statt Objekte oberflächlich in Polygone zu zerschneiden und sie dann auf den Bildschirm per Z-Buffer zu projizieren, wirft die Kamera Strahlen in die Szenerie und auf jedem Strahl prüft man, ob sich ein Objekt mit dem Strahl schneidet. Man verliert dadurch sehr deutlich Geschwindigkeit: die wenigsten Raytracer sind so schnell, dass man interaktiv damit arbeiten kann. Wozu also ist dann Raytracing gut? Man kann im Raytracer hoch realistisch wirkende Bilder erzeugen und auch Verfahren verwenden, die im Rasterizer nicht oder kaum nachzubauen sind - die gute alte Grafikkarte muss dabei nicht völlig unnütz werden: Diese besitzen sehr flotte und massiv parallele Geometrie-Einheiten, die auch im Raytracer Verwendung finden können - dies ist aber etwas zu speziell für unser kleines Tutorial und vielleicht auch nicht das, was man in seinem ersten Raytracer implementieren würde. Was sich im Bereich interaktiver Grafik allerdings anbietet, ist den Raytracer ein wenig umzumodeln und mit ihm statische Lightmaps erzeugen oder ihn zur Selection missbrauchen. Das einzige Problem welches wir dabei haben: Wir müssen alles von Grund auf zusammenbasteln - nicht so schön, wie bei OpenGL, wo man nach ein paar Stunden recht ansehnliche Bilder samt Beleuchtung zeichnen kann. Wir werden da wohl etwas länger brauchen, aber ewig wird es auch nicht dauern - und schliesslich musste OpenGL ja auch erst einmal designed werden. Andere Dinge werden sich dagegen deutlich leichter implementieren lassen als mit OpenGL, so sind etwa Schatten im Raytracer ein Kinderspiel - im Rasterizer können sie richtig arbeitsintensiv werden.
  
== Die Griechische Vorstellung ==
+
== Die griechische Vorstellung ==
[[Bild:Tutorial_RaytracingI_griechisch.jpg|center]]
+
[[Bild:Tutorial_RaytracingI_griechisch.jpg|right]]
Die Griechen hatten eine etwas sonderbare Vorstellung vom Sehen: Sie stellten sich vor, daß aus ihren Augen Strahlen kommen, die dann auf die Umgebung treffen und dann quasi Nachricht an das Auge geben, was sie gesehen haben, wie weit weg es ist und welche Farbe es hat. Das ist in etwa das, was auch ein Raytracer macht. Wir wollen das also ersteinmal im Hinterkopf behalten und uns zuerst mit Strahlen einmal genauer auseinandersetzen. Danach werden wir Kugeln mit diesen Strahlen schneiden und eine passende perspektivische Kamera entwerfen. Schließlich werden wir einen sehr einfachen Raytracer schreiben, und ihn anschließend noch Ebenen als Objekte näherbringen, weil Kugeln alleine doch etwas langweilig sind.
+
Die Griechen hatten eine etwas sonderbare Vorstellung vom Sehen: Sie stellten sich vor, dass aus ihren Augen Strahlen kommen, die dann auf die Umgebung treffen und quasi Nachricht an das Auge geben, was sie getroffen haben, wie weit weg es ist und welche Farbe es hat. Das ist in etwa das was auch ein Raytracer macht. Wir wollen das erst einmal im Hinterkopf behalten und uns zunächst mit Strahlen genauer auseinandersetzen. Danach werden wir Kugeln mit diesen Strahlen schneiden und eine passende perspektivische Kamera entwerfen. Schließlich werden wir einen sehr einfachen Raytracer schreiben, und ihm anschließend noch Ebenen als Objekte näherbringen, weil Kugeln alleine doch etwas langweilig sind.
  
 
== Strahlen ==
 
== Strahlen ==
Was ist also ein Strahl? Ein Strahl hat
+
Was ist also ein Strahl? Ein Strahl hat einen Ursprung, an dem er beginnt, und eine Richung, in die er verläuft. Wer in der Schule in Geometrie aufgepasst hat, kennt dieses Objekt sicher auch noch als Halbgerade. Da wir später damit rechnen werden, müssen wir den Strahl in eine schöne Formel packen:
einen Ursprung, an dem er beginnt, und eine Richung, in die er Verläuft. Wer in
 
der Schule in Geometrie aufgepasst hat, kennt dieses Objekt sicher auch noch
 
als Halbgerade. Da wir später damit rechnen werden, müssen wir den Strahl in
 
eine schöne Formel packen:
 
 
[[Bild:Tutorial_RaytracingI_strahlgleichung.png|center]]
 
[[Bild:Tutorial_RaytracingI_strahlgleichung.png|center]]
Die Punkte auf unserem Strahl R sind also parametrisiert durch t, welches die
+
Die Punkte auf unserem Strahl r sind also parametrisiert durch t, welches die
 
Zahlen von 0 bis unendlich durchläuft. Der Ursprung des Strahles ist o und seine
 
Zahlen von 0 bis unendlich durchläuft. Der Ursprung des Strahles ist o und seine
Richung d. Somit kennen wir alle Punkte auf dem Strahl. Um nun zu prüfen, ob
+
Richung d. Somit kennen wir alle Punkte auf dem Strahl.  
ein Strahl nun ein Objekt trifft, beginnen wir bei t = 0 und laufen alle Punkte
 
ab, bis wir bei t = unendlich angekommen . . . Nein so machen wir das natürlich nicht funktionieren würde es zwar, es würde aber unendlich lange dauern: Nicht
 
gerade das, was wir uns unter schnell vorstellen.  
 
  
Bevor wir weitermachen, sollten wir unseren Strahl gleich noch in
+
Um nun zu prüfen, ob ein Strahl nun ein Objekt trifft, beginnen wir bei t = 0 und laufen alle Punkte ab, bis wir bei t = unendlich angekommen ... ... ... Nein so machen wir das natürlich nicht - funktionieren würde es zwar, würde aber unendlich lange dauern: Nicht gerade das, was wir uns unter schnell vorstellen.
etwas Code verpacken, schließlich wollen wir uns ja einen Ray-Tracer schreiben:
+
 
public struct Ray
+
Bevor wir weitermachen, sollten wir unseren Strahl gleich in
{
+
etwas Code verpacken, schließlich wollen wir uns ja einen Raytracer schreiben:
    public Vertex3 Or igin ;
+
<source lang="cpp">public struct Ray
    public Vertex3 Di r e c t i on ;
+
{
+
    public Vertex3 Origin;
    public Vertex3 Evaluate (double t )
+
    public Vertex3 Direction;
    {
+
 
        return Origin + t * Direction ;
+
    public Vertex3 Evaluate (double t)
    }
+
    {
}
+
        return Origin + t * Direction;
 +
    }
 +
}</source>
  
Zurück zu unserem Problem: Wir müssten also unendlich lange darauf warten,
+
Zurück zu unserem Problem: Wir müssten also unendlich lange darauf warten, bis unser Raytracer das Objekt gefunden hat, mit dem sich der momentan betrachtete Strahl schneidet. Viel schneller geht die Sache, wenn wir vorher beschließen, welche Objekte wir anzeigen können wollen. Für den Anfang wollen wir uns mit sehr einfachen Objekten begnügen: Kugeln. Sie sind schnell berechnet und werden für erste Experimente ausreichen.
bis unser Ray-Tracer das Objekt gefunden hat, mit dem sich der momentan
 
betrachtete Strahl schneidet. Viel schneller geht die Sache, wenn wir vorher beschließen,  
 
welche Objekte wir anzeigen können wollen. Für den Anfang wollen
 
wir uns mit sehr einfachen Objekten begnügen: Kugeln. Sie sind schnell
 
berechnet und werden für erste Experimente ausreichen.
 
  
 
== Kugeln ==
 
== Kugeln ==
Erinnerung: Eine Kugel ist definiert durch ihren Mittelpunkt und ihren Radius
+
Erinnerung: Eine Kugel ist definiert durch ihren Mittelpunkt und ihren Radius r. Setzt man den Mittelpunkt auf den Ursprung des Koordinatensystems, dann sind die Punkte auf der Oberfläche O unserer Kugel gerade die Punkte, die vom Ursprung den Abstand r haben. Die uns interessierende Bedingung wird so zu ||p|| = r für Punkte p auf O. Die Gleichung kann man schadlos quadrieren und statt der Vektorlänge ||p|| bekommt man das ohne Wurzel ziehen zu berechnende [[Standard Skalarprodukt|Skalarprodukt]] von p mit sich selbst:
r. Setzt man den Mittelpunkt auf den Ursprung des Koordinatensystems, dann
 
sind die Punkte auf der Oberfläche O unserer Kugel gerade die Punkte, die vom
 
Ursprung den Abstand r haben. Die uns interessierende Bedingung wird so zu
 
||p|| = r für Punkte p in O. Die Gleichung kann man schadlos quadrieren und
 
statt der Vektorlänge ||p|| bekommt man das ohne Wurzel ziehen zu berechnende
 
[[Standard Skalarprodukt|Skalarprodukt]] von p mit sich selbst:
 
 
[[Bild:Tutorial_RaytracingI_skalprodpp.png|center]]
 
[[Bild:Tutorial_RaytracingI_skalprodpp.png|center]]
 
Setzt man hierein die obige Gleichung für den Strahl, ergibt sich:
 
Setzt man hierein die obige Gleichung für den Strahl, ergibt sich:
Zeile 56: Zeile 39:
 
Und damit:
 
Und damit:
 
[[Bild:Tutorial_RaytracingI_radsqr2.png|center]]
 
[[Bild:Tutorial_RaytracingI_radsqr2.png|center]]
Da die Richtung o und d unseres Strahls bekannt sind, haben wir
+
Da die Richtung o und d unseres Strahls bekannt sind, haben wir eine quadratische Gleichung vor der Nase, die wir mittels Mitternachtsformel lösen können:
eine quadratische Gleichung vor der Nase, die wir mittels Mitternachsformel
 
lösen können:
 
 
[[Bild:Tutorial_RaytracingI_mitternacht.png|center]]
 
[[Bild:Tutorial_RaytracingI_mitternacht.png|center]]
Anhand der Diskriminante D, also dem Teil des obigen Ausdrucks, der unter
+
Anhand der Diskriminante D, also dem Teil des obigen Ausdrucks, der unter der Wurzel steht, können wir entscheiden, ob der Strahl die Kugel trift. Ist nämlich D < 0, so kann man in den reelen Zahlen die Wurzel nicht berechnen. Ist D = 0, so gibt es genau eine Lösung der Schnittgleichung und für D > 0 schneidet der Strahl die Kugel genau 2 mal. Da wir unseren Strahl nur für positive Parameter t definiert haben, sollten wir die errechneten Schnittpunkte t<sub>1</sub> und t<sub>2</sub> noch daraufhin untersuchen:
der Wurzel steht, können wir entscheiden, ob der Strahl die Kugel trift. Ist
+
<source lang="cpp">public double RayIntersect ( Ray ray )
nämlich D < 0, so kann man in den reelen Zahlen die Wurzel nicht berechnen.  
+
{
Ist D = 0, so gibt es genau eine Lösung der Schnittgleichung und für D > 0 schneidet
+
    double boundingSquare = sphereRadius * sphereRadius ;
der Strahl die Kugel genau 2 mal. Da wir unseren Strahl nur für positive Parameter
+
    ray.Origin -= Position;
t definiert haben, sollten wir die errechneten Schnittpunkte t<sub>1</sub> und t<sub>2</sub> noch
+
    double a, b, c;
daraufhin untersuchen:
+
    a = ray.Direction.DotDot ;
public double RayIntersect ( Ray ray )
+
    // DotDot ^= Skalarprod mit sichselbst : <d, d>
{
+
    b = 2 * ( ray.Origin * ray.Direction );
    double boundingSquare = sphereRadius * sphereRadius ;
+
    // * ^= normales Skalarprod
    ray.Origin -= Position;
+
    c = ray.Origin.DotDot - boundingSquare;
    double a, b, c;
+
 
    a = ray.Direction.DotDot ;
+
    double t1 , t2 ;
    // DotDot ^= Skalarprod mit sichselbst : <d , d>
+
    int roots = CalcQuadricRoots (a, b, c, out t1, out t2) ;
    b = 2 * ( ray.Origin * ray.Direction );
+
 
    // * ^= normales Skalarprod
+
    if (roots > 0)
    c = ray.Origin.DotDot - boundingSquare;
+
        return t1 >= 0 ? t1 : t2 ;
+
        // kleinsterpositiver pos. Wert aus t1, t2
    double t1 , t2 ;
+
    else
    int roots = CalcQuadricRoots (a , b, c, out t1, out t2) ;
+
        return -1; // Kein Schnittpunkt
+
}</source>
    if (roots > 0)
+
Einen kleinen Haken hat die Sache jedoch: Analytisch, d.h. per Stift und Papier, lässt sich mit der Mitternachtsformel wunderbar rechnen. Am Computer neigt sie zu Fehlern, was ganz allein an dem &plusmn; liegt. So führt man verlässlich eine Subtraktion durch, wenn D > 0 ist - und Subtraktionen sind reines Gift für die Genauigkeit bei numerischen Rechnungen. Durch kleine Umformungen und das Bestimmen eines Vorzeichens, können wir das Problem umgehen:
        return t1 >= 0 ? t1 : t2 ;
 
        // kleinsterpositiver pos. Wert aus t1 , t2
 
    else
 
        return -1; // Kein Schnittpunkt
 
}
 
Einen kleinen Haken hat die Sache jedoch: Analytisch (d.h. per Stift und Papier)
 
lässt sich mit der Mitternachtsformel wunderbar rechnen. Am Computer
 
neigt sie zu Fehlern, was ganz allein an dem +- liegt. So führt man verlässlich
 
eine Subtraktion durch, wenn D > 0 ist und Subtraktionen sind reines Gift
 
für die Genauigkeit bei numersichen Rechnungen. Durch kleine Umformungen
 
und das bestimmen eines Vorzeichens, können wir das Problem umgehen:
 
  
 
== Quadratische Gleichungen ==
 
== Quadratische Gleichungen ==
Zeile 99: Zeile 69:
 
dann bestimmt man die Nullstellen am besten durch:
 
dann bestimmt man die Nullstellen am besten durch:
 
[[Bild:Tutorial_RaytracingI_quadratisch_numerisch.png|center]]
 
[[Bild:Tutorial_RaytracingI_quadratisch_numerisch.png|center]]
Bei der Auswertung von q wird so sicherlich echt addiert, weil zu b eine Zahl
+
Bei der Auswertung von q wird so sicherlich echt addiert, weil zu b eine Zahl gleichen Vorzeichens summiert wird. Dass der Wert für t<sub>1</sub> stimmt, hat man dann auch sehr leicht nachgerechnet, wohingegen t<sub>2</sub> in wildes Rumgeschiebe der Formel ausartet und sich erst recht spät sign(b) herauswerfen lässt. Ich erspare euch nähere Erläuterungen ;-) Ein bisschen Quellcode hierzu:
gleichen Vorzeichens summiert wird. Dass der Wert für t<sub>1</sub> stimmt, hat man
 
dann auch sehr leicht nachgerechnet, wohingegen t<sub>2</sub> in wildes rumgeschiebe der
 
Formel ausartet und sich erst recht spät sign(b) herauswerfen lässt. Ein bischen
 
Quellcode hierzu:
 
  
public static int CalcQuadricRoots(double a, double b, double c, out double x1, out double x2)
+
<source lang="cpp">public static int CalcQuadricRoots(double a, double b, double c, out double x1, out double x2)
{
+
{
    double determinant = b * b - 4 * a * c;
+
    double determinant = b * b - 4 * a * c;
    if (determinant < 0)
+
    if (determinant < 0)
    {
+
    {
        x1 = 0.0;
+
        x1 = 0.0;
        x2 = 0.0;
+
        x2 = 0.0;
        return 0;
+
        return 0;
    }
+
    }
    determinant = Math.Sqrt(determinant);
+
    determinant = Math.Sqrt(determinant);
    double q = -0.5 * (b + PSgn(b) * determinant);
+
    double q = -0.5 * (b + PSgn(b) * determinant);
    // Psgn: gives - 1 if b < 0 and 1 if b >= 0.  
+
    // Psgn: gives - 1 if b < 0 and 1 if b >= 0.  
    // so no zero as normal sgn would give us.
+
    // so no zero as normal sgn would give us.
    x1 = q / a;
+
    x1 = q / a;
    x2 = c / q;
+
    x2 = c / q;
    // Sort by value
+
    // Sort by value
    if (x1 > x2)
+
    if (x1 > x2)
    {
+
    {
        q = x2; x2 = x1; x1 = q;
+
        q = x2; x2 = x1; x1 = q;
    }
+
    }
    return x1 == x2 ? 1 : 2;
+
    return x1 == x2 ? 1 : 2;
}
+
}</source>
Die Funktion speichert die Nullstellen in den Variablen x1, x2 dem Wert
+
Die Funktion speichert die Nullstellen in den Variablen x1, x2 dem Wert nach sortiert ab und gibt die Anzahl der Nullstellen zurück.
nach sortiert ab und gibt die Anzahl der Nullstellen zurück.
+
Da wir jetzt bereits bestimmen können, wo und wie oft unser Strahl die Kugel trift, können wir, nachdem wir uns noch einen Strahlenwerfer, (also eine Kamera) konstruiert haben, unseren ersten Raytracer bauen.
Da wir jetzt bereits bestimmen können, wo und wie oft unser Strahl die
 
Kugel trift, können wir, nachdem wir uns noch einen Strahlenwerfer, (also
 
eine Kamera) konstruiert haben, unseren ersten Ray-Tracer bauen.
 
  
 
== Perspektivische Kamera ==
 
== Perspektivische Kamera ==
 +
Jeder, der sich mit OpenGL auskennt, wird bei der Konstruktion einer perspektivischen Kamera gleich schreien, dass man dazu doch einfach nur eine Projektionsmatrix braucht, die man sich ganz einfach aus der OpenGL Spezifikation stibitzen kann. Falsch gedacht: Ein Raytracer ist kein Rasterizer: Wir brauchen keine Projektionsmatrizen, noch nicht einmal Matrizen. Die perspektivische Kamera eines Ray-Tracers lässt sich direkt nach vorn heraus entwerfen:
 +
 +
[[Bild:Tutorial_RaytracingI_perspektivisch.png|center]]
 +
 +
Unrotiert und unverschoben soll unsere Kamera in die Tiefenrichtung z blicken. Dabei wird unser Bildschirm durch die Parameter links, rechts, oben und unten beschrieben. Ist die Auflösung des Bildschirms in X wie in Y-Richtung bekannt, so kann man leicht die Richtung d des Vektors bestimmen, der vom Betrachter auf den Bildschirm zeigt. Sofort bekommt man so einen Strahl, wenn man als Anfangspunkt o die Position des Betrachters wählt:
 +
 +
<source lang="cpp">public Ray ShootRay ( int x , int y )
 +
{
 +
    Ray result = new Ray();
 +
    result.Origin = Position;
 +
 +
    double xpart , ypart ;
 +
    xpart = ( ( double ) x ) / (double ) widthpixels;
 +
    ypart = ( ( double ) y ) / (double ) heightpixels;
 +
 +
    xpart = left + xpart * ( right - left ) ;
 +
    ypart = top + ypart * ( bottom - top ) ;
 +
 +
    result.Direction.x = xpart;
 +
    result.Direction.y = ypart;
 +
    result.Direction.z = 1.0;
 +
 +
    /* if ( Transformation != null )
 +
    {
 +
        result.Direction =
 +
        Transformation.Apply( result.Direction );
 +
    } */
 +
    result.Direction.Normalize();
 +
    return result;
 +
}</source>
 +
Die auskommentierte if-Abfrage soll vorerst nicht stören. Ihr wird später leben eingehaucht, wenn wir dem Raytracer Verschiebungen,
 +
Rotationen, Skalierungen, Scheerungen, u.s.w. einbauen.
  
 
== Einfacher Raycaster ==
 
== Einfacher Raycaster ==
 +
[[Bild:Tutorial_RaytracingI_depthcasting.jpg|right]]
 +
Damit sind wir dann auch schon soweit, dass wir unsere ersten Gehversuche in Sachen Raytracing wagen können. Für jedes Pixel im Bild werfen wir mittels ShootRay einen Strahl und prüfen, ob dieser die Kugeln in unserer Szene schneidet. Wenn ja, merken wir uns den nähestes dieser Schnittpunkte und weisen ihm einen Farbwert zu. So erhalten wir ein Bild, das in etwa die Informationen wieder gibt, die OpenGl in seinem Tiefenpuffer speichern würde. Ich gebe zu, das ist nicht hochgradig spannend, aber solange wir uns noch nicht eingehender mit Licht und Shading beschäftigt haben, können wir auch nicht mehr erwarten - und wir haben beim Raytracing ja leider das Problem, dass wir ganz von vorne anfangen müssen:
 +
 +
<source lang="cpp">public RaytraceImage ( int width , int height )
 +
{
 +
    // near und far sind die Werte fuer den Bereich ,
 +
    // von dem Tiefeninformationen abgebildet werden
 +
    for ( int x = 0; x < width; x++) {
 +
        for ( int y = 0 ; y < height; y++) {
 +
            Ray shoot = ShootRay (x , y);
 +
            double maxdist = double.Infinity;
 +
           
 +
            foreach (Kugel obj in SichtbareKugeln) {
 +
                double hitdist = obj.RayIntersect(shoot) ;
 +
                if (hitdist > 0 && maxdist > hitdist)
 +
                    maxdist = hitdist;
 +
            }
 +
           
 +
            if (maxdist < double.Infinity) {
 +
                SetColor(x, y, Colors.Gray (Math.Min(Math .Max(0,
 +
                    (maxdist - near) / ( near - far ))), 1.0)) ;
 +
            }
 +
            else
 +
                SetColor(x, y, BackgroundColor); 
 +
        }
 +
    }
 +
}</source>
 +
Eine kleine Anmerkung noch: Da wir uns noch nicht über Transformationen Gedanken gemacht haben, und unsere Kugeln bislang am Nullpunkt aufgehäng sind, können wir diese noch nicht positionieren - sprich es wird höchstens die größte Kugel sichtbar, weil alle weiteren verdeckt sind. Das lässt sich beheben, indem man vor dem Test auf Schnitt vom Ursprung des entsprechenden Strahles, die Position der Kugel abzieht.
 +
 
== Ebenen ==
 
== Ebenen ==
 +
Mit Kugeln kann man zwar so einiges darstellen, aber nur Kugeln sind vielleicht doch etwas langweilig. Wir wollen deshalb noch Ebenen implementieren. Am besten betrachten wir diese dazu in der Normalform, d.h. die Ebene wird allein durch ihre Flächennormale angegeben. Für Punkte auf der Ebene gilt dann:
 +
[[Bild:Tutorial_RaytracingI_ebenengleichung.png|center]]
 +
Setzt man nun in x unseren Strahl ein, ergibt sich:
 +
[[Bild:Tutorial_RaytracingI_ebenenrechnung.png|center]]
 +
Ist <d,n>=0, dann gibt es keine Lösung, sonst genau eine.
 +
 +
Welche Objekte eignen sich sonst gut zum Raytracing? ... Alle Objekte, die sich in kartesischen Koordinaten durch eine Gleichung der Form [[Bild:Tutorial_RaytracingI_kartesisch.png|center]] darstellen lassen. In (x,y,z) setzt man seinen Strahl r(t) ein und versucht nach t aufzulösen. In einigen Fällen wird dieses Problem leider kaum zu lösen sein: man kommt dann um den Einsatz von numerischen Verfahren nicht herum. Ich werde versuchen, in Folgetutorials noch ein paar weitere, interessante Objekte vorzustellen, die sich direkt lösen lassen und wenn ich viel Geduld habe, vielleicht auch einmal einen eigenen Artikel bezüglich numerischer Verfahren.
  
 
== Vorschau ==
 
== Vorschau ==
Damit sind wir auch schon wieder soweit. Die ersten Grundlagen sind abgehandelt aber wirklich überzeugt sind wir vom Raytracing noch nicht. Damit sich das ändert, ist ein weiteres Tutorial in Planung: Wir wollen uns dann mit Licht und Normalen beschäftigen. Ausserdem sind Reflektionen und Transparenz spannende Dinge, denen wir uns widmen können. Wir wollen ausserdem unsere Objekte transformieren, scheeren, rotieren, ... Es bleibt also noch einiges im Bereich Raytracing zu tun, was hier nicht behandelt werden konnte.
+
Damit sind wir auch schon wieder soweit. Die ersten Grundlagen sind abgehandelt, aber wirklich überzeugt sind wir vom Raytracing noch nicht. Damit sich das ändert, sind weitere Tutorials in Planung: Wir wollen uns dann mit Licht und Normalen beschäftigen. Außerdem sind Reflektionen und Transparenz spannende Dinge, denen wir uns widmen können. Wir wollen außerdem unsere Objekte transformieren, scheeren, rotieren, ... Es bleibt also noch einiges im Bereich Raytracing zu tun, was hier nicht behandelt wurde.
 +
 
 +
Bis es soweit ist, könnt ihr euch ja selbst schonmal ein paar Gedanken zum Thema machen oder euch doch lieber in die Weiten von OpenGl flüchten.
 +
 
 +
'''Delphic'''
  
Bis es soweit ist, könnt ihr euch ja selbst schonmal ein paar Gedanken zu dem Thema machen.
+
[[Kategorie:Tutorial|Raytracing - Grundlagen I]]
  [[Benutzer:Nico Michaelis]]
 

Aktuelle Version vom 9. März 2014, 12:01 Uhr

Tutorial Raytracing - Grundlagen I

Tutorial RaytracingI teaser.jpg

Einführung

Da melde ich mich mal wieder zurück mit einem kleinen Tutorial bezüglich Raytracing. Ihr sollt ja gelegentlich was neues lernen. Es ist zwar etwas schade, dass nur noch selten Tutorials aus der Community kommen - ich hoffe immer noch, dass sich das irgendwann wieder ändern wird. Und alle die bislang Tutorials geschrieben haben, mussten ja irgendwann ihr erstes schreiben - also nur Mut (mein allererstes war im Übrigen das 1. Tutorial aus der Terrain-Reihe). Nunja. Was hat es also mit dem Raytracing auf sich? Und warum heißt dieses Tutorial Grundlagen I? Ich will es euch erklären. Beim Raytracing verfolgt man im Gegensatz zum Rastern wie es etwa OpenGL oder Direct3D machen, einen anderen Ansatz. Statt Objekte oberflächlich in Polygone zu zerschneiden und sie dann auf den Bildschirm per Z-Buffer zu projizieren, wirft die Kamera Strahlen in die Szenerie und auf jedem Strahl prüft man, ob sich ein Objekt mit dem Strahl schneidet. Man verliert dadurch sehr deutlich Geschwindigkeit: die wenigsten Raytracer sind so schnell, dass man interaktiv damit arbeiten kann. Wozu also ist dann Raytracing gut? Man kann im Raytracer hoch realistisch wirkende Bilder erzeugen und auch Verfahren verwenden, die im Rasterizer nicht oder kaum nachzubauen sind - die gute alte Grafikkarte muss dabei nicht völlig unnütz werden: Diese besitzen sehr flotte und massiv parallele Geometrie-Einheiten, die auch im Raytracer Verwendung finden können - dies ist aber etwas zu speziell für unser kleines Tutorial und vielleicht auch nicht das, was man in seinem ersten Raytracer implementieren würde. Was sich im Bereich interaktiver Grafik allerdings anbietet, ist den Raytracer ein wenig umzumodeln und mit ihm statische Lightmaps erzeugen oder ihn zur Selection missbrauchen. Das einzige Problem welches wir dabei haben: Wir müssen alles von Grund auf zusammenbasteln - nicht so schön, wie bei OpenGL, wo man nach ein paar Stunden recht ansehnliche Bilder samt Beleuchtung zeichnen kann. Wir werden da wohl etwas länger brauchen, aber ewig wird es auch nicht dauern - und schliesslich musste OpenGL ja auch erst einmal designed werden. Andere Dinge werden sich dagegen deutlich leichter implementieren lassen als mit OpenGL, so sind etwa Schatten im Raytracer ein Kinderspiel - im Rasterizer können sie richtig arbeitsintensiv werden.

Die griechische Vorstellung

Tutorial RaytracingI griechisch.jpg

Die Griechen hatten eine etwas sonderbare Vorstellung vom Sehen: Sie stellten sich vor, dass aus ihren Augen Strahlen kommen, die dann auf die Umgebung treffen und quasi Nachricht an das Auge geben, was sie getroffen haben, wie weit weg es ist und welche Farbe es hat. Das ist in etwa das was auch ein Raytracer macht. Wir wollen das erst einmal im Hinterkopf behalten und uns zunächst mit Strahlen genauer auseinandersetzen. Danach werden wir Kugeln mit diesen Strahlen schneiden und eine passende perspektivische Kamera entwerfen. Schließlich werden wir einen sehr einfachen Raytracer schreiben, und ihm anschließend noch Ebenen als Objekte näherbringen, weil Kugeln alleine doch etwas langweilig sind.

Strahlen

Was ist also ein Strahl? Ein Strahl hat einen Ursprung, an dem er beginnt, und eine Richung, in die er verläuft. Wer in der Schule in Geometrie aufgepasst hat, kennt dieses Objekt sicher auch noch als Halbgerade. Da wir später damit rechnen werden, müssen wir den Strahl in eine schöne Formel packen:

Tutorial RaytracingI strahlgleichung.png

Die Punkte auf unserem Strahl r sind also parametrisiert durch t, welches die Zahlen von 0 bis unendlich durchläuft. Der Ursprung des Strahles ist o und seine Richung d. Somit kennen wir alle Punkte auf dem Strahl.

Um nun zu prüfen, ob ein Strahl nun ein Objekt trifft, beginnen wir bei t = 0 und laufen alle Punkte ab, bis wir bei t = unendlich angekommen ... ... ... Nein so machen wir das natürlich nicht - funktionieren würde es zwar, würde aber unendlich lange dauern: Nicht gerade das, was wir uns unter schnell vorstellen.

Bevor wir weitermachen, sollten wir unseren Strahl gleich in etwas Code verpacken, schließlich wollen wir uns ja einen Raytracer schreiben:

public struct Ray
{
    public Vertex3 Origin;
    public Vertex3 Direction;

    public Vertex3 Evaluate (double t)
    {
        return Origin + t * Direction;
    }
}

Zurück zu unserem Problem: Wir müssten also unendlich lange darauf warten, bis unser Raytracer das Objekt gefunden hat, mit dem sich der momentan betrachtete Strahl schneidet. Viel schneller geht die Sache, wenn wir vorher beschließen, welche Objekte wir anzeigen können wollen. Für den Anfang wollen wir uns mit sehr einfachen Objekten begnügen: Kugeln. Sie sind schnell berechnet und werden für erste Experimente ausreichen.

Kugeln

Erinnerung: Eine Kugel ist definiert durch ihren Mittelpunkt und ihren Radius r. Setzt man den Mittelpunkt auf den Ursprung des Koordinatensystems, dann sind die Punkte auf der Oberfläche O unserer Kugel gerade die Punkte, die vom Ursprung den Abstand r haben. Die uns interessierende Bedingung wird so zu ||p|| = r für Punkte p auf O. Die Gleichung kann man schadlos quadrieren und statt der Vektorlänge ||p|| bekommt man das ohne Wurzel ziehen zu berechnende Skalarprodukt von p mit sich selbst:

Tutorial RaytracingI skalprodpp.png

Setzt man hierein die obige Gleichung für den Strahl, ergibt sich:

Tutorial RaytracingI radsqr.png

Und damit:

Tutorial RaytracingI radsqr2.png

Da die Richtung o und d unseres Strahls bekannt sind, haben wir eine quadratische Gleichung vor der Nase, die wir mittels Mitternachtsformel lösen können:

Tutorial RaytracingI mitternacht.png

Anhand der Diskriminante D, also dem Teil des obigen Ausdrucks, der unter der Wurzel steht, können wir entscheiden, ob der Strahl die Kugel trift. Ist nämlich D < 0, so kann man in den reelen Zahlen die Wurzel nicht berechnen. Ist D = 0, so gibt es genau eine Lösung der Schnittgleichung und für D > 0 schneidet der Strahl die Kugel genau 2 mal. Da wir unseren Strahl nur für positive Parameter t definiert haben, sollten wir die errechneten Schnittpunkte t1 und t2 noch daraufhin untersuchen:

public double RayIntersect ( Ray ray )
{
    double boundingSquare = sphereRadius * sphereRadius ;
    ray.Origin -= Position;
    double a, b, c;
    a = ray.Direction.DotDot ;
    // DotDot ^= Skalarprod mit sichselbst : <d, d>
    b = 2 * ( ray.Origin * ray.Direction );
    // * ^= normales Skalarprod
    c = ray.Origin.DotDot - boundingSquare;

    double t1 , t2 ;
    int roots = CalcQuadricRoots (a, b, c, out t1, out t2) ;

    if (roots > 0)
        return t1 >= 0 ? t1 : t2 ;
        // kleinsterpositiver pos. Wert aus t1, t2
    else
        return -1; // Kein Schnittpunkt
}

Einen kleinen Haken hat die Sache jedoch: Analytisch, d.h. per Stift und Papier, lässt sich mit der Mitternachtsformel wunderbar rechnen. Am Computer neigt sie zu Fehlern, was ganz allein an dem ± liegt. So führt man verlässlich eine Subtraktion durch, wenn D > 0 ist - und Subtraktionen sind reines Gift für die Genauigkeit bei numerischen Rechnungen. Durch kleine Umformungen und das Bestimmen eines Vorzeichens, können wir das Problem umgehen:

Quadratische Gleichungen

Hat man also eine Quadratische Gleichung in der allgemeinen Form:

Tutorial RaytracingI quadratisch.png

dann bestimmt man die Nullstellen am besten durch:

Tutorial RaytracingI quadratisch numerisch.png

Bei der Auswertung von q wird so sicherlich echt addiert, weil zu b eine Zahl gleichen Vorzeichens summiert wird. Dass der Wert für t1 stimmt, hat man dann auch sehr leicht nachgerechnet, wohingegen t2 in wildes Rumgeschiebe der Formel ausartet und sich erst recht spät sign(b) herauswerfen lässt. Ich erspare euch nähere Erläuterungen ;-) Ein bisschen Quellcode hierzu:

public static int CalcQuadricRoots(double a, double b, double c, out double x1, out double x2)
{
    double determinant = b * b - 4 * a * c;
    if (determinant < 0)
    {
        x1 = 0.0;
        x2 = 0.0;
        return 0;
    }
    determinant = Math.Sqrt(determinant);
    double q = -0.5 * (b + PSgn(b) * determinant);
    // Psgn: gives - 1 if b < 0 and 1 if b >= 0. 
    // so no zero as normal sgn would give us.
    x1 = q / a;
    x2 = c / q;
    // Sort by value
    if (x1 > x2)
    {
        q = x2; x2 = x1; x1 = q;
    }
    return x1 == x2 ? 1 : 2;
}

Die Funktion speichert die Nullstellen in den Variablen x1, x2 dem Wert nach sortiert ab und gibt die Anzahl der Nullstellen zurück. Da wir jetzt bereits bestimmen können, wo und wie oft unser Strahl die Kugel trift, können wir, nachdem wir uns noch einen Strahlenwerfer, (also eine Kamera) konstruiert haben, unseren ersten Raytracer bauen.

Perspektivische Kamera

Jeder, der sich mit OpenGL auskennt, wird bei der Konstruktion einer perspektivischen Kamera gleich schreien, dass man dazu doch einfach nur eine Projektionsmatrix braucht, die man sich ganz einfach aus der OpenGL Spezifikation stibitzen kann. Falsch gedacht: Ein Raytracer ist kein Rasterizer: Wir brauchen keine Projektionsmatrizen, noch nicht einmal Matrizen. Die perspektivische Kamera eines Ray-Tracers lässt sich direkt nach vorn heraus entwerfen:

Tutorial RaytracingI perspektivisch.png

Unrotiert und unverschoben soll unsere Kamera in die Tiefenrichtung z blicken. Dabei wird unser Bildschirm durch die Parameter links, rechts, oben und unten beschrieben. Ist die Auflösung des Bildschirms in X wie in Y-Richtung bekannt, so kann man leicht die Richtung d des Vektors bestimmen, der vom Betrachter auf den Bildschirm zeigt. Sofort bekommt man so einen Strahl, wenn man als Anfangspunkt o die Position des Betrachters wählt:

public Ray ShootRay ( int x , int y )
{
    Ray result = new Ray();
    result.Origin = Position;

    double xpart , ypart ;
    xpart = ( ( double ) x ) / (double ) widthpixels;
    ypart = ( ( double ) y ) / (double ) heightpixels;
 
    xpart = left + xpart * ( right - left ) ;
    ypart = top + ypart * ( bottom - top ) ;
 
    result.Direction.x = xpart;
    result.Direction.y = ypart;
    result.Direction.z = 1.0;

    /* if ( Transformation != null )
    {
        result.Direction =
        Transformation.Apply( result.Direction );
    } */
    result.Direction.Normalize();
    return result;
}

Die auskommentierte if-Abfrage soll vorerst nicht stören. Ihr wird später leben eingehaucht, wenn wir dem Raytracer Verschiebungen, Rotationen, Skalierungen, Scheerungen, u.s.w. einbauen.

Einfacher Raycaster

Tutorial RaytracingI depthcasting.jpg

Damit sind wir dann auch schon soweit, dass wir unsere ersten Gehversuche in Sachen Raytracing wagen können. Für jedes Pixel im Bild werfen wir mittels ShootRay einen Strahl und prüfen, ob dieser die Kugeln in unserer Szene schneidet. Wenn ja, merken wir uns den nähestes dieser Schnittpunkte und weisen ihm einen Farbwert zu. So erhalten wir ein Bild, das in etwa die Informationen wieder gibt, die OpenGl in seinem Tiefenpuffer speichern würde. Ich gebe zu, das ist nicht hochgradig spannend, aber solange wir uns noch nicht eingehender mit Licht und Shading beschäftigt haben, können wir auch nicht mehr erwarten - und wir haben beim Raytracing ja leider das Problem, dass wir ganz von vorne anfangen müssen:

public RaytraceImage ( int width , int height )
{
    // near und far sind die Werte fuer den Bereich ,
    // von dem Tiefeninformationen abgebildet werden
    for ( int x = 0; x < width; x++) {
        for ( int y = 0 ; y < height; y++) {
            Ray shoot = ShootRay (x , y);
            double maxdist = double.Infinity;
            
            foreach (Kugel obj in SichtbareKugeln) {
                double hitdist = obj.RayIntersect(shoot) ;
                if (hitdist > 0 && maxdist > hitdist)
                    maxdist = hitdist;
            }
            
            if (maxdist < double.Infinity) {
                SetColor(x, y, Colors.Gray (Math.Min(Math .Max(0,
                    (maxdist - near) / ( near - far ))), 1.0)) ;
            }
            else
                SetColor(x, y, BackgroundColor);   
        }
    }
}

Eine kleine Anmerkung noch: Da wir uns noch nicht über Transformationen Gedanken gemacht haben, und unsere Kugeln bislang am Nullpunkt aufgehäng sind, können wir diese noch nicht positionieren - sprich es wird höchstens die größte Kugel sichtbar, weil alle weiteren verdeckt sind. Das lässt sich beheben, indem man vor dem Test auf Schnitt vom Ursprung des entsprechenden Strahles, die Position der Kugel abzieht.

Ebenen

Mit Kugeln kann man zwar so einiges darstellen, aber nur Kugeln sind vielleicht doch etwas langweilig. Wir wollen deshalb noch Ebenen implementieren. Am besten betrachten wir diese dazu in der Normalform, d.h. die Ebene wird allein durch ihre Flächennormale angegeben. Für Punkte auf der Ebene gilt dann:

Tutorial RaytracingI ebenengleichung.png

Setzt man nun in x unseren Strahl ein, ergibt sich:

Tutorial RaytracingI ebenenrechnung.png

Ist <d,n>=0, dann gibt es keine Lösung, sonst genau eine.

Welche Objekte eignen sich sonst gut zum Raytracing? ... Alle Objekte, die sich in kartesischen Koordinaten durch eine Gleichung der Form
Tutorial RaytracingI kartesisch.png
darstellen lassen. In (x,y,z) setzt man seinen Strahl r(t) ein und versucht nach t aufzulösen. In einigen Fällen wird dieses Problem leider kaum zu lösen sein: man kommt dann um den Einsatz von numerischen Verfahren nicht herum. Ich werde versuchen, in Folgetutorials noch ein paar weitere, interessante Objekte vorzustellen, die sich direkt lösen lassen und wenn ich viel Geduld habe, vielleicht auch einmal einen eigenen Artikel bezüglich numerischer Verfahren.

Vorschau

Damit sind wir auch schon wieder soweit. Die ersten Grundlagen sind abgehandelt, aber wirklich überzeugt sind wir vom Raytracing noch nicht. Damit sich das ändert, sind weitere Tutorials in Planung: Wir wollen uns dann mit Licht und Normalen beschäftigen. Außerdem sind Reflektionen und Transparenz spannende Dinge, denen wir uns widmen können. Wir wollen außerdem unsere Objekte transformieren, scheeren, rotieren, ... Es bleibt also noch einiges im Bereich Raytracing zu tun, was hier nicht behandelt wurde.

Bis es soweit ist, könnt ihr euch ja selbst schonmal ein paar Gedanken zum Thema machen oder euch doch lieber in die Weiten von OpenGl flüchten.

Delphic