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 in der Volumenvisualisierung
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]
Raycasting als Verfahren in der Volumenvisualisierung
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-Verfahren
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 als einfaches Raytracing
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]
Filterung
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:
- 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.
Raycasting bei Computerspielen
In der Computerspielentwicklung bezeichnet der Begriff Raycasting das auf einer zweidimensionalen Karte basierte Berechnen einer Pseudo-3D-Ansicht.[4][5] 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. Diese Art des Raycasting findet zum Beispiel im Computerspiel Wolfenstein 3D Anwendung.
Da diese Technik keinem echten 3D entspricht, unterliegt sie diversen Einschränkungen: Es können keine dreidimensionalen Objekte wie Personen und Gegenstände dargestellt werden, Boden und Decke sind immer gleich hoch und Schrägen sind nicht möglich.
Es wurden diverse Umgehungslösungen gefunden, die den Eindruck der Dreidimensionalität herstellen sollen. So werden zweidimensionale Grafiken, so genannte Sprites, für beliebige Objekte verwendet, die skaliert in das berechnete Bild eingefügt werden. Diese wurden bei fortgeschrittenen Spielen wie Duke Nukem 3D winkelabhängig ausgewählt, sodass ein Objekt von vorne anders aussieht als von hinten.
Texturen für Wände, Böden und Himmel wurden eingebaut, die dreidimensionale Strukturen abbilden. Himmel bzw. Decke und Boden wurden für Abschnitte einer Karte abhängig einstellbar gemacht, sodass Treppen, Durchgänge und Ähnliches möglich wurden (so etwa in Doom). Bei Duke Nukem 3D wurden schließlich sogar schräge Böden bzw. Himmel oder Decken ermöglicht und eine vertikale Rotation des Sichtpunkts, sodass man nach oben oder unten schauen konnte. Allerdings verzerrt sich die Darstellung damit stark und unnatürlich. Auch bei den besten Erweiterungen sind keine übereinander liegenden dreidimensionalen Objekte wie Brücken möglich. Darstellungen derselben sind immer mit Hilfe von Sprites oder anderen Tricks „gefälscht“.
Populär wurde das Raycasting durch die frühen Ego-Shooter Catacomb, Wolfenstein 3D, Doom, Heretic und Duke Nukem 3D, da es erheblich weniger Berechnungszeit benötigt als echtes 3D.
Verwandt mit dem Raycasting ist der mit dem Spiel Comanche eingeführte VoxelSpace-Algorithmus zur Visualisierung von Höhenfeldern. Darauf basierende Grafik-Engines werden oft schlicht als Voxel-Engines bezeichnet, obwohl keine Voxel visualisiert werden.
Programmierung
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.[6]
#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;
}
}
Weblinks
- 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
Einzelnachweise
- Frank Sawitzki, Universität Koblenz-Landau: GPU-basiertes Raycasting
- Alan Watt, Mark Watt: Advanced Animation and Rendering Techniques Theory and Practice. Addison-Wesley, Reading 1992, ISBN 0-201-54412-1, S. 305–312.
- James Foley u. a.: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6, S. 701.
- Stefan Becker: Virtuelle Welten mit der Raycasting-Technik darstellen. In: c’t 2/1996, ISSN 0724-8679, S. 246.
- Boris Bertelsons u. a.: PC Underground. Data Becker, Düsseldorf 1995, ISBN 3-8158-1185-6.
- Rosetta Code: Ray-casting algorithm