Schrittweise Verfeinerung

In Anbetracht des hohen Aufwands beim bisher beschriebenen Radiosity-Algorithmus stellt sich die Frage, ob man die Ergebnisse der Beleuchtungsberechnung inkrementell approximieren kann. Die Auswertung der $i$-ten Zeile des Gleichungssystems liefert eine Schätzung für die Strahlung $B_i$ des Flächenelements, die auf den Schätzungen für die Strahlungswerte der anderen Flächenelemente basiert. Jeder Term in der Summe der Gleichung beschreibt die Auswirkung des Elements $j$ auf die Strahlung des Elements $i$:

$$B_i~~ \mbox{updaten durch }~~ \sum_j^n \rho_iB_jF{ij}$$

Diese Methode ``sammelt'' also das Licht der restlichen Szene ein.

Der Ansatz zur schrittweisen Verfeinerung verteilt dagegen die Strahlung eines Flächenelements auf die Szene, wobei jede Fläche $j$ mithilfe von Fläche $i$ aktualisiert wird:

$$B_j~~ \mbox{updaten durch }~~ \rho_jB_iF{ji}$$

Wenn man eine Schätzung für $B_i$ hat, kann man den Beitrag des Flächenelements $i$ zum Rest der Szene ermitteln, indem man vorstehende Gleichung für jedes Element $j$ auswertet. Dazu braucht man leider $F_{ji}$ für alle $j$. Jeder dieser Werte wird mit einem separaten Halbwürfel bestimmt. Dies erfordert ebensoviel Aufwand an Speicherplatz und Rechenzeit wie der ursprüngliche Ansatz. Man kann die Gleichung jedoch umschreiben, wenn man die Reziprozitätsbeziehung berücksichtigt.

$$\mbox{ Beitrag von } B_{i} \mbox{ zu } B_{j} = \rho_{j} B_{i} F_{ij} \frac{A_i}{A_j}\mbox{ f\uml {u}r alle } j\ .$$

Zur Auswertung dieser Gleichung für alle $j$ sind nur die Formfaktoren nötig, die mit einem einzigen Halbwürfel um das Flächenelement $i$ berechnet wurden. Kann man die Formfaktoren des Elements $i$ schnell berechnen (z.B. mit $z$-Puffer-Hardware), kann man sie wieder löschen, sobald die Strahlungen vom Flächenelement $i$ aus berechnet sind. Man muß also immer nur einen einzigen Halbwürfel und dessen Formfaktoren gleichzeitig berechnen und speichern.
Sobald die Strahlung eines Elements verteilt wurde, wählt man ein anderes Element aus. Ein Element kann wieder Strahlung verteilen, sobald es neues Licht von anderen Elementen erhält. Dabei wird nicht die gesamte geschätzte Radiosity des Elements $i$ verteilt, sondern nur der Betrag $\Delta B_{i}$, den das Element $i$ seit dem letzten Verteilen empfing. Der Algorithmus läuft so lange weiter, bis die gewünschte Genauigkeit erreicht ist. Es ist sinnvoll, das Element mit der größten Differenz zu nehmen, statt die Elemente in zufälliger Reihenfolge auszuwählen. Man wählt also das Element, das noch am meisten Energie abzustrahlen hat. Da die Strahlung pro Flächeneinheit gemessen wird, wählt man ein Flächenelement, bei dem $\Delta B_{i}F_{i}$ maximal ist. Am Anfang gilt für alle Flächenelemente $B_{i} = \Delta B_{i}=E_i$. Dieser Wert ist nur bei Lichtquellen ungleich Null.

Im folgenden bezeichnet $\Delta B_{i}$ also die noch nicht verteilte Strahlung, d.h. die Differenz zwischen der Radiosity im letzten und im gegenwärtigen Iterationsschritt. Es wird ausgenutzt, daß gilt $F_{ji}=(F_{ij}\cdot A_{i})/A_j$.

for i:= 1 to n do                     $\{$initialisiere$\}$
     if patch i ist Lichtquelle                $\{$für jede Fläche$\}$
          then $B_i$ := $\Delta B_{i}$ := Emissionswert           $\{$Strahlung und Differenz$\}$
          else $B_{i}$ := $\Delta B_i$ := 0
end;

repeat
     for {jede Fläche i, beginnend bei größter Ausstrahlung} do begin
          Plaziere Hemicube auf Fläche i
          Berechne $F_{ij}$ für alle $1 \leq j \leq n$
          for j := 1 to n do begin           {für jede Fläche j tue}
               $\Delta R := \rho_{j} * \Delta B_{i} * F_{ij}*A_{i}/A_{j}$      $\{$Strahlung von Fläche i$\}$
               $\Delta B_{j} := \Delta B_j + \Delta R$      $\{$Differenz erhöhen$\}$
               $B_j := B_j+\Delta R$      $\{$Strahlung erhöhen$\}$
          end;
          $\Delta B_i := 0$;           $\{$Überschuß ist verteilt$\}$
     end
until fertig                     $\{$bis zur Konvergenz$\}$

Bei jeder Ausführung der äußeren FOR-Schleife verteilt ein weiteres Flächenelement seine unverbrauchte Strahlung auf die Szene. Daher werden nach der ersten Ausführung nur die Flächen beleuchtet, die selbst Lichtquellen sind sowie solche, die beim Verteilen der Strahlung des ersten Elements direkt beleuchtet werden. Rastert man am Ende jeder Ausführung des Codes ein neues Bild, so wird das erste Bild relativ dunkel und die nachfolgenden Bilder immer heller.

Abbildung 23.4 faßt den gesamten Ablauf zusammen.

Abbildung 23.4: Ablaufschema beim Radiosityverfahren