A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> SHADOW MAP PREFILTERING <s> Shadows are advocated for improved comprehension and enhanced realism in computer-synthesized images. A classification of shadow algorithms delineates three approaches: shadow computation during scanout; division of object surfaces into shadowed and unshadowed areas prior to removal of hidden surfaces; and inclusion of shadow volumes in the object data. The classes are related to existing shadow algorithms and implementations within each class are sketched. A brief comparison of the three approaches suggests that the last approach has the most appealing characteristics. <s> BIB001 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> SHADOW MAP PREFILTERING <s> Shadowing has historically been used to increase the intelligibility of scenes in electron microscopy and aerial survey. Various methods have been published for the determination of shadows in computer synthesized scenes. The display of shadows may make the shape and relative position of objects in such scenes more comprehensible; it is a technique lending vividness and realism to computer animation. To date, algorithms for the determination of shadows have been restricted to scenes constructed of planar polygons. A simple algorithm is described which utilizes Z-buffer visible surface computation to display shadows cast by objects modelled of smooth surface patches. The method can be applied to all environments, in fact, for which visible surfaces can be computed. The cost of determining the shadows associated with each light source is roughly twice the cost of rendering the scene without shadows, plus a fixed transformation overhead which depends on the image resolution. No extra entities are added to the scene description in the shadowing process. This comprehensive algorithm, which permits curved shadows to be cast on curved surfaces, is contrasted with a less costly method for casting the shadows of the environment on a single ground plane. In order to attain good results, the discrete nature of the visible-surface computations must be treated with care. The effects of dither, interpolation, and geometric quantization at different stages of the shadowing algorithm are examined. The special problems posed by self-shadowing surfaces are described. <s> BIB002 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> SHADOW MAP PREFILTERING <s> We introduce deep shadow maps , a technique that produces fast, high-quality shadows for primitives such as hair, fur, and smoke. Unlike traditional shadow maps, which store a single depth at each pixel, deep shadow maps store a representation of the fractional visibility through a pixel at all possible depths. Deep shadow maps have several advantages. First, they are prefiltered, which allows faster shadow lookups and much smaller memory footprints than regular shadow maps of similar quality. Second, they support shadows from partially transparent surfaces and volumetric objects such as fog. Third, they handle important cases of motion blur at no extra cost. The algorithm is simple to implement and can be added easily to existing renderers as an alternative to ordinary shadow maps. <s> BIB003 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> SHADOW MAP PREFILTERING <s> Opacity shadow maps approximate light transmittance inside a complex volume with a set of planar opacity maps. A volume made of standard primitives (points, lines, and polygons) is sliced and rendered with graphics hardware to each opacity map that stores alpha values instead of traditionally used depth values. The alpha values are sampled in the maps enclosing each primitive point and interpolated for shadow computation. The algorithm is memory efficient and extensively exploits existing graphics hardware. The method is suited for generation of self-shadows in discontinuous volumes with explicit geometry, such as foliage, fur, and hairs. Continuous volumes such as clouds and smoke may also benefit from the approach. <s> BIB004 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> SHADOW MAP PREFILTERING <s> Recent advances in GPU technology have produced a shift in focus for real-time rendering applications, whereby improvements in image quality are sought in addition to raw polygon display performance. Rendering effects such as antialiasing, motion blur and shadow casting are becoming commonplace and will likely be considered indispensable in the near future. The last complete and famous survey on shadow algorithms — by Woo et al. 52 in 1990 — has to be updated in particular in view of recent improvements in graphics hardware, which make new algorithms possible. This paper covers all current methods for real-time shadow rendering, without venturing into slower, high quality techniques based on ray casting or radiosity. Shadows are useful for a variety of reasons: first, they help understand relative object placement in a 3D scene by providing visual cues. Second, they dramatically improve image realism and allow the creation of complex lighting ambiances. Depending on the application, the emphasis is placed on a guaranteed framerate, or on the visual quality of the shadows including penumbra effects or “soft shadows”. Obviously no single method can render physically correct soft shadows in real time for any dynamic scene! However our survey aims at providing an exhaustive study allowing a programmer to choose the best compromise for his/her needs. In particular we discuss the advantages, limitations, rendering quality and cost of each algorithm. Recommendations are included based on simple characteristics of the application such as static/moving lights, single or multiple light sources, static/dynamic geometry, geometric complexity, directed or omnidirectional lights, etc. Finally we indicate which methods can efficiently exploit the most recent graphics hardware facilities. <s> BIB005
The average visibility U A ðl; vÞ in (9), i.e., the proportion of texels in the footprint A that are not shadowed by objects other than S, can be computed with many methods: shadow volumes BIB001 , shadow maps BIB002 , deep shadow maps BIB003 , opacity shadow maps BIB004 , etc. A survey of these methods can be found in BIB005 and  . Here, we consider only the case of shadow maps BIB002 , for which nonlinear prefiltering methods are needed, and have been proposed. A shadow map is a depth map of the scene, computed from the point of view of a punctual light source. Then, a binary depth test suffices to compute shadows: a point x is lit by this source if and only if its depth is less than or equal to the depth stored in the shadow map (see Fig. 4) . A shadow map cannot be directly prefiltered: the average number of lit texels in a footprint A cannot be computed from their average depth, because the depth test is a nonlinear function of these depths. As shown below,  one solution is to prefilter instead the probability distribution of these depths, that we call here a depth distribution function, or ZDF. The problem is then to find compact, accurate, and linearly interpolable ZDF representations. Before presenting the methods that have been proposed for that, we present the hypothesis made by all these methods, sometimes implicitly.