Improved Algorithms for Fast Shading and Lighting

Shading is a technique that is used in computer graphics to make faceted objects appear smooth and more realistic. In the research presented in this thesis we have investigated how shading can be generated as efficiently as possible without sacrificing quality. In the classical approach to high quality shading proposed by Phong, the illumination equation is computed per pixel using an interpolated normal. The normals at the vertices are bi-linearly interpolated over the polygon to obtain a normal per pixel. Correct shading requires normalization of these normals, which is computationally demanding involving a square root. In our research we have shown how this normalization can be eliminated through the use of spherical interpolation and the Chebyshev recurrence formula, reducing the calculation to a few single arithmetic operations per pixel. Still a substantial setup operation is needed for each scanline. We have studied how also this can be made more efficient, with some limited progress so far. An alternative approach is to do the most of the setup on polygon level and incrementally compute the setup needed per scanline. In particular, we have studied quadratic shading approaches, i.e. fitting second degree surfaces to the polygons. The most successful approach has been through what we have called X-shading, where the setup is calculated by using an efficient approximation for the mid-edge normals. This setup is about four times faster than previously known methods. In the process of studying shading methods we have also made some contributions to improving bump-mapping and simulation of different kinds of light sources. The developed methods will be of interest in future generations of computer graphics software and hardware systems, ranging from high end systems to generate realistic movies and 3D games, to handheld devices such as mobile phones with graphics displays