Radiosity (computer graphics)

Radiosity or radiosity is a method of calculating the distribution of heat or light radiation within a virtual model. In image synthesis , radiosity is one of the two important methods for calculating the incidence of light within a scene, along with algorithms based on ray tracing . It is based on the law of conservation of energy : All light that falls on a surface and is not absorbed by it is reflected back by it. In addition, a surface can also be self-luminous.

The radiosity method is based on the assumption that all surfaces are ideally diffuse reflectors and that all light sources are ideally diffuse emitters. Ideally diffuse means that light is reflected or emitted evenly in all directions.

Unlike ray tracing, radiosity is not point of view dependent; the lighting of the surfaces is calculated for the entire scene regardless of the position of the observer. The viewpoint-dependent occlusion calculation has to be done in an independent step.

properties

advantages

An image rendered using diffuse ray tracing without simulating the indirect lighting of diffuse surfaces.

An image rendered using radiosity. You can clearly see that the light is reflected from the balls onto the floor. You can also see that the white wall illuminates the spheres indirectly from behind.

Point of view independence

One advantage of the radiosity method is that the calculation is carried out independently of the viewer's location and perspective. The light distribution only has to be calculated once for a scene. The scene can then be rendered in real time (mostly using scanline algorithms or Z-buffering ), which is interesting for applications such as virtual architecture models. However, not all programs have this advantage.

Simple indirect, ideally diffuse light reflection

Ideally diffuse light reflections are supported in a natural way by the radiosity process. The brightness and color of a surface are not only determined by the direct illumination of a light source, but also by diffusely reflected light from other surfaces. An example of this is a room that is not only lighter in the areas directly illuminated by incident sunlight, but also in general.

disadvantage

No analytical primitives

Due to the mandatory division of the scene into polygons, no analytically defined primitives, such as the spheres common in ray tracing , can be used. Due to the fine division necessary to avoid visible edges, a very large number of surfaces is quickly necessary for complex scene geometry. This often leads to a long waiting time when calculating the form factors (see below).

Attempts have been made to partially solve this problem by means of adaptative simplification of the geometry, but this is a manual process that has its limits. In addition, the effects on the light calculation resulting from the errors of this procedure are difficult to predict.

High memory and time requirements

If the number of primitives in a scene is, the most efficient radiosity variants have an asymptotic time complexity of , as has been empirically established. In contrast, ray tracing only requires a runtime of . This quickly limits the degree of refinement that is practically possible in radiosity. In addition, there are relatively high storage requirements for calculating and storing the form factors. ${\displaystyle N}$ ${\displaystyle O(N\log N)}$ ${\displaystyle O(\log N)}$

Global lighting difficult to implement

For the most realistic possible representation of a scene, the global lighting must be simulated, but this is only possible efficiently with radiosity in special cases. In its basic form, radiosity is only capable of simulating ideally diffuse reflection. Any lighting models as well as translucent surfaces can be taken into account , but has not been widely used, since such effects are possible faster or more precisely by means of solutions based on ray tracing .

Comparison with ray tracing

Historically, radiosity was interesting because it made it possible to simulate indirect diffuse lighting in a simple way, which was not possible with ray tracing for a long time. On the other hand, ray tracing worked well for reflective and transparent objects, which radiosity was unable to do. Initially, therefore, proposals were made to combine radiosity with ray tracing, but these were complex and ultimately could not be widely accepted.

However, with the advent of modern global lighting techniques such as path tracing and photon mapping , the possibilities of ray tracing have expanded considerably. Because such algorithms can simulate all effects supported by radiosity with fewer errors and in a more elegant way, radiosity has largely gone out of fashion in the field of high-quality, realistic image synthesis . Radiosity is primarily used commercially for rendering architectural models, where time-consuming forecasting is justifiable. However, such applications are also possible with ray tracing-based methods ( particle tracing ).

Radiosity methods are also used in the areas of climate and heat research, since heat distribution is more diffuse than directional and radiosity is more practicable here than radiation-based approaches.

principle

With the assumption formulated at the beginning, the general rendering equation can be converted into the radiosity equation.

${\displaystyle 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'}$

With

B (x) = total energy radiated from point x (sum of natural radiation and reflection as power per unit area), called radiosity at point x

E (x) = natural radiation emitted at point x

ρ (x) = reflection factor at point x

S = all surfaces of the scene

r = distance between points x and x '

${\displaystyle \phi (x)}$= The angle between the normal at point x and the connecting line between points x and x '

${\displaystyle V(x,x')={\begin{cases}1,&{\mbox{wenn }}x{\mbox{ von }}x'{\mbox{ aus sichtbar}}\\0,&{\mbox{sonst}}\end{cases}}}$.

The radiosity sought at point x results from an integral in closed form, which cannot be calculated directly. The remedy is the discretization of the surface S: instead of considering all infinitesimally small partial areas δA ', the surface S is divided into contiguous partial areas (called facets or patches ) A _i ( finite element method ). Further assumptions apply to these partial areas: every A _i is planar; the respective radiosity B _i and the reflection factor ρ _i are constant over A _i . This then leads to the discrete radiosity equation.

${\displaystyle B_{i}=E_{i}+\rho _{i}\sum _{j=1}^{n}B_{j}F_{ij},\quad 1\leq i\leq n}$

With

B _i = total energy radiated by sub-area i (sum of natural radiation and reflection as power per unit area), called radiosity of sub-area i

E _i = natural radiation emitted by the partial area i

ρ _i = reflection factor of the partial area i

n = number of partial areas

F _ij = proportion of the energy given off by surface j that hits surface i, called the form factor .

The radiosity of the partial area is therefore equal to the natural radiation of the partial area plus the sum of the radiosity of all other partial areas weighted with the diffuse reflection factor . Whereby the form factor , which defines the proportion of the energy released by surface j that hits surface i, is included. The form factor therefore takes into account the alignment and the distance between the partial surfaces . Since this has to be calculated for all partial areas , the result is a linear system of equations with as many equations and unknowns as there are partial areas. ${\displaystyle B_{i}}$ ${\displaystyle i}$ ${\displaystyle E_{i}}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle j}$ ${\displaystyle F_{i,j}}$ ${\displaystyle i,j}$ ${\displaystyle i}$

1. Subdivision of the surfaces

The first step is to define the primitives: How and into which partial areas should a given continuous surface be broken down? Triangle and square are common. Already in this phase a decision is made between quality and efficiency. The finer the network, the more precise the results, but the more complex the calculations.

In practice, adaptive methods are mostly used. Starting from a z. B. triangulated surface, the associated radiosity values ​​of all facets are determined according to the scheme given here. With this data, further location-dependent network refinements are made. Decisive for this can be: a high radiosity gradient of neighboring facets, discontinuities in the course of the light (e.g. light spot) or a locally unfavorable network division (e.g. T-nodes).

Determination of radiosity values ​​for constant, linear and quadratic basis functions

2. Definition of the basic functions

The discrete radiosity equation is one way of discretization. It is based on the assumption that radiosity is constant over a given facet and therefore uses constant basis functions. The choice of basic functions of a higher degree is also possible, especially with the Galerkin approach .

3. Calculation of the form factors

Regardless of the algorithm chosen , the most complex step in radiosity is the calculation of the form factors. A form factor always applies between two patches and describes the amount of radiation exchanged, i.e. it lies between zero (no radiation is exchanged) and one (all radiation is exchanged).

The form factor is of a purely geometric nature and is determined by the position of the patches to one another. The visibility of the patches also plays a role. The visibility calculation takes by far the most time in the calculation.

The formula for a form factor is:

${\displaystyle 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}}$

With

${\displaystyle F_{s,e}}$= Form factor between the transmitter and the receiver ${\displaystyle S}$ ${\displaystyle E}$

${\displaystyle A_{s}}$ = The area of ​​the transmitter ${\displaystyle S}$

${\displaystyle A_{e}}$ = The area of ​​the recipient ${\displaystyle E}$

${\displaystyle \phi _{u}}$= The angle between the normal of the transmitter and the line connecting the transmitter and receiver ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle E}$

${\displaystyle \phi _{v}}$= The angle between the normal of the receiver and the connecting line between receiver and transmitter ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle S}$

${\displaystyle r}$= Distance between transmitter and receiver ${\displaystyle S}$ ${\displaystyle E}$

${\displaystyle V(u,v)={\begin{cases}1,&{\mbox{wenn }}u{\mbox{ von }}v{\mbox{ aus sichtbar}}\\0,&{\mbox{sonst}}\end{cases}}}$

Since this double integral is very difficult to calculate directly, approximations are generally used.

The simplest method is only correct for areas that are relatively small and relatively far away and between which there is no partial obscuration. The angle and distance are only calculated between two representative points, the centers of the two surfaces.

${\displaystyle F_{s,e}\approx A_{e}{\frac {\cos \phi _{u}\cos \phi _{v}d_{u,v}}{\pi r^{2}}}}$

Where is the center of and the center of . ${\displaystyle u}$ ${\displaystyle A_{s}}$ ${\displaystyle v}$ ${\displaystyle A_{e}}$

Nusselt method

Determination of the form factors according to Nusselt

(also "Nusselt's analogue")

A representative point of the receiver surface, the center point, is selected. The visible parts of the transmitter surface are projected onto the unit hemisphere around this point. This is observed. Then the projection on the unit sphere is again projected into the area in which it lies. The resulting area is divided by (area of ​​the unit circle). This step determines the form factor . ${\displaystyle {\frac {\cos \phi _{v}}{r^{2}}}}$ ${\displaystyle A_{j}}$ ${\displaystyle \pi }$ ${\displaystyle 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}}$

Hemi-Cube process

Approximation of the form factors using Hemi-Cube

From Cohen et al. comes the so-called Hemi-Cube process. The unit hemisphere according to Nusselt is approximated by a unit half cube, the side faces of which are divided into a discrete grid. Each grid area is assigned a weighting factor, the delta form factor , which depends on the position of the grid area. A delta form factor is therefore the form factor of the grid surface according to Nusselt. The sum of the delta form factors is 1.

An item buffer is calculated for each of the five half-cube areas with modified raster algorithms (usually Z-Buffer ) . For each grid area, this contains the identity of the object area ( item , red triangle in the image) that was projected onto it. For each item , the sum of the delta form factors of the covered grid areas is calculated (red grid areas in the picture). This sum is understood as a form factor between the item and the area under consideration.

Sillions of improvement

Instead of a half-cube, only a single area is now used, which is placed centered over the differentially small area piece ( dA ). This area is also divided into small, discrete areas. As with the Hemicube process, these are then assigned to dA , the so-called delta form factors, depending on the geometry . The advantage of this method is that a patch only has to be projected onto this one surface and no longer onto five surfaces of a cube. In addition, this method is legitimate, since patches that are orthogonal to the surface of dA do not make a large contribution to the overall brightness. This observation can be made clear from the cosine between the normals of the two patches of surface.

4. Calculation of the radiosity values

The discrete radiosity equation can be understood as a linear system of equations and can therefore be represented in matrix form after a few reshaping steps as follows .

${\displaystyle {\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}}}$or B = E + T • B for short .

The system of equations must be solved in order to determine all the radiosity values ​​sought. The inversion of the matrix ( I - T ) ( matrix inversion according to Gauss ) is obvious , but this is impractical due to the enormous effort involved.

In general, there are two different iterative solution strategies that converge towards the exact solution . A freely selectable compromise between display quality and computing time is thus possible.

• In gathering , the radiosity B _{i of} a facet is formed by collecting all influencing B _j (depending on the respective form factor). The starting point is B ⁰ = E and you can only see the self-illuminating surfaces. After the first step B ¹ = E + T • B ⁰ , all directly illuminated objects are also visible. In the next iteration step B ² = E + T • B ¹ , the simple reflections are taken into account, etc. It is noticeable that all form factors are required in each step. Methods based on this principle are Jacobi iteration and Gauß-Seidel iteration .
• When shooting the undistributed radiosity B _i to all the recipients in question facets (depending on the form factor) shot . The starting point is again the self-luminous surfaces, thus applies B = E .

 für jede Facette i
   Radiosity B = Eigenleuchten E
   unverteilte Radiosity ΔB = Eigenleuchten E
 wiederhole
   i = Facette mit maximaler Restenergie ΔBi•Ai
   für jede Facette j
     rad = ΔBi•ρj•Fji         (wie viel der zu verteilenden Radiosity bekommt Facette j)
     ΔBj = ΔBj+rad            (zu verteilende Radiosity der Facette j wird um diesen Betrag erhöht)
     Bj = Bj+rad              (Radiosity der Facette j wird um diesen Betrag erhöht)
   ΔBi = 0                    (zu verteilende Radiosity der Facette i wurde verteilt und ist nun 0)
 bis (Abbruchkriterium)

In addition to objective values ​​such as error metrics , the subjective impression can also be used as termination criteria . Shooting processes are superior to gathering processes in two respects. On the one hand, it can be derived from the pseudocode that only j form factors are required for each iteration step. On the other hand, the radiosity of the facet with the greatest residual energy is distributed in each run, which means that shooting processes converge much more quickly against “beautiful” images than gathering processes. Algorithms based on this principle are Southwell iteration and progressive refinement .

5. Render

The final step is rendering the finished image. The radiosity values ​​calculated at the selected points are combined according to the selected basic functions. If radiosity values ​​were determined in the network nodes, z. B. Gouraud shading is also possible. If the image created in this way does not meet the requirements, further iterations from (4) can follow. If unwanted graphical artifacts occur, the algorithm should be started from the beginning with appropriate changes in the network structure.

historical development

Image rendered with radiosity

In 1984 the method was first used by Goral et al. presented. It comes from thermodynamics , where it was used to calculate the exchange of thermal radiation ( radiation calculation ). At that time, the full form factor matrix method was used to solve the system of equations. Here the system of equations for all form factors between all patches (= areas) in the world is set up and then solved using a mathematical method (usually the Gauss-Seidel method). In principle, this procedure corresponds to collecting radiosity. For each patch, it is calculated how much light it receives from each other patch. This has the disadvantage that the calculation of the entire matrix takes an extremely long time and takes up a lot of storage space, which makes the method unusable for complex scenes.

In 1988, the progressive refinement process by Cohen et al. presented. Here the process is reversed and the light is no longer collected at each patch, but rather fired from each patch. So you can first send the light from the patches with the greatest radiosity value and then turn to those with little radiosity. Here it is no longer necessary to calculate the entire matrix, instead only the form factors from one individual patch to all the others are required in each step. This reduces the required storage space enormously, and you get a usable image after each step. The longer you wait, the better the picture, as more and more indirections are calculated. In order to converge, however, this method takes just as long as the full form factor matrix method.

In principle, the method corresponds to a series expansion of the matrix. The linear equation system resulting from the radiation equation is then , with the unit matrix , the matrix consisting of the form factors and the reflection coefficient and describes the characteristic radiation. If you now rearrange the equation , the right part can be developed as a series of the following form, and you get an incremental approximation to the actual radiation intensity: ${\displaystyle (I-M)B=E}$ ${\displaystyle I}$ ${\displaystyle M}$ ${\displaystyle E}$ ${\displaystyle B=(I-M)^{-1}E}$ ${\displaystyle (I-M)^{-1}}$

${\displaystyle \sum _{i=1}^{\infty }x^{i}={\frac {1}{1-x}}=(1-x)^{-1}}$.

In 1991, Hanrahan et al. the hierarchical radiosity presented. This process uses a patch hierarchy. A few large patches are made up of many small ones. The light exchange is now carried out at different levels. If the error is small, the light is exchanged at a higher level in the hierarchy, if a large error is to be expected (for example if a lot of light is exchanged or the surfaces are very close together) then the light is exchanged at a lower level. This substantially reduces the number of form factors to be calculated and the calculation is significantly accelerated.

In addition to these procedures, many extensions have been devised. For example there is the clustering method , which is an extension of the hierarchical radiosity. Here another hierarchy is created above the patch hierarchy, the cluster. Light can then also be exchanged between entire cluster groups, depending on the error to be expected. Again you save yourself the calculation of many form factors.

literature

• Michael F. Cohen, John R. Wallace: Radiosity and Realistic Image Synthesis . Morgan Kaufmann, San Francisco 1993, ISBN 0-12-178270-0 .
• François X. Sillion, Claude Puech: Radiosity and Global Illumination . Morgan Kaufmann, San Francisco 1994, ISBN 1-55860-277-1 .

swell

1. ↑ HE Rushmeier u. A: Geometric simplification for indirect illumination calculations. In: Proceedings of Graphics Interface '93. Canadian Information Processing Society, Toronto 1993, pp. 227-236 ( smartech.gatech.edu ( memento of August 7, 2016 in the web archive archive.today ) PDF).
2. ↑ MF Cohen et al. A .: Radiosity and realistic image synthesis. Academic Press Professional, San Diego 1993, ISBN 0-12-178270-0 .
3. ↑ H. Rushmeier, K. Torrance: Extending the radiosity method to include specularly reflecting and translucent materials. In: ACM Transactions on Graphics. Volume 9, pp. 1–27, ACM Press, New York 1990 ( graphics.cornell.edu PDF)
4. ↑ E. Gobbetti et al. A .: Hierarchical Higher Order Face Cluster Radiosity for Global Illumination Walkthroughs of Complex Non-Diffuse Environments. In: Computer Graphics Forum , Volume 22-3 (9/2003).
5. ↑ B. Walter u. A. Global Illumination Using Local Linear Density Estimation. In: ACM Transactions on Graphics , Vol. 16-3 (7/1997), pp. 217-259, ACM Press, New York 1997
6. ^ MF Cohen, DP Greenberg: The hemi-cube: a radiosity solution for complex environments. In: Proceedings of the 12th annual conference on Computer graphics and interactive techniques , pp. 31-40, ACM Press, New York 1985, ISBN 0-89791-166-0
7. ↑ C. Goral, KE Torrance, DP Greenberg and B. Battaile: Modeling the interaction of light between diffuse surfaces. (PDF; 1.1 MB) In: Computer Graphics. Volume 18, No. 3.
8. ↑ MF Cohen et al. A .: A progressive refinement approach to fast radiosity image generation. In: Proceedings of the 15th annual conference on Computer graphics and interactive techniques , pp. 75-84, ACM Press, New York 1988
9. ↑ Pat Hanrahan et al. A .: A Rapid Hierarchical Radiosity Algorithm . In: Proceedings of the 18th annual conference on Computer graphics and interactive techniques , pp. 197-206, ACM Press, New York 1991
10. ↑ B. Smits et al. A .: A Clustering Algorithm for Radiosity in Complex Environments. In: Proceedings of the 21st annual conference on Computer graphics and interactive techniques. ACM Press, New York 1994, pp. 435–442 ( cs.ucl.ac.uk ( Memento of March 10, 2004 in the Internet Archive ) PDF)

This version was added to the list of articles worth reading on September 3, 2005 .