Repositorio Institucional de Documentos

2012 27 Fernando Navarro Gil Optimization techniques for computationally expensive rendering algorithms Departamento Director/es Informática e Ingeniería de Sistemas Gutiérrez Pérez, Diego Serón Arbeloa, Francisco Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Fernando Navarro Gil OPTIMIZATION TECHNIQUES FOR COMPUTATIONALLY EXPENSIVE RENDERING ALGORITHMS Director/es Informática e Ingeniería de Sistemas Gutiérrez Pérez, Diego Serón Arbeloa, Francisco Tesis Doctoral Autor 2012 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA OPTIMIZATION TECHNIQUES FOR COMPUTATIONALLY EXPENSIVE RENDERING ALGORITHMS luis fernando navarro gil Supervisors: dr.diego gutiérrez dr.francisco josé serón Grupo de Informática Gráfica Avanzada Dpto. de Ingeniería de Sistemas e Informática Universidad de Zaragoza April 2012 Luis Fernando Navarro Gil: Optimization techniques for computationally expensive rendering algorithms, © April 2012 ACKNOWLEDGMENTS I have been lucky enough to meet exceptional people, whose knowledge and personal values are first-class. That is why there are many individuals that have been instrumental in this thesis and should share part of the merit. The people from Lionhead Studios, Microsoft Games Studios and Telefonica I+D have been extremely welcoming, encouraging and have offered invaluable technical advises. A list of names will surely be incomplete, that is why I would rather thank all of them, instead of leaving a single one out. The members of the Graphics and Imaging Lab of the University of Zaragoza, for their support, advises and insightful comments. Among them, I want to thank the directors of this thesis, Diego Gutiérrez and Francisco Serón, for accepting my proposal, steering my efforts and adapting their schedules to the pace imposed by my other compromises. To my friends for their supportive attitude. Even after my frequently unspecific explanations, they managed to show interest and make fun of what I decided it was going to be a serious hobby for the next few years. My parents, for patiently listening the details of what was occupying my spare time. They helped me see the bigger picture when my reports were limited to news of a somehow unclear advance. And to my brother, Joaquin and his fiancée Xenia, for making up amusing conversations that gave me the opportunity to think about so many other different topics. Finally, to Alicia, who has provided limitless support during these years of work. She has being considerate and patient even when my time and attention were diverted. You understood my passion and figure out were the value of beautiful images reside. v 800 balas, Goya Awards 2002, Best special effects. R&D Supervisor. Los otros, Goya Awards 2001, Nomination to the Best special effects. R&D Supervisor. In association with Microsoft Games Studios, I have generated intellectual property that is the process of being patented: IPCOM000195648D, Rig proportion tool: Tool to reproportion rigs and reuse animations. May 2010. I have been lecturer at several conferences on game and visual effects development: What they did not tell you about game development: Lessons learnt with Fable. VII MillaGame, Milla Digital, Ayuntamiento de Zaragoza. December 2011. Current trends in game development, and How to get a job in a game company. MAaster in Video game production, Universidad de Zaragoza. December 2011. Animation methods. Autodesk 3December launch party, London. December 2008. Animation and rendering. Universidad de La Coruña. September 2005. VFX in The Incredibles, Star Wars and The Lord of the rings: Why and how. Universidad de verano de Jaca. July 2005. Management and Optimization in 3D production with proprietary tools: SoftBren. Mundos digitales, La Coruña. July 2005. Development of a 3D production. Universidad de verano de Teruel. June 2005 3D Animation. Xuventude Galicia Net, Santiago de Compostela. April 2004. Technical aspects in visual effects and animation. Universidad de Santiago de Compostela. October 2005 VFX creation and new technologies. Centro Cultural Ibercaja, Zaragoza. April 2005. Engineers in animation and visual effects. JETAI 2003. Centro Politécnico Superior, Universidad de Zaragoza. March 2003. Lecturer at several editions of the courses: Computer Graphics, User-machine interaction and Visual modeling and animation. Universidad de Zaragoza, between 2001 and 2006. Two open source developments have attracted the attention of the professional visual effects community: fnPeltMapper, first UV automatic unwrapping tool for Autodesk Softimage XSI. Based on [ 137 ]. 15000 downloads from highend3d.com. fnDualQuaternion, first dual quaternion deformation plugin for Autodesk Softimage XSI. Based on [ 113 ]. 5000 downloads from highend3d.com CONTENTS 1 introduction 1 1.1The proposals 1 1.2Structure 2 i accelerating volume rendering 5 2 gpu accelerated rendering of participating media 7 2.1Previous work 8 2.1.1Traditional models 8 2.1.2Real time rendering 9 2.2Lighting model 9 2.2.1Lighting environment 9 2.2.2Light transport 10 2.3Implementation details 11 2.3.1Distance based optimization 12 2.3.2Validity mask 13 2.3.3Ray marching passes 15 2.4Results 17 2.5Conclusions 19 ii accelerating antialiasing rendering 23 3 morphological antialiasing 25 3.1Previous work 26 3.1.1Edge antialiasing 26 3.1.2Aliasing in textures 26 3.1.3Real time multisampling 27 3.1.4Postproduction 28 3.2Overview 29 3.3Algorithm structure 29 3.4Pass #1: Detecting Edges 30 3.5Pass #2: Blending Weights 31 3.5.1Searching for Distances 32 3.5.2Fetching Crossing Edges 33 3.6Pass #3: Blending with the 4-neighborhood 33 3.7Results 34 3.8Conclusion 34 iii accelerating motion blur rendering 39 4 motion blur rendering:state of the art 41 4.1Origin of the phenomenon 41 4.2Formalization of the motion blur problem 44 4.3Motion blur rendering algorithms 45 4.3.1Overview 45 xvii 4.3.2Analytic methods 46 4.3.3Geometric substitution 48 4.3.4Texture clamping 52 4.3.5Monte Carlo methods 53 4.3.6Postprocessing 62 4.3.7Hybrid methods 66 4.3.8 Mechanical, optical and sensory inspired models 69 4.4Method comparison 71 4.5Future directions 74 4.6Conclusion 75 5 perceptual considerations for motion blur rendering 77 5.1Previous work 78 5.1.1Perception of motion blur 80 5.1.2 Technical aspects of motion blur perception 80 5.2Algorithmic model 81 5.3Description of the stimuli 82 5.4Perceptual tests: Overview 85 5.5Test #1: Broad comparison 86 5.5.1Description 86 5.5.2Results 87 5.6 Test #2: Tolerance to variations in shutter time and antialiasing level 88 5.6.1Description 89 5.6.2Results 89 5.6.3 Discounting the effects of memory and matching ability 90 5.7 Test #3: Interactions between shutter time and sampling level 92 5.7.1Description 92 5.7.2Results 92 5.8Conclusions and future directions 94 6 influence of stereo vision on motion blur perception 97 6.1Previous work 97 6.1.1Stereo vision 97 6.1.2Displays and visual confort 98 6.1.3Stereo artifacts and image quality 99 6.1.4Rendering optimizations 100 6.2Description of the stimuli 101 6.2.1Stereo pairs 102 6.2.2Monte Carlo, noise and stereo 102 6.3Perceptual tests: Overview 103 6.4Test #1: Broad comparison 104 6.5 Test #2: Tolerance to variations in shutter time and antialiasing level 106 6.5.1Description 107 6.5.2Results 107 6.6 Test #3: Interactions between shutter time and sampling level 110 6.6.1Description 110 6.6.2Results 110 6.7Conclusions and future directions 112 6.8Final remaks 113 iv conclusions 115 7 conclusions 117 7.1Volumetric rendering 117 7.2Screen space anti-aliasing 118 7.3Motion blur rendering 118 7.4Final remarks 120 8 conclusiones 121 8.1Render volumétrico 121 8.2Antiasing en espacio de pantalla 122 8.3Cálculo de motion blur 123 8.4Notas finales 125 bibliography 127 LIST OF FIGURES Figure 2.1Distance map optimization. 12 Figure 2.2Pixel validity mask. 14 Figure 2.3Lighting models. 18 Figure 2.4Extinction coefficients. 20 Figure 2.5 Smoke datasets rendered using different light probes. 21 Figure 3.1 Aliased image, edgels texture, blending weights and antialiased result. 30 Figure 3.2 Antialiasing process and precomputed areas texture. 31 Figure 3.3Distance computation. 32 Figure 3.4Crossing edges. 33 Figure 3.5 Examples without antialiasing, MLAA and MSAA 35 Figure 3.6Images processed with MLAA 36 Figure 3.7Images processed with MLAA 37 Figure 4.1Photographic motion blur. 42 Figure 4.2Method of Korein and Badler. 47 Figure 4.3Motion blurred particle systems. 49 Figure 4.4 Real time motion blur using the technique of Tatarchuck et al. 50 Figure 4.5 Motion trails computed the technique of Schmid et al. 51 Figure 4.6Motion blur in point sampled rendering. 52 Figure 4.7Distribution ray tracing. 54 Figure 4.8Effect of different reconstruction filters. 55 Figure 4.9Photon mapped motion blur. 57 Figure 4.10 Multidimensional light cuts and motion blur. 58 Figure 4.11 Accumulation buffer. 59 Figure 4.12 Frameless rendering 59 Figure 4.13 Eulerian motion blur. 61 Figure 4.14 Deep shadow maps. 62 Figure 4.15 Method of Potmesil. 63 Figure 4.16 Postprocessed motion blur using the technique of Brostow and Essa. 64 Figure 4.17 Use of optical flow to render motion blur. 65 Figure 4.18 Real time motion blur using the technique of Shimizu et al. 66 Figure 4.19 Multiple effects rendered with the REYES architecture. 68 Figure 4.20 Photo-consistent motion blur. 70 Figure 5.1 Stimuli matrix: shutter times and sampling levels. 78 xx Figure 5.2 Detailed view of different render parameters. 79 Figure 5.3 Variations of materials and object speeds. 84 Figure 5.4 Animations perceived with higher quality. 87 Figure 5.5 Results of the matching tasks using shutter speeds and antialiasing levels. 89 Figure 5.6 Perceptual groups associated with different antialiasing levels and shutter times. 93 Figure 5.7Pair of perceptually equivalent renders. 94 Figure 5.8 Second pair of perceptually equivalent renders. 95 Figure 6.1Example of a stereo pair. 98 Figure 6.2 High quality stereo pair and absolute pixel differences. 101 Figure 6.3 Low quality quality stereo pair and absolute pixel differences. 102 Figure 6.4Perceived quality for stereo stimuli. 105 Figure 6.5 Comparison of the answers for mono and stereo stimuli. 106 Figure 6.6 Stimuli used test #2(shutter time) grouped in perceptually equivalent groups. 108 Figure 6.7 Stimuli used test #2(sampling level) grouped in perceptually equivalent groups. 109 Figure 6.8 Stimuli combining sampling level and shutter times grouped in perceptually equivalent groups. 111 Figure 6.9Perceptually equivalent stereo pairs. 113 LIST OF TABLES Table 2.1Frames per second (speed ups) 19 Table 3.1Execution times. 38 Table 4.1Motion blur rendering methods 43 Table 5.1 Dimensions and values considered in the study. 83 Table 5.2 Psychophysical tests completed by the participants in the study. 86 Table 6.1 Psychophysical tests completed by the participants in the stereo study. 104 xxi Table 6.2Number of votes per sequence. 108 LISTINGS Listing 2.1Slice sampling pseudocode. 16 2 GPU ACCELERATED RENDERING OF PARTICIPATING MEDIA Rendering participating media is one of the most computationally intensive processes in computer graphics. Light transport relies on the simulation of scattering, absorption and emission and is commonly based on the Radiative Transfer Equation (RTE) [ 38 ] [ 102 ]. However, this model is expensive to evaluate and in order to make it tractable, it needs to be approximated using simplified versions of the original phenomena. Just a few approaches can efficiently solve the mathematical expressions associated with the RTE. Among them, the ray marching algorithm is probably the most popular. This method solves the multidimensional integral equations of the RTE incrementally. However, even in cases where it is accelerated using techniques such as volume photon mapping, it cannot be evaluated in real time. Alternatively, interactive rendering has relied on ad-hoc methods that rely on precomputation or impose severe restrictions to the underlying model. Except for a few exceptions, high quality results are reserved to offline frameworks. In this chapter, we describe an interactive system to light and render participating media by solving an approximation of the Radiance Transfer Equation. We use two novel optimizations that allow evaluating the ray marching algorithm as GPU shaders executed as a series of passes. Interactive frame rates are achieved using a view dependent technique that reduces the number of pixels processed, and a view independent empty space skipping technique that allows speeding up volume traversals. The method is original as it uses HDR maps to define environment lighting. These are efficiently sampled by transforming them into a light constellation. In our method, participating media is characterized as volumetric data obtained by sweeping a laser sheet through a volume of real smoke using the method of Hawkins, Einarsson and Debevec [ 93 ]. However, since it is general enough, it has also been applied to data generated using numerical simulation. None of these steps are required to be precomputed nor are based on predetermined illumination models. As a consequence, the system can handle time-varying participating media, single scattering including self shadowing, free camera movement and dynamic lighting where the incident light field can be arbitrarily rotated. The following sections are organized as follows. In section 2.1, we briefly present an overview of traditional volume rendering tech7 8 gpu accelerated rendering of participating media niques and recent GPU based implementations. Section 2.2describes the lighting model based on the Radiative Transfer Equation. The implementation details are covered in section2.3. Finally, section 2.4 and 2.5present the results, a brief discussion on the limitations and future directions. 2.1 previous work Light transport in participating media has been a topic of intense research. An important part of the effort has been focused on different methods for solving the radiative transfer equation (RTE) [38] [102]. 2.1.1Traditional models A number of analytic solutions have been described, but they are frequently based on strong simplifications such as assuming homogeneous [ 14 ] and optically thick media [ 165 ] or infinitelly distant light sources [151]. Numerical simulation approaches are based on evaluating the radiance transport integral [ 111 ] [ 212 ] [ 232 ]. By sampling points inside the media, stochastic methods like Monte Carlo path tracing [ 231 ], bidirectional path tracing [ 131 ] or photon mapping [ 104 ] can generate high quality results. They are capable of modelling complex phenomena including multiple scattering in inhomogeneous media but their cost is usually high: worst cases may involve computations of several hours per frame. Performance can be increased using precomputation combined with efficient storage. With these methods, results of certain calculations that depend on the light, the media or their interactions are baked so they can be reused at render time. By using pre-computed radiance transfer, Sloan et al. [ 228 ] handle complex lighting phenomena like soft shadows and scattering. Other methods use pre-calculated forward multiple scattering [ 91 ], pre-integrated lighting [ 257 ], spherical harmonics for fourier volume rendering [ 67 ], precalculated transmission integrals [ 96 ] or reuse light scattering paths in a particle system [ 239 ]. Recently, Zhou uses a set of radial basis functions to convert the media into an equivalent sparse representation [ 287 ]. With all the benefits of these methods, interactivity is limited to static camera positions, specific transfer functions or prefixed light types. Furthermore, rendering data sets containing a sequence of frames requires precomputation on each of them. An overview of the existing techniques and the mathematical background of the scattering phenomena can be found elsewhere [88]. 2.2 lighting model 9 2.1.2Real time rendering Implementations of interactive and real time volume rendering methods have become increasingly more popular after recent advances in graphics hardware. Since analytic solutions evaluate a closed set of mathematical formulas, they can be efficiently implemented using GPU shaders [ 236 ] [ 286 ]. These methods rely on precomputation, but other solutions are based on 2D texturing [66] or are not physically based [126]. There are a number of acceleration techniques designed to improve the efficiency of media sampling. Kruger and Westermann [ 126 ] describe an efficient streaming model over GPUs and implemented different acceleration techniques for volume ray-casting. Early ray termination is based on space classification structures and compression techniques: Guthe et al. use hierarchical wavelets [ 86 ], LaMar, Hamman and Joy [ 132 ] rely in an octree; Westermann and Senenich [ 271 ] use CPU precalculated 2D textures. Li, Mueller and Kaufman’s [ 138 ] empty space skipping technique avoids sampling areas that contain no data. Spatial and temporal data coherence has also been exploited [ 245 ] [ 118 ]. All these techniques set up acceleration structures in a precomputation step. Our intention is efficiently rendering time dependent participating media without significant pre-computation. This precludes the application of the previous methods. The solution we describe in the following sections relies on a physically based light transfer model capable of calculating single scattering with self shadowing. Two optimizations, based on the media rendered and the camera position, provide the extra acceleration required. Moreover, they do not use any pre-computed lighting nor depends on the illumination model or the environment. Acceleration structures and lighting can be calculated on the fly, therefore position and orientation of the environment and camera can be interactively changed. 2.2 lighting model 2.2.1Lighting environment High dynamic range maps are one of the most popular methods to represent lighting environments [ 203 ]. Several image-based algorithms have been developed based on well known Monte Carlo methods [ 112 ]. However, since they rely on intensive sampling of the irradiance map, they cannot be efficiently implemented on a GPU. Different techniques can convert these maps into spherical harmonics [ 196 ], light constellations [ 42 ] [ 148 ] or wavelets [ 172 ]. An environment represented with these alternatives can be efficiently sampled at the cost of using similar but not identical lighting conditions. Except 10 gpu accelerated rendering of participating media for wavelets, these representations can only include the low frequency components of the environment. For our purposes, this is a mild limitation as the phenomena involved in participating media tends to blur the effects of lighting [172]. The methods that produce light constellations replace areas of the irradiance image with individual light emitters, usually point or infinite directional lights. Among others, Cohen and Debevec’s [ 42 ] mediancut technique extracts a set of equal energy point lights, each of them representing areas with different sizes. Alternatively, K-means clustering [ 148 ] generates lights with different energy but with more regular spatial distribution. Similar algorithms have also been implemented in real time [120] [180]. Conversion to a finite number of sources benefits from deterministic sampling without the storage and complex representations of traditional techniques. At the same time, noise, the principal problem associated with stochastic methods, is eliminated and a desirable coherence over time is added. With such a representation, computing the light received from the environment is converted to repeating a finite number of times the same sampling that is required for a single emitter . All these characteristics make them specially suitable for a GPU based implementation. 2.2.2Light transport Once the light field has been computed, a solution to the light transport needs to be provided. Using the integral form of the RTE [ 38 ] [ 102 ], the radiance Lat a point xin direction ωcan be written as: L(x,ω) = τ(x0,x)L(x0,ω) +Zx x0 τ(u,x)κt(u)(1−Ω(u))Le(u,ω)du +Zx x0 τ(u,x)κt(u)Ω(u)ZS L(u,ωi)ρ(u,ω,ωi)dσωidu (2.1) where x and x0 are points in the <3 space, κt denotes the extinction coefficient and is the sum of the scattering κs and absorption κa coefficients, Ω(x) = κs(x)/κt(x) is the scattering albedo and Le(x , ω) is the radiance emitted by the media at point x in direction ω . S represents the set of directions on the sphere around point x , and the normalized phase function ρ(x , ω , ωi) determines the amount of the incident light arriving at x in direction ω that is scattered in direction ωi . τ(x0 , x) , the transmittance factor along the segment from x0 to x , is expressed as τ(x0,x) = e−Rx x0κt(ξ)dξ (2.2) 2.3 implementation details 11 The cost of computing Equation 2.1can be reduced by: first, discarding multiple scattering and considering a single scattering event at every point of the volume; second, assuming the media is isotropic; and third, using non emissive media. Single scattering makes the model accurate for low albedo or optically thin media only. An isotropic phase function ρ(x , ω , ωi) = 1 4π excludes participating media such as fog, smoke or clouds that show a strong forward scattering behaviour. However, the model could be easily extended to support anisotropic phase functions with reduced run-time cost [ 13 ]. Finally, common participating media does not emit light so the emission term Le(x , ω) can be safely discarded. With the previous assumptions and given that the lighting environment has been replaced by a finite set of N light emitters, Equation 2.1 can be transformed to: L(x,ω) = τ(x0,x)L(x0,ω) +Zx x0 τ(u,x)κt(u)Ω(u) 4π N X n=1 Lri(u,ωn)du (2.3) Where Lri(u , ωn) is the reduced incidence radiance [ 36 ] arriving at u in the direction of the nth light emitter . Finally, using small integration steps ∆x =x−x0 , the integral Equations 2.3and 2.2can be discretized as L(x,ω)≈τ(x0,x)L(x0,ω) +τ(x0,x)κt(x0)Ω(x0) 4π N X n=1 Lri(x0,ωn)∆x (2.4) τ(x0,x) = τ(x0,x0+∆x)≈e−κt(x0)·∆x (2.5) This Equation calculates the radiance arriving at a point x as a function of the radiance and media properties at a near point x0 . If eye is the viewer position and ωij is the direction from a pixel with coordinates (i , j) to the observer, then L(eye , ωij) can determine the radiance arriving at the observer from each of the image pixels. Given that the initial conditions at the furthest position in the media can be established, this formulation can be mapped to traditional back to front ray marching using ∆x increments. In the following sections we will explain the details on how Equation 2.4can be solved following this schema. 2.3 implementation details CPU based ray marching algorithms have been commonly used to display volumetric data. However GPU based implementations are 12 gpu accelerated rendering of participating media Figure 2.1: Distance map optimization: Left: One of the 256 slices of smoke from a volume data set. Middle: Distance map corresponding to this slice. Brighter regions corresponds to lower distances. Right: Volumetric representation of the whole distance map. not so frequent due to restrictions in the logic complexity and number of instructions in fragment programs. To overcome these limitations we use an OpenGL and Cg [176] multi-pass approach. The following section describes its implementation details. As an overview, our system performs the following steps: Initially, volumetric data is loaded from CPU to GPU memory. This data is represented as a 3D array of floating point voxels containing the density of the media. Its structure is analysed and a view independent distance map is computed. This map is used to accelerate media traversals. Taking into account camera position, a different pass builds a validity mask that helps eliminating computations on areas that will be empty in the final image. Once these two acceleration methods are set-up, a succession of passes solve Equation 2.4using back to front ray marching. Independently, every time the lighting is changed the existing light constellation is replaced by a new one that approximates the illumination of the new environment. In the absence of changes in the environment, the corresponding set of lights will be reused for different frames. The previous steps are performed using floating point arithmetic so a final tone mapping pass is required to display the final image. 2.3.1Distance based optimization The speed of memory accesses is one of the principal bottlenecks in existing GPU architectures . Shader performance is drastically reduced when more than just a few texture fetches are executed. Since the ray marching algorithm is based on intensively sampling the media and accesses lack spatial coherence, brute force implementations fail to run at interactive frame rates. In this section we describe a novel use of an optimization technique that, based on a distance map, drastically reduces the bandwidth requirements by skipping volume regions containing no data. 2.3 implementation details 13 A distance map determines, for each position x inside the volume, the distance δ(x) to the nearest non empty voxel. Other authors have used related approaches to calculate surface displacement [ 61 ] or compute geometry in shell space [ 207 ]. The novelty in our case is we apply this technique to optimize lighting calculations by accelerating primary and shadow ray traversals. Without loss of generality our implementation calculates the distance map as a preprocess but existing algorithms can calculate it in real time [49]. At runtime, for every sampling point, the next visited position is determined jumping a distance given by δ(x) in the sampling direction. The map stores scalar values without any directional information, so no cues on the exact location of the nearest non-empty voxel can be inferred. As such, each δ(x) identifies the radius of a sphere centered at x which contains empty data only. This is a conservative optimization, but given the memory constraints of the hardware framework and since we have observed important speed ups (see section 2.4), this seems to be a good tradeoff. Talking about data layout, the original density data and the distance map are stored in the red and green channels of the same 3D texture. This option doubles the memory footprint, but allows retrieving both values in the same instruction at no extra cost. The outcome between use floating-point or integer values is also clear. The images computed using low or high precision representations show neglectable differences but the performance of the rendering algorithm drops an order of magnitude when the most accurate representation is selected. 2.3.2Validity mask In this section we explain an optimization, implemented as a new pass, that uses the volume of data and the camera settings to determine which areas of the final image will be empty. The method follows each of the primary rays cast from the eye through the media, flagging the traversals that find non-transparent data. Once computed, a full rendering loop is executed for this subset of image pixels. This approach does not require performing any lighting calculations and uses the optimization described in the previous section. As a consequence it is lightweight to evaluate while the speed-ups associated are significant. Initially, using the method described by Kruger and Westermann [ 126 ], each pixel with coordinates (i , j) is assigned a pixel-to-eye direction ωij . A traditional slabs test [ 114 ] is used to determine Pnear and Pfar , the nearest and furthest intersections with the bounding box of the volume. Any pixels which do not define intersections are discarded for further computations. The sampling strategy is based on using shells or spherical slices centered at the camera position [ 84 ]. Although this technique eliminates the need for perspective correction, it requires building proxy 14 gpu accelerated rendering of participating media Figure 2.2: Values generated by pixel validity mask pass: From left to right: Smoke volume being rendered, pixel validity mask showing red pixels for those fragments containing valid information and color representation of index of first slice containing non transparent data (iFirst). geometry containing segmented data. That is one of the reasons why it has been traditionally reserved to cases where extreme viewports were used [ 66 ]. Our method does not create any geometry at all as shells are implicitly represented in the mathematical formulae that calculates the position of each sampling point. Each of these positions are found after intersecting a ray with an sphere using their corresponding analytic representations. Slices are i∆slice units away from the camera position, with i being the index of the slice and ∆slice the distance between them. To prevent aliasing artifacts ∆slice is chosen to be smaller than half the side of a voxel. However, given the data varies smoothly, is trilinearly filtered by the hardware and the mask is not directly visible, this value can be relaxed and more sparse sampling can be used. We have found that, in some cases, up to one slice every five voxels can yield good results. iNear =ceil(|Pnear −eye|/∆slice)(2.6) iFar =floor(|Pfar −eye|/∆slice)(2.7) In order to determine which ray directions will generate empty image pixels, ray marching is performed in back to front order. The indexes of the nearest and furthest slices inside the bounding box are calculated using Equations 2.6and 2.7. During the traversal from iFar to iNear , a direction is tagged as containing data as soon as a density value above a given threshold are found. The index of the corresponding slice is noted as iFirst . To improve performance the process is accelerated using the technique explained in section 2.3.1. This pass outputs a half floating point RGBA image composed of each pixel’s normalized ray direction ωij (RGB components) and iFirst index (alpha component). The later is set to -1for pixels with no data nor bounding box intersection associated. In Figure 2.2we can see a false color representation of the validity mask and the first slice index. 2.3 implementation details 15 It is worth noting that both the validity mask and the distance map make no assumptions on the underlying physical model and are calculated before any light computations are started. This is an important improvement respect to other acceleration methods that only generate time reductions at the cost of making them dependent on specific types of physical phenomena. The single scattering model explained in previous sections it is just a convenient example and a proof of concept. Since our optimizations focus on speeding up traversals and reducing the number of fragments to be calculated, the heavier the computation imposed by the lighting model, the bigger will be the speed-ups associated with our technique. 2.3.3Ray marching passes The radiance arriving to the observer from each of the pixels in the image plane L(eye , ωij) is the main magnitude that needs to be determined to solve the lighting of the participating media. This section explains the details of the Cg fragment program that computes it. The initial steps of the lighting pass perform a quick test on the validity mask to avoid undesired computations. As soon the pixel is known not to contain data, evaluation of the shader is stopped and a transparent pixel is returned. For the remaining pixels, a primary ray is marched from the position corresponding to iFirst slice in the ωij direction in ∆slice increments. This traversal is continued until the ray exits the bounding box. At each point x , a shadow ray is followed from each of the N light emitters to the sampling point itself. Since this ray accounts for absorption and scattering, self shadowing effects are included in the final image. We assume the space surrounding the bounding box is empty so the target radiance L(eye , ωij) is L(Pnear , ωij) , the radiance measured where the ray exits the bounding box. Program 2.1shows pseudocode that performs lighting calculations on the slice with index iSlice . The parameters vol3D , rayDir and pathRad refer respectively to the 3D texture containing the density data and distance maps, ray direction ωij and path radiance accumulated in previous slices. x and x_uvw are the sampling point global and texture space coordinates. The function GetIntersection returns the intersection of the slice iSlice and the ray starting at eye with direction rayDir . τ(x , x+∆x) is returned by Transmittance , whilst κt(x) and Ω(x) are calculated by Extinction and ScattAlbedo . All three functions are internally implemented as lookup tables, calculated once ∆x is known. Function OneLightRad calculates the radiance arriving from the n th emitter and is based on a shadow ray traversal. SkipSlices returns the number of slices that are skipped according to the value stored in the distance map. Both iSlice and pathRad are output in a render target. 16 gpu accelerated rendering of participating media Listing 2.1: Slice sampling pseudocode. function SampleSlice( vol3D,rayDir,iSlice,pathRad ) { x = GetIntersection(iSlice, eye, rayDir); x_uvw = ToTxtCoords(x); volValue,distValue = tex3D(vol3D,x_uvw); // accumulate each light contribution lightsRad = (0,0,0); for (n=0; n<N; n++) { lightsRad += OneLightRad(x,n); } lightsRad *=ScattAlbedo(volValue)/(16*pi*pi); lightsRad *=Extinction(volValue); // add current sample to path radiance pathRad += lightsRad; pathRad *=Transmittance(volValue,deltaX); // determine next sampled slice iSlice += SkipSlices(distValue); return (iSlice,pathRad); }  Part II ACCELERATING ANTIALIASING RENDERING Aliasing is an intrinsic limitation of sampling methods. In the case of computer rendered images, processes such as rasterization tend to generate artifacts in the form of staircase lines and jaggies. While hardware vendors have provided their own proprietary solutions, they frequently rely on expensive techniques such as multisampling. In order to overcome these costs, a number of postproduction methods have been described. One of the most recent is morphological anti-aliasing, MLAA. This algorithm is simple to implement, and it is capable of producing images of reasonable quality. However, the original implementation is not GPU amenable. In this section we describe a novel method inspired on Reshetov’s original algorithm that is specially designed to leverage the parallelism available on the GPU. Our method can be easily integrated in an existing rendering pipeline, it is temporally stable and produces high quality anti-aliasing at a very modest cost. 3 MORPHOLOGICAL ANTIALIASING In general terms, aliasing is a known issue of signal processing. It is produced when two different signals are handled by a process that makes them indistinguisable. Aliasing may also be the result of a reconstruction process that fail to produce the original signal from a set of samples. Aliasing and the issues associated have been studied in depth and are known for a variety of scientific fields [179]. A computer generated image is the result of sampling and reconstruction of the continuous optical signals that represent the natural interactions between light, geometry and materials. Virtual cameras deliver a pixel-based discrete representation of the original signals. Aliasing results from insufficient sampling levels respect to their bandwidth. In this case, the reconstructed image differs from the original representation of the scene. While this description of the phenomena is generic, it is frequently found in two specific ways: • Edges and textures with sharp transitions are defined by signals with a infinitely wide frequency spectra. In these cases, no sampling level provides enough data to reconstruct the originals. Edges generate staircase and jagged lines, and textures lose part of the original detail which in some cases will add up to moire patterns. These issues are commonly described as screen-space or spatial aliasing. • In the case of functions that evolve along time, insufficient sampling will not only produce the issues described before, but will also generate flickering and strobbing artifacts. The problem of temporal aliasing and its perceptual implications will be studied in chapters 4,5and 6 In this section we study the implications of spatial aliasing and suggest a solution to improve the visible quality of any rendered images. Our method is based on morphological anti-aliasing [ 206 ], which relies on detecting certain image patterns. The shape of the original line before rasterization is reconstructed using a non-linear filter. The original implementation is designed run in a CPU and relies on memory structures that can hardly be represented in a real time environment. Our method leverage the parallelism available in a GPU. The quality of our results lies between 4x and 8x MSAA, considered the current gold standard for real time antialiasing rendering, at a fraction of the time and memory consumption. 25 26 morphological antialiasing 3.1 previous work For many years, the aliasing problem has been solved using different approaches and as soon as in 1977 it was covered in the context of synthetic imagery [ 48 ]. The most salient methods are covered in the following section. 3.1.1Edge antialiasing In some cases, the solution comes from an improved method to convert the geometrical description of the objects in the scene to image pixels. This process is called generically as rasterization. Line segments can be antialiased using improved versions of Bresenham’s algorithm such as Wu’s line algorithm [277]. The method of Cook et al. performs antialiasing by converting the geometry of the scene into a set of tiny quadrilaterals [ 46 ]. Their shading is stochastically sampled and filtered down to produce an image pixel. This has certain advantages such as allowing lower shading sampling levels respect to the pixel sampling levels. 3.1.2Aliasing in textures In the same way that geometry edges produce high frequency signals, textures can also contain sharp transitions and fine detail. This produces similar challenges to any sampling method, but at at difference from the previous methods, it is not supported by a geometrical description. One of the options consists of pre-filtering the textures so high frequencies from the original signal are removed before it is sampled. Low pass filtering removes any undesired signal contents while leaving any frequencies under the Nyquist level intact [ 175 ]. In this case, the difficulty is how to reduce image blur and keep enough detail while eliminating the highest range of frequencies. Clamping is a special filtering method that is frequently applied to textures that are generated by spectral synthesis [ 64 ]. Since texture generation explicitly adds each frequency component to the texture profile, the procedure ignores any undesired frequency components. A final alternative relies on using enhanced filter functions. The simplest box filter averages every sample with equal weight, which in most cases produces excessive blur. Second-order linear, third-order quadratic and four-order cubic filters provide better approximations to the optimal sync-filter. The latter as well as the Catmull-Rom and Mitchell filters contain negative lobes, which tend to produce sharper texture patterns although in some cases can make ringing artifacts visible [33,161]. 3.1 previous work 27 In most cases, the design of the previous techniques make them suitable for environments where there is no limitations in the latency where each image is produced. In the following sections we will describe approaches that are applicable in all cases, but will focus on the alternatives that can be implemented as part of a real-time framework. 3.1.3Real time multisampling Multisampling methods perform several computations per visible pixel and the final color is determined by a filtered down version of these samples. While this method is popular in the context of offline rendering [ 170 ], the difficulties associated with the use of limited hardware have reduced the introduction into real-time frameworks. The earliest instance of multisample rendering taking advantage of hardware acceleration is the accumulation buffer algorithm [ 90 ]. This method, performs several full renders with slightly different camera parameters. The final image comes from the addition of those images into the accumulation buffer. In the current generation of hardware graphics units, multisampling anti-aliasing (MSAA) remains the most extended solution and the one that offers the best results. The precursor of this technique, FSAA (Full Scene Antialiasing), performs a full render of the scene using an oversized resolution framebuffer that is downsampled to generate the final image. MSAA uses different optimizations whereas certain components of the image such as stencil and depth buffers are supersampled while others, ie. lighting and shading, are not. Different flavors of this technique have been introduced by each hardware vendor. However, techniques such as CSAA, Qintix, ... are based on similar concepts. CSAA, short for coverage antialiasing [ 281 ], reduces shading complexity after decoupling color and coverage samples. In this case, the image results from the combination of higher number of coverage samples than shading/z/stencil samples. These methods allow better image quality where imaging was traditionally based on non-antialiased methods. However, there are important drawbacks to the use of multisampling, specifically MSAA, in certain scenarios: • It is roughly equivalent to computing a higher resolution image that is sampled down. The increase in processing time and storage is not negligible [242]. • In some cases activating multisampling prevents the use of multiple render targets (MRT). This is specially relevant as MRTs are widely used and are the basis of fundamental techniques such as deferred shading [226,122]. 28 morphological antialiasing • Implementation of MSAA is neither trivial nor cost-free [ 242 ]. In fact, the current generation of consoles does not offer a simple and complete solution. In the case of the Xbox 360, memory constraints force the use of CPU-based tiling techniques to handle high resolution frame buffers in conjunction with MSAA; whereas on the PS3multisampling has not been widely applied. • MSAA is uncapable of smoothing non-geometric edges. This has an impact on vegetation rendering for example, where fine details are generated using rough geometry and alpha channels. In these cases, antialiasing can only computed if an adhoc technique such as alpha to coverage is added [174]. 3.1.4Postproduction Postproduction methods are an interesting alternative to multisampling. This family of methods uses the information contained in a rendered image and applies different enhancement filters to reduce the visibility of the aliasing artifacts. The most popular approaches rely on a feature detection stage that analyses the information present at the neighbourhood of each pixel and detects those that can potentially be the result of a rasterized edge. A blurring stage uses the pixels in the image to generate a new antialiased value. This imposes certain quality compromises but it is efficient to evaluate and only requires information that is produced at render time. In its simplest form, edge detection can be based on the color of each pixel but some methods also take advantage of normal and depth information. In S.T.A.L.K.E.R [ 226 ], edge detection is performed using differences in the 8-neighbourhood depth values and the 4neighbourhood normal angles; then, edges are blurred using a crossshaped sampling pattern. A similar, improved scheme is used in Tabula Rasa [ 122 ], where edge detection uses threshold values that are resolution independent, and the full 8-neighbourhood of the pixel is considered for differences in the normal angles. In Crysis [ 229 ], edges are detected using depth values and texture lookups using bilinear filtering. Finally, in Killzone 2samples are rendered into a double horizontal resolution G-buffer. The lighting pass averages two samples from the G-buffer to produce a pixel in the final image buffer. However, this implies executing the lighting shader several times for each final pixel. Morphological antialiasing [ 206 ] is a recent improvement in this area. Using the neighbourhood of each pixel in the rendered image, certain patterns are detected and based on them, the original topology of the edges is reconstructed. The image is blurred using an adaptive filter that smooths the image based on this reconstructed geometry. The original CPU based implementation has been successfully ported to 3.2 overview 29 the cell-processor architecture of the PS3[ 99 ]. In the following sections we will describe the first GPU based implementation available to the date of publication. 3.2 overview Reshetov searches for specific patterns (U-shaped, Z-shaped and Lshaped patterns) which are then decomposed into simpler ones. This approach, while feasible in architectures where random memory accesses have low impact on performance, it is impractical for GPU based stream frameworks. We have found that the pattern type and the consequent anti-aliasing parameterization, only depends on a small set of values that can be obtained for each edge pixel. For brevity, in the following, we will call edgel to any pixel belonging to a detected edge. Furthermore, this approach allows to handle all pattern types in a symmetric way so the need for decomposing them to simpler ones is avoided. The original algorithm is transformed so that it uses texture framebuffers instead of lists (see Figure 3.1). In addition, pre-computing certain values and storing the results as textures allows for an even faster implementation. Section 3.5discusses this optimization. Finally, in order to accelerate calculations, we make extensive use of hardware bilinear interpolation. This allows fetching several blended values without the need of explicit computation in a single operation. Moreover, we store certain magnitudes in a way that the neighbourhood that correspond to certain pixel values can be inferred without explicitly retrieving them. Section 3.6gives details of this short-cut. The combined speed-ups associated with this algorithm allows it to be efficiently executed by a GPU, has a moderate memory footprint and can be integrated in the standard rendering pipeline of any game architecture. 3.3 algorithm structure The algorithm searches for patterns in edges. Based on this information, the original lines are constructed to be later rasterized using an improved antialiased profile. This can, in general terms, be seen as a re-vectorization of edges. The method is implemented as a succession of three render passes: 1. The initial pass performs edge detection on the image that needs to be antialiased and yields a texture containing edgels (see Figure 3.1,center left). 2. In the second pass the blending weight a is computed for each pixel adjacent to the edge being smoothed (see Figure 3.1,center 30 morphological antialiasing Original Image Edges texture Blending weights texture Anti-aliased Image Figure 3.1: Starting from an aliased image (left), edgels can be detected and stored in a edges texture (center left). The color of each pixel represents the relative position of each pixel relative to the edge: green pixels have an edge at their top boundary, red pixels at their left boundary, and yellow pixels have edges at both boundaries. The edges texture is used in conjunction with the precomputed area texture to produce the blending weights texture (center right). This texture stores the weights for the pixels at each side of an edgel in the RGBA channels. In the third pass, blending is performed to obtain the final anti-aliased image (right). right). The value is based on the pattern type for each line passing through the north and west boundaries or each pixel and is followed by a calculation of the distances to the crossing edges. Both values are used to query the precomputed area texture. 3. The third and final pass involves blending each pixel with its 4-neighborhood according to the blending weights from the previous pass. See Figure Figure 3.1,right. 3.4 pass #1:detecting edges Edge detection is performed using the data contained in the depth buffer of the original rendered image. For each pixel, the difference with respect to the pixel to the top and to the left left is computed. This difference is thresholded to obtain a binary value indicating whether an edge exists in a pixel boundary. The value stating the existence of left and top edges is stored in the red and green channels of the edges texture, respectively. In most cases, depth information is enough to detect edges. However, in those locations where no depth discotinuity exists, for example where two different polygons meet at an angle, an additional condition based on the normals to the polygons. In case no geometric information is available, thresholding needs to be performed using magnitudes other than depth or normals. In these cases, the final rendered image can be used to extract a luminance value per pixel using the CIE XYZ standard formulation: L=0.2126 ·R+0.7152 ·G+0.0722 ·B(3.1) 3.5 pass #2:blending weights 31 Figure 3.2: Left: Anti-aliasing process. Color copp bleeds into cold according to the area a below the reconstructed blue line. Right: Texture containing the precomputed areas. The texture uses two channels to store areas at each side of the edge, i.e. for a pixel and its opposite (pixels (1 , 1) and (1 , 2) on the left). Each 9×9 subtexture corresponds to a pattern type. Inside each of these subtextures (u , v) coordinates encode distances to end of the left and to the right end of the line, respectively. As an example, when dense vegetation is present, using luminances is faster than using depth (around 12% faster for the particular case shown in Figure 3.5,bottom row), due to the amount of edges detected using depth. Figure 3.1,center left shows the resulting image of the edge detection pass, in this particular case using luminance-based detection. 3.5 pass #2:blending weights Those edgels that need to be modified are blended according to the following equation: cnew = (1−a)·cold +a·copp, (3.2) where cold is the original color of the pixel, copp is the color of the pixel on the other side of the line and cnew is the new color of the pixel. The blending factor a is a function of both the pattern type and the distances to both ends of the line. In Figure 3.2,left represents the rasterized line and its respective crossing edges as blue and green segments respectively. The blending factor is displayed as a yellow area. In order to save processing time we precompute this area and store it as a two-channel texture that can be seen in Figure 3.2,right. In order to calculate the blending weights, the second pass will compute the distances to both ends of the line which the edgel belongs to. Taking the edges texture as input, a linear search in the horizontal direction for the ends of the edge will provide this information (see Section 3.5.1). The distances are used to fetch the crossing edges at both ends of the line (see Section 3.5.2). These crossing edges indicate the type of pattern. 32 morphological antialiasing Figure 3.3: Distance computation relies on hardware bilinear filtering. The color of the dot at the center of each pixel represents the value of that pixel in the edges texture. In the example, distance search progresses from the the pixel marked with a star to the one to the leftmost end of blue line. Each access to the edges texture is marked with a rhombus. This allows us to travel double the distance with the same number of accesses as a standard pixel by pixel traversal. The pass outputs a texture that contains, for each pixel, the areas at each side of its corresponding edgels. This produces two values for north edgels and two values for west edgels in the final blending weights texture. These values are directly used by the final pass to control pixel blending and produce the antialiased texture. 3.5.1Searching for Distances Distances are determined using an interative search algorithm that steps over the pixels of an horizontal edge. Each iteration simply checks whether the end of the line has been reached or not. Once the end of the line has been reached, the number of hops is returned as a distance map. The process is accelerated by leveraging the fact that the information stored in the edges texture is binary –it simply encodes whether an edgel exists–. Since the texture is queried using hardware bilinear filtering, a query at a position placed between two pixels retrieves a value that represents the linear combination of the two pixels at their sides. (see Figure 3.3). Based on this, a fething the value in the mid point of the center of two pixels can only produce the following results: (a) 0.0, which means that none of the pixels contain an edgel, (b) 1.0, which implies an edgel exists in both pixels, (c) 0 . 5 , which is returned when just one of the two pixels contains an edgel These values are used as stop condition for the search, that is, the end of the line has been found if the returned value is lower than one. Searches are limited to a maximum distance. This makes execution times bounded and more predictable, independently of the complexity and the visual characteristics of the image. As expected, the highest the Part III ACCELERATING MOTION BLUR RENDERING Motion blur is a fundamental cue in the perception of objects in motion. This phenomenon manifests as a visible trail along the trajectory of the object and is the result of the combination of relative motion and light integration taking place in film and electronic cameras. Motion blur is also a frequent requirement for the generation of high quality animated images. Due to the nature of computer rendering methods, it needs to be explicitly simulated and this process is frequently resource hungy. Section 4makes an in-depth review of the existing algorithms and categorizes them in the context of a formal model that highlights their differences, strengths and limitations. Research has traditionally been focused on finding new methods to reduce the cost and alleviate sampling artifacts. They usually try to steer computation to the most important dimensions of the rendering equation. In sections 5and 6, we take a different approach and study monoscopic and stereoscopic images rendered with motion blur from the perspective of human perception. We evaluate the influence of high-level properties such as object material and speed, shutter time and sampling level. Based on several psychophysical experiments, we determine which ones are more influential in the perception of image quality. Interestingly, we have found that radically different motion blurred stimuli may be indistinguishable and even equivalent to a gold standard. This has direct implications on how scenes can be rendered and opens the door to time optimizations. To our knowledge, this is the first time that the perceptual limits of the Human Visual System have been considered to accelerate motion blur rendering. What follows can be considered an important step in that direction. 4 MOTION BLUR RENDERING: STATE OF THE ART Motion blur is an effect that manifests as a visible streak generated by the movement of an object in front of a recording device. It is the result of combining apparent motion in the scene and an imaging media that integrates light during a finite exposure time. This relative motion can be produced from object movement and camera movement and is observed both in still pictures and image sequences. In general, sequences containing a moderate amount of motion blur are perceived as natural, while its total absence produces jerky and strobing movement. This phenomenon is an integral effect of photography and film recording. It needs to be accounted for and in some cases compensated with the use of specific techniques [ 2 ]. Moreover, it has become part of the toolkit used by filmmakers and photographers [ 187 ] and is commonly used to increase dynamism in still images (see Figure 4.1). Motion blur for synthetic images has been an active area of research from the early ’80s. Unlike recorded footage that automatically integrates motion blur, rendering algorithms need to explicitly simulate it. These cases require accurate temporal integration to avoid aliasing artifacts that can otherwise be easily noticed by an untrained eye. This simulation is one of the most expensive processes in the production of high quality renders. The cost becomes more relevant knowing that the result is a blurred image whose high spatial frequencies have been removed. In this work we describe the origin of the phenomenon and make a detailed discussion of the existing algorithmic solutions. In section 4.1 we start with a description of the physical phenomena that generate motion blur in a recording device. In section 4.2, it is mathematically formalized based on the models by Meredith [ 157 ] and Sung et al. [ 237 ]. In section 4.3we review the techniques that can produce synthetic motion blur and classify them according to this formalization. Their similarities and differences are analyzed in section 4.4. Section 4.5briefly discusses current research trends and future directions. 4.1 origin of the phenomenon The amount of light entering a camera, independently of whether it uses photosensitive film or an electronic sensor, is limited by the diaphragm and shutter [2]. The diaphragm defines the size and shape of the aperture where the light enters the body of the camera, and it statically influences 41 42 motion blur rendering:state of the art Figure 4.1: Motion blur is frequently used to increase the perceived motion in photographic snapshots. As seen in the images, carefully controlling shutter timing, camera motion, illumination, lens and filter configurations can produce dramatic effects. Images reproduced with permission of their respective authors: © Tony Margiocchi, flickr users Noodle Snacks and E01, Carl Rosendahl, Peter Heacox and Enrique Mandujano. the amount of exposure of the film, depth of field, optical aberrations, vignetting and field of view. Shutters are mechanical or electronic devices designed to limit the exposition to a finite range of time. Once opened, and since the media integrates all light hitting its surface, a continuous view of a moving object is projected to different areas of the image plane. Additionally, since transitioning from the closed to the open state and back takes a finite amount of time, its effective aperture size and shape evolve over time. The resulting interactions between light, diaphragm, shutter, exposed media and object motion produce motion blur. The exposure process can be formalized using Equation 4.1. During scene capture, I(ω) represents the contents of the image plane when the scene is seen in the direction ω . Captured light is the result of the integration of the incoming radiance L during the exposition time when the shutter is open ∆T . f(ω , t) models the influence of optics, shutter, aperture and film. I(ω)=Z∆T f(ω,t)L(ω,t)dt (4.1) The previous equation already gives clues about the characteristics of the resulting images. If a rendering process generates each image in a sequence as an instantaneous snapshot ( ∆T is zero), quickly moving objects will miss parts of their trajectories and the continuity of the sequence will be lost. Even if the shutter range is long enough, different exposures may be separated by gaps. This may result in double images and ghosting. In the previous equation, this situation is represented by ∆T bigger than zero but secuential I(ω) separated with unsampled time ranges. 4.1 origin of the phenomenon 43 category methods Analytic [123] [81] Geometric substitution Generic [200] [35] [76] Motion Hints [275] [163] [240] [83] [85] [109] [216] Texture clamping [175] [145] Monte Carlo Distributed Ray tracing [45] [89] [65] [182] Evolutions [251] [29] [92] [261] [171] [194] Accumulation buffer [123] [90] Frameless rendering [11] [215] [54] [55] Specific to a primitive type [192] [117] [4] Postprocessing Generic [220] [191] [152] [40] Motion fields [225] [19] [224] [285] [209] [230] [256] Hybrid [46] [237] Mechanical and optical [220] [77] [139] [241] [183] Table 4.1: Motion blur rendering methods classified according to the categories explained in section 4.3 Rendered image sequences usually look more natural when they integrate motion blur. Three basic reasons are commonly accepted for this [77]: • Firstly, images recorded using real cameras automatically incorporate motion blur. Even natural images as seen by our eyes contain a similar effect, motion smear [ 22 ]. As such, motion blur is part of what we expect to find in any moving image. • Secondly, sequences of images lacking motion blur can contain strobing artifacts. This makes the predictions of the human visual system (HVS) difficult and object trajectories may not be understood as continuous paths. • Finally, discretization of continuous signals is a by-product of many imaging algorithms. This results in different forms of aliasing artifacts that are usually easily noticed by the HVS. Reducing temporal aliasing by avoiding time undersampling is the main target of motion blur rendering techniques. An overview of these will be given in section 4.3. Although this work focuses on the problems associated with the generation of motion blur, there are many complementary fields. Interested readers can find useful references for the algorithms used to simulate realistic camera lenses [10], depth of field [9], film emulsion grain and exposition [ 75 ] or the dynamic range of recording devices [ 203 ]. The inverse problems, such as image deblurring and restoration [127] have also been covered elsewhere. 44 motion blur rendering:state of the art 4.2 formalization of the motion blur problem Different motion blur rendering algorithms have been proposed based on several formal models [ 220 , 191 , 152 , 159 , 225 ]. Probably, the most widely accepted describes a motion blurred image as a spatio-temporal integral that includes independent terms for the geometric and shading functions. Equation 4.2mathematically states this idea. The expression follows the formulation of Sung et al. [ 237 ], but similar descriptions have been used by Meredith [157]. Ixy =X lZΩZ∆T r(ω,t)gl(ω,t)Ll(ω,t)dtdω (4.2) In this equation, Ixy represents the contents of the image pixel with coordinates (x , y) and Ω is its corresponding subtended solid angle. Independently of their geometrical representation, the overall contribution of all primitives in the scene is considered by iterating over each individual object l . gl(ω , t) is a geometrical term that accounts for occlusions between objects. Its value is 1if object l is directly visible in the direction ω ,0otherwise. As we have seen, shutter shape and efficiency, lens aberrations and film influence the final image. The reconstruction filter r(ω , t) accounts for their overall effect. In general, this term cannot be split into pure spatial and temporal components. However, an approximation that is widely accepted is to replace it with the product of two filters r(ω , t) = rs(ω)rt(t) , where each term exclusively depends on one of the dimensions. Ll(ω , t) represents the radiance of object l without explicitly establishing the method by which is calculated. In order to account for the complex spatio-temporal relationships taking place in an animated scene, all terms are evaluated at an instantaneous time t over the aperture time ∆T , and over the solid angle Ω . In some cases and depending on the desired filter footprint, Ωcan represent narrower or wider solid angles than the one defined by the pixel. Although gl(ω , t) is a binary function that assumes that a single object is visible at ω at a specific instant, this should not be considered a limitation of the model since the radiance term Ll(ω , t) already accounts for cases where images of several objects can be seen simultaneously. Kajiya’s rendering equation [ 110 ] is an example of formulation for light interaction that can be used as a method to resolve complex transparent, translucent, reflective, refractive and shadowed phenomena. Different geometrical descriptions can be included in Equation 4.2, even when those are based on non traditional representations. The term Llsimply accounts for the final value of the radiance of object l independently of the nature and complexity of the phenomena. Something similar occurs with the geometrical term gl . With this in mind, 4.3 motion blur rendering algorithms 45 the original formulation can be used to render scenes where, for example, surfaces based on polygonal, analytical or implicit descriptions are mixed with objects built from liquids and gases. Due to reasons we will discuss, the previous formulation is not always practical to calculate. In the following sections we will see how it can be adapted so it can be implemented as an algorithm suitable to be run in a computer. 4.3 motion blur rendering algorithms Even if many methods can gather subpixel information to produce spatial antialiasing, they are not designed to find the subframe information on which temporal antialiasing relies. Any methods that are not aware of the time dimension, when applied to each frame of a sequence, may produce images that lack any temporal coherence, and display a myriad of different artifacts. Motion blur rendering algorithms are designed to handle the degree of complexity associated with the addition of the time dimension. However, even if they can produce temporally correct images, their computational complexity may be unacceptable. As observed in the photographic snapshots of Figure 4.1, the amount of fine detail is drastically reduced when the images integrate motion blur. When considered from the perspective of the Fourier theory [ 65 ], common visual phenomena suffer similar transformations under the presence of motion blur and their spectra is confined to a specific region of the domain. This supports the initial intuition that motion blur produces a reduction of the spatial complexity and frequency contents with respect to an equivalent instantaneous unblurred image. While the mathematical framework has been already described, different algorithms use alternative methods to evaluate the expressions associated. Knowledge of the physical phenomena may also be exploited. In all cases, it is desirable to reduce the impact of any simplifications, so it can be applied in a broader set of situations and still be accurate. In the next sections we will describe and group the existing methods based on an analysis of their assumptions, limitations and associated visual artifacts. 4.3.1Overview From the description in Equation 4.2, two different problems must be addressed. Firstly, a good approximation for the evolution of the geometry needs to be found; and secondly, the shading of the objects needs to be accurately simulated. By considering the approaches and assumptions used to solve each of these problems, the following categories can be established. They are also summarized on table 4.1. 46 motion blur rendering:state of the art •Analytic methods , while frequently relying on heavy assumptions, use a closed form solution that can be exactly evaluated. Section 4.3.2covers them in detail. • In section 4.3.3, geometric substitution methods use alternative primitives that represent the original geometry and its evolution along time. These methods are ideal to be implemented in real time frameworks or when approximate motion hints suffice. •Monte Carlo methods have received a great deal of attention due to the fact that a wide range of phenomena can be modeled inside a flexible and technically simple framework. However, stochastic point sampling methods are not deterministic and tend to produce artifacts due to insufficient sampling. These techniques and its associated methods are described in section 4.3.5. •Postprocessing methods extend the information of an image snapshots to the whole exposure range. Temporal information is extracted directly from the render engine or extrapolated from different frames of the sequence. A detailed description can be found in section 4.3.6 • A number of models have been combined together to solve specific aspects of the general problem. Section 4.3.7contains a description of hybrid algorithms which have proved to be the best options when an open and unconstrained problem needs to be solved. This is probably the main reason for their wide acceptation in the visual effects and film industry. • Finally, section 4.3.8contains recent techniques that include physically accurate models of the imaging device . The availability of CMOS/CCD chips in digital video cameras and the need for better composition of rendered images into real footage are giving these solutions an increasing relevancy. 4.3.2Analytic methods Analytic methods are among the pioneering solutions to render motion blur. They replace Equation 4.2with closed form expressions that efficiently provide an exact value of the pixel’s radiance. In general, lighting equations are highly non-linear functions that may not have analytical equivalents so this family of methods are only valid under strong compromises. The first example of this approach is the work of Korein and Badler [ 123 ]. Their algorithm finds a continuous function that represents the time intervals when the projection of an object covers a given image plane pixel. Once those visibility ranges τl are found, the problem is 4.3 motion blur rendering algorithms 47 Figure 4.2: Method of Korein and Badler [ 123 ]. Top row images use a filter that emphasizes later movement, while the bottom row shows the same motion using a a temporal box filter. reduced to determining a single shading sample for the pixel in ω at a time t. Equation 4.3models this approach: Ixy =X lZ∆T r(ω,t)gl(ω,t)Ll(ω,t)dt =X lZτl r(ω,t)Ll(ω,t)dt =X l τlLl(ω,t)(4.3) Since their implementation is limited to objects represented as spheres, polygons and polyhedra, and their trajectories are approximated using piecewise linear interpolation, the corresponding projections in motion are determined by simple primitives, see Figure 4.2. Occluded objects are stripped out from the calculations using depth sorting and a single object is considered for each time range and pixel. This method focuses on solving geometric temporal aliasing and, since it uses a single sample Ll , changes in shading are beyond the capabilities of the algorithm. An alternative method, adapted for polygonal primitives, is described by Grant [ 81 ]. Dynamic 3D polygons are converted to static 4D polyhedra that describe the volumes swept by the geometry. Visibility is determined by scan-converting those continuous 4D (x,y,z,t) primitives into continuous visible 3D (x,y,t) geometry using a temporal extension of Catmull’s visible surface algorithm [ 35 ]. Non occluded geometry is rendered using an extension of Feibush et al. analytical filtering algorithm [ 70 ]. Intersecting and non intersecting objects under 48 motion blur rendering:state of the art image space translational and scaling motion can be represented with this approach. Grant’s polyhedral algorithm can also be included in the category of methods that use geometry substitution. Those methods are explained in the following section. 4.3.3Geometric substitution Methods that use geometric substitution are fundamented on the idea that, in order to render motion blur, each moving object can be replaced by static geometry built from the original primitives and their motion. Time-sampling is no longer needed, as the new geometry contains an implicit description of the temporal evolution of the shape, shading and trajectory. In general these methods can be described by adapting the formulation from Equation 4.2to: Ixy =X lZΩZ∆T r(ω,t)gl(ω,t)Ll(ω,t)dtdω ≈X l0ZΩ rs(ω)g0 l0(ω)L0 l0(ω)dω (4.4) In Equation 4.4, each geometric object l is replaced by an alternative primitive l0 . Functions r , gl and Ll are also swapped with rs , g0 l0 and L0 l0 , their time independent counterparts. This formulation is just an approximation that drops the integration over time while keeping the corresponding image space evaluation over the domain Ω . Different algorithms make different interpretations of this expression and, as we will see, each approach is associated with a specific set of implications and varying flexibility. One of the earliest proposals is made by Reeves. He establishes the fundamentals of particle systems [ 200 ]. Motion blur is achieved by replacing each moving particle by an antialiased line segment describing its trajectory during the exposure time. Their color is based on a single shading sample. Since they are rendered as point light sources, all particles projected to a given pixel can be simply added together without accounting for visibility, that is, g0 l0 is always one. The original algorithm is not applicable to particles that use different shapes or textured billboards and layer composition is needed to solve occlusion with other types of primitives. An image rendered with the original technique can be seen in Figure 4.3. Catmull’s visibility algorithm [ 35 ] focuses on finding which polygons are visible from a given pixel. Each primitive is decomposed into a set of micro-polygons whose shading is weighted with a circularly symmetric filter [ 70 ] and composited using depth sorting. Spatio-temporal filtering is achieved by using the original filter on geometry that has been deformed according to the speed of each of 4.3 motion blur rendering algorithms 55 Figure 4.8: Scene rendered with a static camera (a). Images (b) to (e) use a camera that moves progressively faster. A box reconstruction filter creates aliasing patterns in images (d) and (e). The patterns are corrected in image (f) by using a gaussian filter. Reproduced from [50]. by standard ray tracing produce poor results with distributed ray tracing. Stochastic methods like minimum distance Poisson or jittered sampling [ 44 , 60 ], precomputed sampling patterns [ 44 ], adaptative sampling [ 110 , 135 , 158 ], importance sampling [ 63 ] or stratified sampling [ 160 ] are designed to reduce those problems. As seen in Figure 4.8, alternative reconstruction filters can combine a given sample set resulting in varying qualities [ 161 , 50 ]. The topic of sampling and reconstruction has been discussed in detail [189,63]. Those methods which produce estimates as seen in image space may produce noisy reconstructions and miss image features. Alternative methods, like Metropolis light transport [ 251 ] or the recent Hachisuka’s et al. [ 89 ] multidimensional adaptive sampling, place samples based on the changes of the functions in the original multidimensional space. The latter evaluates the contrast of the rendering equations to determine the sampling level and analytically reconstructs 56 motion blur rendering:state of the art the original function in all but the image dimensions. A Riemann sum is used to integrate the illumination of each pixel. Several studies have considered the rendering problem from the perspective of the frequency domain [ 60 , 37 , 62 ]. Recent results [ 65 ] have shown new methods to design sampling and reconstruction filters. In essence, for common effects such as object and texture motion, rotations of both the BRDF and lighting and non static shadows, the influence of motion blur can be approximated by a shear filter. The frequency contents and ideal sampling levels can be estimated for each image pixel based on their respective image space velocities. Based on the same data, an improved reconstruction can also be obtained by tuning the orientation and extent of the filter. In contrast to previous methods that exhaustively sample the integral to reconstruct a smooth image, adaptive wavelet rendering [ 182 ] directly estimates a smooth function in the wavelet domain. With this multi-scale representation, coarse-scale wavelets represent large smooth regions while finer-scale ones represent edges and small details. Adaptive sampling can efficiently detect sharp changes in image-space as well as smooth image regions with high variance in the non-image-space dimensions. The algorithm reconstructs smooth images even in regions of high variance, scales well for high dimensional problems but it may show ringing and over smoothing artifacts. 4.3.5.2Evolutions of naive distribution ray tracing The original distribution ray tracing method has been improved to produce results more efficiently with increased accuracy. In this section we will focus on exploring those techniques. Metropolis light transport [ 251 ] is an evolution of the original bidirectional path tracing [ 130 , 252 ]. Paths are built from the light sources to the eye, and different mutation strategies are used to generate variations of these. This method naturally extends to calculate motion blur when the mutations include the temporal dimension. Caching techniques, like Jensen’s photon mapping increase performance by storing and reusing lighting results [ 103 ]. However, since they produce estimates that are descriptive of a given value in the time domain, they cannot represent objects with changing shading, motion or shape. An extension of this technique [ 29 ], handles motion blur by assigning a random time to each photon and its descendants in the light path. The final reconstruction pass relies on a filter that averages the photons of the spatio-temporal neighbourhood of the pixel being calculated. In Figure 4.9, motion blur is incorporated to a set of shadowing, reflective, refractive and caustic effects. The original Lightcuts algorithm [ 260 ] has been expanded to support temporal sampling [ 261 ]. The new method builds on the original discretization of the lighting integrals and graph partitioning. However, the temporal domain is represented with a fixed set of time instants 4.3 motion blur rendering algorithms 57 Figure 4.9: A transparent sphere projects a caustic on a diffuse cube that moves downwards. Left-top: Noisy image rendered using path tracing with 10000 random paths per pixel. Right-top: Accumulation buffer averaging 20 images placed at equal intervals. Bottomleft: Photon mapping using standard estimation that underestimates the final value of the radiance. Bottom-right: Photon mapping using the time dependent radiance estimation from [ 29 ] and any light interactions are limited to those subintervals. Even with these simplifications, the method can provide high quality results while drastically reducing the cost and the noise produced. Figure 4.10 shows examples of the results. Other methods focus on exploiting spatio-temporal coherence [ 92 ]. Since a given area of an object can usually be seen within several consecutive frames, novel views can be built by reprojecting existing samples. The algorithm of Cabral and Leedom can be used to account for the image space projection [ 26 ]. Motion blur is computed by determining the trajectory of each sample and accumulating their energy contribution over the motion path. Like similar methods [ 19 ], it uses linear constant speed motions, but in contrast, precise trajectories are computed from object space and not image space data. While reprojection clamps the shading functions, the technique is only available for non deformable objects, cannot directly model view dependent effects and due to the simplified nature of the paths, may produce occlusion artifacts. Using a similar approach, real-time reprojection caching [ 171 ] allows supersampling at high frame rates. In this case, cached values are reused using hardware texture filtering. Noise is reduced while keeping storage requirements low by using a recursive low-pass filter that averages new samples with the existing ones. 58 motion blur rendering:state of the art Figure 4.10: Comparison of two renders performed using multidimensional lightcuts (left) and traditional Metropolis light transport (right). Lightcuts’ image is less noisy and can be rendered faster (15x). Reproduced from [261] Decoupled shading [ 194 ] leverages the intrinsic coherence of depth and motion blurred scenes by using a shading cache. The technique densely evaluates the visibility function and reuses any previously calculated shading samples. The defining parameters of each visibility location are hashed so they deterministically map to a shading value. On a cache miss, the value is calculated on demand and stored so they can be later retrieved. This method is built on the assumption that shading does not change rapidly and it is view independent, so a single value is representative of the whole shutter range. Shading rates are reduced respect to other methods that shade before visibility or those in which visibility and shading samples have a one-to-one relation. It should be noted that exploiting spatio-temporal coherence is not only applied to calculating motion blur. Other methods have relied on similar approaches for the rendering of sequences of images where the interest is obtaining high frame rates and not temporal supersampling [259,244,238,227]. 4.3.5.3The accumulation buffer A number of methods have been designed to leverage the use of accumulation buffers to super-sample multidimensional spaces. These hardware framebuffers are specially suited to efficiently weight and combine samples in image space using high precision computations. Korein and Badler [ 123 ] include the description of an algorithm that can be considered a precursor to the accumulation buffer method. It calculates temporal anti-aliasing by supersampling the temporal domain using several independent renders performed at different times. Full images are stored externally and filtered down to produce the resulting image. Haeberli and Akeley [ 90 ] weight and add several passes computed using a single sample per pixel. By updating different parameters between passes, the resulting image is spatially antialiased, integrates 4.3 motion blur rendering algorithms 59 Figure 4.11: Images rendered with the original accumulation buffer method [ 90 ]. Left image contains a motion blurred image composed from 23 different passes. Right image uses 66 individual images to simultaneously render motion blur, depth of field and soft shadows. Figure 4.12: Images generated using frameless rendering. Left, naive frameless rendering where each sample is displayed as soon as is calculated. Right, the same image using adaptive frameless rendering [55] depth of field, soft shadows, anisotropic reflection or filtered texture maps. Motion blur, as can be seen in Figure 4.11, is the result of combining scene renders at time instants are that equally placed in the shutter range. A final image is the result of N subframe passes or, in the case of repeated integration [94], every two passes. Before the appearance of flexible programable GPUs, this was the preferred method to leverage the parallelism available in hardware frameworks. Since the solution comes by iteratively applying the original algorithm, the implementation is simple and avoids the overhead of elaborated control logics [ 213 ]. However this method shows poor results with scenes with high temporal correlation and does not scale well with scene complexity. 60 motion blur rendering:state of the art 4.3.5.4Frameless rendering Frameless rendering [ 11 ] is a paradigm designed to reduce the latency of interactive display systems. Unlike traditional approaches that expose frames after they have been fully computed, frameless rendering derives each pixel from the most recent instant in time and immediately shows it. As a consequence, high motion scenes show an effect that resembles motion blur, while static ones converge to the same solution as a traditional renderer does. The original technique randomly selects the samples to be rendered. Further evolutions use a probability distribution function based on the age of the pixels [ 54 ] or even closed loop adaptative sampling to steer computation to regions undergoing significant changes [ 55 ]. Related techniques use one temporal sample per scanline [ 178 ], dynamically modify frame rate [ 276 ] or adapt frame rates for each individual object [ 202 ]. Perceptually based heuristics have also been envisaged [ 283 , 215 ]. Image plane pixels can be reconstructed from a single sample [ 11 ], a temporally weighted set of samples corresponding to a slice of time or even from a 3D volume in which the filter is adapted to local sampling density and color gradients [ 55 ]. Examples of the resulting images can be seen in Figure 4.12. Since computation speed is bounded, these methods trade temporal supersampling with spatial undersampling. Scenes with high spatiotemporal coherence are well suited for this schema. Otherwise quick changes are shown as a dissolve filter between scene snapshots. As a side effect, traditional strobing effects associated with temporal low sampling, are replaced by less perceptually disturbing noise. 4.3.5.5Methods designed for specific types of primitives Distribution ray tracing has been traditionally oriented to handle polygonal meshes. With frequency, other types of primitives are rendered after a conversion to these primitives. This section covers the methods that have focused on using different geometric representations without requiring any previous transformations. In some cases, using those alternative models open the door to speed and quality improvements. Preston implements motion blurred distribution tracing for NURBS surfaces [ 192 ]. His algorithm expands the original parametric representation so it represents the surface and its temporal evolution. The surface’s control points are stored as slices representing different moments in time and any surface configuration is constructed as an in-between of two of them. Motion blur is achieved by sampling the resulting surface at different time lapses. Fluids, based on non polygonal surfaces, can be rendered with Eulerian motion blur [ 117 ]. Since newtonian inertia is not a valid assumption, the status of the system cannot be inferred using inter- 4.3 motion blur rendering algorithms 61 Figure 4.13: Images comparing an Eulerian system rendered with and without motion blur. Left image has been rendered using the method of Kim and Ko [117] polation between known states. Kim’s approach is based on defining intermediate states based on sparse level-sets, density data and the fluid’s semi-lagrangian advection. From that point, existing Monte Carlo methods can be used to render the fluid [ 69 , 173 ]. Figure 4.13 shows the result of the algorithm. Rendering motion blur for voxel sets, rigid and time-varying point clouds has already been described in section 4.3.3.1. Guan and Mueller briefly introduce an alternative approach [ 85 ] using optical flow or mpeg-like motion estimation to determine motion flows inside the evolving voxel grids. However this method has not yet been implemented neither described in detail. Akenine-Möller et al. implement real time rasterization of triangles [ 4 ] whose motion is described as a continuous function of their vertices at two moments in time. Using this representation, any surface attribute can be interpolated using GPU tiled rasterization, accumulation buffers and piecewise linear approximation of the trajectories. Motion blur, soft shadows and depth of field can be rendered using this framework. Inspired by the shadow mapping algorithm [ 273 , 201 ], this method can render motion blurred shadows without relying on ray tracing. Unlike the original algorithms or deep shadow maps [ 141 ], see image 4.14, time dependent textures are not limited to static scenes or static shadow receivers. 62 motion blur rendering:state of the art Figure 4.14: Left image shows a motion blurred shadow rendered using deep shadow maps [ 141 ]. This technique can only be used when the object receiving the shadow is stationary respect to the light emitter. Right image shows the same scene with static shadows. ©Pixar 4.3.6Postprocessing Postprocessing methods use one or several prerendered snapshots of the scene and blur them using motion information built from the images themselves or the objects’ animation data. With this approach, motion blurring and rendering methods are fully decoupled. As they operate in image space, they are also independent of scene complexity. They tend to be quite efficient, but not everything are advantages: as we will see, they are also associated with certain quality compromises. In general these methods can be modeled as in Equation 4.7. A motion blurred image is calculated by convolving each pixel I(x , y , ti) of an instantaneous image at time ti , with a function Φ(t0 , t∞ , ti) . This function is built based on the information available in the scene or its rendered images. Even if it can potentially use all image data available between t0 and t∞ , most methods will reduce the temporal scope of the analysis. In general, the details of the algorithm that computed the unblurred images are not needed, but in some cases it may provide guidance to setting up the convolution kernel. Ixy ≈I(x,y,ti)⊗Φ(t0,t∞,ti)(4.7) The first of the methods is described by Potmesil and Chakravarty [ 191 ] and extends their previous formulation of an aperture camera model [ 190 ]. In their work, Whitted’s pinhole raytracer [ 272 ] is used to render static images of the world. The image formation process is modeled as a series of image degradation transformations represented by point spread functions (PSF). PSFs can be analytically calculated for shutters of different types [ 220 ] and are specific of each object’s relative motion. In general, postprocessing do not properly handle effects that are baked into the image, but this method can blur reflections and refractions by explicitly convolving each object’s rendering samples with the PSF. Figure 4.15 shows an image rendered with this technique. 4.3 motion blur rendering algorithms 63 Figure 4.15: Method of Potmesil [ 191 ]. Left to right: Instantaneous snapshot, using extended exposure and simulating several exposures of finite length. A similar model is proposed by Max and Lerner [ 152 ]. Objects having similar motion are skewed in the direction of maximum movement according to the intensity of the motion. Incremental summation is used to add blur. Blurred images are unskewed using the inverse of the original transformation before they are alpha composited. In this method, Potmesil’s PSF is replaced by an equivalent blurring process, with the rest of the algorithm remaining similar. As a result, both methods have the same limitations. Sharing common points with the reprojection methods explained in section 4.3.5.2, morphing methods exploit frame to frame coherence [ 40 ]. Motion estimation for each sample is described using precomputed morph maps that are constructed from the image pixels, their depth information and the camera transform. While the main focus of the technique is efficiently generating scene walkthroughs, images can incorporate motion blur by generating several temporal samples per rendered pixel. This method is not specific to CG imagery and can also be applied to any images given range data is available [39]. 4.3.6.1Methods based on motion fields An alternative approach is based on synthesizing vectorial fields containing the direction and speed of each image pixel. A motion field represents a snapshot of the dynamic status of the system and it is used as a replacement for the real movement during exposure time. Object motion can be intricate, so these methods are a compromise between simplicity and accuracy. However, some of them are capable of efficiently rendering production quality motion blur. 64 motion blur rendering:state of the art Figure 4.16: Motion blur using the technique of Brostow and Essa [ 19 ]. Images at the top are two instantaneous pictures taken from the original scene. Bottom image shows the resulting motion blur applied to the propeller. Shinya [ 225 ] calculates spatial and temporal antialiasing by applying an image transformation that is built on the motion flow of a sequence of images. The pixel-tracing filter is adapted to gather information from sequences of different lengths, with linear computation times. Samples from each image are weighted and combined together so a trail of the object is produced. The method proposed by Brostow and Essa [19] can be used when no information from the original scene is available. This is the case for stop motion animated sequences where each image is a photograph. Initially, foreground and background pixels are separated using a motion detection procedure. The moving foreground is then segmented into contiguous pixel blobs that are matched between consecutive frames using an exhaustive search. An initial estimate of the velocity field is locally refined using hierarchical optical flow [ 12 ] and the resulting velocity is used to smear each pixel assuming constant speed and linear trajectories during the simulated exposure. The results can be observed in Figure 4.16. 4.4 method comparison 71 Motion blur may also be seen as an effect that needs to be corrected. Pictures taken with long exposure times may contain unexpected motions that can compromise the spatial resolution of the captured image. Artificial motion blur can be recreated by integrating motion compensated snapshots [241]. 4.4 method comparison In the previous sections, we have provided a detailed description of most of the algorithms that can integrate motion blur in computer generated images. In this section we compare them, identify their computational requirements and focus on identifying which methods are applicable to each specific situation. From an operational point of view, an important element to consider is the type of inputs that the algorithm can process. Some methods are specific to certain geometrical representations while others are capable of accepting a wider set of primitives. In the first category, the most popular representation is polygonal geometry [ 81 , 35 , 46 , 237 ], that may be processed using hardware acceleration both for primitives [ 275 , 240 , 83 , 109 ] and textures [ 4 , 145 ]. Other methods can handle NURBS [ 192 ], spheres [ 123 ], particles [ 200 ] or voxels [ 85 ]. Non eulerian fields, such as liquids and gases, can be converted to polygonal representations but they have also been considered without previous transformation [ 117 ]. Monte Carlo methods, section 4.3.5, can accept any geometrical description given that it can be point sampled. Postprocessing algorithms are fairly independent from the type and geometrical complexity of the scene. Motion information can be extracted directly from the images using adhoc heuristics [ 225 ] and optical flow methods [ 19 ]. In some cases, motion data from the scene is used [ 224 ], while in other situations rendered velocity, object-id or depth passes [ 285 , 230 ] may be used. An in-between approach is used by reprojection algorithms [ 40 ], where the original geometry of the scene is needed, but only as a mean to finding novel positions for precalculated shading samples. An important criteria that helps determining the respective merits of each method is the degree of quality of the results . Do we want to produce motion blur that is physically based, photorrealistic or just a cue to the evolution of the scene? In one extreme, geometric replacement use gross shading and geometrical approximations but is capable of producing high frame rates. Common simplifications are based on roughly approximating the original motion [ 275 , 83 , 109 ], non physically based energy distribution [ 200 , 240 ], artistically driven motion trails [ 85 , 216 ] or even alpha transparency as a replacement for the light integration process [ 275 , 109 ]. A number of methods avoid the computation of all but local lighting events [ 175 , 123 , 81 , 275 ]. 72 motion blur rendering:state of the art Motion blurred shadows, reflections, transparency or refraction are difficult to achieve with these methods. A special case is represented by postprocessing and reprojection methods. They both base their computations on prerendered samples whose radiance is the result of completely simulating a given lighting model. View dependent phenomena have to be explicitly handled by, for example, storing intermediate stages of the render. A small group of algorithms accurately model dynamic geometry and shading. They are frequently based on intensive point sampling which makes them them the most computationally heavy approaches [ 45 , 237 , 29 , 251 , 261 , 89 ]. Recent developments have improved this situation [ 65 , 182 , 194 ]. Extended descriptions and a discussion of their respective sampling approaches have already been exposed in sections 4.3.5.1,4.3.5.2and 4.3.7. These can be combined with the methods described in section 4.3.8so that the influence of the recording device is accurately modeled. If we consider the complexity of the motion , most algorithms approximate intraframe object motion with piecewise linear paths. These paths may be defined at object or vertex level which allows rigid object motion [ 152 , 275 , 85 ] and deforming polygonal meshes [ 109 ] respectively. Most methods interpolate motion using a single straight segment built from one or two temporal samples. Some algorithms assume the original motion has to be linear in world space [ 35 ], while other will use alternative coordinate systems to enforce more restrictive motions [123,163,19]. To our knowledge there is no published algorithm capable of using the original path or equivalent non linear approximations. The nature of the motions and the shutter times involved in the computation (a maximum span of 33 milliseconds at 30 frames per second) makes assumptions like path linearity and constant velocities safe for an ample range of situations. The most flexible extreme is represented by distributed ray tracing [ 45 ] and its Monte Carlo based descendants that can generally evaluate both true shading and intricate motion at any point of the problem domain. Different methods use alternative assumptions on the number of samples that are representative of the whole aperture range. Some of them, postproduction and geometric replacement methods, simply evaluate the lighting functions once, usually at the start or middle of the time slot. Image samples can also be based on several time instants that are randomly selected [ 54 ], from a predefined pattern [ 90 , 4 ] or stochastically determined [ 46 ]. While the differences can be subtle, a properly selected sampling method can alleviate aliasing artifacts that are perceptually objectionable [50]. In certain situations, the availability of computational resources determines which algorithms are applicable to a given scenario. Geometrical replacement methods, section 4.3.3, are usually good candidates 4.4 method comparison 73 to be included in those hardware frameworks where polygonal geometry, texturing and depth culling can be efficiently evaluated. Real time anisotropic filtering allows the use of techniques previously reserved to offline renderers [ 145 ]. Gaming frameworks can also provide real time rates by using postprocessing [ 209 , 230 , 256 ]. However they are frequently constrained to certain types of motion. Given the existence of GPU based optical flow algorithms [ 162 , 185 ], motion field based methods may also be implemented in real time. Monte Carlo methods, due to computational complexity, are usually reserved for batch rendering environments. Only a few methods based on accumulation buffers [ 90 ] and frameless rendering [ 11 , 54 , 55 ] have implemented subsets of distribution ray tracing at interactive frame rates. Recent works based on the REYES rendering architecture may also open the door to efficient hybrid methods [288,68,16,20,101]. Most Monte Carlo and hybrid algorithms are also known for being memory hungry algorithms. They are usually associated with intensive ray traversals which results in incoherent memory accesses and the need to store the whole scene in memory. Acceleration structures such as Kd-trees and BSPs can improve efficiency [ 258 ] at the cost of extra memory usage. The need to keep in memory both light paths [ 251 , 261 ] and samples until the image is reconstructed [ 89 , 65 , 182 ] also contribute to this extra cost. In summary, and from a strictly practical point of view, there is a tradeoff between the models that can efficiently produce approximate results, and a computationally heavy implementation that accurately calculates the light integration process. For those cases where rendering time and computational resources are not the limiting factors, both hybrid methods and those based on distributed ray tracing are the best candidates. They are capable of producing the most accurate solutions as well as modeling the most complex phenomena. Among all of them, the REYES architecture is probably the one with lower requirements even if, in some cases, it needs to rely on external ray tracers to implement global lighting models [ 41 ]. Together with distribution ray tracing, their extensions for photon mapping, lightcuts and metropolis transport and the model of Sung et al. are probably the most flexible. In those cases where images must be produced at interactive frame rates, geometrical replacement and postprocessing are the primary categories to consider. Every algorithm in these categories are tailored to solve specific subsets of the problem. Real time postprocessing methods are constrained to specific types of camera and object deformation. In any case, there is a clear preference for them in current game architectures [209,230,256]. In those cases where a full flagged method is not an option and there is no need for real time solutions, postprocessing methods such as the one of Brostow and Essa [ 19 ] and Zheng et al. [ 285 ] are capable 74 motion blur rendering:state of the art of producing adequate results that in some cases can be comparable to other more expensive methods. 4.5 future directions Recent research trends seem to be focused on two diverging directions: finding improved sampling schemes to evaluate the rendering equation; and implementing more efficient algorithms based on hardware acceleration . Whether the solution comes from focusing computation in the most important areas of the image or redesigning algorithms to make use of parallelism, the main challenge is the efficient use of limited computational resources. An unexplored approach is based on the complex relationships between the human visual system and how objects in motion are perceived . We know the HVS is an incredible biological design even though it is not free of limitations in its spatial [ 30 ] and temporal resolutions [ 115 , 217 ]. Its response is non linear with respect to light wavelength, chromatic and achromatic light [ 278 ]. Perceived images are not fully focused [ 8 ] and in some circumstances may be noisy [ 274 ] or contain aliasing [ 280 ]. Also, temporal and spatial integration seem to be an important factor in the perception of images in motion [125,22,222]. Knowledge of perceptual mechanisms have been successfully exploited in fields like image quality assessment [ 51 , 199 ], tonemapping [ 28 ] and geometric modeling, rendering and simulation [ 52 , 164 , 181 , 6 ]. There is good foundation to think a similar approach can be applied to rendering motion blur. Computational optimizations can exploit the fact that certain stimuli are not perceived or generate such a low response that can be ignored. Also, existing methods are tuned to produce antialiased images at the image plane sampling rate. Even if this is a reasonable assumption for static images, the limited attentional bandwidth of the HVS makes us think this rate can be relaxed. Also, given the existence of a temporal window of integration, each frame can be rendered taking into account a context that includes the images immediately before and after. This gives opportunities for further improvement. In previous sections, we also have implicitly accepted that all temporal samples are equally important. In light of HVS’ non-linearities this may not be a correct assumption. Determining which integration mechanisms take part, whether they are biased or not and how we can simulate them are important questions that remain unanswered. Algorithms that are aware of the differences between what is perceptually acceptable and what is physically and numerically accurate can also be used to produce motion cues as a substitute for ideal motion blur. 4.6 conclusion 75 4.6 conclusion This chapter provides an overview of the state-of-the-art in motion blur rendering techniques. We have started our discussion with a description of the physical phenomena and mechanisms involved in the generation of motion blur in film and recording devices. We have also described a formalization that, in the context of computer generated images, mathematically models the light integration process. It explains the complex interactions that take place in an animated scene based on the objects’ geometrical relations and their shading functions. Existing motion blur rendering methods have been categorized according to the approach followed to evaluate this expression. An organization based on analytical, geometrical substitution, texture clamping, Monte Carlo, postproduction, hybrid and physically inspired methods is the result of this effort. Simulation of motion blur is known to be one of the areas of the rendering pipeline that is heavier in computational resources. We have classified the methods based on their processing requirements and areas of application. Finally, we have briefly introduced a possible area of improvement that, by exploiting the limits of our perceptual system, can provide performance gains. This family of temporally aware methods is an exciting and novel direction that is explored in the following chapters. 5 PERCEPTUAL CONSIDERATIONS FOR MOTION BLUR RENDERING Motion blur is an important cue for the perception of objects in motion. This phenomenon results from the light integration at the imaging device’s sensor combined with object or camera motion. This generates a visible streak that follows the trajectory of the movement. It is naturally produced by both film and digital cameras although it has also been leveraged as an artistic resort [187]. Computing motion blur is a requirement for computer generated images where it is used to generate more natural looking images, as well as, to reduce time sampling artifacts such as strobbing, flickering and stuttering. Unlike with real cameras, syntethic images need to explicitly simulate motion blur. While the methods to produce synthetic motion blur have been studied and classified [ 170 ], the perceptual aspects associated with the observation of motion blurred images have not received the same attention. Research has mostly been focused on determining the lower level capabilities of the HVS (human visual system). These works have relied on controlled studies where the stimuli are composed of gratings, gradients and moving dots. There is still the need to determine how these mechanisms work with imagery that is representative of the complexity of real world scenes. We believe this work is one of the first that exposes some insight in this area. In the next sections we design a series of psychophysical experiments to determine how the HVS reacts to complex stimuli. This study also links the perceptual and practical algorithmic aspects of the problem. We have used path traced images of objects under the influence of complex lighting with the intention of associating standard rendering parameters such as shutter time and antialiasing level to their corresponding perceptual effects. This problem is inherently multidimensional and the interplay of the different aspects involved is complex. However, this study is targeted to give answers to simple questions such as: When the scene is composed of simple materials, can a render be produced at a reduced cost without perceived quality loss? Do users detect the difference between alternative shutter times? How important are high sampling levels in the computation of motion blur? The conclusions and recommendations contained in this work may prove useful for the production of photorealistic images. We hope that CG practitioners, render technical directors, shader writers and hobbyists will be able to apply them to minimize render times and 77 78 perceptual considerations for motion blur rendering Figure 5.1: In this work, we explore the implications of alternative scene properties and rendering parameters on the perception of motion blurred images. In the figure, a matrix showing a subset of the stimuli used in a series of psychophysical experiments: Columns, from left to right, use shutter times T1(0% of the frame time, no motion blur), T2(25%), T3(50%), T4(75%) and T5(100%). Rows, from bottom to top, use antialiasing levels A1(4samples per pixel), A3(256 samples) and A5(512 samples). reduce scene complexity without visual quality loss. These results may help settle some ground for the implementation of perceptually inspired motion blur rendering methods. This is especially interesting for the production of feature films and VFXs, where the cost of generating temporally antialiased images may be several times higher with respect to their non-motion-blurred equivalents. Even more, its importance is clear given that render times are usually optimized by following intensive hand-made processes. 5.1 previous work The literature covering the perception of computer generated stimuli has identified different psychophysical trends. Recent examples include models for the psychophysics of photorealistic materials [ 249 , 211 , 105 ], natural illumination [ 73 , 27 , 128 , 144 ], occlusions [ 124 , 282 ], the ability to differentiate close variations of the stimuli [ 199 , 154 ] and has also described the influence of object variety [ 153 , 198 ]. However, none of these focus on the specifics of motion blurred images nor time varying images. Motion blur rendering has received an important degree of attention. Existing works have mostly focused on the algorithmic aspects of the problem and describe methods capable of performing temporal antialiasing on different frameworks. We refer the reader to the work 5.1 previous work 79 Figure 5.2: Detailed view of the renders at the four corners of figure 5.1. Noisy artifacts are visible in the images computed with lower sampling levels (bottom row), while the snippets at the upper row are clean. Upper left render was computed without motion blur, while the right one uses a temporal window of 100% the frame time. of Navarro et al. which contains detailed classifications and extensive descriptions of the state-of-the art of the existing techniques [170]. Even if not specific to computer rendered images, the perceptual aspects of temporally varying images have also been described [ 3 ] [ 269 ] and their corresponding sensitivity functions [ 134 ] [ 208 ] [ 255 ] have been clearly determined. The work of Burr and colleagues is fundamental in this area, being the first ones to describe motion smear, identify the window of temporal integration and quantify the perception of motion blurred stimuli [ 22 ] [ 25 ]. Even if many of the psychophysical factors have been clearly determined, the literature covering how the HVS reacts to dynamic photorealistic stimuli is still scarce. This chapter focuses on this aspect while exploring the implications of using Monte Carlo rendering algorithms. Other works have focused on determining how visible certain features are when they are observed in a picture or a rendered image. As such, the corresponding saliency functions have been suggested [6] [142] which, in some cases, are temporally aware [284] [262] [250]. Other studies have proposed alternative perceptual metrics that can determine how different two images are [ 149 ] [ 263 ] [ 197 ]. The tempo- 80 perceptual considerations for motion blur rendering ral component has been considered notably in the context of video processing [270] [279] and quality assurance [266]. 5.1.1Perception of motion blur The existence of a temporal window of integration produces an effect that is known as motion smear. During a certain time span, the light hitting the retina is accumulated. As a result, each spatial location contains an image that represents the evolution of the scene and not a discrete snapshot of it. Depending on the stimuli and environmental conditions, the window of integration can span from a few milliseconds to several seconds [269]. Peripheral vision [ 23 ] is specialized in the detection of moving objects. Even if it is limited to low spatial frequencies, it is tuned to detect high temporal frequencies. This increases the chances of detecting image flickering, an artifact that is frequently present in low quality rendered images. In contrast, wide fields of view use an alternative visual channel that is specialized for object identification. While it is adapted to prioritize high spatial frequencies, high temporal frequencies are also processed although with reduced efficiency. Temporal integration, increased temporal frequency detection and motion generating faster retinal speeds, may lead to increased perceived blurriness even if this extra blur is not present in the original image. The opposite is also true: Images may look sharper than they really are. Motion deblurring [ 195 , 24 ] is triggered for moving objects and in some cases, perceived images may appear less blurry than their static incarnations. This is thought to be a mechanism to increase the resolved amount of detail in the images of moving targets. The detection of motion itself has been explained using several models that are based on space-time filtering. They focus on the idea of finding moving brightness patterns in the retinal image [ 3 ] [ 268 ]. Alternative explanations exist for second-order motion generated by variations in contrast and flicker which may be helpful in the presence of occlusions and transparency [ 72 ] [ 95 ]. Finally, the surrounding environment has also been identified as a cue to detect motion [ 143 ]. Our study has been designed to analyze perceived quality as the absence of rendering artifacts. As such, we have chosen stimuli that exceed the threshold for motion detection, contains no object occlusions and contains a single object that can be comfortably tracked by the eyes. These images do not make use of any depth of field, so this source of static image blur is also excluded from the study. 5.1.2Technical aspects of motion blur perception The algorithms associated with motion blur rendering will be briefly described in Section 5.2. A by-product of these approaches is the 5.5 test #1:broad comparison 87 Figure 5.4: Percentage of trials where a particular animation is perceived with higher quality. Blue/orange bars represent the corresponding values for noise/checker material (M3/M2), medium/high speed (S2/S3), medium/long shutter time (T3/T5) and medium/high antialiasing level (A3/A5). Each group of bars shows from left to right, the results for all, experienced and naive users, respectively. Error bars represent the standard error. shutter times and medium (A3) and high (A5) antialiasing levels. For each trial, the two videos are displayed in sequence one after the other and subjects are allowed to repeat them as many times as required. The pairs are configured so all combinations from a pool of 16 videos are used. The order of the videos in each pair is randomized, so it is the sequence in which the pairs are shown. 5.5.2Results The results show that users perceive higher quality in the renders containing the noise material, medium speed and medium shutter time. A certainty of 95% has been confirmed using a Chi-square test. The answers, represented in Figure 5.4, have different qualitative interpretations: • The preference for the noise material (67%) seems to be related to the fact that objects whose shading looks too clean or very regular are perceived as unrealistic. Also, the checker material, while not affected by sampling noise, produces more stroboscopic artifacts at every antialiasing level. These results are consistent both for medium and high sampling levels. • Users manifest a preference for the medium speed in 66% of the situations. The reasons reported were excessive blur, lack 88 perceptual considerations for motion blur rendering of detail and a noticeable level of noise in the images using the fastest speed. • Medium shutter times are chosen in 70% of the cases as longer values produce slightly unnatural images due to excessive softness. • More significant is the absence of a clear preference for any of the antialiasing levels (the highest quality setting has received just 5% more votes). However using a visual differences predictor operator [ 150 ], the images of individual frames are reported as perceptually different. This suggests that while an accepted mathematical model can detect the differences on static images, the HVS has difficulties finding differences when the temporal dimension is involved. Segmenting the results according to the users’ knowledge of computer graphics has not shown any statistically significant differences. That said, experienced users took notably longer to complete the test with an average of 11:23 minutes versus 8:28 minutes. We attribute this to this prior knowledge preconditioned them to ensure the answer was the correct one. In some cases, and given the subtle image differences, this represented a challenge. In practical terms the previous results support the idea that certain types of renders can be optimized without visible perceptual degradation, that is, scenes rendered with reasonable levels of quality may be indistinguishable from a gold standard even if the later may have been calculated using more computational resources. This insight will be refined in Sections 5.6and 5.7and gives us a good foundation for the remaining tasks of the study. 5.6 test #2:tolerance to variations in shutter time and antialiasing level The next study focuses on the parameters that can be considered specific of the rendering algorithm: shutter time and antialiasing level. For someone involved in the most practical aspects of the rendering pipeline, these are the only dimensions where he will be allowed to have a direct impact on. In this section we will determine how efficient observers are when two different stimuli need to be matched, or said in a different way, in which cases two sequences cannot be differentiated even if they have been rendered with distinct settings. 5.6 test #2:tolerance to variations in shutter time and antialiasing level 89 Figure 5.5: Answers to the shutter speed (left) and antialiasing level tasks (right). The gray level in cell (i , j) represents the percentage of answers that were correct when the matching task involved stimuli i and j , with darker values meaning less accurate responses. User responses were normalized and are given in terms of a percentage that is equivalent to the response of an imaginary user who provides the same answers. Values T1to T5correspond to increasingly longer shutter times, while A1to A5represent low to high antialiasing levels. 5.6.1Description The test is composed of two matching tasks. Each task fixes the values for three of the dimensions and use different values for the other one. Fixed dimensions are set to the option that a majority of users preferred in Test #1. The free dimension, shutter time for the first task and antialiasing level for the second, uses the five values available. The set of resulting videos are paired so every possible combination is tested. One of them is randomly used as a reference and shown at the top of the screen. Both videos are then played at the bottom of the screen and the user is requested to select which one matches the reference. Videos are played in sequence and can be repeated as many times as required. Sixteen participants completed each task. 5.6.2Results Shutter times can be accurately matched in 86.25% of the cases. A summarized view of the answers is represented in Figure 5.5, left, with brighter areas for those values with the most accurate answers. Matching is done with high success rate in all the pairs comparing the most differing stimuli. Accuracy is lower in those pairs using videos with less diverse values. That is why darker regions surround the diagonal. We have found that: • The high number of incorrect matches that is found when comparing pairs using T1-T2-T3suggests that the strobing artifacts present in these sequences are so objectionable that, in practice, they are visually equivalent. • Values T4and T5seem to be distinguishable. The test in Section 5.5already raised the importance of excessive blur in the images, 90 perceptual considerations for motion blur rendering so we think the differences in the amount may be a cue that is used to differentiate these sequences. Matching sampling levels seems to be a more challenging task in which the percentage of success drops to 63.75%. This is also supported by an increment in the effort required to complete the taks (an average of 7:49 minutes compared to 6:12 for the previous task). Figure 5.5, right, shows the results as a matrix. We can observe that: • The most accurate answers are concentrated in the lowest sampling levels A1, A2and A3where the artifacts are more visible. • Comparisons between higher sampling levels, A4and A5, produce percentages near chance. For these values, the videos can be considered indistinguishable from a gold standard. The previous findings suggest that if the HVS is forced to work near its perceptual limits and given a certain level of quality is reached, it becomes less interesting to make further improvements as they become increasingly less noticeable. It is important to note the lack of accuracy that can be observed in the pairs comparing really low and very high sampling levels.This deviates from the expected trend and the empirical results. We have attributed this singularity to the complexity associated with the task itself. Users informally confirmed that in the shutter time task, the amount of blur and artifacts associated with each level where visible enough to allow an accurate matching. However, we believe that for this task, the lack of strong cues and the importance of visual memory and retention may be factors that need to be considered as a source of bias [ 57 , 247 ]. This may be the reason behind the reduced accuracy exhibited throughout the test. Section 5.6.3contains further results on this. 5.6.3Discounting the effects of memory and matching ability In order to cut the previous effects out, we performed an alternative 2AFC subtest with the five sampling levels. Users were requested to select the stimulus they preferred from a pair of alternative sequences. The selection criteria was the perceived quality under similar conditions to the ones explained in Section 5.3. Ten users completed a task composed of twenty pairs of sequences, twice for each possible pairing. Based on their answers, we perform a significance test following the approach described in previous works [ 87 , 210 ]. With this method, answers can be clustered in statistically indistinguishable groups based on an analysis of score differences. Two groups can be considered similar when the difference between their scores R is below dRce . Using a significance level α of 0.01, we compute Rc so that P(R⩾ 5.6 test #2:tolerance to variations in shutter time and antialiasing level 91 dRce)⩽α [ 218 ]. It can be shown [ 53 ] that Rc can be obtained from P(Wt,α⩾(2Rc−0 . 5)/√nt) , with n the number of participants and t the number of samples we compare (20 and 5in our case). Values of Wt,α≈4 . 604166667 and dRce=24 can be retrieved from Pearson and Hartley’s tables [186]. Results show that users consistently prefer high over low sampling levels: A5was selected over any other level in 59 cases; A4in 51; A3in 48; A2in 34 and A1in 8. Three groups can be built based on these values: the most voted containing A5, A4and A3; second most voted grouping A4, A3and A2; and a final group containing A1. These groups contain stimulus that are perceptually indistinguishable even if users are capable of finding differences between each group. Lower sampling is unequivocally associated with lower quality levels, whereas other stimuli are not so clearly differentiated. In general, these results confirm the capability of the HVS to detect alternative quality levels, and also confirm the suspicion that other factors related to the complexity of the task may affect the performance in the previous matching test. In general, CG-aware participants show a slightly higher accuracy in their answers: 11% when shutter time is considered and 4% for the sampling level task. Since the videos are not played simultaneously, visual memory and other acquired abilities may be influencing factors. The ultimate intention is determining how effectively spectators perceive motion blurred stimuli and in which cases the lack of quality is noticeable. In the most frequent situations, a single sequence will usually be displayed. The previous tasks can be considered a compromise between this visual experience and the case where several videos are played simultaneously. With independence with respect to the HVS’ capabilities to detect such subtle changes in the individual images of a sequence, there are other factors that we have consciously left outside this study. There are many studies that support the influence of phenomena such as inattentional blindness [ 147 ], the attentional spread associated with multiple object tracking [ 193 ], change blindness [ 205 ] and attentional blink [ 221 ]. On the other hand, there is evidence that, in situations where a single element receives all the attentional resources, perception of contrast and spatial frequency is enhanced [ 140 , 1 ]. As such, the participants in this study have completed the test under conditions where any issues associated to the quality of the images should be easily detected. These studies support our belief that under less constrained viewing conditions, the mechanisms involved in the detection of those artifacts may probably fall shorter and more aggressive simplifications could be possible. 92 perceptual considerations for motion blur rendering 5.7 test #3:interactions between shutter time and sampling level The objective of this test is uncovering the existence of any interactions between shutter time and antialiasing level that may affect observers’ performance to differentiate between alternative stimuli. Monte Carlo algorithms, namely those inspired on distribution ray tracing, sample the strata defined for all dimensions of the rendering equation simultaneously [253]. Thus the more complex the geometry and shading functions are, the higher the chances these methods require further computation to produce an accurate approximation and avoid aliasing. Using any rendering engine will immediately reveal these underlying correlations. This section will help support this interpretation based on the results of a new psychophysical test. 5.7.1Description In this test, participants have been requested to complete a 2AFC routine. In this case, the checker material and medium speeds have been fixed in accordance with the preferences manifested in previous tests. Shutter time take the values T3, T4, T5and antialiasing level use A3, A4and A5. Two movies are shown in sequence and observers are requested to select the one with the highest quality. Every pair comes from a pool of 36 tuples containing all possible combinations of the two free parameters. The rest of the conditions and associated explanations are similar as with the previous tests. 5.7.2Results Circular triades have been searched as a method of detecting inconsistencies (i.e. users manifesting preferences that result in contradictions: sequence X1 is preferred over X2 , X2 over X3 but also X3 over X1 ). The coefficient of consistency ξ [ 116 ] is found to be 0.6492, which suggests a relatively low number of inconsistencies. The coefficient of agreement u , in a theoretical range of [−1/21 , 1] , is 0.2794, that is, a moderate agreement among users. The results have been analyzed using a significance test similar to the one detailed in the previous section. In this case, we set the significance level α to 0.01 with n the number of participants and t the number of samples equal to 21 and 9. We compute Wt,α≈5.0769231 and dRce=36. Figure 5.6shows the resulting groups. Group1to Group4have been ordered by decreasing number of votes. Group1, in blue, packages all the images calculated with the shortest shutter time T3and those com- 5.7 test #3:interactions between shutter time and sampling level 93 Figure 5.6: Grouping of the scenes rendered with different antialiasing and shutter time settings. From left to right: Shutter time T3, T4, T5; from bottom to top: Sampling rates A3, A4, A5. Group1to Group4, most to least voted, have been highlighted using blue, red, green and gray respectively. puted using T4and the lowest sampling levels. Group2and Group4, in red and gray, contain all the sequences that have been rendered using shutter settings T4and T5respectively. From the previous partitioning, we can conclude shutter time drives users’ answers with the antialiasing level taking a secondary role. The implications are important and twofold: • first, all the renders computed with any of the settings belonging to a given group are perceptually equivalent to any other render in the same group; • second, the most expensive renders can be optimized by just selecting the parameters that belong to the same group that require the least computational resources. In terms of ordering, each sequence has been preferred over any other according to the following number of votes: A4T3,125; A3T3, 124; A5T3,119; A5T4,96; A4T4,90; A3T4,78; A5T5,46, A4T5,40, A3T5,38. All the previous confirms our first findings, suggest the interplay between different dimensions can be useful in the presence of perceptual limits and opens interesting possibilities to reduce computing requirements. 94 perceptual considerations for motion blur rendering Figure 5.7: A pair of perceptually equivalent renders. Images have been computed using different sampling settings (left,bottom: T5and A3; left,upper: T5and A5). Right image shows a zoomed version of the bitmaps. The lower image was rendered in half the time to render compared to the upper one. 5.8 conclusions and future directions The existing knowledge on the perception of motion blurred images was based on stimuli that was not representative of natural world scenes. We have expanded the results to those situations where the stimuli is based on simple photorealistic images. We have found evidence that psychophysical limits, in line with the ones found with simpler stimuli, are applicable and take an important role on perceptual tasks. We believe there is also a spread of the attentional resources to complete more demanding tasks, as such; the tolerance to noise and high frequency artifacts is notable. This insight comes from different psychophysical experiments that are based on high level properties of the 3D scenes and parameters of the render algorithm. These are object material, object speed, the shutter time simulated by the virtual camera and the antialiasing levels applied by the algorithm. The results suggest that, in some cases, images can be produced using aggressive simplifications without degradation of the perceived quality. In a practical situation, these results can provide methods to drastically reduce the render times and the computational resources required. As an example, Figure 5.8shows two pairs of images, each one using the same object rendered using alternative settings. In each pair, the image that was rendered with the highest sampling level took double the time to render. Even if these images are noticeably different when compared side by side, they are perceptually indistinguishable when played at the viewing conditions considered in the study. 5.8 conclusions and future directions 95 Figure 5.8: A second pair of perceptually equivalent renders. Images have been rendered using alternative sampling and shutter time settings (bottom: T3and A5; upper: T4and A3). Right image shows a zoomed version of the original images. In this case, the upper image was rendered in half the time. There is still work to be completed to to provide more detail for the material and object speed dimensions. The results can also be extended to a wider set of scenarios covered by the rendering equation. Elements such as geometrical occlusion, evolving shading, level of detail or morphing geometry may also be explored as they are known to produce a shift in the appearance of the objects. This may potentially lead to formal models explaining the existing perceptual limitations as well as an expansion of concepts such as visual equivalence [197]. 6.3 perceptual tests:overview 103 pattern of noise that is produced, even if static for a single eye, may not match between different eyes. This results in inter-ocular disparity which, in a extreme case, can make stereo fusion difficult and prevent stereopsis. In the current scene, the most problematic areas are produced by shadows, global illumination, texture sampling and motion blur. The area that may show the most visible issues is the motion trail, which represents a significant percentage of the image pixels the bigger the faster the motion. Speed increases the chances of detecting issues in the image. Figures 6.2and 6.3shows examples of images rendered with different sampling levels. Each eye is compared side-by-side and their pixel differences shown in false color. The images show that the absolute differences are much more intense in the low quality render which is results in more intense interocular disparity. 6.3 perceptual tests:overview As in the case of monoscopic images, we have designed a set of tests to determine the influence of each of the rendering parameters in the perception of motion blurred stimuli. From previous knowledge and in the absence of clear assumptions, we can anticipate two outcomes based on two extremes: • The HVS is less efficient detecting rendering artifacts when the stimuli is composed of stereo pairs. So renders can be accelerated using aggressive assumptions without visual degradation. • On the other hand, stereo fusion may impose severe requirements between the images in the stereo pair. Rendering artifacts may violate those requirements and generate disconfort or prevent stereopsis. So renders may require increased quality and as a consequence, extended rendering times. We will focus our efforts on four different tests, that mimic the ones that thrown the most salient results with monoscopic images. In particular, see Table 6.1, we will perform all the 2AFC tests and exclude the matching tasks. Depending on the task, between 18 and 32 participants completed the tests. The proportion of males to females is roughtly 3:1. Ages ranged between 20 and 40 years old, with an average of 28. Half of them had working experience in computer graphics. All of them self-reported normal or corrected to normal vision. The sequences where displayed in similar dim lighting conditions using a LCD monitor 17.3" diagonal, 1680x1050x120Hz, sRGB color space, contrast 20000:1, luminosity 300 cd/m2 , gamma 2.2. NVidia 3D Vision shutter glasses were used to generate stereo perception. Participants were placed at roughly 60 cm of the screen. In these 104 influence of stereo vision on motion blur perception test type dimensions #1Broad comparison 2AFC All (2each) #2Shutter time / Antialiasing level 2AFC Shutter time (5) / Sampling level (5) #3Shutter time and antialiasing level 2AFC Shutter time (3), sampling level (3) Table 6.1: Psychophysical tests completed by the participants in the study. The Dimensions column lists the dimensions considered by each test, with the number of values used for each axis between parentheses. The dimensions not listed in a given test are sampled at a single value. conditions each of the sequences subtended 14.4degrees of visual angle. 6.4 test #1:broad comparison In the previous chapter we found that users preferred the noise material, medium speed and medium shutter time over any other alternatives. Participants supported their decision based on the absence of visible artifacts, a moderate amount of bluriness and the increased realism of the image. In this section we repeat the same test, this time using stereoscopic stimuli. As before, participants were asked to select one out of two videos according to the question Which sequence has higher quality? Prior to starting the task, every subject was briefed about the most important image features that characterize high quality renders. They also had the opportunity of practising with pairs of stimuli whose differences in quality were so obvious that the answers were straightforward. Figure 6.4shows a graphical representation of the answers, classified by the type of participant. Figure 6.5compares the statistics found for the same test performed with monoscopic and stereoscopic images. In all cases, a certainty of 95% has been confirmed using a Chi-square test. A detailed review of the answers shows the following facts: • Preference for the noise material is higher than for the checker material. This result is equivalent to the one shown for monoscopic stimuli (a difference of less than a 2%) and we attribute it to similar causes: the existence of stroboscopic artifacts. Even if these issues exist for both materials, the checker material contains bigger patches with flat color that tend to make them more visible. • Stereo speed preferences are balanced. Note that the percentages with respect to the monoscopic test differ in more than 15% and error tolerances are slightly higher. However, considering pure statistical results, both are within similar ranges. Even if the 6.4 test #1:broad comparison 105 Figure 6.4: Percentage of trials where a particular animation is perceived with higher quality. Blue/red bars represent the corresponding values for noise/checker material (M3/M2), medium/high speed (S2/S3), medium/long shutter time (T3/T5) and medium/high antialiasing level (A3/A5). Each group of bars shows from left to right, the results for all, experienced and naive users, respectively. Error bars represent the percentage of error. quantitative evidence cannot point to one of the speeds, informal observation of the images using the stereoscopic setup lead us to think the extra cues associated with stereo vision (parallax, image disparity, increased perception of depth and volume, ...) may be aiding the HVS to understand the scene. Also, the excess of noise that was reported for the fastest speed in single eye tests seem to be less noticeable. • Shutter times is the result where preference seems to be more defined. As with previous results, the excessive softness reported for the fastest motion seem to be reason behind it. • Also, antialiasing levels are equally preferable. As with the monoscopic stimuli, the visual differences predictor shows the noise between the aligned stereo pairs are above JND (just-noticeabledifferences) as well when the same eye is compared between different sampling levels. • Even if the images for each eye are generated with two independent render processes and the patterns and associated artifacts do not correspond pixel by pixel, see Figure 6.2and 6.3for examples, participants did not report any issues and were capable of completing stereo fusion without noticeable discomfort. All of the previous points makes us think that attentive resources may be diverted toward generating stereopsis. These results seem to 106 influence of stereo vision on motion blur perception Figure 6.5: Comparison of the answers for mono and stereo stimuli. Bars represent the percentage of trials where a particular animation is perceived with higher quality. Green/red and orange/blue bars represent the corresponding values for noise/checker material (M3/M2), medium/high speed (S2/S3), medium/long shutter time (T3/T5) and medium/high antialiasing level (A3/A5). Each group of bars shows from left to right, the results for stereoscopic and monoscopic stimuli, respectivelly. Error bars represent the percentage of error. suggest that cognitive tasks such as completing the fusion between the two images may take precedence over other tasks like noise and artifact detection. This is an interesting finding that will need to be confirmed in the next sections. 6.5 test #2:tolerance to variations in shutter time and antialiasing level In this section we will determine the observers’ relative capability to detect changes in image quality when the rendering method is modifies the value of a single of the dimensions. From the four parameters studied in the previous section, this exercise focuses on shutter time and antialiasing level. These are the settings that are determined by the algorithm and not the aesthetics of the scene. While they have a direct impact on the quality of the images, they do not essentially change their contents. As a secondary target, we will try to identify the common characteristics of the groups of movies that produce similar perceptual effects. This provides opportunities to optimize rendering jobs, and in case the alternative parameters are selected from the same perceptual group, without loss of quality. 6.5 test #2:tolerance to variations in shutter time and antialiasing level 107 6.5.1Description In the previous chapter, we determined that certain aspects such as visual memory and user professional background may affect the performance of the observers to match video sequences. A secondary test was required to discount the effects of these elements (see section 5.6.3for a complete description). The current test aims to perform an exercise under similar conditions, that is, reducing the influence of the HVS’ abilities that are not directly related to the detection of motion blur and rendering artifacts. As a consequence and building on our previous findings, we have decided to focus on tests designed around 2AFC tasks. This test is composed of two different tasks, each one fixing the values for three of the dimensions and varying the remaining one. Fixed dimensions use the preferred setting as from Test #1. In those axis where there is no clear preference, the same setting as in the monoscopic trial is used. The free dimension, shutter time for the first task and antialiasing level for the second, uses the five values available, T1to T5and A1to A5. Videos are paired so each possible combination is used. Pairs are shuffled and within each pair, videos are displayed in random order. This ensures learning effects do not alter the answers. The videos of each pair are played in sequence and participants can repeat them as many times as required. Users are requested to select the video they consider has the higher quality. Sixteen users completed each task and each one completed two full tests. After gathering the answers, we have performed a statistical significance test with similar characteristics as the one described in section 5.6.3. This method arranges answers in statistically indistinguishable groups based on an analysis of score differences. Like with the previous tests, we set a significance level α of 0.01 and a value of Wt,α≈4 . 604166667 . In this case, dRce=30 , determined from n=32 participants and t=5 video samples. Since both tests use the same n and t values, the previous coefficients are valid for the analysis of shutter time and antialiasing level. 6.5.2Results Table 6.2shows the number of times each video has been selected over the other video from the same pair. After ordering the sequences by decreasing preference, we have performed a statistical analysis to determine the number and contents of the perceptually equivalent groups. Two videos are considered statistically equivalent when the difference in their scores is lower than the value dRce,30 in this case. 108 influence of stereo vision on motion blur perception Figure 6.6: Snippets of the stimuli used in test #2(shutter time). From left to right, T1to T5. Images are clustered in perceptually equivalent groups. In blue, most voted sequences. In red, the images with the lowest perceived image quality. shutter time #votes sampling level #votes T1(0%) 34 A1(4spp) 48 T2(25%) 60 A2(128 spp) 63 T3(50%) 85 A3(256 spp) 77 T4(75%) 87 A4(384 spp) 68 T5(100%) 54 A5(512 spp) 64 Table 6.2: Number of votes per sequence. The table displays the number of times a given sequence has been selected over other sequence for the variations of shutter time and sampling levels. Between parenthesis the percentage of the frame time the shutter time remains opened and the number of samples per pixel. 6.5.2.1Shutter times Under those conditions, two different perceptual groups emerge when different shutter times are considered. The most voted one, surrounded by a blue line in figure 6.6, contains values T4, T3and T2, while the lessvoted group, in red, comprises values T2, T5and T1. The internal order of each group corresponds the relative preference measured in the tests. Each group contains stimuli that are perceptually indistinguishable. The following conclusions can be extracted: • High quality results are associated with middle shutter time values (25,50 and 75% of the frame time). On one hand, excesive bluriness has already pointed out as a signal of low quality and lack of realism. On the other hand, a complete absence of motion blur tends to produce strobing artifacts. These values are a compromise between both extremes and seem to support our previous findings for monoscopic stimuli. • Lower quality results are represented by values T2, T5and T1, that is, the most extreme shutter times. Artifacts associated with those values may be so perceivable that users can easily determine their existence. This is also supported by the results for the matching task in section 5.6.2. In that case, artifacts were 6.5 test #2:tolerance to variations in shutter time and antialiasing level 109 Figure 6.7: Stimuli used in test #2(sampling level). From left to right A1to A5. Images are clustered according to users answers yielding a single perceptually equivalent group. used as a cue to differentiate between sequences which may also be the current case. • Even if strobing and excessive blur are issues with different visual appearance, users seem to equally weight them. • Both groups overlap at value T2. The difference in votes are high enough to generate different arrangements, but at the same time differences are not so detectable to detach each one . This may indicate the HVS is working near its perceptual limits. The integrity and quality of the results has been checked using a circular triades analysis. This method can determine the existence of contradictions in the scores and users answers. In this case, the coefficient of consistency ξ is 0.7813 in the [0 , 1] range which corresponds to a relatively low number of inconsistencies. The coefficient of agreement u is 0.144 in the range [−1/31 , 1] . This range represents increasingly higher degrees of agreement. This value represents a moderate agreement among users, which gives room to think users arrive to similar conclusions but there is still certain variations in their answers. 6.5.2.2Antialiasing level A analagous test was performed based on different antialiasing levels. These values correspond to sampling levels of 4and 512 samples/pixel for A1and A5, and roughly equidistant values for the rest. The most salient conclusion is the lack of any clear preference for a single value or a group of them. Every sampling level receives similar number of votes which may be considered a strong indication of the inability of the HVS to differentiate between different stimuli. Back then, when monoscopic sequences were considered, matching tasks showed significant inconsistencies. This forced us to complete a set 2AFC task to discard memory or learning effects. The second test clearly showed the HVS is capable of determining which sequences have higher quality. In that case, we found three overlapping groups (low to high quality: A1, A2/A3/A4and A3/A4/A5, more details in section 5.6.3). In the case of stereoscopic stimuli, the HVS seem to be incapable of finding any differences. This results in a single group containing 110 influence of stereo vision on motion blur perception all the previous sampling levels. A reduction in the consistency of the answers results in a coefficient ξ of 0.5062 in the [0 , 1] range. Agreement between participants is also lower, u is 0.0177 in the range [−1/31,1]. In summary, the uniformity in the number of votes added to lower consistency and agreement levels seem like strong indicators of the reduced ability to detect noisy artifacts when stereo pairs are used. This is an important result, as for the cases considered, all the render modes tested are equivalent to a gold standard. This is true with independence of how expensive they are to produce. The same conclusions cannot be taken for monoscopic vision where, even if allowing some flexibility, the perceptual limits are clearly defined. 6.6 test #3:interactions between shutter time and sampling level The two previous sections have evaluated the capacity of the HVS to differentiate changes in the rendering parameters when modified one at a time. This section will consider modifying both of them simultaneously. As we will see, the following test will reveal a series of interesting interactions between both axis. In more general terms, this test more closely resembles practical situations where different rendering settings can be balanced so the time required to produce a sequence is reduced. The immediate result is a set of applicable directions on how to produce stimuli that is perceptually equivalent. 6.6.1Description In this test, participants have been requested to complete a 2AFC routine. In this case, the checker material and medium speeds are fixed in accordance with the preferences manifested in previous tests. Shutter time takes the values T3, T4, T5and antialiasing level use A3, A4and A5, which produces a set of nine different video sequences. Movies are paired together and each pair is shown in sequence. Every pair comes from a pool of 36 tuples containing all possible combinations of the two free parameters. Observers are requested to select the one with the highest quality. The rest of the conditions and associated explanations are similar as with the previous tests. 6.6.2Results Results have been clustered according to the number of votes received by each sequence. In this case, significance tests are completed using values of 0.01,18 and 9for α the significance level , n number of partic- 6.6 test #3:interactions between shutter time and sampling level 111 Figure 6.8: Grouping of the scenes rendered with different antialiasing and shutter time settings. From left to right: Shutter time T3, T4, T5; from bottom to top: Sampling rates A3, A4, A5. Group1to Group3, most to least voted, have been highlighted using blue, red and green respectively. ipants and t the size of the stimuli set respectively. The corresponding clustering factors are Wt,α≈5.0769231 and dRce=33. Results are graphically shown in Figure 6.8. The most salient conclusions are: • There are three perceptually equivalent groups. Groups have been ordered by decreasing number of votes from Group1(blue) to Group2(red) and finally Group3(green). • The most voted group corresponds to the lower and medium shutter times. This closely matches the results found for the monoscopic experience. • The two less voted groups correspond to the medium and longest shutter times. These two groups are almost a complete overlap. . • Most of the groups and their corresponding boundaries are associated with changes in shutter levels more frequently than antialiasing levels. This is a result similar to the one found for monoscopic perception and strongly suggest the HVS is more tolerant to noise than it is to strobbing artifacts or excesive blur. • There are significant overlaps in the region that corresponds to the medium shutter times. This seem to suggest the HVS cannot determine the relative quality of the images when this setting is used, and depending on the pair that is compared to, it can be seen as high quality or lower quality. 112 influence of stereo vision on motion blur perception • With minimal exceptions, the HVS seem to be incapable of differentiating between sampling levels. This is a result that was previously found for the study in section 6.5.2. In terms of ordering, each sequence has been preferred over any other according to the following number of votes: A4T3,94; A5T4,90; A5T3,85; A3T4,83; A3T3,80; A4T4,75; A4T5,49; A5T5,49; A3T5,43. An analysis of circular triades throw results that are inbetween the ones found when sampling levels and shutter times are considered individually. While for antialiasing levels and shutter times the coefficient of agreement u are 0.0177 and 0.144, combined stimuli offers a value of 0.1137 in the range [−1/35 , 1] . The same occurs for the coefficient of consistency ξ :0.5062 and 0.7813 for antialiasing level and shutter times, compared to 0.6074 for the combined stimuli. This may indicate that there is an underlying progression in the perceptual difficulty associated with the three tests, that ranges from the simplest one, ie. shutter time to the most challenging one, ie. sampling level. Based on the uncertainty and the degree of agreement of the answers, combined stimuli represents a middle point between both. The final remarks are quite similar, and in some cases go further the ones found for monoscopic perception, that is: • The HVS is capable of determining which renders have higher quality respect to the ones that have been computed with reduced accuracy. As with the previous cases, shutter time seem to drive users’ answers. Sampling levels seem to take a secondary role, to the point of not finding any differences between stimuli rendered using alternative antialiasing levels. • Any renders computed with any settings included in a given group are considered equivalent by a human observer. • The most expensive renders can be optimized by just selecting the parameters that belong to the same group that require the least computational resources. In that sense, there are many alternative settings that are equivalent to the gold standards found in the top row of Figure 6.8. 6.7 conclusions and future directions In this section we have expanded the previous knowledge on the perception of motion blurred images with the use of stereo stimuli. In this case, we have used stereo pairs and performed several tests whose results can be compared to our previous findings for monoscopic renders. As before, we have used photorealistic images using similar scenes, so the respective conclusions can be analysed from a common perspective. 7.3 motion blur rendering 119 are described and matched up in reference to their strengths and limitations. One of the main contributions is a taxonomy of methods based on different formulations of a general mathematical representation. This expression models the light integration process that naturally takes place on film and sensors and it is the basis of the simulation rendering methods perform. The report finishes with a systematic comparison of the methods based on their individual assumptions and provides a set of guidelines to help identifying which methods are more suitable for different practical scenarios. A second section takes a different approach and analyses the responses of the HVS to motion blurred stimuli coming from a Monte Carlo renderer. To our knowledge, this is the first time a perceptual study has been completed using photo-realistic sequences containing temporal antialiasing. Our findings are specific to a single scene and a set of parameter variations, however, we have been able to extract certain clues that may indicate which features are more important for a human observer. The study supports our initial intuition: certain psychophysical limits may play an important role with respect to the visual impact of image artifacts. The net effect is a reduction of the importance of issues such as excessive blur, flickering and strobbing. Moreover, the degree of tolerance to noise and high frequency artifacts is, in the cases considered by us, notable. These results suggest that images may be produced using aggressive algorithmic simplifications without degradation of the perceived quality. We have identified several situations where a lower quality sequence is indistinguishable from a gold standard. In practical terms, this means that a faster and a less accurate render may be used instead of a more expensive one. As important as these findings it is the fact that variations in shutter time tend to be more visible than alternative sampling levels. Given that a minimum level of quality has been reached, observers seem to be more inclined to detect changes in scenes using different exposure ranges than in scenes computed using alternative sampling levels. This is an interesting result, that fits in the design of current rendering pipelines: Shutter times are usually fixed on the basis of given image aesthetics or camera settings, while sampling level is an algorithmic setting that is adjusted to balance quality level and cost. This has a direct practical implication meaning that a production crew in charge of the optimization of renders can leverage the lower sensitivity to the number of samples per pixel and reduce the time taken to compute each frame at the same time the perceived quality is kept constant. 120 conclusions Feature film and VFX studios are continuously demanding improvements in the way stereoscopic images are produced. The last part of this thesis follows this trend and extends the previous results to stereo rendering of motion blurred scenes. Using a similar set of perceptual tests, this time performed with the aid of consumer grade shutter glasses, we have found the HVS may be more elastic to strobbing artifacts and noise. All the sampling settings considered fall in the same perceptually equivalent group. As before, rendering optimizations may be designed on this basis. Even more, the gains can be significant since stereo sequences are much more expensive to compute than single eye renders. Using two independent Monte Carlo renders for each stereo pair produces artifacts that are different for each of the eyes. This generates interocular disparity which in extreme cases can impede stereoscopic fusion. Participants have confirmed stereopsis occurs without increasing fatigue. At least for the stimuli used in the study, it is safe to compute images independently and algorithms are not required to embed any type of sampling coherence. In summary, the results suggest that limitations of the HVS may help reducing the requirements associated with high quality renders. Also, the method used to deliver the images to the spectator introduces new opportunities to play with the balance between a variety of render settings. 7.4 final remarks This thesis has introduced new algorithms to efficiently solve two interesting problems: computation of photorealistic images of participating media and postprocessing of antialiased images. We believe we have also depicted the first steps to designing more efficient methods to render motion blur on the basis of taking advantage of the characteristics of the human visual system. These conclusions are applicable for standard sequences and stereoscopic footage. Even if the results are promising, there is plenty of room for exploration. There are many aspects that still need to be studied, with may lead to opportunities to improve current pipelines. Specifically, the perceptual aspects of image rendering provide exciting directions that need to be analysed as the benefits for the rendering of realistic images may be significant. 8 CONCLUSIONES Esta tesis comenzó poniendo de manifiesto una tendencia que parece estar generalizada en el campo de los gráficos por ordenador y el render foto-realista: las nuevas técnicas vienen frecuentemente asociadas con un incremento importante en los recursos computacionales necesarios para calcular las imágenes. Con estos métodos, los avances vienen dados por la utilización de modelos matemáticos y algorítmicos de complejidad creciente. Con este problema como motivación, nuestra investigación se ha centrado en encontrar métodos alternativos para reducir los requerimientos de un conjunto de algoritmos bien conocidos. Todos ellos son ejemplos de algoritmos utilizados con frecuencia en el campo de los efectos especiales, la industria del cine y la comunidad de render. Hemos utilizado dos aproximaciones alternativas: • La primera basada en extender y mejorar algoritmos existentes de forma que su eficiencia se vea incrementada. Los resultados incluyen dos métodos nuevos para el render de medios participativos y la generación de anti-aliasing en espacio de pantalla. • La segunda trata de reducir el coste de los renders en base a evitar aquellos cálculos que generan mejoras no percibidas por un observador humano. En este caso, describimos varios resultados que permiten utilizar la respuesta del sistema visual humano a ciertas características y problemas asociadas con imágenes que contienen motion blur. Estos resultados han sido definidos tanto para imágenes monoscópicas como estereoscópicas. Estos dos métodos y sus contribuciones correspondientes se detallan en las secciones siguientes. 8.1 render volumétrico En el primer bloque de la tesis, Parte i, hemos presentado un framework capaz de calcular imágenes a partir de medios participativos no homogéneos en tiempos interactivos. La contribución principal del trabajo es la extensión del método tradicional de raymarching para que pueda ser aplicado en tiempos interactivos con uso simultaneo de iluminación avanzada. 121 122 conclusiones Nuestra solución se basa en modelar el campo de luz incidente como una constelación de luces puntuales generadas a partir de un mapa de entorno HDR, mientras que el volumen esta representado por una matriz de vóxeles. Ambos enfoques tienen un amplio uso y existen multitud de algoritmos que son capaces de generar conjuntos de datos compatibles. Como segunda contribución, hemos modificado la ecuación de render para tomar ventaja de la naturaleza de los medios participativos y hemos definido una serie de suposiciones para simplificar el modelo. La representación matemática resultante es capaz de dar lugar a imágenes de alta calidad mientras que puede ser evaluada mas eficientemente. La tercera contribución es el uso de dos optimizaciones no descritas anteriormente: un pase de validez que es dependiente del punto de vista y un mapa de distancias independiente del punto de vista. Ambos introducen reducciones de tiempo de hasta 8veces con respecto a una implementación de fuerza bruta. En resumen, nuestra técnica ataca dos de los problemas que limitan la eficiencia de las implementaciones sobre GPU: la complejidad de los cálculos por fragmento que es reducida utilizando una expresión matemática simplificada; y los recorridos del volumen que son intensivos en accesos a memoria y que son optimizados utilizando cambios en el algoritmo. Nuestra técnica puede ser extendida de varias formas. Actualmente ignora los cálculos relativos a multiple-scattering. Con los métodos actuales, esto solo puede conseguirse con impactos significativos en el rendimiento o bien, utilizando pre-cálculos. También, mientras se es capaz de generar imágenes visualmente aceptables, suponer que el medio tiene una función de fase isotrópica, hace que nuestro método sea menos exacto y elimina la posibilidad de reproducir ciertos tipos de volúmenes. Hay un amplio rango de optimizaciones que se basan en estructuras de organización espacial y métodos de compresión. Estos serian potencialmente capaces de limitar el impacto en memoria y la sobrecarga impuesta por la representación basada en vóxeles. Las ganancias derivadas de utilizar estos métodos pueden compensar el coste asociado con el uso de modelos de iluminación basados en física. 8.2 antiasing en espacio de pantalla En Parte ii, hemos presentado un algoritmo diseñado para calcular antialiasing en imágenes pre-calculadas. El método esta inspirado en el antialiasing morfológico de Reshetov y utiliza el paralelismo disponible en las arquitecturas GPU. Esta técnica extiende los métodos actuales en calidad y, en algunos casos, en eficiencia. El 8.3 cálculo de motion blur 123 método puede ser ejecutado con un coste moderado y es fácilmente integrable dentro de un pipeline existente. La técnica ha recibido una cantidad de atención significativa y ha sido revisada en varias publicaciones internacionales especializadas. Varias implementaciones han sido integradas dentro de conocidos motores de render y juegos comerciales. Además, ha dado lugar a varias extensiones y mejoras. 8.3 cálculo de motion blur Parte iii comienza con una revisión en profundidad del estado del arte en métodos de render de motion blur. Mas de cincuenta técnicas desde los métodos descritos en los 70 hasta las publicaciones mas recientes, son descritas y comparadas en referencia a sus puntos fuertes y limitaciones. Una de las contribuciones mas sobresalientes es una taxonomía de métodos basados en diferentes formulaciones de una expresión matemática general. Esta expresión modela el proceso de integración de la luz que sucede de forma natural en película y sensores fotográficos y que es la base de la simulación incluida en los métodos de render. El informe termina con una comparación sistematizada de los métodos . Estos son comparados de acuerdo a sus correspondientes suposiciones y, de acuerdo a ellas, se proponen una serie de métodos para identificar que soluciones son las mas adecuadas para cada escenario. Una segunda sección toma una postura diferente y analiza las respuestas del sistema visual humano a estímulos que contienen motion blur calculado mediante el algoritmo de render de Monte Carlo. Según hemos podido comprobar, esta es la primera vez que un estudio perceptual ha sido completado utilizando secuencias fotorealistas la cuales incluyen antialiasing temporal. Nuestros resultados son específicos de una sola escena y un conjunto de variaciones de parámetros de render, de todas formas, hemos sido capaces de extraer ciertos indicios que pueden identificar cuales son las características mas importantes para un observador humano. El estudio apoya nuestra intuición inicial: ciertos limites psicofísicos tienen un rol significativo con respecto al impacto visual de los errores de render. El efecto general es una reducción de la importancia de problemas como blur excesivo, flickering y efectos estroboscópicos. Mas aun, el grado de tolerancia al ruido y las altas frecuencias es, para los casos considerados, notable. Estos resultados sugieren que es posible calcular imágenes utilizando simplificaciones algorítmicas agresivas sin degradación de la calidad percibida. Hemos identificado varias situaciones donde una secuencia de baja calidad es indistinguible de una referencia de alta calidad. En términos prácticos, 124 conclusiones esto quiere decir que un render mas rápido y menos detallado puede ser utilizado en vez de uno mas caro de calcular. Tan importante como estos resultados es el hecho de que variaciones en la velocidad de obturación tienden a ser mas visibles que niveles de sampling alternativos. Una vez se ha alcanzado el nivel de calidad mínimo, observadores parecen mas inclinados a detectar cambios en escenas con diferentes rangos de exposición que en escenas calculadas con niveles de sampling alternativo. Este es un resultado interesante, que se ajusta al diseño de los pipelines de render actuales: las velocidades de obturación están normalmente definidas por los parámetros de la cámara o bien por consideraciones estéticas, mientras que el nivel de sampling se ajusta para balancear el nivel de calidad con el coste. Esto tiene implicaciones practicas directas, ya que un equipo de producción encargado de optimizar renders puede tomar ventaja de la menor sensibilidad al número de samples por pixel y reducir el tiempo requerido para calcular cada frame al mismo tiempo que la calidad de las imágenes permanece, perceptualmente, constante. Los estudios de cine y efectos especiales requieren constantemente nuevas mejoras. Entre otras, los métodos para calcular imágenes estereoscópicas pueden verse favorablemente afectadas por nuevas alternativas. La última parte de esta tesis reconoce esta demanda y extiende los resultados anteriormente descritos a render estéreo de escenas con motion blur. Utilizando un conjunto de test perceptuales similares a los anteriores, esta vez con la ayuda de gafas estéreo activas, hemos encontrado que el sistema visual humano puede ser incluso mas elástico al ruido y problemas estroboscópicos. Todos los niveles de sampling considerados caen en la misma categoría perceptual. Como se ha comentado, las optimizaciones de render pueden ser diseñada de acuerdo a esto. Mas aun, las ganancias serán probablemente superiores dado que el render de secuencias estéreo es mucho mas caro de calcular que aquellas para un solo ojo. Utilizar dos renders Monte Carlo independientes para cada par estéreo produce errores que son diferentes para cada ojo. Esto genera disparidad interocular, que en casos extremos, puede impedir la fusión estéreo. Los participantes en el estudio han confirmado que la estereopsis tiene lugar sin incrementar la fatiga. Al menos para los estímulos incluidos en el estudio, es seguro calcular imágenes independientemente y por lo tanto, los algoritmos no necesariamente deben incluir ningún tipo de coherencia en el sampling. En resumen, los resultados sugieren que las limitaciones del sistema visual humano pueden ayudar a reducir los requerimientos asociados con el render de escenas de alta calidad. Además, el método utilizado para presentar las imágenes al espectador introduce nuevas 8.4 notas finales 125 oportunidades para modificar el balance entre diferentes parámetros de render. 8.4 notas finales Esta tesis ha introducido nuevos algoritmos que son capaces de resolver dos problemas interesantes: el render de imágenes fotorealistas de medios participativos y el post-procesado de imágenes con antialiasing. También creemos que hemos definido los primeros pasos que permiten diseñar métodos de render de motion blur mas eficientes en base a tomar ventaja de las características del sistema visual humano. Estas conclusiones son aplicables tanto para secuencias estándar como para las estereoscópicas. Incluso si los resultados son prometedores, hay suficientes áreas para la exploración. Hay bastantes aspectos que aun necesitan ser estudiados, que en algunos casos pueden poner al alcance nuevas oportunidades para mejorar los pipelines actuales. Específicamente, los aspectos perceptuales proveen direcciones fascinantes que necesitan ser analizadas ya que los beneficios para el render imágenes realistas pueden ser significativos. BIBLIOGRAPHY [1] J. Abrams, A. Barbot, and M. Carrasco. Voluntary attention increases perceived spatial frequency. Atten Percept Psychophys,72(6):1510–21,2010.91. [2] Ansel Adams. The Camera. The Ansel Adams Photography series I. Little, Brown and Company, 1980.41. [3] Edward H. Adelson and James R. Bergen. Spatiotemporal energy models for the perception of motion. J. Opt. Soc. Am. A,2(2):284–299, Feb 1985.79 and 80. [4] Tomas Akenine-Möller, Jacob Munkberg, and Jon Hasselgren. Stochastic rasterization using time-continuous triangles. In GH ’07: Proc. of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, pages 7–16. Eurographics Association, 2007.43,61,71, and 72. [5] B. L. Anderson and K. Nakayama. Toward a general theory of stereopsis: binocular matching, occluding contours, and fusion. Psychological review,101 (3), 07 1994.98. [6] Oscar Ansón, Veronica Sundstedt, Diego Gutiérrez, and Alan Chalmers. Efficient selective rendering of participating media. In Proceedings of the 3rd symposium on Applied perception in graphics and visualization, APGV ’06, pages 135–142. ACM, 2006.74 and 79. [7] A.A. Apodaca and L. Gritz. Advanced RenderMan: Creating CGI for Motion Pictures. Morgan Kaufmann Publishers, 2000.67. [8] D. A. Atchison, G. Smith, and N. Efron. The effect of pupil size on visual acuity in uncorrected and corrected myopia. Am J Optom Physiol Opt,56:315–323, May 1979.74. [9] Brian A. Barsky and Todd J. Kosloff. Algorithms for rendering depth of field effects in computer graphics. In Proceedings of the 12th WSEAS international conference on Computers, pages 999–1010. World Scientific and Engineering Academy and Society (WSEAS), 2008.43 and 69. [10] Brian A. Barsky, Daniel R. Horn, Stanley A. Klein, Jeffrey A. Pang, and Meng Yu. Camera models and optical systems used in computer graphics: Part i, object-based techniques. In Proceedings of the 2003 international conference on Computational science and its applications: PartIII, ICCSA’03, pages 246–255. Springer-Verlag, 2003.43 and 69. [11] Gary Bishop, Henry Fuchs, Leonard McMillan, and Ellen J. Scher Zagier. Frameless rendering: double buffering considered harmful. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques, SIGGRAPH ’94, pages 175–176. ACM, 1994.43,60, and 73. [12] Michael J. Black and P. Anandan. The robust estimation of multiple motions: parametric and piecewise-smooth flow fields. Comput. Vis. Image Underst.,63 (1):75–104,1996.64. [13] Philippe Blasi, Bertrand Le Sa ˜ ec, and Christophe Schlick. A rendering algorithm for discrete volume density objects. Computer Graphics Forum (Eurographics ’93), 12(3):201–210,1993.11. [14] James F. Blinn. Light reflection functions for simulation of clouds and dusty surfaces. SIGGRAPH Comput. Graph.,16(3):21–29,1982.8. 127 128 bibliography [15] Atanas Boev, Danilo Hollosi, Atanas Gotchev, and Karen Egiazarian. Classification and simulation of stereoscopic artifacts in mobile 3dtv content. Proceedings of SPIE,7237,2009.99. [16] Solomon Boulos, Edward Luong, Kayvon Fatahalian, Henry Moreton, and Pat Hanrahan. Space-time hierarchical occlusion culling for micropolygon rendering with motion blur. In Proceedings of the Conference on High Performance Graphics, HPG ’10, pages 11–18. Eurographics Association, 2010.73. [17] D. H. Brainard. The Psychophysics Toolbox. Spatial vision,10(4):433–436,1997. 102. [18] Ron Brinkmann. The art and science of digital compositing. Morgan Kaufmann Publishers, 1999.69. [19] Gabriel J. Brostow and Irfan Essa. Image-based motion blur for stop motion animation. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, SIGGRAPH ’01, pages 561–566. ACM, 2001.43,57,64,71, 72, and 73. [20] J. S. Brunhaver, K. Fatahalian, and P. Hanrahan. Hardware implementation of micropolygon rasterization with motion and defocus blur. In Proceedings of the Conference on High Performance Graphics, HPG ’10, pages 1–9. Eurographics Association, 2010.73. [21] Abdullah Bulbul, Zeynep Cipiloglu, and Tolga Capin. Technical section: A perceptual approach for stereoscopic rendering optimization. Comput. Graph., 34(2):145–157, April 2010.100. [22] D. Burr. Motion smear. Nature,284:164–165, Mar 1980.43,74,79, and 81. [23] D. C. Burr. Temporal Summation of Moving Images by the Human Visual System. Royal Society of London Proceedings Series B,211:321–339, March 1981. 80. [24] D. C. Burr and M. J. Morgan. Motion Deblurring in Human Vision. Royal Society of London Proceedings Series B,264:431–436, March 1997.80. [25] D. C. Burr, J. Ross, and M. C. Morrone. Seeing objects in motion. Proc. R. Soc. Lond., B, Biol. Sci.,227:249–265, Mar 1986.79. [26] Brian Cabral and Leith Casey Leedom. Imaging vector fields using line integral convolution. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques, SIGGRAPH ’93, pages 263–270. ACM, 1993.57 and 65. [27] Martin ˇ Cadík. Human perception and computer graphics. Technical Report DC-PSR-2004-04, Department of Computer Science, Faculty of Electrical Engineering, Czech Technical University in Prague, 2004.78. [28] Martin ˇ Cadík, Michael Wimmer, Laszlo Neumann, and Alessandro Artusi. Evaluation of HDR tone mapping methods using essential perceptual attributes. Computers & Graphics,32(3):330–349, June 2008.74. [29] Mike Cammarano and Henrik Wann Jensen. Time dependent photon mapping. In Proceedings of the 13th Eurographics workshop on Rendering, EGRW ’02, pages 135–144. Eurographics Association, 2002.43,56,57, and 72. [30] F. W. Campbell and D. G. Green. Optical and retinal factors affecting visual resolution. J. Physiol. (Lond.),181:576–593, Dec 1965.74.