Background

Radiosity is a lightning model commonly used in game engines. The original idea for radiosity was formulated by a set of writers called Goral, Torrance, Battaile & Greenberg[1]. They suggested that radiosity would simulate energy transference between diffuse surfaces. That is surfaces that reflect light equally in all directions, as opposite to shiny surfaces. The result of such a simulation would give a view independent result, meaning that the illumination on surface would look the same from all viewing angles. This is very well suited for 3D games since the calculations only needs to be done once, during the pre rendering of the map[2].

We will only give a quick brief in how the radiosity algorithm works and focus on how BSP-trees can be used to optimize the calculations. For more knowledge about the algorithm we suggest that you read some of the related reading at the end of this article.

The radiosity algorithm is designed so that the lightning of a scene will be smooth and natural. If we would use a straightforward lightning model where each light sends out rays to the world and illuminates it without any further reflecting of light, shadows would we be very sharp and things would look very unnatural. To use the radiosity algorithm the world has to be divided into patches, where each patch represent a small part of the world. Each of these patches has an initial energy level, normally zero if it is not an emitting source such as lights, glowing walls or something like that.

There are several ways of distributing energy over the world. We chose to use so called iterative radiosity. This means that we start by sending out energy from the patch with the highest level of unsent energy in the scene, after which that patch unsent energy is set to zero. This process is repeated until it doesn’t exist a patch which as energy above a certain threshold value.

When sending out energy from one patch (j) to another (i) the following formula is used:

B_i = B_i + B_j * F_ij * A_i / A_j

In the formula above form factor needs further description:

F_ij = (cos θi * cos θj) / d² * H_ij

As you see above it is extremely expensive to do the radiosity calculations on a scene. This function is of order O(n³) where n is the number of patches in the scene. Since you for every patch will send at least one ray to every other patch in the scene, thus tracing through the scene potentially towards every polygon (it is safe to assume that the number of patches in the scene is greater than the number of polygons). The H (visibility) part of the form factor is the most expensive part to calculate and it is here we can draw usage of the strengths in a BSP-tree.

Radiosity in BSP-trees

Before the actual lightning of the scene can be calculated the surfaces has to be subdivided into patches. One idea is that the patches is of a certain size from the beginning and when the energy is calculated in that patch, it could be divided into smaller patches if the energy varies too much over the patch. Due to lack of time we discarded this idea and continued on what we thought was more important, namely using the BSP-tree to optimize the calculations.

The creation of the patches turned out to be quite a challenging problem, but it is not related to the BSP-trees nor can it draw any use of the BSP-tree, so we will not go further into that.

In the original idea of radiosity each light source in the scene should be considered as one or several patches. We chose to do it another way. Each light source is stored in the BSP-leaf it is located in. The first thing that happens is that each light sends out its energy to all patches. When this is done the radiosity calculations could be ended and the scene would look quite good. To make it look even better we used a technique called progressive refinement[3] slightly modified. In every iteration of the refinement, the patch with highest energy in each of the leaves will reflect its energy to all other patches. This will result the energy spreading from the heavily lighted patches to the patches in shadows. As in real life, where nothing is really black since everything reflects light more or less.

Because of the expensive nature of the radiosity calculations we need to do some optimizations. Using the PVS that was built during the rendering of the BSP-tree when choosing which patches should receive energy can cut a lot of unnecessary calculations. The ray tracing is performed in the same way as when the PVS was calculated.

Our version of the algorithm for distribution of energy through the scene is as follows:

► RADIOSITY
* Indata:
*   Tree – Tree to apply the radiosity in
* Outdata:
*   None
* Effect:
*   Sends energy between the patches in the scene.

RADIOSITY (Tree)
1 for(each leaf L in Tree)
2     for(each light S in L)
3         for(each leaf V that is in L’s PVS)
4             Send S’s energy to the patches in V

  // At this stage we chose to do so that the level designer can at any
  // point check how the scene looks and break the energy sending when
  // he feels it looks good enough
5 while(not looks good enough)
6     for(each leaf L in Tree)
7         for(each leaf V that is in L’s PVS)
8             Send energy from the patch with the most unsent energy in L to all patches in V.

Complexity Analysis

This is a real killer in computational cost. The worst case is that every ray has to be checked versus every polygon in the scene, which is of order O(n³) where n is the number of patches in the tree. Fortunately the optimizations we have done will in most cases reduce the cost a great deal, but it is almost impossible to say how much since it is very dependent of the structure of the tree.

This gives a very speedy lightning of the scene where the advantages of BSP-trees come in handy. Especially the work done during the ray tracing can be cut down significantly. Since the map designer can decide when the rendering of a scene is done, by breaking the loop at any time to see if the result is good enough. It is very easy to pre render the map a couple of times to se an approximate of how it will look, instead of doing a costly full render for each change.

Below is a screenshot from a sample rendering done with our radiosity algorithm:

Figure 1: Radiosity sample

Above is a sample of a scene rendered with our technique. The left part of the image is the unrendered version of the scene, to the right the scene has been rendered with a light approximately in front of the camera.

Summary of BSP-Tree Rendering

Now we have described the steps needed to complete the pre processing part of a BSP engine. Following is the algorithm for rendering a scene into a BSP-tree:

► RENDER-SCENE
* Indata:
*   Scene – The scene to render as a BSP-tree
* Outdata:
*   A BSP-tree
* Effect:
*   Renders a BSP-tree out of the information stored in the scene.

RENDER-SCENE (Scene)
   // Render the BSP-tree using the objects that describes the geometry
   // of the scene
1  GeometryPolygons f {}
2  for (each object O that belongs to the geometry of Scene)
3      GeometryPolygons f GeometryPolygons U O.PolygonSet
4  GENERATE-BSP-TREE (Tree.RootNode, GeometryPolygons)
   // Distribute the sample points in the leaves of the tree.
5  DISTRIBUTE-SAMPLE-POINTS (Tree.RootNode, {})
6  TRACE-VISIBILITY (Tree)
7  for each object O that is a static object in Scene
8      for each polygon P in O
9          PUSH-POLYGON (Node, P)
   // CREATE-PATCHES is an undefined function that needs serious
   // consideration. Our solution of this problem was not good enough, so
   // we choose not to present it.
10 CREATE-PATCHES (Tree)
11 RADIOSITY (Tree)

Related Reading

• Saykol, Ediz and Kirimer, Burak. Progressive Refinement of Radiosity
• Teller, Seth. Application Challenges to Computational Geometry
• Firebaugh, M. Three-Dimensional Graphics – Realistic Rendering
• Nettle, Paul. Radiosity in English
• Nuydens, Tom. 3D Engine Column, Delphi3D

References

1. Goral, Cindy M., Torrance, Kenneth E., Greenberg, Donald P., Battaile , Bennett. Modeling the interaction of light between diffuse surfaces
2. Nettle, Paul. Radiosity in English
3. Nuydens, Tom. 3D Engine Column, Delphi3D