MIT EECS 6.837, Cutler and Durand 1 Ray CastingMIT 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 Administrative•Assignment 1–Due Wednesday September 17MIT EECS 6.837, Cutler and Durand 3 Calendar•1st quiz –Tuesday October 07th •2nd quiz --Thursday Nov 20th•Week Dec 1-5 project presentation•Last day of class: December 9: best projects & final report dueMIT EECS 6.837, Cutler and Durand 4 Questions?MIT EECS 6.837, Cutler and Durand 5 Overview of the semester•Ray Tracing–Quiz 1•Animation, modeling, IBMR–Choice of final project•Rendering pipeline–Quiz 2•Advanced topicsMIT EECS 6.837, Cutler and Durand 6 Overview of today•Introduction•Camera and ray generation•Ray-plane intersection•Ray-sphere intersectionMIT EECS 6.837, Cutler and Durand 7 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 8 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 9 ShadingFor every pixel Construct a ray from the eye For every object in the sceneFind intersection with the ray Keep if closestShade depending on light and normal vector e.g. diffuse shading: dot product N.L a.k.a. LambertianMIT EECS 6.837, Cutler and Durand 10 Ray Tracing•Secondary rays (shadows, reflection, refraction)•In a couple of weeksMIT EECS 6.837, Cutler and Durand 11 Ray representation?MIT EECS 6.837, Cutler and Durand 12 Ray representation•Two vectors:–Origin–Direction (normalized is better)•Parametric line–P(t) = origin + t * directionorigindirectionP(t)MIT EECS 6.837, Cutler and Durand 13 Ray Tracing•Original Ray-traced image by Whitted•Image computed using the Dali ray tracer by HenrikWannJensen•Environment map by Paul Debevec Image removed due to copyright considerations. Image removed due to copyright considerations.MIT EECS 6.837, Cutler and Durand 14 Ray castingFor every pixel Construct a ray from the eye For every object in the sceneFind intersectionwith the rayKeep if closestShade depending on light and normalvector Finding the intersection and normal is the central part of ray castingMIT EECS 6.837, Cutler and Durand 15 Overview of today•Introduction•Camera and ray generation•Ray-plane intersection•Ray-sphere intersectionMIT EECS 6.837, Cutler and Durand 16 CamerasFor 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 17 Pinhole camera•Box with a tiny hole•Inverted image•Similar triangles•Perfect image if hole infinitely small•Pure geometric optics•No depth of field issueMIT EECS 6.837, Cutler and Durand 18 Simplified pinhole camera•Eye-image pyramid (frustum)•Note that the distance/size of image are arbitraryMIT EECS 6.837, Cutler and Durand 19 Camera description–Eye point e–Orthobasisu, v, w–Image distance s–Image rectangle (u0, v0, u1, v1)–Deduce c (lower left)–Deduce a and b–Screen coordinates in [0,1]*[0,1]–A point is then c + x a +y buvwecsabxyMIT EECS 6.837, Cutler and Durand 20 Alternative perspective encoding•4x4 matrix & viewing frustum•More about that next weekMIT EECS 6.837, Cutler and Durand 21 Orthographic camera•Parallel projection•No foreshortening•No vanishing pointperspectiveorthographicMIT EECS 6.837, Cutler and Durand 22 Orthographic camera descriptionMIT EECS 6.837, Cutler and Durand 23 Orthographic camera description•Direction•Image center•Image size•Up vectorsizesizeupcenterMIT EECS 6.837, Cutler and Durand 24 Orthographic ray generation•Direction is constant•Origin = center + (x-0.5)*size*up + (y-0.5)*size*horizontalupdirectionhorizontalsize(0,0)(1,1)centersizeMIT EECS 6.837, Cutler and Durand 25 Other weird cameras•E.g. fish eye, omnimax, panoramaMIT EECS 6.837, Cutler and Durand 26 Overview of today•Introduction•Camera and ray generation•Ray-plane intersection•Ray-sphere intersectionMIT EECS 6.837, Cutler and Durand 27 Ray CastingFor every pixel Construct a ray from the eye For every object in the sceneFind intersection with the ray Keep if closestFirst we will study ray-plane intersectionMIT EECS 6.837, Cutler and Durand 28 Recall: Ray representation•Two vectors:–Origin–Direction (normalized)•Parametric line–P(t) = origin + t * directionorigindirectionP(t)MIT EECS 6.837, Cutler and Durand 29 3D plane equation•Implicit plane equationH(p) = Ax+By+Cz+D= 0•Gradient of H?PHMIT EECS 6.837, Cutler and Durand 30 3D plane equation•Implicit plane equationH(p) = Ax+By+Cz+D= 0•Gradient of H?•Plane defined by –P0(x,y,z,1)–n(A, B, C, 1)P0PHMIT EECS 6.837, Cutler and Durand 31 Explicit vs. implicit?•Plane equation is 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•Ray equation is explicit–Parametric–How to generate points–Harder to verify that a point is on the rayMIT EECS 6.837, Cutler and Durand 32 Plane-point distance•Plane Hp=0•If n is normalizedd=HP•Signed distance!P’P0PHMIT EECS 6.837, Cutler and Durand 33 Explicit vs. implicit?•Plane equation is 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•Ray equation is explicit–Parametric–How to generate points–Harder to verify that a point is on the ray•Exercise: explicit plane and implicit rayLine-plane intersection•Insert explicit equation of line intoimplicit equation of planeorigindirectionP(t) MIT EECS 6.837, Cutler and Durand 34Additional house keeping•Verify that intersection is closer than previous•Verify that it is in the allowed range(in particular not behind the camera, t<0) MIT EECS 6.837, Cutler and Durand 35MIT EECS 6.837, Cutler and Durand 36 Normal•For shading (recall, diffuse: dot product between light and normal)•Simply the normal to the planeorigindirectionP(t)normalMIT EECS 6.837, Cutler and Durand 37 Overview of today•Introduction•Camera and ray generation•Ray-plane intersection•Ray-sphere intersectionSphere equation MIT EECS 6.837, Cutler and Durand 38 •Sphere equation (implicit): ||P––2= r2•(assume centered at origin, easy to translate)Ray-Sphere Intersection MIT EECS 6.837, Cutler and Durand 39 •Sphere equation (implicit): ||P––2= r2•Ray equation (explicit): P(t) = R+tDwith ||D|| = 1•Intersection means both are satisfiedRay-Sphere Intersection MIT EECS 6.837, Cutler and Durand 40Ray-Sphere Intersection MIT EECS 6.837, Cutler and Durand 41 •This is just a quadratic at2+ bt+ c = 0, where a = 1 b = 2D.R c = R.R –r2•With discriminant•and solutionsRay-Sphere Intersection MIT EECS 6.837, Cutler and Durand 42 •Discriminant•Solutions•Three cases, depending on sign of b2–4ac•Which root (t+ or t should you choose?–Closest positive! (usually t-)Ray-Sphere Intersection MIT EECS 6.837, Cutler and Durand 43 •So easy that all ray-tracing images have spheres!MIT EECS 6.837, Cutler and Durand 44 Geometric ray-sphere intersection•Try to shortcut (easy reject)•e.g.: if the ray is facing away from the sphere•Geometric considerations can help•In general, early reject is importantRrODMIT EECS 6.837, Cutler and Durand 45 Geometric ray-sphere intersection•What geometric information is important?–Inside/outside–Closest point–DirectionRrODMIT EECS 6.837, Cutler and Durand 46 Geometric ray-sphere intersection•Find if the ray’s origin is outside the sphere–R2>r2–If inside, it intersects –If on the sphere, it does not intersect (avoid degeneracy)RrODMIT EECS 6.837, Cutler and Durand 47 Geometric ray-sphere intersection•Find if the ray’s origin is outside the sphere•Find the closest point to the sphere center–tP=RO.D–If tP<0, no hitRrODtPPMIT EECS 6.837, Cutler and Durand 48 Geometric ray-sphere intersection•Find if the ray’s origin is outside the sphere•Find the closest point to the sphere center–If tP<0, no hit•Else find squared distance d2–Pythagoras: d2=R2-tP2–…RrODPtPdif d2> r2no hitMIT EECS 6.837, Cutler and Durand 49 Geometric ray-sphere intersection•Find if the ray’s origin is outside the sphere•Find the closest point to the sphere center–If tP<0, no hit•Else find squared distance d2–if d2> r2no hit•If outside t = tP-t’–t’2+d2=r2•If inside t = tP+t’RrODPtPdtt’MIT EECS 6.837, Cutler and Durand 50 Geometric vs. algebraic•Algebraic was more simple (and more generic)•Geometric is more efficient–Timely tests–In particular for outside and pointing awayMIT EECS 6.837, Cutler and Durand 51 Normal•Simply Q/||Q||RrODtQnormalMIT EECS 6.837, Cutler and Durand 52 Precision•What happens when –Origin is on an object?–Grazing rays?•Problem with floating-point approximationMIT EECS 6.837, Cutler and Durand 53 The evil ε•In ray tracing, do NOT report intersection for rays starting at the surface (no false positive)–Because secondary rays–Requires epsilonsMIT EECS 6.837, Cutler and Durand 54 The evil ε: a hint of nightmare•Edges in triangle meshes–Must report intersection (otherwise not watertight)–No false negativeMIT EECS 6.837, Cutler and Durand 55 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 56 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 57 Ray//////////class Ray{//////////Ray () {}Ray (const Vec3f &dir, const Vec3f &orig){_dir =dir; _orig=orig;}Ray (const Ray& r) {*this=r;}const Vec3f &origin() {return _orig;}const Vec3f &direction() {return &dir;}Vec3f pointAtParameter(float t) {return _orig+t*_dir;}private:Vec3f _dir;Vec3f _orig;};MIT EECS 6.837, Cutler and Durand 58 Hit•Store intersection point & various information/////////class Hit{/////////float _t;Vec3f _color;//Material *_material;//Vec3f _normal;};MIT EECS 6.837, Cutler and Durand 59 Tasks•Abstract Object3D•Sphere and intersection•Scene class•Abstract camera and derive Orthographic•Main functionMIT EECS 6.837, Cutler and Durand 60 Thursday: More Ray Casting•Other primitives–Boxes–Triangles–IFS?•Antialiasing