Raycasting

Raycasting (in englischer Schreibweise meist ray casting) ist ein Begriff aus der Computergrafik. Er bezeichnet Techniken zur schnellen Darstellung (Rendern) einer dreidimensionalen Szene, wird aber inzwischen hauptsächlich im Kontext der Volumenvisualisierung verwendet. Die genaue Definition des Begriffs variiert kontextabhängig.

Raycasting bezeichnet eine Methode, skalare Funktionen in einem dreidimensionalen Volumen, die in vielen wissenschaftlichen Anwendungen auftreten, zu visualisieren. Im medizinischen Bereich sind Beispiele hierfür: Computertomographie (CT), Magnetresonanztomographie (MRT) oder Positronen-Emissions-Tomographie (PET); im Bereich der numerischen Simulation, bei einer Finite-Elemente-Methode (FEM) für Computational Fluid Dynamics (CFD), bei der das Strömungsverhalten von Gasen und Flüssigkeiten berechnet wird. Die hier gewonnenen skalaren Daten, zum Beispiel die Dichte oder Temperatur, können mit verschiedenen Verfahren visualisiert werden, hierzu zählt auch das Raycasting. Hierbei unterscheidet man zwischen direkten und indirekten Verfahren. Indirekte Verfahren visualisieren das Volumen mit Hilfe einer polygonalen Zwischenrepräsentation. Marching Cubes zählt zu diesen indirekten Verfahren. Direkte Verfahren visualisieren das Volumen ohne die Erzeugung solcher Zwischendaten. Zu diesen Verfahren zählen Raycasting und Splatting. Weiter unterscheidet man noch zwischen bildraumorientierten Verfahren (Image-Order) und objektraumorientierten Verfahren (Object-Order).

In der Computergrafik werden dreidimensionale Objekte überwiegend durch Oberflächendarstellungen visualisiert. Diese Visualisierung bieten sich in den Bereichen an, in denen regelmäßige Strukturen auftreten. Diese können dann recht einfach in Form von Polygonen dargestellt werden. Bei Daten mit unregelmäßigen Strukturen z. B. aus numerischen Simulationen oder Scans von dreidimensionalen Volumen ist es schwierig diesen eine eindeutige Oberfläche zuzuordnen, weil die Strukturen fließend ineinander übergehen. Bei einer Oberflächendarstellung würden feine Strukturen verloren gehen. Deshalb geschieht die Visualisierung dieser Daten durch Volume Rendering. Mittlerweile gewinnt diese Volumen Rendering auch bei der Visualisierung von Effekten in Computerspielen immer mehr an Bedeutung. Mit ihnen lassen sich Objekte wie Flüssigkeiten, Gase oder andere Naturphänomene realistisch darstellen.

Im Gegensatz zur Oberflächenvisualisierung bieten diese Verfahren den weiteren Vorteil, mehrschichtige oder transparente Informationen darstellen zu können. Allerdings war bisher durch eine aufwendige Berechnung für das Volume Rendering die Bildwiederholungsrate für eine flüssige Animation zu gering. Deswegen wurden unterschiedliche Verfahren entwickelt, die durch eine Vereinfachung der Berechnungen eine schnelle Darstellung ermöglichten, oder es wurde spezielle und somit auch teure Hardware für die Darstellung eingesetzt. Erst durch die Entwicklung von programmierbaren Grafikprozessoren ist es möglich eine gute Bildqualität in Echtzeit auch kostengünstig umzusetzen.^[1]

Grundlegende Idee ist, wie Volumendaten mit Hilfe des Raycasting-Verfahrens visualisiert werden können. Die theoretische Grundlage ist die Volumen-Rendering-Gleichung, eine Zusammensetzung aus Emission und Absorption. Raycasting löst (approximiert) dieses Problem.^[2]

Raycasting schickt für jedes Pixel des Betrachters (des zu berechnenden Bilds) einen Sehstrahl (Primärstrahlen) durch das Volumen. Der Strahl wird innerhalb des Volumens verfolgt und die Farb- und Opazitätswerte in regelmäßigen Abständen an den Abtastpunkten auf dem Strahl bestimmt. Es wird ebenfalls die Schattierung für die Farbwerte an allen Abtastpunkten berechnet. Der für den Sehstrahl so erhaltene Vektor enthält die geordneten Abtast-Werte (Farb-, Opazitätswerte), wobei die Farbwerte dem Quellterm und die Opazitätswerte dem Extinktionskoeffizienten entsprechen. In einem letzten Schritt, dem Compositing, werden dann die Farb- und Opazitätswerte kombiniert und das aus dem Sehstrahl resultierende Pixel in der Bildebene errechnet.

Raycasting bezeichnet oftmals eine einfache Form des Raytracings, eines bekannten Renderverfahrens.^[3] Die dreidimensionale Szene wird entsprechend festgelegter Vorgaben wie Betrachterstandpunkt und Perspektive regelmäßig abgetastet, sodass eine zweidimensionale Abbildung eines Ausschnitts entsteht. Im Gegensatz zu erweiterten Raytracing-Varianten ist das Abtasten eines Strahls mit dem Aufeinandertreffen von Strahl und Objekt beendet, es findet also lediglich eine Verdeckungsberechnung statt. Die an diesem Schnittpunkt festgestellte Farbe bildet den Bildpunktfarbwert. Spiegelungen, Brechungen und Transmissionen des Objekts werden nicht beachtet. Diese Technik ermöglicht eine sehr schnelle Vorschau auf eine Szene.

Gelegentlich wird Raycasting auch synonym zu Raytracing verwendet.^[3]

Zwei Probleme ergeben sich bei der Rekonstruktion des abgetasteten Volumens, die durch eine Filterung der Daten ausgeglichen werden:

• Nach dem Abtasttheorem benötigt die exakte Rekonstruktion des Signals eine Faltung durch eine Sinusfunktion, die für den eindimensionalen Fall lautet:

sinc ⁡ ( x ) = sin ⁡ ( π ⋅ x ) π ⋅ x {\displaystyle \operatorname {sinc} (x)={\frac {\sin(\pi \cdot x)}{\pi \cdot x}}}

Im dreidimensionalen Fall geschieht die Faltung über ein Tensorprodukt. Es werden die gesamten Abtastpunkte berücksichtigt. Dies ist rechnerisch aufwendig zu lösen.

• Es entstehen Alias-Effekte, falls ein Signal rekonstruiert wird, welches nicht bandlimitiert gewesen ist.

Um das kontinuierliche Signal mittels eines Arrays von Voxel rekonstruieren zu können, wird die Sinc-Faltung durch einen Boxfilter oder Tent-Filter ersetzt. Der Boxfilter interpoliert nach dem Nearest-Neighbor-Verfahren. Dieses erzeugt allerdings Unterbrechungen zwischen Nachbarwerten und eine insgesamt blockartige Erscheinung. Der Tent-Filter interpoliert trilinear. Dadurch erhält man ein gutes Verhältnis zwischen Rechenzeit und Qualität des rekonstruierten Signals.

Wenn ein Strahl von der Kamera auf die Oberfläche geworfen wird, ist alles sichtbar, was der Strahl zuerst trifft und alles dahinter bleibt verdeckt. Beim Raycasting zun Entfernen verdeckter Oberflächen wird für jedes Pixel auf dem Bildschirm geprüft, was der Strahl als Erstes trifft, wenn er von der Kamera ausgeht.

Der Algorithmus läuft in folgenden Schritten ab:

• Für jedes Pixel im Ausgabebild wird ein Strahl konstruiert, der an der Kameraposition beginnt, durch die Position dieses Pixels auf der Bildebene verläuft und dann in die aufgenommene Szene hineinführt.
• Der Strahl wird auf Schnittpunkte mit jedem Objekt in der Szene getestet. Dadurch erhält man eine Liste aller Oberflächen, die der Strahl durchquert, jeweils mit einem Entfernungswert, wie weit entlang des Strahls der Treffer erfolgte.
• Der Schnittpunkt mit dem geringsten Abstand von der Kamera ist die sichtbare Oberfläche. Alles dahinter wird verworfen. Dies ist der entscheidende Schritt, der das Entfernen verdeckter Flächen bewirkt. Weiter entfernte Objekte werden automatisch durch das nächstgelegene Objekt verdeckt.
• Das Pixel wird mit der Farbe, Textur und Beleuchtung an diesem ersten Schnittpunkt schattiert. Die anderen Objekte der Szene tragen nichts zum endgültigen Bild für diesen Strahl bei.

Im Gegensatz zu älteren Techniken muss Raycasting keine Informationen über die Tiefenreihenfolge im Voraus kennen. Es ermittelt die Sichtbarkeit automatisch, indem es einfach den minimalen Schnittpunktabstand ermittelt. Es ist nicht notwendig, Objekte zu sortieren, und es besteht kein Risiko von Sortierfehlern bei überlappenden Polygonen.^[4]

Um die Schatten einer aufgenommenen Szene zu berechnen, kann folgender Algorithmus verwendet werden:

• Die Kamera sendet einen Primärstrahl senkrecht aus. Dieser trifft an einem Punkt P auf eine Oberfläche.
• Von P aus wird ein neuer Strahl in Richtung der Lichtquelle ausgesendet. Dies ist der Schattenstrahl.
• Der Schattenstrahl prüft, ob er mit der gesamten Geometrie der Szene schneidet. Entscheidend ist nur das Vorhandensein eines Schnittpunkts, aber nicht, welcher am nächsten liegt. Befindet sich ein Objekt zwischen P und der Lichtquelle, liegt der Punkt im Schatten.
• Trifft der Schattenstrahl ungehindert auf die Lichtquelle, wird die volle direkte Beleuchtung angewendet. Wird er blockiert, werden die diffusen und gerichteten Lichtanteile der Lichtquelle auf null gesetzt. Es bleibt nur das Umgebungslicht übrig.

Der oben beschriebene Algorithmus erzeugt harte Schatten, d. h. ein Punkt ist entweder vollständig beleuchtet oder vollständig im Schatten. Da liegt daran, dass die Lichtquelle als einzelner Punkt behandelt wird. Reale Lichtquellen haben jedoch eine Fläche. Um weiche Schatten mit einer Halbschattenzone zu simulieren, wird die Lichtquelle an mehreren Positionen auf ihrer Oberfläche abgetastet. Pro Abtastpunkt werden mehrere Schattenstrahlen erzeugt, einer pro Punkt. Der Anteil der Strahlen, die die Lichtquelle ungehindert erreichen, bestimmt, wie stark der Punkt beleuchtet ist. So entsteht ein weicher Übergang von vollständig beleuchtet über die Halbschattenzone bis hin zum tiefen Schatten. Dies ist rechenintensiv. Um die Schattenstrahlen effizient zu verteilen, werden Monte-Carlo-Simulationen verwendet.^[5]

Im zweiten Schritt des Algorithmus tritt ein Problem auf. Der Schattenstrahl beginnt genau am Oberflächenpunkt P, d. h., er schneidet die Oberfläche, die er gerade getroffen hat, sofort und meldet fälschlicherweise, dass der Punkt sich selbst beschattet. Dies erzeugt ein verrauschtes Artefakt, das als Schattenakne bezeichnet wird. Die Lösung besteht darin, den Ursprung des Schattenstrahls leicht entlang der Oberflächennormalen zu verschieben, ihn also vor dem Auslösen minimal von der Oberfläche wegzubewegen. Die Verschiebung ist winzig, aber ihre Genauigkeit ist entscheidend. Ist sie zu klein, bleiben Artefakte bestehen. Ist sie zu groß, verlieren Objekte fälschlicherweise ihre Schatten an Kanten.^[6][7]

In der Computerspielentwicklung bezeichnet der Begriff Raycasting das auf einer zweidimensionalen Karte basierte Berechnen einer Pseudo-3D-Ansicht.^[8][9] Auf Basis der Entfernung zu einem Objekt, den ein „Sichtstrahl“ trifft, wird zum einen die Objektfarbe vertikal zentriert dargestellt und zum anderen der Anteil an Decke oder Boden der entsprechenden Pixel-Spalte berechnet. Im Gegensatz zur normalen Raytracing-Technik wird hier nur eine einzelne Bildzeile abgetastet, um das gesamte Bild zu berechnen; die Verdeckungsberechnung findet also nur in einer Ebene und nicht im Raum statt. Populär wurde das Raycasting durch frühe Ego-Shooter wie Catacomb und Wolfenstein 3D, da es erheblich weniger Berechnungszeit benötigt als polygonales 3D.

Diese Technik unterliegt modernen Verfahren gegenüber diversen Einschränkungen: Es werden keine dreidimensionalen Objekte wie Personen und Gegenstände dargestellt, Boden und Decke sind immer gleich hoch und Schrägen sind nicht möglich. Es wurden diverse Umgehungslösungen gefunden, so werden zweidimensionale Grafiken, auch Sprites genannt, für beliebige Objekte verwendet, die skaliert in das berechnete Bild eingefügt werden. Diese wurden winkelabhängig ausgewählt, sodass ein Objekt von vorne anders aussieht als von hinten.

Verwandt mit dem Raycasting ist der mit dem Spiel Comanche: Operation White Lightning eingeführte Voxel-Space-Algorithmus zur Visualisierung von Höhenfeldern. Darauf basierende Grafik-Engines werden oft schlicht als Voxel-Engines bezeichnet, obwohl keine Voxel visualisiert werden.

Das folgende Beispiel in der Programmiersprache C++ zeigt eine Implementierung des Raycasting-Algorithmus, die prüft, ob Punkte innerhalb von gegebenen geometrischen Figuren liegen. Bei der Ausführung des Programms wird die Funktion main verwendet, die die Ergebnisse auf der Konsole ausgibt.^[10]

#include <iostream>
#include <list>
using namespace std;

struct Point { const double x, y; };

struct Edge
{
    const Point point1, point2;

    bool operator()(const Point& point) const
    {
        if (point1.y > point2.y) return Edge{ point2, point1 }(point);
        if (point.y == point1.y || point.y == point2.y) return operator()({ point.x, point.y + numeric_limits<float>().epsilon() });
        if (point.y > point2.y || point.y < point1.y || point.x > max(point1.x, point2.x)) return false;
        if (point.x < min(point1.x, point2.x)) return true;
        double blue = abs(point1.x - point.x) > numeric_limits<double>::min() ? (point.y - point1.y) / (point.x - point1.x) : numeric_limits<double>::max();
        double red = abs(point1.x - point2.x) > numeric_limits<double>::min() ? (point2.y - point1.y) / (point2.x - point1.x) : numeric_limits<double>::max();
        return blue >= red;
    }
};

struct Figure
{
    const string name;
    const list<Edge> edges;

    bool contains(const Point& point) const
    {
        int c = 0;
        for (Edge edge : edges)
        {
            if (edge(point))
            {
                c++;
            }
        }
        return c % 2 != 0;
    }
};

int main()
{
    const list<Point> points = { { 5.0, 5.0}, {5.0, 8.0}, {-10.0, 5.0}, {0.0, 5.0}, {10.0, 5.0}, {8.0, 5.0}, {10.0, 10.0} };
    const Figure square = { "Quadrat",
        {
            {{0.0, 0.0}, {10.0, 0.0}}, {{10.0, 0.0}, {10.0, 10.0}}, {{10.0, 10.0}, {0.0, 10.0}}, {{0.0, 10.0}, {0.0, 0.0}}
        }
    };
    const Figure square_hole = { "Quadrat mit Loch",
        {
            {{0.0, 0.0}, {10.0, 0.0}}, {{10.0, 0.0}, {10.0, 10.0}}, {{10.0, 10.0}, {0.0, 10.0}}, {{0.0, 10.0}, {0.0, 0.0}},
                {{2.5, 2.5}, {7.5, 2.5}}, {{7.5, 2.5}, {7.5, 7.5}}, {{7.5, 7.5}, {2.5, 7.5}}, {{2.5, 7.5}, {2.5, 2.5}}
        }
    };
    const Figure strange = { "Strange",
        {
            {{0.0, 0.0}, {2.5, 2.5}}, {{2.5, 2.5}, {0.0, 10.0}}, {{0.0, 10.0}, {2.5, 7.5}}, {{2.5, 7.5}, {7.5, 7.5}},
                {{7.5, 7.5}, {10.0, 10.0}}, {{10.0, 10.0}, {10.0, 0.0}}, {{10.0, 0}, {2.5, 2.5}}
        }
    };
    const Figure exagon = { "Exagon",
        {
            {{3.0, 0.0}, {7.0, 0.0}}, {{7.0, 0.0}, {10.0, 5.0}}, {{10.0, 5.0}, {7.0, 10.0}}, {{7.0, 10.0}, {3.0, 10.0}},
                {{3.0, 10.0}, {0.0, 5.0}}, {{0.0, 5.0}, {3.0, 0.0}}
        }
    };
    for (Figure figure : { square, square_hole, strange, exagon })
    {
        cout << "Liegt der Punkt der innerhalb vom " << figure.name << '?' << endl;
        for (Point point : points)
        {
            cout << "(" << point.x << ", " << point.y << "): " << boolalpha << figure.contains(point) << endl;
        }
        cout << endl;
    }
}

Wikibooks: Spielewelten mit Raycasting – Lern- und Lehrmaterialien

• Raycasting-Tutorial von F. Permadi (englisch)
• Interaktiver Raycaster für MSDOS in 64 Bytes (mit Quellcode)
• Matthias Teschner, Albert-Ludwigs-Universität Freiburg: Computer Graphics Ray Casting

1. ↑ Frank Sawitzki, Universität Koblenz-Landau: GPU-basiertes Raycasting
2. ↑ Alan Watt, Mark Watt: Advanced Animation and Rendering Techniques Theory and Practice. Addison-Wesley, Reading 1992, ISBN 0-201-54412-1, S. 305–312.
3. ↑ ^{a b} James Foley u. a.: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6, S. 701.
4. ↑ Scribd, Inc.: Hidden Surface Removal Techniques
5. ↑ Stanford University: State of the Art in Monte Carlo Ray Tracing for Realistic Image Synthesis
6. ↑ Stanford University: Multiple Importance Sampling
7. ↑ Stanford University: Bidirectional Path Tracing
8. ↑ Stefan Becker: Virtuelle Welten mit der Raycasting-Technik darstellen. In: c’t 2/1996, ISSN 0724-8679, S. 246.
9. ↑ Boris Bertelsons u. a.: PC Underground. Data Becker, Düsseldorf 1995, ISBN 3-8158-1185-6.
10. ↑ Rosetta Code: Ray-casting algorithm