Mit dem Befehl SetPixel der Klasse System.Drawing.Bitmap lassen sich einzelne Pixel in einem Bitmap verändern. Leider arbeitet diese Methode sehr langsam, und es ist nicht möglich sie aus mehreren Threads gleichzeitig aufzurufen. Möchte man also ein Bitmap Pixel für Pixel durch mehrere Threads berechnen lassen, so muss man die SetPixel-Aufrufe z.B. durch lock(…) Anweisungen vor zeitgleichen Aufrufen schützen. Dies macht den Geschwindigkeitsvorteil, den mehrere Threads bringen, teilweise wieder zunichte.

Abhilfe schafft die hier vorgestellte Klasse RawRgbBitmap. Sie bietet ebenfalls eine Methode namens SetPixel, welche jedoch deutlich schneller arbeitet als die der Bitmap-Klasse und zudem von mehreren Threads gleichzeitig aufgerufen werden kann. Durch den „implicit operator Bitmap“ wird ein RawRgbBitmap automatisch in ein System.Drawing.Bitmap umgewandelt, wann immer es einer System.Drawing.Bitmap-Variablen zugewiesen wird.

Und so funktioniert’s:

Der Konstruktor der Klasse RawRgbBitmap erzeugt zunächst ein Byte-Array. Anschließend wird ein neues System.Drawing.Bitmap erzeugt, dessen Bildspeicher auf genau dem gleichen Speicherbereich abgelegt wird, wie das Byte-Array. Wir können nun also alle Pixelmanipulationen direkt an dem Byte-Array vornehmen, ohne dafür das (langsame) Bitmap-Objekt zu verwenden. Da das Bitmap jedoch auf dem gleichen Speicherbereich liegt, wie das Array, wirken sich alle Änderungen im Array auch auf das Bitmap aus.

    public class RawRgbBitmap :IDisposable
    {
        int width;
        int height;
        int stride;

        byte[] raw;
        GCHandle handle;
        Bitmap bmp;

        public RawRgbBitmap(int width, int height)
        {
            this.width = width;
            this.height = height;
            int validBitsPerLine = width * 24;
            // Jede Zeile im Array muß ein ganzes Vielfaches von einem int32 (4 Byte) sein. Dies ist also die Schrittweite pro Bildzeile im Array:
            stride = ((validBitsPerLine + 31) / 32) * 4;

            raw = new byte[stride * height];
            handle = GCHandle.Alloc(raw, GCHandleType.Pinned);
            bmp = new Bitmap(width, height, stride, PixelFormat.Format24bppRgb, handle.AddrOfPinnedObject());
        }

        public void SetPixel(int x, int y, Color c)
        {
            int idx = y * stride + x*3;
            raw[idx] = c.B;
            raw[idx+1] = c.G;
            raw[idx+2] = c.R;
        }

        public static implicit operator Bitmap(RawRgbBitmap rbmp)
        {
            return rbmp.bmp;
        }

        public void Dispose()
        {
            bmp.Dispose();
            handle.Free();
        }
    }

Mit den Grundlagen, die wir in den vorherigen Teilen dieser Artikelserie erarbeitet haben, werden wir nun unsere erste 3D Grafik rendern. Zunächst erweitern wir die Klasse Scene um zwei Methoden „AddSphere“ und „AddParallelepiped“, mit denen wir einen Spat (bzw. Quader oder Würfel) und eine Kugel in die Szene einfügen können. Diese Methoden berechnen alle einzelnen Primitive, aus denen der Spat bzw. die Kugel besteht und fügen diese in die Szene ein.

Wir fügen die folgenden Methoden in die Klasse Scene ein:

        public void AddParallelepiped(Vector3D Origin, Vector3D U, Vector3D V, Vector3D W, Color color)
        { // Spat hinzufügen
            Primitives.Add(new Lozenge(Origin, U, V, color));
            Primitives.Add(new Lozenge(Origin, U, W, color));
            Primitives.Add(new Lozenge(Origin, V, W, color));
            Primitives.Add(new Lozenge(Origin + W, U, V, color));
            Primitives.Add(new Lozenge(Origin + V, U, W, color));
            Primitives.Add(new Lozenge(Origin + U, V, W, color));
        }

        public void AddSphere(Vector3D center, double radius, int noOfSteps, Color color)
        {
            double step = Math.PI / noOfSteps;

            for (int bN = 1; bN < noOfSteps; bN++)
            {
                double b = bN * step;
                for (int aN = 0; aN < noOfSteps * 2; aN++)
                {
                    double a = aN * step;

                    Vector3D p1 = new Vector3D(radius * Math.Cos(a) * Math.Sin(b), radius * Math.Cos(b), radius * Math.Sin(a) * Math.Sin(b)) + center;
                    Vector3D p2 = new Vector3D(radius * Math.Cos(a + step) * Math.Sin(b), radius * Math.Cos(b), radius * Math.Sin(a + step) * Math.Sin(b)) + center;
                    Vector3D p3 = new Vector3D(radius * Math.Cos(a) * Math.Sin(b + step), radius * Math.Cos(b+step), radius * Math.Sin(a) * Math.Sin(b + step)) + center;
                    Primitives.Add(new Trapezoid(p1, p2 - p1, p3 - p1, color));
                } 
            }

            for (int aN = 0; aN < noOfSteps * 2; aN++)
            {
                double a = aN * step;
                double b = step;
                Vector3D p1 = new Vector3D(radius * Math.Cos(a) * Math.Sin(b), radius * Math.Cos(b), radius * Math.Sin(a) * Math.Sin(b)) + center;
                Vector3D p2 = new Vector3D(radius * Math.Cos(a + step) * Math.Sin(b), radius * Math.Cos(b), radius * Math.Sin(a + step) * Math.Sin(b)) + center;
                Vector3D p3 = new Vector3D(0,radius,0) + center;
                Primitives.Add(new Trapezoid(p1, p2 - p1, p3 - p1, color));
            }
        }

Wir erstellen nun ein neues Fenster, bzw. eine Form und fügen eine PictureBox mit dem Namen „picture“ ein. Den Quelltext der Form ändern wir wie folgt:

    public partial class Form1 : Form
    {
        Scene scene = new Scene();
        RayTraceCamera cam;
        double camAngle = 0;

        public Form1()
        {
            InitializeComponent();

            // Elemente zur Szene hinzufügen:
            scene.Primitives.Add(new Plane(Vector3D.Zero, Vector3D.eX, Vector3D.eZ, Color.Green)); // Endlos ausgedehnter grüner Boden
            scene.AddParallelepiped(Vector3D.Zero, Vector3D.eX*4, Vector3D.eY*2, Vector3D.eZ*4, Color.Blue); // Blauer Quader
            scene.AddSphere(new Vector3D(-3,2.5,0), 2.5, 6, Color.Red); // Rote Kugel

            camAngle = 2.0; // Der Winkel, aus dem die Kamera auf die Szene schaut (in Radiant).
            Vector3D p = new Vector3D(Math.Cos(camAngle) * 23, 7, Math.Sin(camAngle) * 23); // Position der Kamera aus Winkel berechnen
            cam = new RayTraceCamera(scene, p, new Vector3D(0, 3, 0) - p);
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            cam.ResizeScreen(picture.Width, picture.Height); // Kamera-Screen an PictureBox anpassen
            picture.Image = cam.RenderBitmap(); // Das fertige Bild Rendern und in der PictureBox anzeigen
        }
    }

Beim Start der Applikation wird eine Szene erstellt und ein grüner Plane als Boden eingefügt. Es folgt ein blauer Quader und eine rote Kugel, welche durch viele kleine Primitive angenähert wird. Anschließend wird eine RayTraceCamera erstellt, welche ein Bild der Szene rendert. Nach dem Start der Applikation wird folgendes Bild angezeigt:

Alle Objekte werfen Schatten auf den Boden. Der Schatten der Kugel fällt sogar teilweise auf den Quader. Der Boden ist unendlich ausgedehnt und trifft hinten im Bild auf den Horizont. Die Farbe des Himmels ist die Farbe „Background“ des Scene-Objekts.

Basierend auf dem Plane-Primitiv, welches eine unendlich ausgedehnte Ebene darstellt können wir mit wenig Aufwand weitere ebene Primitive implementieren. Zum Beispiel Rauten, Trapeze und Dreiecke. Alle diese Formen sind eben und stellen damit also nur einen Ausschnitt aus einem Plane-Primitiv dar. Wir können für jede dieser geometrischen Grundformen also eine neue Klasse erstellen, welche von Plane erbt, und überschreiben nur die Methode „RayTrace“. Die neuen „RayTrace“ Methoden werden zu der Methode „RayTrace“ aus der Plane Klasse sehr ähnlich implementiert: Wir berechnen wieder den Schnittpunkt des Rays mit der Ebene, welche von V und W aufgespannt wird. Anschließend prüfen wir jedoch noch zusätzlich, ob der Schnittpunkt auch innerhalb der Form liegt. Ist dies der Fall, geben wir einen PointOnPlane zurück, andernfalls den Wert null.

Das Raute-Primitiv

    public class Lozenge : Plane // Eine Raute, die von V und W aufgespannt wird
    {
        public Lozenge(Vector3D Origin, Vector3D V, Vector3D W, Color color) : base(Origin, V, W, color)
        {
        }

        public override PointOnPrimitive RayTrace(Ray ray)
        {
            double v;
            double w;
            double d;
            if (Vector3D.cramer(V, W, ray.Direction, ray.Start - Origin, out v, out w, out d))
            {
                if (w < 0 || w > 1) return null; // Schnittpunkt außerhalb Raute
                if (v < 0 || v > 1) return null; // Schnittpunkt außerhalb Raute
                if (-d > 0) return new PointOnPlane(v, w, this, -d);
            }
            return null; // Ray und Lozenge schneiden sich nicht
        }
    }

Das Dreieck-Primitiv

    public class Triangle : Plane // Ein Dreieck, das von V und W aufgespannt wird
    {
        public Triangle(Vector3D Origin, Vector3D V, Vector3D W, Color color) : base(Origin, V, W, color)
        {
        }

        public override PointOnPrimitive RayTrace(Ray ray)
        {
            double v;
            double w;
            double d;
            if (Vector3D.cramer(V, W, ray.Direction, ray.Start - Origin, out v, out w, out d))
            {
                if (v < 0 || w < 0 || v + w > 1) return null; // Schittpunkt zur Ebene außerhalb Dreieck
                if (-d > 0) return new PointOnPlane(v, w, this, -d);
            }
            return null; // Ray und Dreieck schneiden sich nicht
        }
    }

Das Trapez-Primitiv

    public class Trapezoid : Plane // Ein Trapez, das von der Grundseite V und einem Schenkel W aufgespannt wird
    {
        public Trapezoid(Vector3D Origin, Vector3D V, Vector3D W, Color color) : base(Origin, V, W, color)
        {
        }

        public override PointOnPrimitive RayTrace(Ray ray)
        {
            double v;
            double w;
            double d;
            if (Vector3D.cramer(V, W, ray.Direction, ray.Start - Origin, out v, out w, out d))
            {
                if (v < 0 || w < 0 || w > 1) return null;
                double bottomMinusTop = 2 * (V.normalize() * W) / V.length();
                double vmax = 1 - w * bottomMinusTop;
                if (v > vmax) return null;
                if (-d > 0) return new PointOnPlane(v, w, this, -d);
            }
            return null; // Ray und Trapez schneiden sich nicht
        }
    }

Weiter

Im ersten Teil dieser Artikelserie haben wir die beiden abstrakten Klassen Primitive und PointOnPrimitive definiert. Ein Primitiv ist allgemein eine elementare geometrische Form, welche vom Raytracer direkt verarbeitet werden kann. Alle komplexeren Formen und Objekte müssen aus mehreren Primitiven zusammengesetzt werden. Schreiben wir nun unsere erste Primitiv-Klasse namens „Plane“, welche von „Primitive“ erbt. Ein Plane ist eine unendlich ausgedehnte Ebene, welche ausgehend von dem Stützpunkt „Origin“ von den beiden Vektoren V und W aufgespannt wird:

public class Plane : Primitive // Eine unendliche Ebene, die von V und W aufgespannt wird
    { 
        protected Vector3D Origin { get; private set; }
        protected Vector3D W { get; private set; } // Vektor in W-Richtung (lokales Koordinatensystem auf der Ebene) [Daumen rechte Hand]
        protected Vector3D V { get; private set; } // Vektor in V-Richtung (lokales Koordinatensystem auf der Ebene) [Mittelfinger rechte Hand]. Entspricht der unteren Kante des TexturBitmap

        protected Vector3D Normal { get; private set; } // Einheitsvektor Senkrecht zu V und W [Zeigefinger Rechte-Hand-Regel]
        protected double CosAlpha { get; private set; } // Cosinus des von V und W eingeschlossenen Winkels.
        protected double Vlength { get; private set; }
        protected double Wlength { get; private set; }

        public Plane(Vector3D Origin, Vector3D V, Vector3D W, Color color) : base(color)
        {
            this.Origin = Origin; this.V = V; this.W = W;
            Normal = V.cross(W).normalize();
            CosAlpha = (V * W) / (V.length() * W.length());
            Vlength = V.length();
            Wlength = W.length();
        }

Dem Konstruktor wird neben den drei Vektoren Origin, V und W auch noch eine Farbe (Color) übergeben. Dies ist die Farbe des Primitivs. Im Konstruktor werdennoch einige Werte berechnet, welche des Öfteren benötigt werden: Der Normalenvektor „Normal“, welcher senkrecht auf der Ebne steht, der Kosinus CosAlpha des zwischen V und W eingeschlossenen Winkels und die Längen der Vektoren V und W.
Bevor wir die Methode „RayTrace“ aus der abstrakten Klasse „Primitive“ in die Klasse „Plane“ implementieren, erstellen wir noch die Klasse „PointOnPlane“, welche eine Implementierung der abstrakten Klasse „PointOnPrimitive“ darstellt. Neben dem Konstruktor gibt es in dieser Klasse noch die Methoden „GetColor“, welche die Farbe des PointOnPrimitive liefert, „GetNormal“, welche den Normalenvektor der Ebene zurück gibt und „GetPrimitive“, welche das Primitiv selbst, auf dem sich der PointOnPrimitive befindet, zurück liefert. Weiterhin können wir einen PoitOnPrimitive mit der Methode ToPointInSpace in XYZ-Koordinaten umwandeln. Die Klassenvariablen v und w sind dabei die Vielfachen der Vektoren V und W der Ebene. Die XYZ-Koordinaten lassen sich also so berechnen: PointInSpace = Origin + V*v + W*w .

        public class PointOnPlane : PointOnPrimitive
        {
            private double v; // in Vielfachen von V.length()
            private double w; // in Vielfachen von W.length()
            private Plane plane;

            public PointOnPlane(double v, double w, Plane plane, double distanceToRayStart) : base(distanceToRayStart)
            {
                this.v = v;
                this.w = w;
                this.plane = plane;
            }

            public override Color GetColor()
            {
                return plane.color;
            }

            public override Vector3D GetNormal()
            {
                return plane.Normal;
            }

            public override Vector3D ToPointInSpace()
            {
                return plane.Origin + (plane.V * v) + (plane.W * w);
            }

            public override Primitive GetPrimitive()
            {
                return plane;
            }
        } // class PointOnPlane

Um den Schnittpunkt einer Ebene mit einem Ray zu ermitteln müssen wir das folgende lineare Gleichungssystem nach den skalaren Variablen v, w und d lösen:
V*v + W*w + rayDirection*d = rayStart – Origin
Die Klasse Vector3D stellt die Methode „cramer“ bereit, welche ein lineares Gleichungssystem mit Hilfe der Cramerschen Regel löst. Wenn das Gleichungssystem lösbar ist, gibt „cramer“ true zurück. Wenn sich der Punkt dann noch vor der Kamera (und nicht dahinter) befindet, erstellt „Raytrace“ einen neuen PointOnPlane als Rückgabewert.

        public override PointOnPrimitive RayTrace(Ray ray)
        {
            double v;
            double w;
            double d;
            if (Vector3D.cramer(V, W, ray.Direction, ray.Start - Origin, out v, out w, out d))
            {
                if (-d > 0) return new PointOnPlane(v, w, this, -d);
            }
            return null; // Ray und Plane sind parallel, oder der Schnittpunkt liegt in negative Richtung
        }

Mit der Methode „RayTrace“ können wir ein Plane-Primitiv also fragen, ob und an welcher Stelle es von einem Ray getroffen wird. Damit ist auch diese Klasse fertig.

Weiter

Im ersten Teil dieser Artikelreihe haben wir das Interface „IRayTraceable“, welches die Schnittstelle der Szene zur RayTraceCamera aus Teil 2 darstellt, definiert. Jedes Objekt, welches „IRayTraceable“ implemetiert, kann von der RayTraceCamera als Szene verwendet werden.

public interface IRayTraceable
{
    Vector3D DirectionToSun { get; set; }
    Color Background { get; set; }
    double MaxLightening { get; set; } // Gültige Werte von 0 (Originalfarbe) bis 1 (jede Farbe wird bis auf Weiss aufgehellt)
    double MaxDarkening { get; set; } // Gültige Werte von 0 (Originalfarbe) bis -1 (jede Farbe wird bis auf Schwarz abgedunkelt)
    PointOnPrimitive RayTrace(Ray ray);
    bool RayTraceHits(Ray ray); // Liefert true, wenn der Ray auf ein beliebiges Primitive trifft.
} 

Wir werden uns nun mit der Klasse „Scene“ beschäftigen, welche eine Implementierung dieses Interfaces darstellt:

    public class Scene : IRayTraceable
    {
        public Color Background { get; set; }
        public Vector3D DirectionToSun { get; set; }
        public double MaxLightening { get; set; } // Gültige Werte von 0 (Originalfarbe) bis 1 (jede Farbe wird bis auf Weiss aufgehellt)
        public double MaxDarkening { get; set; } // Gültige Werte von 0 (Originalfarbe) bis -1 (jede Farbe wird bis auf Schwarz abgedunkelt)

        public List<Primitive>; Primitives = new List<Primitive>();

        public Scene()
        {
            Background = Color.SkyBlue;
            DirectionToSun = new Vector3D(1, 1, 1).normalize();
            MaxLightening = 0.8;
            MaxDarkening = -0.8;
        }
}

Der Konstruktor setzt Standardwerte für alle Properties aus dem Interface. Weiterhin bekommt die Klasse die Liste „Primitives“, in der alle Primitive der Szene abgelegt werden sollen. Nun fehlen noch die Methoden „RayTrace“ und „RayTraceHits“ aus dem Interface. Die Methode „RayTrace“ soll ermitteln ob und auf welches Primitiv ein Ray trifft. Zurückgegeben wird ein PointOnPrimitive. Sollte der Ray auf mehrere Primitive treffen, so wird nur der PointOnPrimitive zurückgegeben, welcher der Kamera am nächsten ist, denn alle dahinterliegenden Primitive sind für die Kamera nicht sichtbar. Es gibt mehrere Möglichkeiten das entsprechende Primitiv zu ermitteln. Leider sind effiziente Algorithmen für diese Aufgabe nicht einfach zu implementieren. Daher wollen wir uns mit diesem sehr einfachen, aber auch sehr langsamen Algorithmus begnügen: Wir überprüfen einfach immer alle Primitive auf Schnittpunkte mit dem Ray. Dies hat den Nachteil, dass auch Primitive aus weit entfernten Bildbereichen immer mit geprüft werden. Zum Beschleunigen des Raytracings gibt es in dieser Funktion ein großes Potential.

        public PointOnPrimitive RayTrace(Ray ray)
        {
            PointOnPrimitive nearestPoint = null;
            foreach (var p in Primitives)
            {
                PointOnPrimitive q = p.RayTrace(ray);
                if (nearestPoint == null || (q != null && q.distanceToRayStart < nearestPoint.distanceToRayStart)) nearestPoint = q;
            }
            return nearestPoint;
        }

Die Methode „RayTraceHits“ soll nur ein true oder false zurück liefern, abhängig davon ob ein beliebiges Primitiv von dem Ray getroffen wird, oder nicht. Wir können sie also ähnlich der Methode „RayTrace“ implementieren, jedoch reicht es, wenn wir die Schleife über alle Primitive abbrechen, sobald wir den ersten Schnittpunkt mit einem Primitiv gefunden haben:

        public bool RayTraceHits(Ray ray)
        {
            foreach (var p in Primitives)
            {
                PointOnPrimitive pop = p.RayTrace(ray);
                if (pop != null) return true; // Schnittpunkt mit Primitiv gefunden
            }
            return false;
        }

Nachdem wir diese beiden Methoden zur Klasse „Scene“ hinzugefügt haben, ist sie einsatzbereit.

Weiter