# Radiosity (Computergrafik)

Radiosity bzw. Radiosität ist ein Verfahren zur Berechnung der Verteilung von Wärme- oder Lichtstrahlung innerhalb eines virtuellen Modells. In der Bildsynthese ist Radiosity neben auf Raytracing basierenden Algorithmen eines der beiden wichtigen Verfahren zur Berechnung des Lichteinfalls innerhalb einer Szene. Es beruht auf dem Energieerhaltungssatz: Alles Licht, das auf eine Fläche fällt und von dieser nicht absorbiert wird, wird von ihr zurückgeworfen. Außerdem kann eine Fläche auch selbstleuchtend sein.
Das Radiosity-Verfahren basiert auf der Annahme, dass alle Oberflächen ideal diffuse Reflektoren bzw. alle Lichtquellen ideal diffuse Strahler sind. Ideal diffus bedeutet dabei, dass Licht in alle Richtungen gleichmäßig reflektiert bzw. abgestrahlt wird.
Im Gegensatz zu Raytracing ist Radiosity nicht vom Blickpunkt abhängig; die Beleuchtung der Flächen wird also für die gesamte Szene unabhängig von der Position des Betrachters berechnet. Die blickpunktabhängige Verdeckungsberechnung hat in einem unabhängigen Schritt zu erfolgen.

## Eigenschaften
### Vorteile
#### Blickpunktunabhängigkeit

    Ein Vorteil des Radiosity-Verfahrens ist, dass die Berechnung vom Standort und Blickwinkel des Betrachters unabhängig erfolgt. Die Lichtverteilung muss so für eine Szene nur einmal berechnet werden. Danach kann die Szene in Echtzeit gerendert werden (meist mittels Scanline-Algorithmen oder Z-Buffering), was für Anwendungen wie virtuelle Architekturmodelle interessant ist. Diesen Vorteil haben jedoch nicht alle Programme.

#### Einfache indirekte, ideal diffuse Lichtreflexion

    Ideal diffuse Lichtreflexionen werden vom Radiosity-Verfahren auf natürliche Weise unterstützt. Die Helligkeit und Farbe einer Fläche werden nicht allein aufgrund der direkten Beleuchtung einer Lichtquelle, sondern auch durch diffus reflektiertes Licht anderer Flächen bestimmt. Ein Beispiel dafür ist ein Zimmer, das durch einfallendes Sonnenlicht nicht nur an den direkt beschienenen Stellen, sondern auch insgesamt heller wird.

### Nachteile
#### Keine analytischen Primitiven

    Durch die zwingende Aufteilung der Szene in Polygone können keine analytisch definierten Primitiven, wie die bei Raytracing üblichen Kugeln, verwendet werden. Durch die zur Vermeidung von sichtbaren Kanten notwendige feine Aufteilung ist bei komplexer Szenengeometrie rasch eine sehr hohe Zahl von Flächen notwendig. Dies führt häufig zu einer hohen Wartezeit bei der Berechnung der Formfaktoren (siehe weiter unten).
    Es wurde versucht, mittels adaptativer Vereinfachung der Geometrie dieses Problem teilweise zu lösen, was jedoch ein manueller Vorgang ist, der seine Grenzen hat. Daneben sind die aus den Fehlern dieses Verfahrens resultierenden Auswirkungen auf die Lichtberechnung schwer vorhersehbar.

#### Hoher Speicher- und Zeitbedarf

    Wenn $N$ die Anzahl der Primitiven einer Szene ist, so weisen die effizientesten Radiosity-Varianten eine asymptotische Zeitkomplexität von $O(N\log N)$ auf, wie empirisch festgestellt wurde. Dagegen benötigt Raytracing nur eine Laufzeit von $O(\log N)$. Dies begrenzt schnell den praktisch möglichen Verfeinerungsgrad bei Radiosity. Daneben ergeben sich zur Berechnung und Speicherung der Formfaktoren relativ hohe Speicheranforderungen.

#### Globale Beleuchtung schwer realisierbar

    Für die möglichst realistische Darstellung einer Szene muss die globale Beleuchtung simuliert werden, was aber nur in Spezialfällen mit Radiosity effizient möglich ist. In seiner Grundform ist Radiosity nur zur Simulation ideal diffuser Reflexion fähig. Die Berücksichtigung beliebiger Beleuchtungsmodelle sowie transluzenter Flächen ist möglich, hat jedoch keine breite Verwendung gefunden, da derartige Effekte schneller bzw. präziser mittels auf Raytracing basierter Lösungen möglich sind.

### Vergleich mit Raytracing

Historisch gesehen war Radiosity interessant, da es die Simulation indirekter diffuser Beleuchtung auf einfache Weise erlaubte, was mit Raytracing lange Zeit nicht möglich war. Andererseits war Raytracing gut für spiegelnde und transparente Objekte geeignet, wozu wiederum Radiosity nicht fähig war. Es wurden daher anfangs Vorschläge zur Kombination von Radiosity mit Raytracing gemacht, die jedoch aufwendig waren und sich letztendlich nicht im großen Maße durchsetzen konnten.
Mit dem Aufkommen moderner globaler Beleuchtungsverfahren wie Path Tracing und Photon Mapping wurden jedoch die Möglichkeiten von Raytracing beträchtlich erweitert. Weil derartige Algorithmen alle von Radiosity unterstützten Effekte mit weniger Fehlern und auf elegantere Weise simulieren können, ist Radiosity im Bereich der hochwertigen realistischen Bildsynthese weitgehend aus der Mode gekommen. Kommerzielle Verwendung findet Radiosity vor allem beim Rendern von Architekturmodellen, bei denen eine zeitaufwendige Vorausberechnung vertretbar ist. Auch derartige Anwendungen sind jedoch mit Raytracing-basierten Verfahren (Particle Tracing) möglich.
Weitere Anwendung finden Radiosity-Verfahren in den Bereichen der Klima- bzw. Wärmeforschung, da Wärmeverteilung eher diffus als gerichtet geschieht und Radiosity hier praktikabler als strahlenbasierte Ansätze ist.

## Prinzip

Mit der eingangs formulierten Annahme kann die allgemeine Rendergleichung in die Radiosity-Gleichung überführt werden.
    $B(x)=E(x)+\rho (x)\int _{x'\in S}B(x'){\frac {1}{\pi r^{2}}}\cos \phi _{x}\cos \phi _{x'}\cdot V(x,x')\,\mathrm {d} x'$
mit
    B(x) = gesamte vom Punkt x abgestrahlte Energie (Summe aus Eigenstrahlung und Reflexion als Leistung pro Flächeneinheit), genannt Radiosity im Punkt x
    E(x) = im Punkt x abgegebene Eigenstrahlung
    ρ(x) = Reflexionsfaktor im Punkt x
    S = alle Oberflächen der Szene
    r = Abstand der Punkte x und x'
    $\phi (x)$ = Der Winkel zwischen der Normale im Punkt x und der Verbindungslinie zwischen den Punkten x und x'
    $V(x,x')={\begin{cases}1,&{\mbox{wenn }}x{\mbox{ von }}x'{\mbox{ aus sichtbar}}\\0,&{\mbox{sonst}}\end{cases}}$.
Die gesuchte Radiosity im Punkt x ergibt sich aus einem Integral in geschlossener Form, was auf direktem Weg nicht berechnet werden kann. Abhilfe schafft die Diskretisierung der Oberfläche S: anstatt alle infinitesimal kleinen Teilflächen δA' zu betrachten, teilt man die Oberfläche S in zusammenhängende Teilflächen (Facetten oder Patches genannt) A$_i$ auf (Finite-Elemente-Methode). Für diese Teilflächen gelten weitere Annahmen: jedes A$_i$ ist planar; die jeweilige Radiosity B$_i$ und der Reflexionsfaktor ρ$_i$ sind über A$_i$ konstant. Dies führt dann zur diskreten Radiosity-Gleichung.
    $B_{i}=E_{i}+\rho _{i}\sum _{j=1}^{n}B_{j}F_{ij},\quad 1\leq i\leq n$
mit
    B$_i$ = gesamte von Teilfläche i abgestrahlte Energie (Summe aus Eigenstrahlung und Reflexion als Leistung pro Flächeneinheit), genannt Radiosity der Teilfläche i
    E$_i$ = von der Teilfläche i abgegebene Eigenstrahlung
    ρ$_i$ = Reflexionsfaktor der Teilfläche i
    n = Anzahl der Teilflächen
    F$_{ij}$ = Anteil an der von Fläche j abgegebenen Energie, die auf Fläche i auftrifft, genannt Formfaktor.
Die Radiosity $B_{i}$ von Teilfläche $i$ ist also gleich der Eigenstrahlung $E_{i}$ der Teilfläche $i$ plus der mit dem diffusen Reflexionsfaktor $p_{i}$ gewichteten Summe der Radiosity $B_{j}$ von allen anderen Teilflächen $j$. Wobei hierbei der Formfaktor $F_{i,j}$, welcher den Anteil an der von Fläche j abgegebenen Energie die auf Fläche i auftrifft festlegt, eingeht. Der Formfaktor berücksichtigt also die Ausrichtung und den Abstand der Teilflächen $i,j$ zueinander. Da man dies für alle Teilflächen $i$ berechnen muss, ergibt sich ein lineares Gleichungssystem mit so vielen Gleichungen und Unbekannten wie es Teilflächen gibt.

### 1. Unterteilung der Oberflächen

Im ersten Schritt erfolgt die Festlegung der Primitiven: Wie und in welche Teilflächen soll eine gegebene kontinuierliche Oberfläche zerlegt werden? Üblich sind Dreieck und Quadrat. Bereits in dieser Phase wird zwischen Qualität und Effizienz entschieden. Je feinmaschiger das Netz, desto genauer sind die Ergebnisse, aber umso aufwendiger die Berechnungen.
In der Praxis benutzt man meist adaptive Verfahren. Ausgehend von einer z. B. triangulierten Oberfläche, werden nach dem hier angegebenen Schema die zugehörigen Radiosity-Werte aller Facetten bestimmt. Mit diesen Daten erfolgen dann weitere ortsabhängige Netzverfeinerungen. Ausschlaggebend dafür können sein: ein hoher Radiosity-Gradient benachbarter Facetten, Diskontinuitäten im Lichtverlauf (z. B. Lichtfleck) oder eine örtlich ungünstige Netzeinteilung (z. B. T-Knoten).

### 2. Festlegung der Basisfunktionen

Die diskrete Radiosity-Gleichung stellt eine Möglichkeit der Diskretisierung dar. Sie beruht auf der Annahme, dass die Radiosity über einer gegebenen Facette konstant ist, und verwendet daher konstante Basisfunktionen. Die Wahl von Basisfunktionen höheren Grads ist ebenfalls insbesondere mit dem Galerkin-Ansatz möglich.

### 3. Berechnung der Formfaktoren

Der aufwendigste Schritt bei Radiosity ist, unabhängig von dem gewählten Algorithmus, die Berechnung der Formfaktoren. Ein Formfaktor gilt immer zwischen zwei Patches und beschreibt die Menge der ausgetauschten Strahlung, liegt also zwischen null (keine Strahlung wird ausgetauscht) und eins (alle Strahlung wird ausgetauscht).
Der Formfaktor ist rein geometrischer Natur und wird durch die Stellung der Patches zueinander bestimmt. Außerdem spielt die Sichtbarkeit der Patches eine Rolle. Die Sichtbarkeitsberechnung braucht bei weitem die meiste Zeit in der Berechnung.
Die Formel für einen Formfaktor lautet:
    $F_{s,e}={\frac {1}{A_{s}}}\int _{v\in A_{e}}\int _{u\in A_{s}}{\frac {1}{\pi r^{2}}}\cos \phi _{u}\cos \phi _{v}V(u,v)\,\mathrm {d} A_{s}\mathrm {d} A_{e}$
mit
    $F_{s,e}$ = Formfaktor zwischen dem Sender $S$ und dem Empfänger $E$
    $A_{s}$ = Der Fläche des Senders $S$
    $A_{e}$ = Der Fläche des Empfängers $E$
    $\phi _{u}$ = Der Winkel zwischen der Normale des Senders $S$ und der Verbindungslinie zwischen Sender $S$ und Empfänger $E$
    $\phi _{v}$ = Der Winkel zwischen der Normale des Empfängers $E$ und der Verbindungslinie zwischen Empfänger $E$ und Sender $S$
    $r$ = Entfernung zwischen Sender $S$ und Empfänger $E$
    $V(u,v)={\begin{cases}1,&{\mbox{wenn }}u{\mbox{ von }}v{\mbox{ aus sichtbar}}\\0,&{\mbox{sonst}}\end{cases}}$
Da das direkte Berechnen dieses Doppelintegrals sehr schwierig ist, werden im Allgemeinen Annäherungen verwendet.
Das simpelste Verfahren ist nur für Flächen korrekt, die relativ klein und relativ weit entfernt sind und zwischen denen keine partielle Verdeckung besteht. Man berechnet dabei Winkel und Entfernung nur zwischen zwei repräsentativen Punkten, den Mittelpunkten der beiden Flächen.
    $F_{s,e}\approx A_{e}{\frac {\cos \phi _{u}\cos \phi _{v}d_{u,v}}{\pi r^{2}}}$
Wobei $u$ der Mittelpunkt von $A_{s}$ und $v$ der Mittelpunkt von $A_{e}$ ist.

#### Methode nach Nusselt

(auch „Nusselts Analogon“)
Es wird ein repräsentativer Punkt der Empfängerfläche, der Mittelpunkt, ausgewählt. Die sichtbaren Teile der Senderfläche werden auf die Einheitshalbkugel um diesen Punkt projiziert. Dadurch wird ${\frac {\cos \phi _{v}}{r^{2}}}$ beachtet. Dann wird die Projektion auf der Einheitskugel wiederum in die Fläche, in der $A_{j}$ liegt, projiziert. Die entstandene Fläche wird durch $\pi$ geteilt (Fläche des Einheitskreises). Durch diesen Schritt wird der Formfaktor $F_{s,e}\approx \int _{v\in A_{e}}{\frac {\cos \phi _{u}\cos \phi _{v}d_{u,v}}{\pi r^{2}}}\,\mathrm {d} A_{e}$ ermittelt.

#### Hemi-Cube-Verfahren

Von Cohen et al. stammt das sogenannte Hemi-Cube-Verfahren. Die Einheitshalbkugel nach Nusselt wird durch einen Einheitshalbwürfel approximiert, dessen Seitenflächen in ein diskretes Gitter unterteilt sind. Jeder Gitterfläche wird ein Gewichtungsfaktor, der Delta-Formfaktor, zugeordnet, welcher von der Position der Gitterfläche abhängig ist. Ein Delta-Formfaktor ist damit der Formfaktor der Gitterfläche nach Nusselt. Die Summe der Delta-Formfaktoren ist 1.
Für jede der fünf Halbwürfelflächen wird mit modifizierten Rasteralgorithmen (üblicherweise Z-Buffer) ein Item-Buffer berechnet. Dieser enthält für jede Gitterfläche die Identität der Objektfläche (Item, rotes Dreieck im Bild), die darauf projiziert wurde. Für jedes Item wird die Summe der Delta-Formfaktoren der überdeckten Gitterflächen berechnet (rote Gitterflächen im Bild). Diese Summe wird als Formfaktor zwischen Item und betrachteter Fläche aufgefasst.

#### Sillions Verbesserung

Statt eines Halbwürfels wird nun nur noch eine einzige Fläche verwendet, welche zentriert über dem differentiell kleinen Flächenstück (dA) platziert wird. Diese Fläche wird ebenfalls in kleine, diskrete Bereiche aufgeteilt. Diesen werden dann genau wie beim Hemicube-Verfahren in Abhängigkeit von der Geometrie zu dA, den sogenannten Delta-Formfaktoren zugeordnet. Der Vorteil bei diesem Verfahren ist, dass ein Patch nur auf diese eine Fläche projiziert werden muss und nicht mehr auf fünf Flächen eines Würfels. Außerdem ist dieses Verfahren legitim, da Patches, die orthogonal auf der Fläche von dA stehen, keinen großen Beitrag an der Gesamthelligkeit haben. Diese Beobachtung kann man sich über den Cosinus zwischen den Normalen der beiden Flächenstücke klarmachen.

### 4. Berechnung der Radiosity-Werte

Die diskrete Radiosity-Gleichung kann als lineares Gleichungssystem aufgefasst werden und lässt sich demzufolge nach einigen Umformschritten wie folgt in Matrixform darstellen.
    ${\begin{pmatrix}B_{1}\\B_{2}\\\vdots \\B_{n}\end{pmatrix}}={\begin{pmatrix}E_{1}\\E_{2}\\\vdots \\E_{n}\end{pmatrix}}+{\begin{pmatrix}\rho _{1}F_{11}&\rho _{1}F_{12}&\ldots &\rho _{1}F_{1n}\\\rho _{2}F_{21}&\rho _{2}F_{22}&\ldots &\rho _{2}F_{2n}\\\vdots &\vdots &\ddots &\vdots \\\rho _{n}F_{n1}&\rho _{n}F_{n2}&\ldots &\rho _{n}F_{nn}\end{pmatrix}}\cdot {\begin{pmatrix}B_{1}\\B_{2}\\\vdots \\B_{n}\end{pmatrix}}$ oder kurz B = E+T•B.
Um alle gesuchten Radiosity-Werte zu bestimmen, muss das Gleichungssystem gelöst werden. Naheliegend ist die Invertierung der Matrix (I-T) (Matrix-Inversion nach Gauß), was aber aufgrund des enormen Aufwands unpraktikabel ist.
Im Allgemeinen existieren zwei unterschiedliche iterative Lösungsstrategien, die gegen die exakte Lösung konvergieren. Damit ist ein frei wählbarer Kompromiss zwischen Darstellungsqualität und Rechenzeit möglich.
* Beim Gathering wird die Radiosity B$_i$ einer Facette durch Einsammeln aller einflussnehmenden B$_j$ (abhängig vom jeweiligen Formfaktor) gebildet. Ausgangspunkt ist B$^0$=E und man sieht nur die selbstleuchtenden Flächen. Nach dem ersten Schritt B$^1$=E+T•B$^0$ sind zusätzlich alle direkt beleuchteten Objekte sichtbar. Im nächsten Iterationsschritt B$^2$=E+T•B$^1$ werden die einfachen Reflexionen berücksichtigt usw. Auffällig ist, dass in jedem Schritt alle Formfaktoren benötigt werden. Auf diesem Prinzip beruhende Verfahren sind Jacobi-Iteration und Gauß-Seidel-Iteration.
* Beim Shooting wird die unverteilte Radiosity B$_i$ auf alle als Empfänger in Frage kommenden Facetten (abhängig vom jeweiligen Formfaktor) geschossen. Ausgangspunkt sind wiederum die selbstleuchtenden Flächen, somit gilt B=E.
    Als Abbruchkriterien können neben objektiven Werten wie Fehlermetriken auch der subjektive Eindruck benutzt werden. Shooting-Verfahren sind den Gathering-Verfahren in zwei Gesichtspunkten überlegen. Zum einen kann aus dem Pseudocode abgeleitet werden, dass für jeden Iterationsschritt lediglich j Formfaktoren benötigt werden. Zum anderen wird in jedem Durchlauf die Radiosity der Facette mit der größten Restenergie verteilt, wodurch Shooting-Verfahren wesentlich schneller gegen „schöne“ Bilder konvergieren als Gathering-Verfahren. Auf diesem Prinzip beruhende Algorithmen sind Southwell-Iteration und Progressive-Refinement.

### 5. Rendern

Den letzten Schritt bildet das Rendern des fertigen Bildes. Die an den ausgesuchten Stellen berechneten Radiosity-Werte werden gemäß den gewählten Basisfunktionen kombiniert. Wurden Radiosity-Werte in den Netzknoten bestimmt ist z. B. auch Gouraud Shading möglich. Genügt das so erstellte Bild dem Anspruch nicht, so können weitere Iterationen aus (4) folgen. Treten ungewollte grafische Artefakte auf, so sollte mit entsprechenden Änderungen in der Netzstruktur der Algorithmus von vorn gestartet werden.

## Geschichtliche Entwicklung

1984 wurde das Verfahren erstmals von Goral et al. vorgestellt. Es stammt aus der Thermodynamik, wo es verwendet wurde, um den Austausch von Wärmestrahlung zu berechnen (Strahlungsrechnung). Zu dieser Zeit wurde die Full-Form-Factor-Matrix-Methode zum Lösen des Gleichungssystems verwendet. Hier wird das Gleichungssystem für alle Formfaktoren zwischen allen Patches (=Flächen) der Welt aufgestellt und dann mittels eines mathematischen Verfahrens (meist dem Gauß-Seidel-Verfahren) gelöst. Prinzipiell entspricht dieses Vorgehen dem Einsammeln von Radiosity. Für jedes Patch wird berechnet, wie viel Licht es von jedem anderen Patch erhält. Das hat den Nachteil, dass die Berechnung der gesamten Matrix extrem viel Zeit benötigt und viel Speicherplatz belegt, was das Verfahren für komplexe Szenen unbrauchbar macht.
1988 wurde dann das Progressive-Refinement-Verfahren von Cohen et al. vorgestellt. Hier wird der Prozess umgedreht, und das Licht wird nicht mehr an jedem Patch eingesammelt, sondern von jedem Patch verschossen. So kann man zuerst einmal das Licht von den Patches mit dem größten Radiositywert versenden und sich dann denen mit wenig Radiosity zuwenden. Hier ist es nicht mehr nötig, die gesamte Matrix zu berechnen, sondern es werden in jedem Schritt nur noch die Formfaktoren von einem einzelnen Patch zu allen anderen benötigt. Dadurch sinkt der benötigte Speicherplatz enorm, und man erhält nach jedem Schritt ein brauchbares Bild. Je länger man wartet, desto besser wird das Bild, da immer mehr Indirektionen berechnet werden. Um zu konvergieren, braucht dieses Verfahren allerdings genauso lange wie die Full-Form-Factor-Matrix-Methode.
Im Prinzip entspricht das Verfahren einer Reihenentwicklung der Matrix. Das Lineare Gleichungssystem, das sich aus der Strahlungsgleichung ergibt ist dann $(I-M)B=E$, wobei $I$ die Einheitsmatrix, $M$ die Matrix, bestehend aus den Formfaktoren und den Reflexionskoeffizienten und $E$ die Eigenstrahlung beschreibt. Stellt man die Gleichung nun um zu $B=(I-M)^{-1}E$, so lässt sich der rechte Teil $(I-M)^{-1}$ als Reihe der folgenden Form entwickeln, und man erhält eine inkrementelle Annäherung an die tatsächliche Strahlungsintensität:
    $\sum _{i=1}^{\infty }x^{i}={\frac {1}{1-x}}=(1-x)^{-1}$.
1991 wurde von Hanrahan et al. das Hierarchische Radiosity vorgestellt. Bei diesem Verfahren wird eine Patchhierarchie verwendet. Wenige große Patches bestehen aus vielen kleinen. Der Lichtaustausch wird jetzt auf unterschiedlichen Stufen vorgenommen. Wenn der Fehler gering ist, wird das Licht auf einer hohen Hierarchieebene ausgetauscht, wenn ein großer Fehler zu erwarten ist (zum Beispiel wenn viel Licht ausgetauscht wird oder die Flächen sehr nahe beieinander liegen), dann wird das Licht auf einer niedrigeren Ebene ausgetauscht. Dadurch reduziert sich die Anzahl der zu berechnenden Formfaktoren substantiell, und die Berechnung wird deutlich beschleunigt.
Zusätzlich zu diesen Verfahren wurden noch viele Erweiterungen ersonnen. Zum Beispiel gibt es die Methode des Clustering, welches eine Erweiterung des Hierarchischen Radiosity ist. Hier wird oberhalb der Patchhierarchie eine weitere Hierarchie erzeugt, die Cluster. Licht kann dann auch zwischen ganzen Clustergruppen ausgetauscht werden, abhängig vom zu erwartenden Fehler. Wieder spart man sich die Berechnung vieler Formfaktoren.