Recursive Ray TracingRon GoldmanDepartment of Computer ScienceRice UniversitySetup1. Eye Point2. Viewing Screen3. Light Sources4. Objects in Scenea. Reflectivityb. Transparencyc. Index of Refraction5. Bounding Boxes {Optional}AlgorithmFor each pixelFind all intersections of ray from eye to pixel with every object in the scene.{Line–Surface Intersection)Keep the intersection closest to the eye.{Smallest positive parameter value along the line.}Compute the color and intensity of the light at this intersection point.{Recursion -- see below.}Display the scene.Color and Intensity at a PointBinary Light TreeI = Idirect+ ksIreflected+ ktIrefractedIdirect= Iambiant+ Idiffuse+ IspecularIdirectIreflectedIreflectedIrefractedIrefractedIreflectedIrefracted MksksksktktktTree truncated at specified depth to avoid infinite recursion.Reflections, Refractions, and ShadowsFor each object in the sceneDecide whether it is reflecting, transparent, semi-transparent, or opaque.Assign values forks = reflectivitykt = transparency {for shadowing and refraction}ci = index of refractionopaque = 0air = 1Note: if transparent, then Idirect= 0ShadowsAlgorithmFor each visible point cast a virtual ray to each light source.If the virtual ray hits an opaque object before it hits the light source {0<t<1},then omit the contribution of this light source.•Idiffuse= Ispecular= 0• Note: an object may be self shadowed -- lie in its own shadow (e.g. sphere) -- so we must compute intersections even with the object containing the point.If the virtual ray hits a transparent or semi–transparent object before it hits the light source, then scale the contribution of this light source and continue to look for further intersections.Shadows (continued)Shadow Coherence • To speed up the algorithm• Store current shadowing object. • Test it first for next ray.Problem• Shadow rays not refracted (if they were they would not hit the light source!).Solution• Trace rays starting from light sources. • Very expensive. • Not generally done.ReflectionFor each visible point on a reflecting object: Treat the point as a virtual eyeUse the law of mirrors: angle of incidence = angle of reflectionto calculate a reflected secondary ray. {See calculation of R(t) below.}Find all intersections of the reflected ray with every object in the scene.Keep the intersection closest to the virtual eye.{Smallest positive parameter value along the line.}Compute the color and intensity of the light at this intersection recursivelyand add a scaled version of this contribution to the color and intensity of the original point as ksIreflected.{Note: some algorithms also scale by distance.}ReflectionNθVSurfaceθW(V ∞N)N€ V −(V ∞N)NEye€ (V ∞N)N −VP∞R(t) = P + tW {virtual (secondary) ray}W = 2(V ∞N)N − VRefractionFor each visible point on a transparent object: Treat the point as a virtual eye.Use Snell’s Law: € c2c1=sin(θ2)sin(θ1)to find the refracted secondary ray {See calculation of R(t) below.}Find all intersections of the refracted ray with every object in the sceneKeep the intersection closest to the virtual eye.{Smallest positive parameter value along the line.}Compute the color and intensity of the light at this intersection recursivelyand add a scaled contribution to the color and intensity of the original point as ktIrefracted. {Note again some algorithms also scale by distance.}RefractionSetup• N = unit vector normal to surface {known}• V = unit vector from surface to eye {known}• W = refracted ray {to be computed}•R(t) = P + tW{virtual (refracted) ray}RefractionNθ1VSurfaceθ2WEye−NP∞Refraction Made SimpleSnell’s Law•€ c2c1=sin(θ2)sin(θ1)Rotation Matrix•€ rot(θ2,u) = cos(θ2)I + 1− cos(θ2)( )(u ⊗ u) + sin(θ2)(u × _)•€ sin(θ2) =c2c1sin(θ1)•€ cos(θ2) = 1− sin2θ2•€ u =N ×V| N ×V | (unit vector normal to the plane of N and V)Refraction Vector€ W = −N ∗rot(θ2,u)Refraction Made Simple (continued)Refraction Vector € W = −N ∗rot(θ2,u) = −cos(θ2)N − 1− cos(θ2)( )(N ∞u=0{)u − sin(θ2)(u × N) = −cos(θ2)N + sin(θ2)(N × u)Further Simplification € u =N ×V| N ×V |=N ×V| N |=1{| V |=1{sin(θ1)=N ×Vsin(θ1)€ W = −cos(θ2)N +sin(θ2)sin(θ1)N ×(N ×V) = −cos(θ2)N +c2c1N ×( N ×V )Refraction Made Simple (continued)Further Simplification•€ A ×(B ×C) = ( A ∞C)B− (A∞B)C• € N ×(N ×V ) = (N ∞V)N − (N ∞N=11 2 3 )V = (N ∞V )N −VRefraction Vector•€ W = −cos(θ2)N +c2c1(N ∞V)N −V( )•€ cos(θ2) = 1− sin2θ2= 1−c22c12sin2θ1= 1−c22c12(1- cos2θ1)•€ cos(θ2) = 1−c2c1      21- (N ∞V)2( )Total Reflection• May occur when c2c1> 1.•€ c2c1sin(θ1) >1 ⇒ sin(θ2) cannot exist.• Test for total reflection•€ c22c121- (N ∞V)2( )> 1⇔ 1 -(N ∞V)2>c1c2      2 • Must check for this case. Be careful!Observations1. Refraction is caused by different speeds of light in different mediums.2. Note that for each color, we use the same index of refraction and therefore the same refracted ray. Technically this is incorrect, but it saves tremendously on computation.Extents1. Ray–Surface intersections are expensive to compute.2. Lots of rays are caste -- m(2n−1)m = number of light sourcesn = depth of ray treeEven more rays for antialiasing!3. To speed computations, bound the objects in the scene with simple objects.Each object comes equiped (after some preprocessing) witha. a bounding box in 3-space;b. a bounding rectangle in the viewing plane.4. Quick reject if ray fails to intersect the bound.Bounding Boxes and Bounding RectanglesBounding Boxes -- 3-Space• For secondary and virtual rays• Sides parallel to axes for faster computation -- coordinate dependent• Sides in arbitrary orientations for tighter fit -- view independentBounding Rectangles -- Viewing Plane• Rectangle surrounding projection of bounding box in 3-space• View dependent and coordinate dependent -- speed• If pixel not within rectangle bound, do not bother to intersect ray with objectParallel Computations1. Independent rays can be cast in parallel.2. Reflection, Refraction, and Shadow rays can be caste in parallel.3. Ray–Surface intersection can be calculated independently for each surface.AntialiasingCaste rays through corners of pixel instead of center.If 4 corner values are close, take their average.Otherwise Subdivide the pixel into 4 virtual