MIT EECS 6.837, Cutler and Durand 1 MIT 6.837 Monte-Carlo Ray TracingMIT EECS 6.837, Cutler and Durand 2 Schedule•Review Session: Tuesday November 18th, 7:30 pmbring lots of questions!•Quiz 2: Thursday November 20th, in class(one weeks from today)MIT EECS 6.837, Cutler and Durand 3 Review of last week?MIT EECS 6.837, Cutler and Durand 4 Radiosity•Form-factor between patches•Geometry and visibility•Big Matrix system•Diffuse surfaces•Subdivide scene•Radiosity assumed constant over a patchMIT EECS 6.837, Cutler and Durand 5 Radiosity•Smoothing and other gimmicksMIT EECS 6.837, Cutler and Durand 6 Limitations of radiosity•Diffuse only for basic method–Costly extension to specular•Requires meshing•Cost of visibility computation–If you send rays, why not use ray tracing?•Memory consumption vs. time scalabilityMIT EECS 6.837, Cutler and Durand 7 Why still learn radiosity?•Still used in architecture (Lightscape)•Introduction to finite element method–Project the problem onto a finite basis of functions•In the case of radiosity: piecewise constant–Express interaction between elements–Get a big matrix system–Same as deformable object simulation•Pre-computed radiance transfer: same strategy–Use finite basis function–Precomputelighting as a function of primary sources–Use in a simplified version in Max Payne 2MIT EECS 6.837, Cutler and Durand 8 Today: Monte Carlo Ray Tracing•Principle of Monte-Carlo Ray Tracing•Monte Carlo integration•Review of Rendering equation•Advanced Monte Carlo Ray TracingMIT EECS 6.837, Cutler and Durand 9 Probabilistic Soft Shadows•Multiple shadow rays to sample area light source•Monte-Carlo ray tracing generalizes thisone shadow raylots of shadow raysMIT EECS 6.837, Cutler and Durand 10 Ray Casting•Cast a ray from the eye through each pixel MIT EECS 6.837, Cutler and Durand 11 Ray Tracing•Cast a ray from the eye through each pixel •Trace secondary rays (light, reflection, refraction)MIT EECS 6.837, Cutler and Durand 12 Monte-Carlo Ray Tracing•Cast a ray from the eye through each pixel•Cast random rays from the visible point –Accumulate radiance contributionMIT EECS 6.837, Cutler and Durand 13 Monte-Carlo Ray Tracing•Cast a ray from the eye through each pixel•Cast random rays from the visible point •RecurseMIT EECS 6.837, Cutler and Durand 14 Monte-Carlo•Cast a ray from the eye through each pixel•Cast random rays from the visible point •RecurseMIT EECS 6.837, Cutler and Durand 15 Monte-Carlo•Systematically sample primary lightMIT EECS 6.837, Cutler and Durand 16 Results (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 17 Monte-Carlo•Take reflectance into account–Multiply incoming radiance by BRDF valueMIT EECS 6.837, Cutler and Durand 18 •1 sample per pixel (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 19 •256 samples per pixel (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 20 Monte Carlo Path Tracing•Trace only one secondary ray per recursion•But send many primary rays per pixel•(performs antialiasingas well)MIT EECS 6.837, Cutler and Durand 21 Monte Carlo Path tracingtraceRayIntersect all objectsShade visible objectShade visible objectTrace random ray to sample incoming lightShade using brdfMIT EECS 6.837, Cutler and Durand 22 Vintage path tracing image•by Jim Kajiya(1986)•Also introduced the rendering equationMIT EECS 6.837, Cutler and Durand 23 Convergence speed 0 0.06 0.08 0.1 0.12 0.14 Reference Value One Estimator Min of 1000 Runs Max of 1000 Runs 500 PATHS/PIXEL 1000 1500 2000 AVERAGE L 2500 3000 3500 4000 4500 5000 Image adapted from: Henrik Wann Jensen. Realistic Image Synthesis Using Photon Mapping. 1st Ed. A K Peters, Ltd. July 2001. ISBN: 1568811470.MIT EECS 6.837, Cutler and Durand 24 Results•10 paths/pixel (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 25 Results•10 paths/pixel (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 26 Results•100 paths/pixel (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 27 Why use random numbers?•Fixed random sequence•We see the structure in the error (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 28 Recap•Send random rays•Sample the rendering equation•No meshing required, no special storage•No limitation–On reflectance–On geometry•Extremely flexible•Can be noisy (or slow)MIT EECS 6.837, Cutler and Durand 29 Today: Monte Carlo Ray Tracing•Principle of Monte-Carlo Ray Tracing•Monte Carlo integration•Review of Rendering equation•Advanced Monte Carlo Ray TracingMIT EECS 6.837, Cutler and Durand 30 Monte-Carlo computation of π•Take a square•Take a random point (x,y) in the square•Test if it is inside the ¼ disc (x2+y2 < 1)•The probability is π/4 xyMIT EECS 6.837, Cutler and Durand 31 Monte-Carlo computation of π•The probability is π/4 •Count the inside ratio n = # inside /total # trials•π≈n * 4•The error depends on the number or trialsMIT EECS 6.837, Cutler and Durand 32 Why not use Simpson integration?•Yeah, to compute π, Monte Carlo is not very efficient•But convergence is independent of dimension•Better to integrate high-dimensional functions•For d dimensions, Simpson requires NddomainsMIT EECS 6.837, Cutler and Durand 33 What’s the link to ray tracing?•Light source is square•Occluderis sphere•Some pixels have exactly π/4 visibility ;-) one shadow raylots of shadow raysMIT EECS 6.837, Cutler and Durand 34 Dumbest Monte-Carlo integration•Compute 0.5 by flipping a coin•1 flip: 0 or 1=> average error =0.5•2 flips: 0, 0.5, 0.5 or 1 =>average error=0. 25•4 flips: 0 (*1),0.25 (*4), 0.5 (*6), 0.75(*4), 1(*1) => average error =0.1875•Does not converge very fast•Doubling the number of samples does not double accuracyConvergence of Monte Carlo integration MIT EECS 6.837, Cutler and Durand 35 •Variance decrease in 1/n•Convergence is•Independent of dimensionn1MIT EECS 6.837, Cutler and Durand 36 Monte Carlo integration•Want to evaluate•Use random variable xiwith uniform probability over the domain•Note that achieving uniform probability can be tough for complex domain (e.g. sphere)dxxfba∫)(∑=niixfn1)(1MIT EECS 6.837, Cutler and Durand 37 Monte Carlo integration –smarter •Want to evaluate•Use random variable xiwith probability pi•The whole trick is to choose the xiand pidxxfba∫)(∑=niiipxfn1)(1MIT EECS 6.837, Cutler and Durand 38 Sampling strategy•Sample directions vs. sample light source (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 39 Sampling strategiesSampling more the lightSampling more the BRDF (Images removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 40 Monte Carlo recap•Turn integral into finite sum•Use random samples•Convergence•Independent of dimension•Very flexible•Tweak sampling/probabilities for optimal result•A lot of integration and probability theory to get things rightn1MIT EECS 6.837, Cutler and Durand 41 What can we integrate?•Pixel: antialiasing•Light sources: Soft shadows•Lens: Depth of field•Time: Motion blur•BRDF: glossy reflection•Hemisphere: indirect lighting Image removed due to copyright considerations. Please see Computer Graphics 25, no. 4 (July,1991): 157-164. ISBN: 0097-8930.MIT EECS 6.837, Cutler and Durand 42 Questions? (Images removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 43 Today: Monte Carlo Ray Tracing•Principle of Monte-Carlo Ray Tracing•Monte Carlo integration•Review of Rendering equation•Advanced Monte Carlo Ray TracingMIT EECS 6.837, Cutler and Durand 44 The Rendering Equationx'ω'L(x',ω') = E(x',ω')+ ∫ρx'(ω,ω')L(x,ω)G(x,x')V(x,x') dAL (x',ω') is the radiance from a point on a surface in a given direction ω'MIT EECS 6.837, Cutler and Durand 45 The Rendering Equationx'ω'L(x',ω') = E(x',ω')+ ∫ρx'(ω,ω')L(x,ω)G(x,x')V(x,x') dAE(x',ω') is the emitted radiance from a point: E is non-zero only if x' is emissive (a light source)MIT EECS 6.837, Cutler and Durand 46 The Rendering Equationx'ω'L(x',ω') = E(x',ω')+ ∫ρx'(ω,ω')L(x,ω)G(x,x')V(x,x') dASum the contribution from all of the other surfaces in the sceneMIT EECS 6.837, Cutler and Durand 47 The Rendering Equationx'ω'ωxL(x',ω') = E(x',ω')+ ∫ρx'(ω,ω')L(x,ω)G(x,x')V(x,x') dAFor each x, compute L(x, ω), the radiance at point x in the direction ω(from x to x') MIT EECS 6.837, Cutler and Durand 48 The Rendering Equationscale the contribution by ρx'(ω,ω'), the reflectivity (BRDF) of the surface at x'x'ω'ωxL(x',ω') = E(x',ω')+ ∫ρx'(ω,ω')L(x,ω)G(x,x')V(x,x') dA f q q r n i r fiMIT EECS 6.837, Cutler and Durand 49 The Rendering EquationFor each x, compute V(x,x'), the visibility between x and x': 1 when the surfaces are unobstructed along the direction ω, 0 otherwise x'ω'ωxL(x',ω') = E(x',ω')+ ∫ρx'(ω,ω')L(x,ω)G(x,x')V(x,x')dAMIT EECS 6.837, Cutler and Durand 50 The Rendering Equationx'ω'ωxL(x',ω') = E(x',ω')+ ∫ρx'(ω,ω')L(x,ω)G(x,x')V(x,x') dAFor each x, compute G(x, x'), which describes the on the geometric relationship between the two surfaces at x and x’MIT EECS 6.837, Cutler and Durand 51 Monte Carlo Path Tracing•Trace only one secondary ray per recursion•But send many primary rays per pixel•(performs antialiasingas well)MIT EECS 6.837, Cutler and Durand 52 Radiosity vs. Monte Carlo•We have an integral equation on an infinite space•Finite elements (Radiosity)–Project onto finite basis of functions–Linear system•Monte Carlo–Probabilistic samplingMIT EECS 6.837, Cutler and Durand 53 Radiosity vs. Monte Carlo•We have an integral equation on an infinite space•Finite elements (Radiosity)–Project onto finite basis of functions–Linear system–View-independent(no angular information)•Monte Carlo–Probabilistic sampling–View-dependent(but angular information)MIT EECS 6.837, Cutler and Durand 54 References•See also Eric Veach’sPhD http://graphics.stanford.edu/papers/veach_thesis/• Dutre, P., P. Bekaertand K. Bala. Advanced Global Illumination. AK Peters, Ltd. 2003. ISBN:1568811772. • Shirley, Pete. Realistic Ray Tracing. AK Peters, Ltd. 1st. Ed. 2000. ISBN:1568811101. • Jensen, HenrikWann. Realistic Image Synthesis Using Photon Mapping. AK Peters, Ltd. 1st Ed. 2001. ISBN:1568811470.MIT EECS 6.837, Cutler and Durand 55 Today: Monte Carlo Ray Tracing•Principle of Monte-Carlo Ray Tracing•Monte Carlo integration•Review of Rendering equation•Advanced Monte Carlo Ray Tracing–Irradiance caching–Photon mappingMIT EECS 6.837, Cutler and Durand 56 Path Tracing is costly•Needs tons of rays per pixelMIT EECS 6.837, Cutler and Durand 57 Direct illumination (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 58 Global Illumination (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 59 Indirect illumination: smooth (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 60 Irradiance cache•The indirect illumination is smoothMIT EECS 6.837, Cutler and Durand 61 Irradiance cache•The indirect illumination is smoothMIT EECS 6.837, Cutler and Durand 62 Irradiance cache•The indirect illumination is smooth•Interpolate nearby valuesMIT EECS 6.837, Cutler and Durand 63 Irradiance cache•Store the indirect illumination•Interpolate existing cached values•But do full calculation for direct lightingMIT EECS 6.837, Cutler and Durand 64 Irradiance caching (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 65 Photon mapping•Preprocess: cast rays from light sources•Store photonsMIT EECS 6.837, Cutler and Durand 66 Photon mapping•Preprocess: cast rays from light sources•Store photons (position + light power + incoming direction)MIT EECS 6.837, Cutler and Durand 67 Photon map•Efficiently store photons for fast access•Use hierarchical spatial structure (kd-tree)MIT EECS 6.837, Cutler and Durand 68 Photon mapping -rendering•Cast primary rays•For secondary rays–reconstruct irradiance using adjacent stored photon–Take the k closest photons•Combine with irradiance caching and a number of other techniquesMIT EECS 6.837, Cutler and Durand 69 Photon map results (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 70 Photon mapping -caustics•Special photon map for specularreflection and refractionGlass sphereMIT EECS 6.837, Cutler and Durand 71 •1000 paths/pixel (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 72 •Photon mapping (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 73 Photon mapping recap•Preprocess: Path tracing –Store photons–Special map for caustics (because not as uniform)•Rendering–Primary rays–Direct lighting–Indirect lighting•Reconstruct irradiance using k nearest photons•Irradiance caching–Reconstruct caustics from caustic mapMIT EECS 6.837, Cutler and Durand 74 Questions? (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 75 Why is the sky blue? (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 76 Answer: because sunset is red (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 75 Why is the sky blue? (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 39 Sampling strategies Sampling more the light Sampling more the BRDF (Image removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 75 Why is the sky blue?MIT EECS 6.837, Cutler and Durand 80 Sun Color•At sunset, longer traversal of atmosphere•More blue is scattered, red remains•Therefore redderMIT EECS 6.837, Cutler and Durand 81 Computer graphics sky models•E.g. Preethamet al. SIGGRAPH 99. (Images removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 82 Night Sky Model•Jensen, Durand, Stark, Premoze, Dorsey, Shirley 2001 (Images removed due to copyright considerations.)MIT EECS 6.837, Cutler and Durand 83 Questions? (Image removed due to copyright considerations.)