Ray TracingClassic Ray TracingRay Tracing in Computer GraphicsSlide 4Ray Tracing VideoSpheres-over-plane.pbrt (g/m 10)Spheres-over-plane.pbrt (mirror 0)Spheres-over-plane.pbrt (mirror 1)Spheres-over-plane.pbrt (mirror 2)Spheres-over-plane.pbrt (mirror 5)Spheres-over-plane.pbrt (mirror 10)Spheres-over-plane.pbrt (glass 0)Spheres-over-plane.pbrt (glass 1)Spheres-over-plane.pbrt (glass 2)Spheres-over-plane.pbrt (glass 5)Spheres-over-plane.pbrt (glass 10)Slide 17Slide 18PBRT ArchitectureSlide 20Ray-Surface IntersectionRay-Plane IntersectionRay-PolyhedraRay-Triangle Intersection 12D Homogeneous CoordinatesSlide 26Ray-Triangle Intersection 2Ray-Triangle Intersection 3Ray-Polygon IntersectionPoint in PolygonRay-Sphere IntersectionGeometric MethodsRay-Implicit Surface IntersectionRay-Algebraic Surface IntersectionHistoryCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray TracingTodayBasic algorithmsOverview of pbrtRay-surface intersection for single surfaceNext lectureAcceleration techniques for ray tracing large numbers of geometric primitivesCS348B Lecture 2 Pat Hanrahan, Spring 2005Classic Ray TracingGreeks: Do light rays proceed from the eye to the light, or from the light to the eye?Gauss: Rays through lensesThree ideas about light1. Light rays travel in straight lines2. Light rays do not interfere with each other if they cross3. Light rays travel from the light sources to the eye (but the physics is invariant under path reversal - reciprocity).CS348B Lecture 2 Pat Hanrahan, Spring 2005Ray Tracing in Computer GraphicsAppel 1968 - Ray casting1. Generate an image by sending one ray per pixel2. Check for shadows by sending a ray to the lightCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray Tracing in Computer GraphicsWhitted 1979 Recursive ray tracing (reflection and refraction)Ray Tracing VideoCS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (g/m 10)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (mirror 0)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (mirror 1)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (mirror 2)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (mirror 5)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (mirror 10)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (glass 0)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (glass 1)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (glass 2)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (glass 5)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (glass 10)CS348B Lecture 2 Pat Hanrahan, Spring 2005Spheres-over-plane.pbrt (glass 10)CS348B Lecture 2 Pat Hanrahan, Spring 2005CS348B Lecture 2 Pat Hanrahan, Spring 2005PBRT ArchitectureCS348B Lecture 2 Pat Hanrahan, Spring 2005PBRT ArchitectureRay-Surface IntersectionCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Plane IntersectionRay: Plane: Solve for intersection Substitute ray equation into plane equationt= +P O Drr r( ) 00ax by cz d- � =�+ + + =P P Nr r rOvDrt0 t� <�Nr- � = + - � =� �- ��=-�rr r r r r rrr rr r( ) ( ) 0( )ttP P N O D P NO P ND NPr�PrCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-PolyhedraRay-SlabRay-Convex PolyhedraRay-Box1t2tNote: Procedural geometryCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Triangle Intersection 11Pr2Pr3PrPr1s2s3s1 1 2 2 3 3s s s= + +P P P Pr r r rBarycentric coordinates1231 2 30 10 10 11ssss s s� �� �� �+ + =Inside triangle criteria1 2 3area( )s = DPP P2 3 1area( )s = DPP P3 1 2area( )s = DPP PCS348B Lecture 2 Pat Hanrahan, Spring 20052D Homogeneous Coordinatesax by cz� = + +L Pr r1 2 1 21 2 1 2 1 21 2 1 2x b c c by c a a cz a b b a-�� � ��� � �= = � = -�� � ��� � �-�� � �P L Lr r r1 2 1 21 2 1 2 1 21 2 1 2a y z z yc z x x zc x y y x-�� � ��� � �= = � = -�� � ��� � �-�� � �L P Pr r rCS348B Lecture 2 Pat Hanrahan, Spring 20052D Homogeneous Coordinates1 1 11 2 3 2 2 23 3 3area( )x y zx y zx y z�P P P1 1 11 2 3 2 2 23 3 3x y zx y zx y z� � =P P Pr r rCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Triangle Intersection 2= + +r r r r1 1 2 2 3 3s s sP P P P[ ] [ ]11 2 3 23sss� �� �=� �� �� �P P P P[ ]1 2 32 3 13 1 2sss�� � � �� � � �= �� � � �� � � ��� � � �P PP P PP PCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Triangle Intersection 32 32 31 2 31 2 31 33 12 3 11 2 31 21 23 1 21 2 3sss�= = � = � �D�= = � = � �D�= = � = � �DP P PP PP P P PP P PP P PP PP P P PP P PP P PP PP P P PP P P[ ]1 2 32 3 13 1 2sss�� � � �� � � �= �� � � �� � � ��� � � �P PP P PP PCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Polygon Intersection1. Find intersection with plane of support2. Test whether point is inside 3D polygona. Project onto xy planeb. Test whether point is inside 2D polygonCS348B Lecture 2 Pat Hanrahan, Spring 2005Point in Polygoninside(vert v[], int n, float x, float y){ int cross=0; float x0, y0, x1, y1; x0 = v[n-1].x - x; y0 = v[n-1].y - y; while( n-- ) { x1 = v->x - x; y1 = v->y - y; if( y0 > 0 ) { if( y1 <= 0 ) if( x1*y0 > y1*x0 ) cross++; } else { if( y1 > 0 ) if( x0*y1 > y0*x1 ) cross++; } x0 = x1; y0 = y1; v++; } return cross & 1;}CS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Sphere IntersectionRay:Sphere:()220R- - =P CrrOrCrDr( )220t R+ - - =O D Cr rr20at bt c+ + =2a =Dr2( )b = - �O C Dr rr2 2( )c R= - -O Cr r242b b acta- � -=t= +P O Drr rPrCS348B Lecture 2 Pat Hanrahan, Spring 2005Geometric MethodsMethodsFind normal and tangentsFind surface parameterse.g. SphereNormalParameters= -N P Crr rsin cossin sincosxyzq fq fq===11tan ( , )cosx yzfq--==NrSrTr, ,u vPrCS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Implicit Surface Intersection1. Substitute ray equation2. Find p ositive, real rootsUnivariate root findingNewton’s methodRegula-falsiInterval methodsHeuristics( , , ) 0f x y z =*( ) 0f t =0 10 10 1x x x ty y y tz z z t= += += +CS348B Lecture 2 Pat Hanrahan, Spring 2005Ray-Algebraic Surface Intersection( , , ) 0np x y z =*( ) 0np t =Degree nLin ear : PlaneQuadric: Spheres, …Quartic: ToriPolynomial root findingQuadratic, cubic, quarticBezier/Bernoulli basisDescartes’ rule of signsSturm sequences0 10 10
View Full Document