Spatial transformations for rapid scan-line surface shadowing

A novel approach to surface shadowing is presented that is based on a parallel solution to the hidden-surface (visibility) problem. The approach computes visibility along scan lines of a spatial transformation of the surface height data. The transformation aligns in scan lines all potentially occluding points on the surface, allowing rapid 1-D determination of whether a point can be seen by the light source. Using this approach, arbitrarily defined surfaces can be shadowed very much more quickly than by conventional methods; a 512×512 surface image can be shadowed in less than 30 s on a MicroVAX II. The method also provides an efficient preprocessor for realistic 3-D scene synthesis, allowing the marking of shadowed pixels to eliminate unnecessary diffuse and specular reflection computations