imported>Maximum 2520: /* Anwendungen / / Berechnen von Schatten */ hinzugefügt

2026-03-14T14:28:06Z

Anwendungen: Berechnen von Schatten: hinzugefügt

Neue Seite

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

== Raycasting in der Volumenvisualisierung ==
Raycasting bezeichnet eine Methode, skalare Funktionen in einem [[Voxel|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 [[Dreidimensional|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 [[Polygon]]en 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|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|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 [[Grafikprozessor]]en ist es möglich eine gute Bildqualität in Echtzeit auch kostengünstig umzusetzen.<ref>Frank Sawitzki, Universität Koblenz-Landau: [https://www.uni-koblenz.de/~cg/Studienarbeiten/SA_Sawitzki.pdf GPU-basiertes Raycasting]</ref>

== 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 [[Spontane Emission|Emission]] und [[Absorption (Physik)|Absorption]]. Raycasting löst ([[Approximation|approximiert]]) dieses Problem.<ref name="Watt">Alan Watt, Mark Watt: ''Advanced Animation and Rendering Techniques Theory and Practice.'' Addison-Wesley, Reading 1992, ISBN 0-201-54412-1, S. 305–312.</ref>
[[Datei:High Definition Volume Rendering.JPG|mini|Schädel, visualisiert aus einem Voxeldatensatz unter Verwendung von Raycasting]]

=== 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ät]]swerte in regelmäßigen Abständen an den Abtastpunkten auf dem Strahl bestimmt. Es wird ebenfalls die [[Shading|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#Volumengrafik|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 [[Raytracing]]s, eines bekannten Renderverfahrens.<ref name="foley">James Foley u. a.: ''Computer Graphics: Principles and Practice.'' Addison-Wesley, Reading 1995, ISBN 0-201-84840-6, S. 701.</ref> 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 [[Sichtbarkeitsproblem|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.<ref name="foley" />

== Filterung ==
Zwei Probleme ergeben sich bei der Rekonstruktion des abgetasteten [[Volumen]]s, die durch eine Filterung der Daten ausgeglichen werden:
* Nach dem [[Abtasttheorem]] benötigt die exakte Rekonstruktion des Signals eine [[Faltung (Mathematik)|Faltung]] durch eine [[Sinusfunktion]], die für den [[Eindimensional|eindimensionalen]] Fall lautet:
::<math>\operatorname{sinc}(x) = \frac{\sin(\pi \cdot x)}{\pi \cdot x}</math>
:Im [[Dreidimensional|dreidimensionalen]] Fall geschieht die [[Faltung (Mathematik)|Faltung]] über ein [[Tensorprodukt]]. Es werden die gesamten Abtastpunkte berücksichtigt. Dies ist rechnerisch aufwendig zu lösen.
* Es entstehen [[Alias-Effekt]]e, 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-Funktion|Sinc]]-Faltung durch einen [[Boxfilter]] oder Tent-Filter ersetzt. Der Boxfilter interpoliert nach dem [[Nearest-Neighbor-Heuristik|Nearest-Neighbor]]-Verfahren. Dieses erzeugt allerdings Unterbrechungen zwischen Nachbarwerten und eine insgesamt blockartige Erscheinung. Der Tent-Filter [[Interpolation (Mathematik)|interpoliert]] trilinear. Dadurch erhält man ein gutes Verhältnis zwischen [[Rechenzeit]] und Qualität des rekonstruierten Signals.

== Anwendungen ==

=== Entfernen verdeckter Flächen ===
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 [[Schnittpunkt|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 [[Polygon|Polygonen]].<ref>Scribd, Inc.: [https://www.scribd.com/document/215655380/Hidden-Surface-Removal-Techniques ''Hidden Surface Removal Techniques'']</ref>

=== Berechnen von Schatten ===
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-Simulation|Monte-Carlo-Simulationen]] verwendet.<ref>[[Stanford University]]: [https://graphics.stanford.edu/courses/cs348b-03/papers/mc-course.pdf ''State of the Art in Monte Carlo Ray Tracing for Realistic Image Synthesis'']</ref>

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 (Computergrafik)|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.<ref>[[Stanford University]]: [https://graphics.stanford.edu/courses/cs348b-03/papers/veach-chapter9.pdf ''Multiple Importance Sampling'']</ref><ref>[[Stanford University]]: [https://graphics.stanford.edu/courses/cs348b-03/papers/veach-chapter10.pdf ''Bidirectional Path Tracing'']</ref>

== Raycasting bei Computerspielen ==
[[Datei:Raycasting.svg|mini|Raycasting in Computerspielen: Abtasten einer zweidimensionalen Karte mit regelmäßigen Strahlen]]
In der [[Computerspiel]]entwicklung bezeichnet der Begriff ''Raycasting'' das auf einer zweidimensionalen Karte basierte Berechnen einer Pseudo-3D-Ansicht.<ref>Stefan Becker: ''Virtuelle Welten mit der Raycasting-Technik darstellen.'' In: ''[[c’t]]'' 2/1996, {{ISSN|0724-8679}}, S. 246.</ref><ref>Boris Bertelsons u. a.: ''PC Underground.'' Data Becker, Düsseldorf 1995, ISBN 3-8158-1185-6.</ref> 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 [[Sichtbarkeitsproblem|Verdeckungsberechnung]] findet also nur in einer Ebene und nicht im Raum statt. Populär wurde das Raycasting durch frühe [[Ego-Shooter]] wie [[Catacomb (Computerspiel)|Catacomb]] und Wolfenstein 3D, da es erheblich weniger Berechnungszeit benötigt als [[Polygon|polygonales]] 3D.

[[Datei:Raycasting2.png|mini|Entsprechend der oberen Grafik wird die Bildpunktfarbe festgestellt (oberer „Streifen“) und entsprechend der Entfernung wird ein vertikaler Bereich in dieser Farbe gezeichnet. Alle übrigen Bereiche sind Himmel bzw. Decke oder Boden.]]
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 [[Sprite (Computergrafik)|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|Voxel-Space]]-Algorithmus zur Visualisierung von [[Höhenfeld]]ern. Darauf basierende [[Grafik-Engine]]s 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 (Mathematik)|Funktion]] ''main'' verwendet, die die Ergebnisse auf der Konsole ausgibt.<ref>Rosetta Code: [https://rosettacode.org/wiki/Ray-casting_algorithm Ray-casting algorithm]</ref><syntaxhighlight lang="c#">
#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;
}
}
</syntaxhighlight>

== Weblinks ==
{{Wikibooks|Spielewelten mit Raycasting}}
* [https://permadi.com/1996/05/ray-casting-tutorial-table-of-contents/ Raycasting-Tutorial von F. Permadi] (englisch)
* [https://www.pouet.net/prod.php?which=78044 Interaktiver Raycaster für MSDOS in 64 Bytes (mit Quellcode)]
* Matthias Teschner, Albert-Ludwigs-Universität Freiburg: [https://cg.informatik.uni-freiburg.de/course_notes/graphics_01_raycasting.pdf Computer Graphics Ray Casting]

== Einzelnachweise ==
<references />

[[Kategorie:Bildsynthese]]
[[Kategorie:Algorithmus (Computergrafik)]]

Raycasting - Versionsgeschichte

imported>Maximum 2520: /* Anwendungen */ /* Berechnen von Schatten */ hinzugefügt

imported>Maximum 2520: /* Anwendungen / / Berechnen von Schatten */ hinzugefügt