Version vom 25. Dezember 2006, 17:39 Uhr

Tutorial Raytracing - Grundlagen I

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, daß nur noch selten Tutorials aus der Community kommen - ich hoffe immernoch, daß 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 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 oberflächlich in Polygone zu zerschneiden und sie dann auf den Bildschirm per Z-Buffer zu projezieren, 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 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 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 zuerst 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:

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:

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

Und damit:

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:

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₁ und t₂ 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:

dann bestimmt man die Nullstellen am besten durch:

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₁ stimmt, hat man dann auch sehr leicht nachgerechnet, wohingegen t₂ 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 bischen 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, daß 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:

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

Damit sind wir dann auch schon soweit, daß 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, daß 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:

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

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

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. 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 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.

Nico Michaelis