Radiosity (Computergrafik)

Radiosity bzw. Radiosität ist neben Raytracing eines der beiden großen Verfahren zur Berechnung der Lichtverteilung in der 3D-Computergrafik. Es beruht auf dem Energieerhaltungssatz: alles Licht, das eine Fläche empfängt und nicht absorbiert, muss sie wieder reflektieren. Außerdem kann eine Fläche auch selbstleuchtend sein.

Im Radiosity-Verfahren wird für jede Fläche eine Gleichung aufgestellt, die das emittierte Licht aus dem von den anderen Flächen empfangenen Licht und evtl. ihrer eigenen Leuchtkraft bestimmt. Insgesamt ergibt sich damit ein Gleichungssystem, dessen Lösung die Helligkeit jeder einzelnen Fläche (patch) angibt. Damit ist Radiosity eine Finite-Elemente-Methode.

Eigenschaften

Vorteile

Radiosity-no.jpg, nur direkte Beleuchtung.]]

Radiosity-yes.jpg

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 ein Mal berechnet werden. Danach kann die Szene in Echtzeit gerendert werden (meist mittels Scanline Rendering), was für Anwendungen wie virtuelle Architekturmodelle interessant ist. Diesen Vorteil genießen 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 wird 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 H. E. Rushmeier u. A: Geometric simplification for indirect illumination calculations. In: Proceedings of Graphics Interface ’93, S. 227–236, Canadian Information Processing Society, Toronto 1993 (PDF), 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 M. F. Cohen u. A.: Radiosity and realistic image synthesis. Academic Press Professional, San Diego 1993, ISBN 0-12-178270-0. 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 H. Rushmeier, K. Torrance: Extending the radiosity method to include specularly reflecting and translucent materials. In: ACM Transactions on Graphics, Vol. 9, S. 1–27, ACM Press, New York 1990 (PDF)E. Gobbetti u. A.: Hierarchical Higher Order Face Cluster Radiosity for Global Illumination Walkthroughs of Complex Non-Diffuse Environments. In: Computer Graphics Forum, Vol. 22-3 (9/2003), hat jedoch keine breite Verwendung gefunden, da derartige Effekte schneller bzw. präziser mittels auf Raytracing basierten 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 aufwändig 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 auf elegantere und physikalisch korrektere Weise simulieren können, ist Radiosity im Bereich der hochwertigen realistischen Bildsynthese weitgehend aus der Mode gekommen. Kommerzielle Verwendung findet Radiosity vor allem bei Echtzeitrendering von Architekturmodellen, bei denen eine zeitaufwändige Vorausberechnung vertretbar ist. Auch derartige Anwendungen sind jedoch mit Raytracing möglich B. Walter u. A.: Global Illumination Using Local Linear Density Estimation. In: ACM Transactions on Graphics, Vol. 16-3 (7/1997), S. 217–259, ACM Press, New York 1997.

Prinzip

Grundgleichung

Mathematisch lässt sich Radiosity als spezielle Form der Rendergleichung interpretieren. Das Verfahren besteht in der Lösung des Gleichungssystems

B_i = E_i + \rho_i \sum_{j=1}^n B_jF_{ij},\quad 1 \le i \le n

mit

E_i

= Von der Fläche

i

abgegebene Eigenstrahlung

\rho_i

= Reflexionsvermögen der Fläche

i

n

= Anzahl der Flächen

F_{ij}

= Anteil an der von Fläche

i

abgegebenen Energie, die auf Fläche

j

auftrifft, genannt Formfaktor

B_i

= gesamte von Fläche

i

abgestrahlte Energie (Summe aus Eigenstrahlung und Reflexion als Energie pro Zeit und pro Flächeneinheit), genannt Radiosity der Fläche

i

Für die Lösung des Gleichungssystems kann ein iteratives Verfahren angewendet werden, das gegen die exakte Lösung konvergiert. Damit ist ein frei wählbarer Kompromiss zwischen Darstellungsqualität und Rechenzeit möglich.

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. Des Weiteren 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{\cos\phi_u\cos\phi_v d_{u,v}}{\pi r^2} \Delta A_e \Delta A_s

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

d_{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. FormfaktorenfuerRadiosityBerechnung.PNG

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_j \frac{\cos\phi_u\cos\phi_v d_{u,v}}{\pi r^2}

Wobei

u

der Mittelpunkt von

A_i

und

v

der Mittelpunkt von

A_j

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 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} \Delta A_e$ ermittelt.

Hemicube.png

Hemi-Cube-Verfahren

Von Cohen et al. stammt das sogenannte Hemi-Cube-Verfahren M. F. Cohen, D. P. Greenberg: The hemi-cube: a radiosity solution for complex environments. In: Proceedings of the 12th annual conference on Computer graphics and interactive techniques, S. 31–40, ACM Press, New York 1985, ISBN 0-89791-166-0. Die Einheitshalbkugel nach Nusselt wird durch einen Einheitshalbwürfel approximiert, dessen Flä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 (üblicher Weise Z-Buffer) ein Item Buffer berechnet. Dieser enthält für jede Gitterfläche die Identität der Objektfläche (Item, im Bild rotes Dreieck), die darauf projiziert wurde. Für jedes Item wird die Summe der Delta-Formfaktoren der überdeckten Gitterflächen berechnet (im Bild rote Gitterflächen). Diese Summe wird als Formfaktor zwischen Item und betrachteter Fläche aufgefasst.

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 komplett 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 anderem 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 M. F. Cohen u. A.: A progressive refinement approach to fast radiosity image generation. In: Proceedings of the 15th annual conference on Computer graphics and interactive techniques, S. 75–84, ACM Press, New York 1988. 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 komplette 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 Identitätsmatrix, $M$ die Matrix, bestehend aus den Formfaktoren und den Reflektionskoeffizienten 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}$ .

Der momentane Stand ist das Hierarchische Radiosity, das 1991 von Hanrahan et al. vorgestellt wurde Pat Hanrahan u. A.: A Rapid Hierarchical Radiosity Algorithm. In: Proceedings of the 18th annual conference on Computer graphics and interactive techniques, S. 197–206, ACM Press, New York 1991. 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 B. Smits u. A.: A Clustering Algorithm for Radiosity in Complex Environments. In: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, S. 435–442, ACM Press, New York 1994 (PDF), 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.

Literatur

Michael F. Cohen, John R. Wallace: Radiosity and Realistic Image Synthesis. Morgan Kaufmann, San Francisco 1993, ISBN 0-1217-827-00.
François X. Sillion, Claude Puech: Radiosity and Global Illumination. Morgan Kaufmann, San Francisco 1994, ISBN 1-5586-027-71.

Weblinks

Geschichte von Radiosity, mit dem angeblich ersten mit Radiosity berechneten Bild (englisch)

Quellen

3D-Computergrafik | 3D-Computergrafik | Algorithmus

Gourt Home::Gourt :: Radiosity (Computergrafik)