Monte Carlo Path TracingLight PathLight TransportPath TracingPenumbra: Trees vs. PathsPath Tracing: From CameraM. Fajardo Arnold Path TracerCornell Box: Path TracingPath Tracing: Include Direct LightingDiscrete Random WalkDiscrete Random ProcessSlide 12Slide 13Monte Carlo AlgorithmSlide 15EstimatorEquilibrium Distribution of StatesLight Ray TracingExamplesPath Tracing: From LightsSlide 21Bidirectional Path TracingBidirectional Ray TracingPath PyramidComparisonGenerating All PathsAdjoint FormulationSymmetric Light PathSlide 29Slide 30Three ConsequencesExample: Linear EquationsCS348B Lecture 14 Pat Hanrahan, Spring 2005Monte Carlo Path TracingTodayPath tracingRandom walks and Markov chains Eye vs. light ray tracingBidirectional ray tracingNextIrradiance cachingPhoton mappingCS348B Lecture 14 Pat Hanrahan, Spring 2005Light Path0 1 2 3 0 1 1 0 1 2 1 2 1 2 3( , , , ) ( , ) ( , ) ( , , ) ( , ) ( , , )S o r rL x x x x S x x G x x f x x x G x x f x x x=0x1x2x1 2( , )G x x0 1 2( , , )rf x x x1 2 3( , , )rf x x x0 1( , )S x x0 1( , )G x x0 1 2 3( , , , )SL x x x xCS348B Lecture 14 Pat Hanrahan, Spring 2005Light TransportIntegrate over all pathsQuestionsHow to sample space of paths2 210 2 1 0 21( , )( , , , , ) ( ) ( )k kS k k k kkM ML x xL x x x x dA x dA x-�- - -==�� �L L LPath TracingCS348B Lecture 14 Pat Hanrahan, Spring 2005Penumbra: Trees vs. Paths4 eye rays per pixel16 shadow rays per eye ray64 eye rays per pixel1 shadow ray per eye rayCS348B Lecture 14 Pat Hanrahan, Spring 2005Path Tracing: From CameraStep 1. Choose a camera ray r given the (x,y,u,v,t) sampleweight = 1;Step 2. Find ray-surface intersection Step 3. if lightreturn weight * Le();elseweight *= reflectance(r)Choose new ray r’ ~ BRDF pdf(r) Go to Step 2.CS348B Lecture 14 Pat Hanrahan, Spring 2005M. Fajardo Arnold Path TracerCS348B Lecture 14 Pat Hanrahan, Spring 2005Cornell Box: Path Tracing10 rays per pixel100 rays per pixelFrom Jensen, Realistic Image Synthesis Using Photon MapsCS348B Lecture 14 Pat Hanrahan, Spring 2005Path Tracing: Include Direct LightingStep 1. Choose a camera ray r given the (x,y,u,v,t) sampleweight = 1;Step 2. Find ray-surface intersection Step 3. weight += Lr(light sources)Choose new ray r’ ~ BRDF pdf(r) Go to Step 2.Discrete Random WalkCS348B Lecture 14 Pat Hanrahan, Spring 2005Discrete Random ProcessCreationTerminationTransitionStates0: probability of creation in state ip i,: probability of transition from state i jp i j�*: probability of termination in state ip i*,1i i jjp p= -�Assign probabilities to each processCS348B Lecture 14 Pat Hanrahan, Spring 2005Discrete Random ProcessCreationTerminationTransitionStates0,i i j j ijP p P p= +�Equilibrium number of particles in each state0P MP p= +, ,i j i jM p=CS348B Lecture 14 Pat Hanrahan, Spring 2005Discrete Random Walk1. Generate random particles from sources. 2. Undertake a discrete random walk.3. Count how many terminate in state i[von Neumann and Ulam; Forsythe and Leibler; 1950s]CreationTerminationTransitionStatesCS348B Lecture 14 Pat Hanrahan, Spring 2005Monte Carlo AlgorithmDefine a random variable on the space of pathsPath:Probability:Estimator:Expectation:1[ ] ( ) ( )kk kkE W P Waa a�==��1 2( , , , )k ki i ia = K( )kP a( )kW aCS348B Lecture 14 Pat Hanrahan, Spring 2005Monte Carlo AlgorithmDefine a random variable on the space of pathsProbability:Estimator:1 1 2 10 *, ,( )k k kk i i i i i iP p p p pa-= � �L,*( )kki jj kiWpda =CS348B Lecture 14 Pat Hanrahan, Spring 2005EstimatorCount the number of particles terminating in state j1 1 2 11,0 *, ,*10 0 2 0[ ] ( )kk k kki jj i i i i i ik i ijj j jE W p p p ppp Mp M pd-�==� � � � � �= + +� � � � � ��� �L LLCS348B Lecture 14 Pat Hanrahan, Spring 2005Equilibrium Distribution of StatesTotal probability of being in states PNote that this is the solution of the equationThus, the discrete random walk is an unbiased estimate of the equilibrium number of particles in each state( )L2 0P I M M p= + + +0( )I M P p- =Light Ray TracingCS348B Lecture 14 Pat Hanrahan, Spring 2005ExamplesBackward ray tracing, Arvo 1986CS348B Lecture 14 Pat Hanrahan, Spring 2005Path Tracing: From LightsStep 1. Choose a light rayChoose a light source according to the light source power distribution function.Choose a ray from the light source radiance (area) or intensity (point) distribution functionw = 1;Step 2. Trace ray to find surface intersect Step 3. InteractionCS348B Lecture 14 Pat Hanrahan, Spring 2005Path Tracing: From LightsStep 1. Choose a light rayStep 2. Find ray-surface intersectionStep 3. Interactionu = rand()if u < reflectanceChoose new ray r ~ BRDFgoto Step 2elseterminate on surface; deposit energyBidirectional Path TracingCS348B Lecture 14 Pat Hanrahan, Spring 2005Bidirectional Ray Tracing0, 3l e= =1, 2l e= =3, 0l e= =2, 1l e= =k l e= +3k =CS348B Lecture 14 Pat Hanrahan, Spring 2005Path Pyramid3k4k5k6kle)1,5( el)1,2( elFrom Veach and GuibasCS348B Lecture 14 Pat Hanrahan, Spring 2005ComparisonBidirectional path tracing Path tracingFrom Veach and GuibasCS348B Lecture 14 Pat Hanrahan, Spring 2005Generating All PathsAdjoint FormulationCS348B Lecture 14 Pat Hanrahan, Spring 2005Symmetric Light Path0 1 1 0 1 2 1 2 1 2 3 2 3 2 3( , ) ( , ) ( , , ) ( , ) ( , , ) ( , ) ( , )o r rM S x x G x x f x x x G x x f x x x G x x R x x=0x1x2x1 2( , )G x x0 1 2( , , )rf x x x1 2 3( , , )rf x x x0 1( , )S x x0 1( , )G x x2 3( , )R x x3x2 3( , )G x xCS348B Lecture 14 Pat Hanrahan, Spring 2005Symmetric Light Path=0 1 0 1 0 1 2 1 2 1 2 3 2 3 2 3( , ) ( , ) ( , , ) ( , ) ( , , ) ( , ) ( , )r rM S x x G x x f x x x G x x f x x x G x x R x x0x1x2x1 2( , )G x x0 1 2( , , )rf x x x=1 2 3 3 2 1( , , ) ( , , )r rf x x x f x x x0 1( , )S x x0 1( , )G x x2 3( , )R x x3x=2 3 3 2( , ) ( , )G x x G x xCS348B Lecture 14 Pat Hanrahan, Spring 2005Symmetric Light Path=3 2 3 2 3 2 1 2 1 2 1 0 1 0 1 0( , ) ( , ) ( , , ) ( , ) ( , , ) ( , ) ( , )r rM R x x G x x f x x x G x x f x x x G x x S x x0x1x2x2 1( , )G x x2 1 0( , , )rf x x x3 2 1( , , )rf x x x1 0( , )S x x1 0( , )G x x3 2( , )R x x3x3 2( , )G x xCS348B Lecture 14 Pat Hanrahan, Spring 2005Three …
View Full Document