The presence of shadows in an image helps viewers to better understand the spatial relationships between objects, is vital for interactive applications such as Virtual Reality, and, in general increases the appearance of reality that a picture provides. Many shadow algorithms have been devised that adequately solve the problem, ranging from the very simple (point light sources and local illumination) to the very detailed and realistic (Radiosity and Ray-tracing). None of these existing algorithms, however, is suitable for interaction, at least on the standard hardware, because they require a total recalculation of the shadows for any change in the scene geometry.
In this thesis various methods are proposed for providing shadows in dynamic scenes, illuminated by point or area light sources. These methods exploit the temporal and spatial coherence present in interactive environments to provide incremental updates to the shadow information in a fraction of the time required by other algorithms.
A data structure used by all shadow algorithms in this thesis, because it provides an efficient space partitioning and searching tool, is the BSP tree. One of the perceived problems of the BSP trees is that they are only suitable for static scenes. An investigation is made into the use of BSP trees for representing dynamic scenes and practical solutions are suggested.
Using the results of the above study, two methods are presented for shadows in dynamic scenes illuminated by point light sources. The first uses a regular space subdivision by means of a tiled cube placed around the source. The second uses a Shadow Volume BSP tree built from the set of unsorted polygons.
For area light sources an algorithm is presented which is a combination of a tiling cube similar to that used for the point sources and the discontinuity meshing (DM) method used in Radiosity. The shadow boundaries as well as other irregularities in the illumination function of each surface in the scene are found and built into a mesh using BSP tree merging. The combination of the space subdivision provided by the tiling and the structured mesh building provided by the merging lead to a significantly faster DM algorithm compared the previous methods, which in addition allows for incremental updates after a change in the scene geometry.
Experimental results have shown that near real-time frame rates can be achieved using the above methods on commonly used workstations which do not have specialised 3-D graphics hardware.
The Thesis:The full document in pdf, gziped (1053kb).