OverviewCamerasVarianceSlide 4Variance ReductionBiasingUnbiased EstimateImportance SamplingSlide 9ExampleExamplesIrradianceCosine Weighted DistributionSampling a CircleShirley’s MappingStratified SamplingMitchell 91DiscrepancyTheorem on Total VariationQuasi-Monte Carlo PatternsHammersley PointsEdge DiscrepancyLow-Discrepancy PatternsHigh-dimensional SamplingBlock DesignSlide 26Space-time PatternsPath TracingViews of IntegrationUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellOverviewLast lectureStatistical sampling and Monte Carlo integrationTodayVariance reductionImportance samplingStratified samplingMultidimensional sampling patternsDiscrepancy and Quasi-Monte CarloLaterSignal processing and samplingPath tracing for interreflectionDensity estimationUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellCameras( , , ) ( ) ( ) cosT AR L x t P x S t dA d dtω θ ωΩ=∫∫∫∫∫Source: Cook, Porter, Carpenter, 1984 Source: Mitchell, 1991Depth of FieldMotion BlurUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellVariance1 shadow ray per eye ray 16 shadow rays per eye rayUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellVariance2 21 11 1 1 1[ ] [ ] [ ] [ ]N Ni ii iV Y V Y NV Y V YN N N N= == = =∑ ∑DefinitionPropertiesVariance decreases with sample size22 22 2[ ] [( [ ]) ][ 2 [ ] [ ] ][ ] [ ]V Y E Y E YE Y YE Y E YE Y E Y≡ −= − += −[ ] [ ]i ii iV Y V Y=∑ ∑2[ ] [ ]V aY a V Y=University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellVariance ReductionEfficiency measureIf one technique has twice the variance of another technique, then it takes twice as many samples to achieve the same varianceIf one technique has twice the cost of another technique with the same variance, then it takes twice as much time to achieve the same varianceTechniques to increase efficiencyImportance samplingStratified sampling1EfficiencyVariance Cost∝•University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellBiasingPreviously used a uniform probability distributionCan use another probability distributionBut must change the estimator~ ( )iX p x( )( )iiif XYp X=University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellUnbiased EstimateProbabilityEstimator~ ( )iX p x( )( )iiif XYp X=( )[ ]( )( )( )( )( )iiiiif XE Y Ep Xf Xp x dxp Xf x dxI⎡ ⎤=⎢ ⎥⎣ ⎦⎡ ⎤=⎢ ⎥⎣ ⎦==∫∫University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellImportance Sampling( )( )[ ]1( )[ ]1f xp x dx dxE ff x dxE f===∫ ∫∫%( )( )[ ]f xp xE f=%Sample according to fUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellImportance SamplingVariance2 2[ ] [ ] [ ]V f E f E f= −2222( )[ ] ( )( )( ) ( )( ) / [ ] [ ][ ] ( )[ ]f xE f p x dxp xf x f xdxf x E f E fE f f x dxE f⎡ ⎤=⎢ ⎥⎣ ⎦⎡ ⎤=⎢ ⎥⎣ ⎦==∫∫∫%%%( )( )[ ]f xp xE f=%( )( )( )f xf xp x=%%Sample according to f2[ ] 0V f =%Zero variance!University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellExamplemethod Samplingfunctionvariance Samples needed for standard error of 0.008importance(6-x)/16 56.8N-1887,500importance1/4 21.3N-1332,812importance(x+2)/16 6.4N-198,432importancex/8 0 1stratified1/4 21.3N-370∫==408xdxIPeter Shirley – Realistic Ray TracingUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellExamplesProjected solid angle4 eye rays per pixel100 shadow raysArea4 eye rays per pixel100 shadow raysUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellIrradianceGenerate cosine weighted distribution2( )cosi i i iHE L dω θ ω=∫( ) cosp d dω ω θ ω=University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellCosine Weighted Distribution€ cos(2H∫θ)dω = dϕ cos(θ)sin(θ)dθ0π2∫02π∫= 2π(12sin2(θ))0π2= π)()()sin()cos(),()sin()cos(),( θϕπθθθϕθϕπθθθϕθϕ pppddddp ==⇒=πϕ21)( =pπϕ21=U12 Uπϕ =πϕϕπϕϕ221)(0000==∫dP)sin()cos(2)( θθθ =p)(sin)(sin)sin()cos(2)(02002000θθθθθθθθ===∫dP)(sin22θ=U)arcsin(2U=θUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellSampling a Circle122 Ur Uθ π==Equi-ArealUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellShirley’s Mapping1214r UUUπθ==University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellStratified SamplingStratified sampling is like jittered samplingAllocate samples per regionNew varianceThus, if the variance in regions is less than the overall variance, there will be a reduction in resulting variance•For example: An edge through a pixel211[ ] [ ]NN iiV F V FN==∑2 1.511 [ ][ ] [ ]NEN jiV FV F V FN N== =∑11NN iiF FN==∑University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellMitchell 91Uniform random Spectrally optimizedUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellDiscrepancyxy( , )( , )( , ) number of samples in n x yx y xyNA xyn x y AΔ = −=,max ( , )Nx yD x y= ΔUniversity of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellTheorem on Total VariationTheorem: Proof: Integrate by parts11( ) ( ) ( )Ni Nif X f x dx V f DN=− ≤∑∫( ) ( )1ix x xx Nδ∂Δ −= −∂10( )( ) [ 1]( )( )( ) ( )( ) ( )( )( )iN Nx xf x dxNxf x dxxf x f xf x dx x dxx xf xD dx V f Dxδ −−∂Δ=∂∂ ∂= Δ − Δ =− Δ∂ ∂∂≤ =∂∫∫∫ ∫∫University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellQuasi-Monte Carlo PatternsRadical inverse (digit reverse) of integer i in integer base bHammersley pointsHalton points (sequential)2 1 00 1 2( ) 0.ib ii d d d di d d d dφ=≡LL1 1 .1 1/22 10 .01 1/43 11 .11 3/44 100 .001 3/85 101 .101 5/82( )iφ2 3 5( / , ( ), ( ), ( ), )i N i i iφ φ φ L1log( )dNND ON−=2 3 5( ( ), ( ), ( ), )i i iφ φ φ Llog( )dNND ON=University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2007 Don FussellHammersley Points2 3 5( / , ( ), (
View Full Document
Unlocking...