We propose an upgrade for the Radiosity algorithm that allows to efficiently apply radiosity for large scale scenes. This is achieved by considering only the patches located close to the observer. For each frame we update local form-factor matrix with a little set of patches, effectively reusing information from the previous frame in this way. Our method is completely expressed via matrix-vector operations, thus, it's GPU implementation is natural and straightforward. We achieve high occupancy for both CPU and GPU versions of the algorithm by thanks to we use special matrix of several reflections for which update operation effectively combine computations with memory operations.
The methods of global real-time global illumination in general can be divided into two classes: the methods that uses preprocessing/precomputation and those who does not uses it (i. e. calculate everything in dynamic). The main advantage of methods that do not use pre-processing is the fully dynamic content. However, the methods of the first group due to the precomputation and pre-integration usually are significantly better in terms ofspeed/quality ratio.
Our work is devoted to the problem of building methods of the ”intermediate class” that combines the advantages of both classes.
LPV [
Instant Radiosity [
PRT
Precomputed Light Transport (PRT) methods al-low to move the most complex calculations from the rendering stage to the precomputationstage.
For example, Radiance regression function [
Spherical harmonics based methods [
Despite huge number of papers in real-time global
illumination, radiosity [
Radiosity, like the previously considered methods,
uses scene discretization (but use patches insteadof
voxels). The pre-calculation is done by calculating the
matrix of form-factors. The form-factor is a value
indicating how much of the lighting is transferred from
one patch to another. The calculation of the global
illumination is reduced to solving the linear equation
system or several matrix-vector multiplications. By
expanding the calculations at the preprocessing stage, it
is possible to reduce the calculation of the global
illumination method to a single matrix-vector
multiplication [
However Radiosity still have O(N 2) algorithmic
complexity where N is the number of scene patches.
This is the main disadvantage of the algorithm, since
such computational complexity is unacceptable for
large scenes (with an increase in the number of sites
N ). Our work is aimed specifically at solving this
problem. The existing approaches of hierarchical
radiosity and analogues [
For a better explanation of our methods, we will begin with a few simple ideas that will be refined further.
Our first idea is that we can consider only M clos-est
patches to the observer (where M << N ). We as-sume
lighting from other patches equals to some con-stant or
evaluate it on a rougher approximation (that is, we may
build cascades of discrete representations of the scene in
the same way as the Cascaded LPV [
However, the direct implementation of this method will not be efficient because the matrix of the formfactor for the entire scene (even isfpecial methods are used to effectively store sparsematrices) does not fit into the computer’s RAM. Therefore, reading even M 2 of random elements (shown in green in Fig. 1, left) from DRAM or external memory cannot be implemented efficiently.
Therefore, second idea is that it is necessary to reuse information from the previous frames as much as possible, updating only patches that were not loaded on previous frames (Fig. 1, right). This allows us to reduce the number of form-factors that areloaded into the local matrix each frame to only a few readings (or approximately M if the observer moves quickly, which, nevertheless, is significantly better than M 2).
However, reading even a few elements from the global matrix at random addresses is still inefficient for modern computing systems. During the update of the local matrix of form-factors, computing system (both CPU and GPU) will be practically idle. At the same time, after updating, when calculating the radi-ance on the local matrix of form-factors, they will be loaded and these calculations may become a bottle-neck since you need to perform at least 3 multiplica-tions of the local matrix by a vector (to account for three light bounces). local matrix matrix update
Therefore, third idea is to combine updating the
local matrix with the multiple reflection matrix from
[
Finally, the fourth idea is that with asmall movement of the observer, it is possible to update the local matrix less often than to calculate the lighting on it (for example, once in 2-5 frames). Therefore, it makes sense to reduce the cost of the stage ocfalculating the lighting usinga local matrix of several reflections. 3.1
The matrix of form-factors of several reflections
[
Consider three patches withindices i, j, k. Then Fij and Fjk — form-factors of energy transfer from the j-th path to the i-th patch and from the k-th patch to the jth patch respectively. Colorsj — color of j patch. Then value
Fij · Colorsj · Fjk shows how much of the world will go from the k-th patch to the i-th patch when the multi-reflection from the j-th patch.
After going through all patches as intermediate in the reflection, we get the complete second reflection of light from the patch number k to the patch number i: =2 F ik
N ∑ j=0
Fij · Colorsj · Fjk, where N — number of patches in local matrix.
Thus, at the preprocessing stage, it is possible to calculate reflections of an arbitrary order. The multiple reflection matrix contains a specified number of reflections. 3.2
In order to extend this approach to a local ma-trix in the surrounding of an observer, two ways are possible: 1. Calculation of the matrix ofseveral reflections for the entire scene and the use of itsparts. 2. ”Online” matrix calculation for the observer’s area using the usual matrix of form-factors (Fig. 1, right).
The first option is not applicable for large scenes since it requires to store 3N 2 of real numbers. The proposed method implements the second option, since the matrix of form-factors is sparse and can be effi-ciently stored/accessed.
To update the matrix of several reflections, two operations are required: (1) adding a site to the matrix and (2) removing the site from it. Delete operation is implemented by zeroing the row and column of the matrix of form-factors corresponding to the deleted patch.
To add a new patch, we must consider several types of reflections. First, we need to include the usual formfactors fcolumn and frow (Fig. 2, ”single”). Next, triple reflections are taken into account, in which light is reflected twice from a new patch. To do this, double reflection is first calculated(Fig. 2, ”double”): double_ref lection = fcolumn ◦ Colors frow reflection be calculated double_ref lection furthe(rFig. 2,
gcol = fcolumn
Color double_ref lection grow = frow Color double_ref lection
Finally, we add information on form-factors that takes into accountthe light reflectionsbetween patches already participating in the matrix (Fig. 2, ”interreflections”): gc′ol = Flocal gcol gr′ow = grow Flocal
Thus, the form-factors for the new patch are equal to gc′ol + gcol + fcolumn;
gr′ow + grow + frow:
Now, in addition to adding the form-factors of the new patch, it is required to update theform-factors of the rest of the matrix. For this we use previously calculated form-factors for newpatch (4):
To implement the proposed method we create 6 compute shaders to update the matrix, one to delete the patch data and one shader to update the lighting. The following shaders are used forupdating: 1. Calculating double_ref lection (1) using parallel reduction on GPU. 2. Calculates triple reflections gcol, grow (2) by multiplying double_ref lection with form-factors. 3. Multiplying gcol by a matrix of form-factorsto get ′ col (3). 4. Multiplying the form-factor matrix by grow to get g′ row (3). 5. Adding to the matrix of information about reflections in view of the newpatch (5). 6. Adding new site form-factors to thematrix.
Multiple reflection matrix from [
Difference image. In average is is less than 0.05. Fig. 3. Comparison of Radiosity for the full matrix and the proposed method. Since the full matrix 63125 × 63125 does not fit in the memory ofthe GPU, the time was estimated.
The most computational-cost are steps 3-5. How-ever, steps 3 and 4 are just matrix-vector multiplica-tions, and the step 5 implements the addition of two matrices. Both of these these operations are to be easily implemented on GPU. 3.4
The matrix of form-factors can be stored as a tex-ture in the format RGBA16F. At the same time, the matrix size is limited to 4096 pixels on some GPU due to the specific hardware limits (mobile GPUs).
The proposed method was compared with the common Radiosity on local form-factor matrix and significantly outperforms it (Fig. 4).
We test our method on the scene of 63125 patches (Fig. 3). We took a Minecraft scene in order to omit scene approximation algorithms in our work. At high speed, the proposed method gives an image close to the image obtained by the methodof full-matrix Radiosity on the CPU.
This work was sponsored by RFBR 18-31-20032 grant. 6. References [1] Akenine-Moller, T., Haines, E., Hoffman, N. Real-time rendering. Fourth Edition. – AK Peters/CRC Press, 2018. page 482. [2] Budak, V.P., Zheltov, V.S., Kalakutsky, T.K. Local estimations of Monte Carlo method with the object spec-tral representation in the solution of global illumina-tion. // Computer Research and Modeling, 2012, vol. 4, no. 1, pp. 75-84. [3] Cohen, M., GreenBurg, D. The Hemi-cube: A Radios-ity solution for complex it is hard to achieve environments // Proceedings of SIGGRAPH 85 in Computer Graphics, 1985. 19. number 3. pp.31-40. [21] Walter, B., Fernandez, S., Arbree, A., Bala, K., Donikian, M., and Donald P. Greenberg. 2005. Lightcuts: a scalable approach to illumination. ACM Trans. Graph. 24, 3 (July 2005), 1098-1107. DOI: https://doi.org/10.1145/1073204.1073318 [22]DIAL Dialux. 2019. URL = https://www.dial.de/en/dialux/ [23] Relux Informatik AG Relux. 2019. URL = https://reluxnet.relux.com/en/