A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> Texture-map computations can be made tractable through use of precalculated tables which allow computational costs independent of the texture density. The first example of this technique, the “mip” map, uses a set of tables containing successively lower-resolution representations filtered down from the discrete texture function. An alternative method using a single table of values representing the integral over the texture function rather than the function itself may yield superior results at similar cost. The necessary algorithms to support the new technique are explained. Finally, the cost and performance of the new technique is compared to previous techniques. <s> BIB001 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> The applications of texture mapping in computer graphics and image distortion (warping) in image processing share a core of fundamental techniques. We explore two of these techniques, the two-dimensional geometric mappings that arise in the parameterization and projection of textures onto surfaces, and the filters necessary to eliminate aliasing when an image is resampled during texture mapping or warping. With respect to mappings, this work presents a tutorial on three common classes of mapping: the affine, bilinear, and projective. For resampling, this work develops a new theory describing the ideal, space variant intialiazing filter for signals warped and resampled according to an arbitrary mapping. Efficient implementations of the mapping and filtering techniques are discussed and demonstrated. <s> BIB002 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> ``Bump'''' mapping is a variant of texture mapping where the texture information is used to alter the surface normal. Current techniques to pre-filter textures are all relying on the fact that the texture information can be linearly "factored out" of the shading equation, and therefore can be pre-averaged in some way. This is not the case with bump maps, and those techniques fail to filter them correctly. We propose here a technique to pre-filter bump maps by building a pyramid where each level stores distributions of normal vectors reconstructed from the distribution given by the underlying bump map. The distributions are represented as sums of a small number of Phong-like spreads of normal vectors. The technique, besides allowing an effective and smooth transition between a bump map and a single surface description, gives rise to the concept of a multiple surface, where each point of the single surface is characterized by more than one normal vector. This allows the description of visually complex surfaces by a trivial modification of current local illumination models. When a surface has an underlying microstructure, masking and self-shadowing are important factors in its appearance. Along with the filtering of normals we include the filtering of the masking and self-shadowing information. This is accomplished by computing the limiting angles of visibility and their variance along the two texture axes for the reconstructed distribution of normals. These techniques allow the modeling of any surface whose microstructure we can model geometrically. This includes complex but familiar surfaces such as anisotropic surfaces, many woven cloth, and stochastic surfaces. <s> BIB003 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> Logic embedded memory is an emerging technology that combines high transfer rates and computing power. Texram implements this technology and a new filtering algorithm to achieve high speed, high quality texture mapping. Integrating arithmetic units and large memory arrays on the same chip and thus exploiting the enormous internal transfer rates provides an elegant solution to the memory access bottleneck of high quality texture mapping. Using this technology, we can not only achieve higher texturing speed at lower system costs, we can also incorporate new functionalities such as detail mapping and footprint assembly to produce higher quality images at real time rendering speeds. Environment and video mapping are also integrated on the Texram, which therefore represents an autonomous and versatile texturing coprocessor. Logic enhanced memories might become the computing paradigm of the future, not just in graphics applications. Technological advances will foster this trend by providing an ever increasing amount of memory capacity and chip space for arithmetic units. As the ultimate solution, we can expect a complete 3D graphics pipeline including all memory systems integrated on a single chip. <s> BIB004 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> Texture mapping using trilinearly filtered mip-mapped data is efficient and looks much better than point-sampled or bilinearly filtered data. These properties have made it ubiquitous: trilinear filtering is offered on a $99 Nintendo 64 video game unit and on a multimillion dollar SGI InfiniteReality. But trilinear filtering represents the projection of a pixel filter footprint from screen space into texture space as a square, when in reality the footprint may be long and narrow. Consequently, trilinear filtering severely blurs images on surfaces angled obliquely away from the viewer. This paper describes a new texture filtering technique called Feline (for Fast Elliptical Lines). Like other recent hardware anisotropic filtering algorithms, Feline uses an underlying space-invariant (isotropic) filter with mipmapped data, and so can be built on top of an existing trilinear filtering engine. To texture a pixel, it uses this space-invariant filter at several points along a line in texture space, and combines the results. With a modest increase in implementation complexity over earlier techniques, Feline more accurately matches the desired projection of the pixel filter in texture space, resulting in images with fewer aliasing artifacts. Feline’s visual quality compares well against Elliptical Weighted Average, the best efficient software anisotropic texture filtering algorithm known to date, but Feline requires much less setup computation and far fewer cycles for texel fetches. Finally, since it uses standard mip-maps, Feline requires minimal extensions to standard 3D interfaces like OpenGL. <s> BIB005 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> Anisotropic filtering has been developed as a way of increasing the quality of texture mapping. However, a real hard-ware implementation of anisotropic filters implies approximations and simplifications that result in lower quality. In this paper we present a new, efficient hardware oriented anisotropic filtering technique. Specifically, the new algorithm we propose is based on the utilisation of a new distance computation method. This distance generation scheme permits simplification of the algorithm without reducing its quality. Additionally, a classification procedure for the identification of the position of each texel inside the footprint is proposed. This simple procedure permits the reduction of the computational requirements associated with the algorithm. We also present a new method for the computation of the coverage of a texel, based on the storage of a reduced set of possible coverage patterns. The new distance scheme obtains the patterns of all texels from a given texel through simple shift operations. The good quality results obtained with the filtering algorithm we propose, together with the low computational and storage requirements of the architecture we present, makes it a good candidate for hardware implementation. <s> BIB006 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> Shadow maps are a widely used shadowing technique in real time graphics. One major drawback of their use is that they cannot be filtered in the same way as color textures, typically leading to severe aliasing. This paper introduces variance shadow maps, a new real time shadowing algorithm. Instead of storing a single depth value, we store the mean and mean squared of a distribution of depths, from which we can efficiently compute the variance over any filter region. Using the variance, we derive an upper bound on the fraction of a shaded fragment that is occluded. We show that this bound often provides a good approximation to the true occlusion, and can be used as an approximate value for rendering. Our algorithm is simple to implement on current graphics processors and solves the problem of shadow map aliasing with minimal additional storage and computation. <s> BIB007 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> Shadow computation in dynamic scenes under complex illumination is a challenging problem. Methods based on precomputation provide accurate, real-time solutions, but are hard to extend to dynamic scenes. Specialized approaches for soft shadows can deal with dynamic objects but are not fast enough to handle more than one light source. In this paper, we present a technique for rendering dynamic objects under arbitrary environment illumination, which does not require any precomputation. The key ingredient is a fast, approximate technique for computing soft shadows, which achieves several hundred frames per second for a single light source. This allows for approximating environment illumination with a sparse collection of area light sources and yields real-time frame rates. <s> BIB008 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> Rendering high-quality shadows in real-time is a challenging problem. Shadow mapping has proved to be an efficient solution, as it scales well for complex scenes. However, it suffers from aliasing problems. Filtering the shadow map alleviates aliasing, but unfortunately, native hardware-accelerated filtering cannot be applied, as the shadow test has to take place beforehand. ::: ::: We introduce a simple approach to shadow map filtering, by approximating the shadow test using an exponential function. This enables us to pre-filter the shadow map, which in turn allows for high quality hardware-accelerated filtering. Compared to previous filtering techniques, our technique is faster, consumes less memory and produces less artifacts. <s> BIB009 </s> A Survey of Nonlinear Prefiltering Methods for Efficient and Accurate Surface Shading <s> Algorithms <s> We present a real-time method for rendering global illumination effects from large area and environmental lights on dynamic height fields. In contrast to previous work, our method handles inter-reflections (indirect lighting) and non-diffuse surfaces. To reduce sampling, we construct one multi-resolution pyramid for height variation to compute direct shadows, and another pyramid for each indirect bounce of incident radiance to compute interreflections. The basic principle is to sample the points blocking direct light, or shedding indirect light, from coarser levels of the pyramid the farther away they are from a given receiver point. We unify the representation of visibility and indirect radiance at discrete azimuthal directions (i.e., as a function of a single elevation angle) using the concept of a "casting set" of visible points along this direction whose contributions are collected in the basis of normalized Legendre polynomials. This analytic representation is compact, requires no precomputation, and allows efficient integration to produce the spherical visibility and indirect radiance signals. Sub-sampling visibility and indirect radiance, while shading with full-resolution surface normals, further increases performance without introducing noticeable artifacts. Our method renders 512x512 height fields (> 500K triangles) at 36Hz. <s> BIB010
The problem of prefiltering a texture k x to efficiently evaluate its weighted average k A in the footprint A with (10) has been extensively studied. The main problem is to approximate an almost arbitrary footprint A with a finite number of predefined footprints. A common solution is to use nested footprints. MIP-maps  use predefined nested footprints given by a quadtree. Summed Area Tables BIB001 , or SAT, use all the rectangles whose bottom left corner is the one of the texture. They are more flexible than MIP-maps but require floating point numbers (unlike MIP-maps, they do not store bounded averages, but potentially unbounded sums-as the name implies). Also, their accuracy is orientation dependent, yielding annoying sharpness oscillations when the surface rotates. Both methods compute k A with a small and constant number of arithmetic operations. But they are limited to a box filter w, with axis aligned square or rectangle footprints. However, in general, a footprint is trapezoidal or elliptical BIB002 , not axis aligned, and w is a more complex filter less prone to aliasing than the box filter. In this case, k A can be approximated by using a (weighted) decomposition of A into a small number of square footprints  , BIB004 , BIB005 . Some methods are now efficiently implemented in hardware BIB004 , BIB006 . It is therefore tempting to take advantage of this hardware acceleration, even for maps used in a nonlinear way for rendering. This is one of the reasons why the methods to prefilter these maps generally try to reformulate them in terms of new parameters that can be linearly filtered. The normal map filtering algorithms can be separated in two groups: those using a single lobe to represent an NDF, and those using multiple lobes. Fournier BIB003 represents the HDF p A ð; i Þ for each azimuth i with its mean A ð i Þ and standard deviation A ð i Þ. As seen in Section 3, these parameters can be linearly MIP-mapped and interpolated, by storing the second moment instead of Fig. 2 . Normal map prefiltering. Prefiltering the normals (black arrows) of a complex surface (bottom) quickly gives an unnormalized average vertical normal (blue) that does not accurately represent the surface (e.g., seen from space an ocean looks flat but does not reflect light like a mirror). Instead, the solution is to prefilter normal distribution functions (gray lobes). The problem is then to find compact, accurate, and linearly interpolable NDF representations. Fig. 3 . Horizon map prefiltering. A horizon map contains horizon elevation angles (black lines) for each azimuthal direction (figure plane). It can be used to compute the remote visibility of points on a complex surface (bottom). Since visibility is a nonlinear function of these angles, a horizon map cannot be linearly interpolated or prefiltered. A solution is to prefilter horizon angle distributions, or HDF (gray lobes). The problem is then to find compact, accurate, and linearly interpolable HDF representations. the standard deviation. Fournier then uses these prefiltered parameters to approximate (26) with a linear ramp going from He then uses an uncorrelation hypothesis to approximate the proportion of texels in the footprint A that are both visible and illuminated, with the product of the visible and illuminated texels proportions: In  where ¼ ð1 þ lvÞ=2. The min term corresponds to the maximum possible fraction of A that can be visible from both l and v. The max term corresponds to the minimum possible fraction. The term interpolates between the two to account for greater correlations when l and v are close (when l ¼ v, V A ðlÞ, and V A ðvÞ are fully correlated). In particular, this approximation correctly reproduces the hotspot effect, which is the fact that when l and v are aligned, all the self-shadows are masked to the viewer, and then all the visible areas are lit. Mathematically, this means that V A ðl; vÞ should be equal to 1 when l ¼ v. This is easily checked on (23) and on (28), but this is not the case with Fournier's method. This approximation also correctly reproduces the fact that if the area A is fully lit, i.e., if V A ðlÞ ¼ 1, then V A ðl; vÞ must be equal to 1. Again, this is easily checked on (23) and on (28), but this is not the case with Fournier's approximation. It should be noted here that Ashikmin et al.  , in the context of BRDF models, propose a similar approximation: where is a Gaussian of the angle between l and v. It is easy to check that this method also gives 1 when l ¼ v (hotspot effect), and when the area is fully lit. All above approximations correctly give V A ðl; vÞ ¼ V A ðlÞ when A is fully visible, i.e., when V A ðvÞ ¼ 1. Finally, we should also mention that among all the papers that use precomputed visibility functions on height fields, some use other representations that can be linearly MIP-mapped and interpolated to compute an average visibility over an arbitrary area (although this was not the primary goal of the authors). This is the case for instance of Nowrouzezahrai and Snyder BIB010 . Indeed, they decompose the Heaviside function in (24) on the linear basis of the normalized Legendre polynomialsP k , which gives The advantage of this decomposition is that the visibility function V x , which was a nonlinear function of the horizon map Â x , is now a linear function of the basis coefficients a k ðÂ x Þ. These coefficients can thus be linearly prefiltered to compute an average visibility: The advantage of their decomposition is that the visibility function U s , which was a nonlinear function of the depth map Z s , is now a linear function of the B k ðZ s Þ coefficients. These coefficients can thus be linearly prefiltered: In practice, Annen et al. decompose the Heaviside function with its Fourier series. This gives an expression with the form expected in (36): Annen et al. use 16 coefficients, which give 16 parameters per shadow map texel. This is not sufficient to avoid artifacts due to ringing (Gibbs phenomenon), but they propose scaling and offsetting methods to reduce these artifacts. This method can be extended to support soft shadows BIB008 . In another paper BIB009 , Annen et al. reuse the idea of decomposing H in separable terms of d and z. Instead of using a Fourier series, they simply approximate H with an exponential (Salvi  uses the same idea). Indeed, for c ) 1, expðcxÞ has a very steep slope near x ¼ 0 and quickly tends toward 0 for x < 0, like the step function H. This gives Here again, the advantage of this approximation is that the visibility function U s becomes a linear function of expðcZ s Þ. These warped depths can thus be linearly prefiltered, unlike the depth map Z s itself:  This gives antialiased hard shadows with only one parameter per shadow map texel. The problem of this approximation is that it diverges for d < Z s . Annen et al. propose some solutions to fix this. Lauritzen and McCool [45] propose to combine this exponential warping with its negative counterpart À expðÀcZ s Þ, together with Chebychev's inequality BIB007 . This solution avoids the divergence problem, but requires four parameters per shadow map texel-first and second moments for the warped ZDFs expðcZ s Þ and À expðÀcZ s Þ.