MIT EECS 6.837, Cutler and Durand 1 Ray Casting IIMIT EECS 6.837Frédo Durand and Barb CutlerSome slides courtesy of Leonard McMillan Courtesy of James Arvo and David Kirk. Used with permission.MIT EECS 6.837, Cutler and Durand 2 Review of Ray CastingMIT EECS 6.837, Cutler and Durand 3 Ray CastingFor every pixel Construct a ray from the eye For every object in the sceneFind intersection with the ray Keep if closestMIT EECS 6.837, Cutler and Durand 4 Ray Tracing•Secondary rays (shadows, reflection, refraction)•In a couple of weeksreflectionrefractionMIT EECS 6.837, Cutler and Durand 5 Ray representation•Two vectors:–Origin–Direction (normalized is better)•Parametric line–P(t) = R + t * DRDP(t)MIT EECS 6.837, Cutler and Durand 6 Explicit vs. implicit•Implicit –Solution of an equation–Does not tell us how to generate a point on the plane–Tells us how to check that a point is on the plane•Explicit–Parametric–How to generate points–Harder to verify that a point is on the rayMIT EECS 6.837, Cutler and Durand 7 A note on shading•Normal direction, direction to light•Diffuse component: dot product•Specularcomponent for shiny materials–Depends on viewpoint•More in two weeks Diffuse sphereshiny spheresMIT EECS 6.837, Cutler and Durand 8 Textbook •Recommended, not required•Peter ShirleyFundamentals of Computer GraphicsAK PetersMIT EECS 6.837, Cutler and Durand 9 References for ray casting/tracing•Shirley Chapter 9•Specialized books:–An Introduction to Ray Tracing, Edited by Andrew S. Glassner–Realistic Ray Tracing, Peter Shirley–Realistic Image Synthesis Using Photon Mapping, Henrik Wann Jensen•Online resourceshttp://www.irtc.org/http://www.acm.org/tog/resources/RTNews/html/http://www.povray.org/http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtrace0.htmhttp://www.siggraph.org/education/materials/HyperGraph/raytrace/rt_java/raytrace.htmlMIT EECS 6.837, Cutler and Durand 10 Assignment 1•Write a basic ray caster–Orthographic camera–Spheres–Display: constant color and distance•We provide –Ray –Hit–Parsing–And linear algebra, imageMIT EECS 6.837, Cutler and Durand 11 Object-oriented design•We want to be able to add primitives easily–Inheritance and virtual methods•Even the scene is derived from Object3D!Object3Dboolintersect(Ray, Hit, tmin)Planeboolintersect(Ray, Hit, tmin)Sphereboolintersect(Ray, Hit, tmin)Triangleboolintersect(Ray, Hit, tmin)Groupboolintersect(Ray, Hit, tmin)MIT EECS 6.837, Cutler and Durand 12 Rayclass Ray {public://CONSTRUCTOR & DESTRUCTORRay () {}Ray (const Vec3f &dir, const Vec3f &orig) {direction = dir;origin = orig; }Ray (const Ray& r) {*this=r;}//ACCESSORSconst Vec3f& getOrigin() const { return origin; }const Vec3f& getDirection() const { return direction; }Vec3f pointAtParameter(float t) const {return origin+direction*t; }private://REPRESENTATIONVec3f direction;Vec3f origin;};MIT EECS 6.837, Cutler and Durand 13 Hit•Store intersection point & various informationclass Hit { public: //CONSTRUCTOR & DESTRUCTOR Hit(float _t, Vec3f c) { t = _t; color = c; } ~Hit() {} //ACCESSORS float getT() const { return t; } Vec3f getColor() const { return color; } //MODIFIER void set(float _t, Vec3f c) { t = _t; color = c; }private: //REPRESENTATION float t; Vec3f color; //Material *material; //Vec3f normal; }; MIT EECS 6.837, Cutler and Durand 14 Tasks•Abstract Object3D•Sphere and intersection•Group class•Abstract camera and derive Orthographic•Main functionMIT EECS 6.837, Cutler and Durand 15 Questions?Image removed due to copyright considerations.MIT EECS 6.837, Cutler and Durand 16 Overview of today•Ray-box intersection•Ray-polygon intersection •Ray-triangle intersectionMIT EECS 6.837, Cutler and Durand 17 Ray-ParallelepipedIntersection•Axis-aligned•From (X1, Y1, Z1) to (X2, Y2, Z2)•Ray P(t)=R+Dty=Y2y=Y1x=X1x=X2RDMIT EECS 6.837, Cutler and Durand 18 Naïve ray-box Intersection•Use 6 plane equations•Compute all 6 intersection•Check that points are inside boxAx+by+Cz+D<0 with proper normal orientationy=Y2y=Y1x=X1x=X2RDFactoring out computation MIT EECS 6.837, Cutler and Durand 19 •Pairs of planes have the same normal•Normalshave only one non-0 component•Do computations one dimension at a time•Maintain tnearand tfar(closest and farthest so far)y=Y2y=Y1x=X1x=X2RDTest if parallel MIT EECS 6.837, Cutler and Durand 20 •If Dx=0, then ray is parallel–If Rxx2 return falsey=Y2y=Y1x=X1x=X2RDMIT EECS 6.837, Cutler and Durand 21 If not parallel•Calculate intersection distance t1 and t2–t1=(X1-Rx)/Dx–t2=(X2-Rx)/Dxy=Y2y=Y1x=X1x=X2RDt1t2MIT EECS 6.837, Cutler and Durand 22 Test 1•Maintain tnearand tfar–If t1>t2, swap–if t1>tnear, tnear=t1 if t2tfar, box is missedy=Y2y=Y1RDt1xt2xtneart1yt2ytfartfarx=X1x=X2MIT EECS 6.837, Cutler and Durand 23 Test 2•If tfar<0, box is behindy=Y2y=Y1RDt1xt2xtfarx=X1x=X2MIT EECS 6.837, Cutler and Durand 24 Algorithm recap•Do for all 3 axis–Calculate intersection distance t1 and t2–Maintain tnearand tfar–If tnear>tfar, box is missed–If tfar<0, box is behind•If box survived tests, report intersection at tneary=Y2y=Y1x=X1x=X2RDtneart1ytfarMIT EECS 6.837, Cutler and Durand 25 Efficiency issues•Do for all 3 axis–Calculate intersection distance t1 and t2–Maintain tnearand tfar–If tnear>tfar, box is missed–If tfar<0, box is behind•If box survived tests, report intersection at tnear•1/Dx, 1/Dy and 1/Dz can be precomputedand shared for many boxes•Unroll the loop –Loops are costly (because of termination if)–Avoids the tneartfarfor X dimensionMIT EECS 6.837, Cutler and Durand 26 Questions?Image removed due to copyright considerations.MIT EECS 6.837, Cutler and Durand 27 Overview of today•Ray-box intersection•Ray-polygon intersection •Ray-triangle intersectionMIT EECS 6.837, Cutler and Durand 28 Ray-polygon intersection•Ray-plane intersection•Test if intersection is in the polygon–Solve in the 2D planeDRMIT EECS 6.837, Cutler and Durand 29 Point inside/outside polygon•Ray intersection definition:–Cast a ray in any direction •(axis-aligned is smarter)–Count intersection–If odd number, point is inside•Works for concave and star-shapedMIT EECS 6.837, Cutler and Durand 30 Precision issue•What if we intersect a vertex?–We might wrongly count an intersection for each adjacent edge•Decide that the vertex is always above the rayMIT EECS 6.837, Cutler and Durand 31 Winding number•To solve problem with star pentagon •Oriented edges•Signed number of intersection•Outside if 0 intersection+-+-MIT EECS 6.837, Cutler and Durand 32 Alternative definitions•Sum of the signed angles from point to vertices–360 if inside, 0 if outside•Sum of the signed areas of point-edge triangles–Area of polygon if inside, 0 if outsideMIT EECS 6.837, Cutler and Durand 33 How do we project into 2D?•Along normal–Costly•Along axis–Smarter (just drop 1 coordinate)–Beware of parallel planeDRDRMIT EECS 6.837, Cutler and Durand 34 Questions?Image removed due to copyright considerations.MIT EECS 6.837, Cutler and Durand 35 Overview of today•Ray-box intersection•Ray-polygon intersection •Ray-triangle intersectionMIT EECS 6.837, Cutler and Durand 36 Ray triangle intersection•Use ray-polygon•Or try to be smarter–Use barycentriccoordinatescabPRDMIT EECS 6.837, Cutler and Durand 37 Barycentricdefinition of a plane[Möbius, 1827]•P( α, β, γ)=αa+βb+γcwith α + β + γ=1•Is it explicit or implicit?cPabMIT EECS 6.837, Cutler and Durand 38 Barycentricdefinition of a triangle•P( α, β, γ)=αa+βb+γcwith α + β + γ=10< α <10< β <10< γ <1cabPGiven P, how can we compute α, β, γ ? MIT EECS 6.837, Cutler and Durand 39 •Compute the areas of the opposite subtriangle–Ratio with complete areaα=Aa/A, β=Ab/Aγ=Ac/AUse signed areas for points outside the trianglecabPTaTMIT EECS 6.837, Cutler and Durand 40 Intuition behind area formula•P is barycenterof a and Q•A is the interpolation coefficient on aQ•All points on line parallel to bchave the same α•All such Ta triangles have same height/areacabPQMIT EECS 6.837, Cutler and Durand 41 Simplify•Since α + β + γ=1we can write α =1−β −γ•P(β, γ)=(1−β−γ) a + βb +γccabPMIT EECS 6.837, Cutler and Durand 42 Simplify•P(β, γ)=(1−β−γ) a + βb +γc•P(β, γ)=a + β(b-a) +γ(c-a)•Non-orthogonal coordinate system of the planecabPMIT EECS 6.837, Cutler and Durand 43 How do we use it for intersection?•Insert ray equation into barycentricexpression of triangle•P(t)= a+β (b-a)+γ (c-a)•Intersection if β+γ<1; 0<β and 0<γabPRDcMIT EECS 6.837, Cutler and Durand 44 Intersection•Rx+tDx= ax+β (bx-ax)+γ (cx-ax)•Ry+tDy= ay+β (by-ay)+γ (cy-ay)•Rz+tDz= az+β (bz-az)+γ (cz-az)cabPRDMIT EECS 6.837, Cutler and Durand 45 Matrix form•Rx+tDx= ax+β (bx-ax)+γ (cx-ax)•Ry+tDy= ay+β (by-ay)+γ (cy-ay)•Rz+tDz= az+β (bz-az)+γ (cz-az)abPRD⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−−=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−−−−−zzyyxxzzzzzyyyyyxxxxxRaRaRatDcabaDcabaDcabaγβcMIT EECS 6.837, Cutler and Durand 46 Cramer’s rule•| | denotes the determinant•Can be copied mechanically in the codeabPRDADcaRaDcaRaDcaRazzzzzyyyyyxxxxx−−−−−−=βADRabaDRabaDRabazzzzzyyyyyxxxxx−−−−−−=γARacabaRacabaRacabatzzzzzzyyyyyyxxxxxx−−−−−−−−−=cMIT EECS 6.837, Cutler and Durand 47 Advantage•Efficient•Store no plane equation•Get the barycentriccoordinates for free–Useful for interpolation, texture mappingabPRDcMIT EECS 6.837, Cutler and Durand 48 Pluckercomputation•Pluckerspace: 6 or 5 dimensional space describing 3D lines•A line is a point in PluckerspaceMIT EECS 6.837, Cutler and Durand 49 Pluckercomputation•The rays intersecting a line are a hyperplane•A triangle defines 3 hyperplanes•The polytopedefined by the hyperplanesis the set of rays that intersect the triangleMIT EECS 6.837, Cutler and Durand 50 Pluckercomputation•The rays intersecting a line are a hyperplane•A triangle defines 3 hyperplanes•The polytopedefined by the hyperplanesis the set of rays that intersect the triangle•Ray-triangle intersection becomes a polytopeinclusion•Couple of additional issuesMIT EECS 6.837, Cutler and Durand 51 Next week: Transformations•Permits 3D IFS ;-) Image removed due to copyright considerations.