WIXLIB

Ray Tracing BasicsCSE 681 Autumn 11Han-Wei Shen

Forward Ray Tracing We shoot a large number of photonsProblem?

Backward TracingFor every pixelConstruct a ray from the eyeFor every object in the sceneFind intersection with the rayKeep if closest

The Viewing Model Based on a simple Pinhole Camera model Simplest lens modelInverted imageSimilar trianglespin-hole camera Perfect image if holeinfinitely smallPure geometric opticsNo blurrysimplified pin-hole camera

Simplified Pinhole Camera Eye pinhole, Image plane box face (re-arrange)Eye-image pyramid (frustum)Note that the distance/size of image are arbitrary

Basic Ray Tracing Algorithmfor every pixel {cast a ray from the eyefor every object in the scenefind intersections with the raykeep it if closest}compute color at the intersection point}

Construct a Ray3D parametric linep(t) eye t (s-eye)r(t): ray equationeye: eye (camera) positions: pixel positiont: ray parametereyet 0r(t)pQuestion: How to calculate the pixel position P?

Constructing a Ray 3D parametric linep(t) e t (s-e)s*(boldface means vector) So we need to know e and sWhat are given (specified by the user or scenefile)? camera position camera direction or center of interest camera orientation orview up vector distance to image plane field of view aspect ratio pixel resolutions-ee

Given Camera Information Camera Eye Look at Orientation (up vector) Image plane Distance to plane, N Field of view in Y Aspect ration (X/Y) Screen Pixel resolutionvnuyresexresN

Construct Eye Coordinate System We can calculate the pixel positions muchmore easily if we construct an eyecoordinate system (eye space) first Known: eye position, center of interest, view-upvector To find out:new origin and three basis vectorscenter of interest (COI)eyeAssumption: the direction of view isorthogonal to the view plane (the planethat objects will be projected onto)

Eye Coordinate System Origin: eye position Three basis vectors: one is the normal vector (n) ofthe viewing plane, the other two are the ones (u andv) that span the viewing planevuCenter of interest (COI)eyen(u,v,n should be orthogonal to each other)

Eye Coordinate System Origin: eye position Three basis vectors: one is the normal vector (n) ofthe viewing plane, the other two are the ones (u andv) that span the viewing planevn is pointing away from theworld because we use righthand coordinate systemuCenter of interest (COI)eyenN eye – COIn N / N Remember u,v,n shouldbe all unit vectors(u,v,n should be orthogonal to each other)

Eye Coordinate System What about u and v?V upCOIWe can get u first -vueyenu is a vector that is perpendicularto the plane spanned byN and view up vector (V up)

Eye Coordinate System What about u and v?V upCOIWe can get u first -vueyenu is a vector that is perpendicularto the plane spanned byN and view up vector (V up)U V up x nu U / U

Eye Coordinate System What about v?V upCOIKnowing n and u, getting v iseasyvueyen

Eye Coordinate System What about v?V upCOIKnowing n and u, getting v iseasyvueyenv n xuv is already normalized

Eye Coordinate System Put it all togetherV upCOIEye space origin: (Eye.x , Eye.y, Eye.z)vueyeBasis vectors:n n u v (eye – COI) / eye – COI (V up x n) / V up x n n x u

Next Step? Determine the size of the image plane This can be derived from distance from the camera to the center ofthe image plane Vertical field of view angle Aspect ratio of the image plane Aspect ratio being Width/Height

Image Plane SetupW Tan(θv /2) H / 2d Then for a pixel s at the image pixel (i,j) , it’s location is atW H * aspect ratioC’s position e - n * dHCθvLL’s position C - u * W/2 - v * H/2Assuming the image resolution is X (horizontal) by Y(vertical), then each pixel has a width of W/X and a heightof H/YL u * i * W/X v * j * H/Yed

Put it all together We can represent the ray as a 3D parametric linep(t) e t (s-e)(now you know how to get s and e) sTypically we offset the ray by halfof the pixel width and height, i.e, cast the ray from the pixelcenterincrementing(i,j)(0,0)s-ee

Put it all together We can represent the ray as a 3D parametric linep(t) e t (s-e)(now you know how to get s and e) sTypically we offset the ray by halfof the pixel width and height, i.e, cast the ray from the pixelcenterincrementing(i,j)(0,0)s-ee

Ray-Sphere Intersection Problem: Intersect a line with a sphere A sphere with center c (xc,yc,zc) and radius R can berepresented as:2c)222(x-x (y-yc) (z-zc) - R 0 For a point p on the sphere, we can write the above invector form:2(p-c).(p-c) - R 0 (note ‘.’ is a dot product) We can plug the point on the ray p(t) e t d2(e td-c).(e td-c) - R 0 and yield22(d.d) t 2d.(e-c)t (e-c).(e-c) - R 0

Ray-Sphere Intersection When solving a quadratic equation2at bt c 0We have Discriminant and Solution

Ray-Sphere Intersectionb2 – 4ac 0 No intersectionb2 – 4ac 0 Two solutions (enter and exit)b2 – 4ac 0 One solution (ray grazes sphere) Should we use the larger or smaller t value?

Ray-Sphere Intersectionb2 – 4ac 0 No intersectionb2 – 4ac 0 Two solutions (enter and exit)b2 – 4ac 0 One solution (ray grazes sphere) Should we use the larger or smaller t value?

Calculate Normal Needed for computing lightingQ P(t) – C and remember Q/ Q CtQ

Calculate Normal Needed for computing lightingQ P(t) – C and remember Q/ Q CtQnormal

Choose the closet sphere Minimum search problemFor each pixel {form ray from eye through the pixel centertmin For each object {if (t intersect(ray, object)) {if (t tmin) {closestObject objecttmin t}}}}

Final Pixel Colorif (tmin )pixelColor background colorelsepixelColor color of object at d along raydeyerayobject

CSE 681Ray-Object Intersections:Axis-aligned Box

Ray-Box Intersection TestY y2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection TestY y2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection Test Intersect ray with each plane– Box is the union of 6 planesY y2x x1, x x2y y1, y y2z z1, z z2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection Test Intersect ray with each plane– Box is the union of 6 planesY y2x x1, x x2y y1, y y2z z1, z z2Z z2X x1 Ray/axis-aligned planeis easy:Z z1Y y1X x2

Ray-Box Intersection Test Intersect ray with each plane– Box is the union of 6 planesY y2x x1, x x2y y1, y y2z z1, z z2Z z2X x1 Ray/axis-aligned planeis easy:Z z1Y y1X x2

Ray-Box Intersection Test Intersect ray with each plane– Box is the union of 6 planesY y2x x1, x x2y y1, y y2z z1, z z2Z z2X x1 Ray/axis-aligned planeis easy:Z z1Y y1E.g., solve x component: ex tDx x1X x2

Ray-Box Intersection TestY y2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection TestY y2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersectionsY y2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersections3. Choose intersectionY y2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersections3. Choose intersectionwith the smallest t 0Y y2Z z2X x1Z z1Y y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersections3. Choose intersectionwith the smallest t 0that is within the rangeX x1Y y2Z z2Z z1Y y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersectionsY y23. Choose intersectionwith the smallest t 0Z z2that is within the rangeX x1of the boxZ z1Y y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersectionsY y23. Choose intersectionwith the smallest t 0Z z2that is within the rangeX x1of the boxZ z1Y y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersectionsY y23. Choose intersectionwith the smallest t 0Z z2that is within the rangeX x1of the boxZ z1 We can do moreY y1X x2

Ray-Box Intersection Test1. Intersect the ray with each plane2. Sort the intersectionsY y23. Choose intersectionwith the smallest t 0Z z2that is within the rangeX x1of the boxZ z1 We can do moreefficientlyY y1X x2

Only Consider 2D for Now if a point (x,y) is in the box, then (x,y) in[x1 , x2] x [y1, y2]y y1y y1x x1x x2

The Principle Assuming the ray hits the box boundary lines atintervals [txmin,txmax], [tymin,tymax], the rayhits the box if and only if the intersection of thetwo intervals is not emptytxmaxtymaxtxmintxmintymintxmaxtymaxtymin28

Pseudo Codetxmin (x1 - ex )/Dxtxmax (x2 - ex )/Dx//assume Dx 0tymin (y1 - ey )/Dytymax (y2 - ey )/Dy //assume Dy 0if (txmin tymax) or (tymin txmax)return falseelsereturn true29

Pseudo Codetxmin (x2 - ex )/Dx//if Dx 0txmax (x1 - ex )/Dxtymin (y2 - ey )/Dytymax (y1 - ey )/Dy//if Dy 0if (txmin tymax) or (tymin txmax)return falseelsereturn true306

Now Consider All Axis We will calculate t1 and t2 for each axis (x,y, and z) Update the intersection interval as wecompute t1 and t2 for each axist2 remember:t1t1 (x1- px)/Dxt2 (x2- px)/DxDpx x1 x x2

Update [tnear, tfar] Set tnear - and tfar For each axis, compute t1 and t2– make sure t1 t2– if t1 tnear, tnear t1– if t2 tfar, tfar t2t2t1 If tnear tfar, box is missedDpx x1 x x2

AlgorithmSet tnear - , tfar R(t) p t * DFor each pair of planes P associated with X, Y, and Z do: (example uses Xplanes)if direction Dx 0 thenif (px x1 or px x2)return FALSEelsebegint1 (xl - px) / Dxt2 (xh - px) / Dxif t1 t2 then swap (t1, t2)if t1 tnear then tnear t1if t2 tfar then tfar t2if tnear tfar return FALSEif tfar 0 return FALSEendReturn tnear

Special Case Ray is parallel to an axis– If Dx 0 or Dy 0 or Dz 0 px x1 or px x2 then missy y2y Y1D x X1 x X2p

Special Case Box is behind the eye– If tfar 0, box is behindDpx x1x x2

The Principle Assuming the ray hits the box boundary lines at intervals [txmin,txmax], [tymin,tymax], the ray hits the box if and only if the intersection of the two intervals is not empty 28 txmin txmax tymin tymax tymin tymax txmin txmax