MIT EECS 6.837, Durand and Cutler Sampling, Aliasing, & MipmapsMIT EECS 6.837, Durand and Cutler Last Time?•2D Texture Mapping•Perspective Correct Interpolation•Common Texture Coordinate Projections•Bump Mapping•Displacement Mapping•Environment MappingMIT EECS 6.837, Durand and Cutler Texture Maps for Illumination•Also called "Light Maps"MIT EECS 6.837, Durand and Cutler Today•What is a Pixel?•Examples ofAliasing•Signal Reconstruction •Reconstruction Filters•Anti-Aliasingfor Texture MapsMIT EECS 6.837, Durand and Cutler What is a Pixel?•A pixel is not:–a box–a disk–a teeny tiny little light•A pixel is a point–it has no dimension–it occupies no area–it cannot be seen–it can have a coordinate•A pixel is more than just a point, it is a sample!MIT EECS 6.837, Durand and Cutler More on Samples•Most things in the real world are continuous,yet everything in a computer is discrete•The process of mapping a continuous function to a discrete one is called sampling•The process of mapping a continuous variable to a discrete one is calledquantization•To represent or render an image using a computer, we must both sample andquantizeMIT EECS 6.837, Durand and Cutler An Image is a 2D Function•An ideal imageis a function I(x,y) of intensities.•It can be plotted as a height field.•In general an image cannot be represented as a continuous, analytic function. •Instead we represent images as tabulated functions. •How do we fill this table? Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler Sampling Grid•We can generate the table values by multiplying the continuous image function by a sampling grid of Kroneckerdelta functions. Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler Sampling an Image•The result is a set of point samples, or pixels. Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•What is a Pixel?•Examples ofAliasing•Signal Reconstruction •Reconstruction Filters•Anti-Aliasingfor Texture MapsMIT EECS 6.837, Durand and Cutler Examples ofAliasing Image removed due to copyright considerations.MIT EECS 6.837, Durand and Cutler Examples ofAliasing JAGGED BOUNDARIESMIT EECS 6.837, Durand and Cutler Examples ofAliasing IMPROPERLY RENDERED DETAILMIT EECS 6.837, Durand and Cutler Examples ofAliasingTexture Errorspoint samplingMIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•What is a Pixel?•Examples ofAliasing•Signal Reconstruction –Sampling Density–Fourier Analysis & Convolution•Reconstruction Filters•Anti-Aliasingfor Texture MapsMIT EECS 6.837, Durand and Cutler Sampling Density•How densely must we sample an image in order to capture its essence? •If we under-sample the signal, we won't be able to accurately reconstruct it... Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler NyquistLimit /Shannon's Sampling Theorem•If we insufficiently sample the signal, it may be mistaken for something simpler during reconstruction (that'saliasing!) POINT SAMPLING WITHIN THE NYQUIST LIMIT POINT SAMPLING BEYOND THE NYQUIST LIMIT Image adapted from: Robert L. Cook, "Stochastic Sampling and Distributed Ray Tracing." In An Introduction to Ray Tracing. Edited by Andrew Glassner. Academic Press Limited, 1989.MIT EECS 6.837, Durand and Cutler Examples ofAliasingTexture Errorspoint samplingmipmaps& linear interpolationMIT EECS 6.837, Durand and Cutler Remember Fourier Analysis?•All periodic signals can be represented as a summation of sinusoidal waves. Images adapted from http://axion.physics.ubc.ca/341-02/fourier/fourier.htmlMIT EECS 6.837, Durand and Cutler Remember Fourier Analysis?•Every periodic signal in the spatial domainhas a dual in the frequency domain.•This particular signal is band-limited, meaning it has no frequencies above some thresholdfrequency domainspatial domainMIT EECS 6.837, Durand and Cutler Remember Fourier Analysis?•We can transform from one domain to the other using the Fourier Transform.frequency domainspatial domainFourier TransformInverse Fourier TransformMIT EECS 6.837, Durand and Cutler Remember Convolution? f g x f g * * f g * =MIT EECS 6.837, Durand and Cutler Remember Convolution?•Some operations that are difficult to compute in the spatial domain can be simplified by transforming to its dual representation in the frequency domain.•For example, convolution in the spatial domain is the same as multiplication in the frequency domain.•And, convolution in the frequency domain is the same as multiplication in the spatial domain MIT EECS 6.837, Durand and Cutler Sampling in the Frequency DomainFourier TransformoriginalsignalFourier Transformsamplinggrid(multiplication)(convolution)Fourier TransformsampledsignalMIT EECS 6.837, Durand and Cutler Reconstruction•If we can extract a copy of the original signal from the frequency domain of the sampled signal, we can reconstruct the original signal!•But there may be overlap between the copies.MIT EECS 6.837, Durand and Cutler Guaranteeing Proper Reconstruction•Separate by removing high frequencies from the original signal (low pass pre-filtering)•Separate by increasing the sampling density•If we can't separate the copies, we will have overlapping frequency spectrum during reconstruction →aliasing.MIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•What is a Pixel?•ExamplesofAliasing•Signal Reconstruction •Reconstruction Filters–Pre-Filtering, Post-Filtering–Ideal,Gaussian, Box, Bilinear, Bicubic •Anti-Aliasingfor Texture MapsMIT EECS 6.837, Durand and Cutler Pre-Filtering•Filter continuous primitives•Treat a pixel as an area•Compute weighted amount of object overlap•What weighting function should we use? s W Region of Overlap Desired Line Pixel Subvolume Ws Cone Weighting Function W Foley et al. Computer Graphics Principles and Practice. 2nd Ed. Pearson Addison Wesley, June 1990. ASIN: 0201121107 Image adapted from: 0 01 1 2 2 3 3 4 4 5 5 6 7 8 9 10 11 Foley et al. Computer Graphics Principles and Practice. 2nd Ed. Pearson Addison Wesley, June 1990. ASIN: 0201121107 Image adapted from:MIT EECS 6.837, Durand and Cutler Post-Filtering•Filter samples•Compute the weighted average of many samples•Regular or jittered sampling (better) 1 16 18 18 14 1 16 1 16 1 16 18 18 1 16 18 18 14 1 16 1 16 1 16 18 18 1 16 18 18 14 1 16 1 16 1 16 18 18 1 16 18 18 14 1 16 1 16 1 16 18 18 Regular JitteredMIT EECS 6.837, Durand and Cutler Reconstruction Filters•Weighting function •Area of influence often bigger than "pixel"•Sum of weights = 1–Each pixel contributes the same total to image–Constant brightness as object moves across the screen. •No negative weights/colors (optional) Region of Overlap Desired Line Pixel Subvolume Ws Cone Weighting Function W Foley et al. Computer Graphics Principles and Practice. 2nd Ed. Pearson Addison Wesley, June 1990. ASIN: 0201121107 Image adapted from:MIT EECS 6.837, Durand and Cutler The Ideal Reconstruction Filter•Unfortunately it has infinite spatial extent–Every sample contributes to every interpolated point •Expensive/impossible to computespatialfrequencyMIT EECS 6.837, Durand and Cutler GaussianReconstruction Filter •This is what a CRTdoes for free!spatialfrequencyMIT EECS 6.837, Durand and Cutler Problems with Reconstruction Filters•Many visible artifacts in re-sampled images are caused by poor reconstruction filters•Excessive pass-band attenuation results in blurry images•Excessive high-frequency leakage causes "ringing" and can accentuate the sampling grid (anisotropy)frequencyMIT EECS 6.837, Durand and Cutler Box Filter /Nearest Neighbor•Pretending pixelsare little squares.spatialfrequency Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler Tent Filter /Bi-Linear Interpolation•Simple to implement•Reasonably smoothspatialfrequency Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler Bi-Cubic Interpolation•Begins to approximate the ideal spatial filter, the sincfunctionspatialfrequency Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler Why is the Box filter bad?•(Why is it bad to think of pixels as squares)Down-sampled with a 5x5 box filter (uniform weights)Original high-resolution imageDown-sampled with a 5x5Gaussianfilter(non-uniform weights) notice the ugly horizontal banding Courtesy of Leonard McMillan, Computer Science at the University of Used with permission. North Carolina in Chapel Hill.MIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Today•What is a Pixel?•ExamplesofAliasing•Signal Reconstruction •Reconstruction Filters •Anti-Aliasingfor Texture Maps–Magnification & Minification–Mipmaps–Anisotropic MipmapsMIT EECS 6.837, Durand and Cutler Sampling Texture Maps•When texture mapping it is rare that the screen-space sampling density matches the sampling density of the texture. 64x64 pixelsOriginal TextureMagnification for DisplayMinificationfor Displayfor which we must use a reconstruction filterMIT EECS 6.837, Durand and Cutler Linear Interpolation•Tell OpenGL to use a tent filter instead of a box filter.•Magnification looks better, but blurry–(texture is under-sampled for this resolution)MIT EECS 6.837, Durand and Cutler Spatial Filtering•Remove the high frequencies which cause artifacts in minification.•Compute a spatial integration over the extent of the sample•Expensive to do during rasterization, but it can be precomputedMIT EECS 6.837, Durand and Cutler MIP Mapping•Construct a pyramid of images that are pre-filtered and re-sampled at 1/2, 1/4, 1/8, etc., of the original image's sampling•During rasterization we compute the index of the decimated image that is sampled at a rate closest to the density of our desired sampling rate•MIP stands for multiumin parvowhich means many in a small placeMIT EECS 6.837, Durand and Cutler MIP Mapping Example•Thin lines may become disconnected /disappearNearest NeighborMIP Mapped (Bi-Linear)MIT EECS 6.837, Durand and Cutler MIP Mapping Example•Small details may "pop" in and out of viewNearest NeighborMIP Mapped (Bi-Linear)MIT EECS 6.837, Durand and Cutler Storing MIP Maps•Can be stored compactly•Illustrates the 1/3 overhead of maintaining the MIP mapMIT EECS 6.837, Durand and Cutler AnisotropicMIP-Mapping•What happens when the surface is tilted?Nearest NeighborMIP Mapped (Bi-Linear)MIT EECS 6.837, Durand and Cutler AnisotropicMIP-Mapping•We can use different mipmapsfor the 2 directions•Additional extensions can handle non axis-aligned viewsImages from http://www.sgi.com/software/opengl/advanced98/notes/node37.html Image removed due to copyright considerations.MIT EECS 6.837, Durand and Cutler Questions?MIT EECS 6.837, Durand and Cutler Next Time: Last Class!Wrap Up &Final Project Review