Slide 1OverviewRasterizationRay TracingRasterization vs. Ray TracingRay TracingRay Tracing algorithmsOverviewRay/Object intersectionRay/Object intersectionExample: Ray/Sphere IntersectionExample: Ray/Sphere IntersectionRay/sphere intersectionOverviewRecursive ray tracing: shadowsRecursive Ray Tracing: ReflectionRecursive Ray Tracing: RefractionWhere’s the recursion?Recursive Ray Tracing: ExampleRecursive Ray Tracing: ExampleComputing ray colorsComputing reflection raysComputing refraction raysOverviewDistributed ray tracingDistributed Ray TracingArea shadows with DRTArea shadows with DRTOther effectsStochastic samplingConclusionRay TracingChristian LauterbachCOMP 770, 2/11/2009OverviewRay Tracing vs. rasterizationRay/Object intersection algorithmsRay Tracing methodsRecursive ray tracingDistributed ray tracingRasterizationViewerScreenRay TracingViewerScreenRasterization vs. Ray TracingRasterizationFor each primitive:For each pixel:Is Pixel in Primitive? Yes: Test depth / write colorRay TracingFor each pixel: generate rayFor each primitive:Does ray hit primitive?Yes: Test depth / write colorRay Tracing“Tracing a ray” = find first hit with scene objectNaïve:Test against all scene objectsLike testing all pixels in rasterization!In reality:Acceleration structure gives quick estimate of potentially visible objects for ray(topic of 2nd lection on RT)Ray Tracing algorithmsSo what’s the big deal?Ray Tracing far more flexible paradigmNot limited to primary visibility!Recursive (Whitted) ray tracing:Reflections, Refractions, ShadowsDistributed ray tracing...and many more applicationsOverviewRay Tracing vs. rasterizationRay/Object intersection algorithmsRay Tracing methodsRecursive ray tracingDistributed ray tracingRay/Object intersectionCan intersect ray with many objectsTriangles, PlanesSpheres, Cylinders, ConesBoxes (axis-aligned or otherwise)General polyhedra and many moreEven procedural/implicit objects!Constructive solid geometry (CSG)Implicit surfaces / equationsRay/Object intersectionRay:Origin xDirection dRay formula:x + t*dt > 0xdExample: Ray/Sphere IntersectionSphere equation:(p – S)2 – r2 = 0So let’s plug in ray equation!((x + t*d)– S)2 – r2 = 0Simplify a bit, let v = (x – S)(t*d + v)2 – r2 = 0Expand:t2d2 + 2dvt + v2 - r2 = 0SrExample: Ray/Sphere IntersectionFrom last slide:t2d2 + 2dvt + v2 - r2 = 0Quadratic equation of t of formAt2 + Bt + C = 0Easy to solvet1,2 = -B ± sqrt[ ¼B2 – C ]Two real solutions: why?SrRay/sphere intersectionThis is only one possible algorithmMany more optimized versions existE.g. early exits or less branchesSometimes best intersection algorithm is hardware specific, tooOne solution: auto-tuningOverviewRay Tracing vs. rasterizationRay/Object intersection algorithmsRay Tracing methodsRecursive ray tracingDistributed ray tracingRecursive ray tracing: shadowsViewerLightShadow rayIf first hit of shadow ray closer than distance to light  in shadowRecursive Ray Tracing: ReflectionViewerLightReflection rayRecursive Ray Tracing: RefractionViewerLightRefraction rayWhere’s the recursion?ViewerLightReflection rayReflection ray Refraction rayRecursive Ray Tracing: Example(from [Whitted80])Recursive Ray Tracing: ExampleComputing ray colorsHow to get the final pixel color?Every material has local color cDefine reflexivity, refraction factors ρ(i.e. between 1.0 (mirror) and 0.0 (no reflection)Each hit returns its color down the chainEnd result:Color = (1 –ρ) c1 + ρ1 ( (1- ρ2)c2 + ρ2 (c3 …. )))Local color also influenced by shadow rays!Computing reflection raysReflection is pretty simpleIncident angle = Exit angleIncident ray: x + t*d Reflection ray: a + t*(d – 2*n*dot(n,d))(careful, assumes n and d normalized!) naComputing refraction raysRefraction occurs at material boundariesE.g. air-glassDepends on refractive index n of materialsSnell’s law: n 1 * sin(θ1) = n2 * sin(θ2)Special case:total internal reflectiondenser to less dense materialθ > critical anglen1n2θ1θ2OverviewRay Tracing vs. rasterizationRay/Object intersection algorithmsRay Tracing methodsRecursive ray tracingDistributed ray tracingDistributed ray tracingRay Tracing: too idealistic!No point light sources in natureNo perfect reflections etc.Distributed ray tracing ideaSubstitute exact single rays with several probabilistically generated raysDistributed Ray TracingAllows many physically correct effects:Soft area shadowsGlossy, imperfect reflections and refractionsDepth of FieldMotion blur(from [Boulos07])Area shadows with DRTViewerLightShadow rayArea shadows with DRTViewerArea lightn shadow rays for randomly selected points on light Lighting now determined by #rays reach light / #rays shotOther effectsReflections, Refraction similarE.g. sample rays inside cone defined by directionDepth of fieldSample different viewer positions on lensMotion blurSample different time pointsAll work together!Stochastic samplingOne new disadvantage: sampling needs to be high, or artifacts visibleManifests as high-frequency noiseGood sample generation is art in itselfMuch, much slower than simple ray tracing(from [Boulos07])ConclusionRay Tracing advantagesReflections, refraction, shadowsRendering of arbitrary objectsDoes not even need explicit representationUsed for global illumination, many othersDisadvantagesUsually much slower(no hardware acceleration,