The Delft painter Johannes Vermeer is regarded as a past master of the use of light. According to the Encyclopædia Britannica, each of his paintings `seems to be the sum of various analytic experiments with light and with the microscopic observation of matter...´. Indeed, it was no accident that Vermeer, regarded as an experimental painter in his own time, should be rediscovered when photography was introduced towards the end of the nineteenth century.
More than three hundred years after Vermeer, experiments with light and shadow are still going on in Delft, not with oil on canvas this time, but with bits and bytes on a computer display. Arjan Kok, a graduate engineer in the Faculty of Technical Mathematics and Informatics of Delft University, was recently awarded his doctorate for his work on algorithms generating photo-realistic computer images.

One of the major objectives of computer graphics is to generate images which not only look realistic, but which are also physically correct and show all the effects of light and shadow. Or, in other words, the computer image of a certain scene must look like a photograph of that scene. This pursuit of `realism´ is not just the hobby of a number of spaced-out computer freaks. Such images are of great importance, for instance, in architecture, civil engineering and lighting design. The more realistic the image, the easier it becomes for designers to tailor the object to the requirements dictated by the surroundings or by their clients. The images are also of interest to the film industry. A film like Jurassic Park could never have been made without computer images. A more realistic look is badly needed also for the foreground and background images in `virtual reality´. The real-time generation of moving images poses a problem because present-day computers are not powerful enough. Mr. Kok estimates that it will take several years for this problem to be solved, at least if lifelike images are the aim. Virtual reality at its present level is still a far cry from actual reality.

Colour bleeding
Arjan Kok says that two things are important in generating realistic images. One is the model, which must resemble physical reality as closely as possible. You can't make a realistic image from a simplistic model. The second aspect of importance, and that's what Mr. Kok has been studying, is the illumination within the scene. In real life there are a great many optical phenomena that influence the illumination of a setting, as Vermeer knew only too well. The challenge facing today's computer experts is to simulate all these optical effects in the images generated by a computer.

When studying illumination a distinction is made between local and global illumination. Mathematical models of local illumination describe how light is reflected by a surface. Only direct light is involved here: the light from a light source that impinges on a surface and is then reflected towards the viewer. In the case of global-illumination models, the aim is to take into account the direction from which the light is coming and the fact that part of the incident light can come from reflections by other surfaces. In general, global-illumination models give a more realistic image than local-illumination models.
However, to produce a truly realistic image one has to take into account all sorts of optical effects. Mr. Kok mentions a few: Diffuse light sources, such as windows, often give soft shadows. A point source, on the other hand, for instance a spotlight, produces a sharp shadow. Another phenomenon is indirect illumination. Direct illumination does not reach all the corners of a scene. Some parts are illuminated indirectly, owing to light being reflected by walls or tables.
A related phenomenon is colour bleeding, when the colour of one object can be seen in another. Thus, a white table placed in a room with red walls will reflect a reddish light. When the same table is moved to a blue room, it looks bluish. Another special effect is caused by the presence of smoke or dust particles in the air. Such particles will reflect part of the light. Thus, even a scene that seems fairly simple can involve quite a few light effects.

Ray tracing
Existing techniques, when used individually, fail to render these light effects satisfactorily on a computer screen. Mr. Kok tried to solve the problem by combining techniques, one of them being ray tracing. The technique has been under development for about a decade now for the `visualization´ of three-dimensional models, varying from a teapot to a viaduct.
Ray tracing, as the term suggests, involves tracing the path of a ray backwards. Rays are traced from the viewpoint through pixels in the viewing plane. If rays intersect a (partly) specularly reflecting object, the rays are traced further in the direction of the reflection. If reflection rays strike an intervening object, this becomes visible in the first object. If the object is translucent, the `refracted´ ray is traced. If the surface is diffusely reflecting, the quantity of incident light from the light source is calculated.

Ray tracing sometimes involves several light sources. Not all the objects and surfaces in a scene receive light from all the light sources. Sometimes an object or part of a surface is in the shade. To find out whether this is the case, a roundabout route is chosen via shadow rays, cast from the object to the light source. If such a shadow ray strikes another object, the former object is not `illuminated´ and hence in shadow. If the shadow ray does not strike another object, then it is assumed that the first object is illuminated.
One drawback of ray tracing is that in a complex scene with several objects and several light sources the total number of rays can become quite large. Generally speaking, calculation of the intersections of the rays with the objects is so complicated that it keeps even a powerful computer busy for quite some time. Another restriction is that, apart from direct illumination, `backward ray tracing´ takes into account only the indirect illumination due to specular reflections. It ignores the light from a diffuse source, such as a window, falling on a diffusely reflecting wall and then on a table. `This can make quite a difference´, says Mr. Kok, `sometimes even as much as thirty per cent in colour and in intensity.´
We can illustrate the foregoing by asking the reader to imagine a cupboard placed in the corner of a room. When ray tracing is used, the ceiling above the cupboard is uniform in colour. In reality, however, that part of the ceiling will adopt its tone from the top colour of the cupboard.

Radiosity
Such indirect reflection between cupboard and ceiling can also be calculated and made visible on the screen using the radiosity method. This technique, which has its roots in thermal engineering, is familiar from the pictures of houses showing heat losses in different colours. Similarly, the radiosity method is used to calculate the quantity of light coming from a surface, by dividing the scene into a mesh of patches and calculating for each of these the illumination in relation to all the other patches in the scene. The relations between the patches depend on their geometry, their orientation with respect to each other, and whether they are `mutually visible´, i.e. whether there are no intervening objects. They can be calculated by casting rays from one patch to another.

All the relations together form a set of equations. The illumination values (colours) of each of the patches in the scene can be calculated using the illumination values of the various light sources as input parameters. If the light becomes stronger or weaker, as it were, then the radiosity values of the various patches are adapted by means of the set of linear equations.

Busy
The drawback of the radiosity method is that computing all the relations between the patches and solving the set of equations is very time-consuming. A scene of moderate complexity will keep a standard workstation busy for several hours at least. Besides, image quality is largely governed by the meshing resolution: the smaller the patches, the better the quality, but also the longer the computation time. Another disadvantage is that the radiosity method can barely be used at all to calculate the contribution of specularly reflecting surfaces. Moreover, the shape of the shadows also depends on the meshing resolution. If the subdivision has not been carried out far enough, oddly shaped shadows will be the result.
An advantage of the radiosity method over the ray tracing method is that the computation, though more complex, needs to be carried out only once for a given scene. This is because the radiosity method calculates the illumination values of surfaces but does not yet render an image.
`When you have finished the computation, you can, as it were, walk through your scene by using a simple and fast imaging algorithm. This is because, when the viewpoint changes, the shadows remain the same. In ray tracing you have to recalculate the illumination of the scene each time the viewpoint changes and that can take a lot of time´, explains Mr. Kok.

Combinations

Given the pros and cons of the two methods, it is not surprising that several scientists have been studying the possibilities of combining the two. When ray tracing is used to display the results of the radiosity method, it becomes possible to render images with both indirect specular and indirect diffuse reflections. The advantage here is that the ray tracing step is speeded up considerably, because the shadow rays no longer need tracing: the illumination value had already been calculated using radiosity. However, this still does not solve the problem of the oddly-shaped shadows. Mr. Kok shows an image of a scene with a teapot on a table. Using the radiosity method alone the teapot has an oddly shaped, ragged shadow. This is due to the meshing technique. `By carrying out part of the illumination calculations by ray tracing instead of the radiosity technique, you can make the shadow a lot sharper, while at the same time, because of the radiosity method, the indirect illumination is included in the scene´, Mr. Kok explains.

The philosophy underlying this approach is that the principal source of `sharp´ shadows is direct light. By means of ray tracing you can therefore direct shadow rays at your light source, which produces a sharply outlined shadow. By directing several shadow rays from an object to a light source, one can make the shadow softer, which creates the impression of a diffuse light source.

Hardness
`All things considered, this combination of radiosity and ray tracing produced quite satisfactory images´', mr. Kok concludes. `The drawback was, however, that ray tracing still involved long computation times.´
This is why he opted for another approach. Admittedly, again a combination of radiosity and ray tracing, but one based on the phenomenon that the geometry and `hardness´ of the shadow depend on the strength and orientation of the light source. Depending on the nature of the light source, the algorithm evolved by Mr. Kok applies a number of criteria to enable a choice to be made between the radiosity method and the ray tracing method for parts of the scene. In fact, the light source can also be a surface reflecting the light of a lamp. So, it is not 20% radiosity method and 80% ray tracing, but any ratio, depending on the light source.
`The great advantage is that you can adapt the image to your requirements´, Mr. Kok points out. `In one case you cast a great many rays -ray tracing-, while the next time it's the radiosity method only. For instance, when the distance to the scene is great, you shoot fewer rays. If you zoom in on the scene, you have to throw more rays to obtain a more realistic image.´
Another advantage is that the meshing technique is no longer of crucial importance to the radiosity method. When the radiosity technique threatens to fail, ray tracing simply takes over shadow rendering. This also reduces the computation time needed to generate an image.

Far ahead
One can conclude that Mr. Kok's new algorithm is a smart combination of two image-rendering techniques. A combination which enhances the images without increasing computation time. Mr. Kok is still unable to equal the subtle play of light and shadow of Vermeer's paintings, but the algorithm certainly is another step in the direction of more realistic image formation. The graphics he produces are well ahead of what most people have in mind when they think of computer images.

For more information on this subject please contact Dr. A.J.F. Kok, phone +31 40 247 3549, E-mail: a.j.f.kok@tue.nl.