1!CS 431/636 !Advanced Rendering Techniques"Dr. David Breen"Korman 105D"Wednesday 6PM → 8:50PM"Presentation 2"4/11/12"Start Up"n Any questions from last time?"n Go over sampling image plane?"n Or intersection algorithms?"Slide Credits"n Leonard McMillan, Seth Teller, Fredo Durand, Barb Cutler - MIT"n G. Drew Kessler, Larry Hodges - Georgia Institute of Technology"n John Hart - University of Illinois"n Rick Parent - Ohio State University"More Geometry & Intersections Ray/Plane Intersection"Ray is defined by R(t) = Ro + Rd*t where t ≥ 0""Ro = Origin of ray at (xo, yo, zo)""Rd = Direction of ray [xd, yd, zd] (unit vector)""Plane is defined by [A, B, C, D]""Ax + By + Cz + D = 0 for a point in the plane""Normal Vector, N = [A, B, C] (unit vector)""A2 + B2 + C2 = 1""D = - N • P0 (P0 - point in plane)"Ray/Plane (cont.)"Substitute the ray equation into the plane equation:"A(xo + xdt) + B(yo + ydt) + C(zo +zdt) + D = 0""Solve for t:"t = -(Axo + Byo + Czo + D) / (Axd + Byd + Czd)"t = -(N • Ro - N • P0 ) / (N • Rd)""2!What Can Happen?" N • Rd = 0!N • Rd > 0!t < 0!Ro!t > 0!Ro!Ray/Plane Summary"Intersection point:"(xi, yi, zi) = (xo + xdti, yo + ydti, zo + zdti)"""1. Calculate N • Rd and compare it to zero."2. Calculate ti and compare it to zero."3. Compute intersection point."4. Flip normal if N • Rd is positive"Ray-Parallelepiped Intersection"n Axis-aligned n From (X1, Y1, Z1) to (X2, Y2, Z2) n Ray P(t)=Ro+Rdt y=Y2 y=Y1 x=X1 x=X2 Ro Rd Naïve ray-box Intersection"n Use 6 plane equations n Compute all 6 intersection n Check that points are inside box Ax+By+Cz+D ≤ 0 y=Y2 y=Y1 x=X1 x=X2 Ro Rd Factoring out computation"n Pairs of planes have the same normal n Normals have only one non-0 component n Do computations one dimension at a time n Maintain tnear and tfar (closest and farthest so far) y=Y2 y=Y1 x=X1 x=X2 Ro Rd Test if parallel"n If Rdx = 0, then ray is parallel n If Rox < X1 or Rox > x2 return false y=Y2 y=Y1 x=X1 x=X2 Ro Rd3!If not parallel"n Calculate intersection distance t1 and t2"n t1 = (X1-Rox)/Rdx"n t2 = (X2-Rox)/Rdx"y=Y2 y=Y1 x=X1 x=X2 Ro Rd t1 t2 Test 1"n Maintain tnear and tfar "n If t1 > t2, swap"n if t1 > tnear, tnear = t1 "n if t2 < tfar, tfar = t2"n If tnear > tfar, box is missed"y=Y2 y=Y1 x=X1 x=X2 Ro Rd t1x t2x tnear t1y t2y tfar tfar Test 2"n If tfar < 0, box is behind"y=Y2 y=Y1 x=X1 x=X2 Ro Rd t1x t2x tfar Algorithm recap"n Do for all 3 axes"n Calculate intersection distance t1 and t2"n Maintain tnear and tfar"n If tnear > tfar, box is missed; Done"n If tfar < 0, box is behind; Done"n If box survived tests, return intersection at tnear"n If tnear is negative, return tfar "y=Y2 y=Y1 x=X1 x=X2 Ro Rd tnear t1y tfar Ray/Ellipsoid Intersection Ray/Cylinder Intersection "Ellipsoid's surface is defined by the set of points {(xs, ys, zs)} satisfying the equation:""(xs/ a)2 + (ys/ b)2 + (zs/ c)2 - 1 = 0""Cylinder's surface is defined by the set of points {(xs, ys, zs)} satisfying the equation:""(xs)2 + (ys)2 - r2 = 0 " "-z0 ≤ zs ≤ z0""Centers at origin""§ Substitute ray equation into surface equations"§ This is a quadratic equation in t:"§ At2 + Bt + C = 0"§ Analyze as before"§ Solve for t with quadratic formula"§ Plug t back into ray equation - Done"§ Well,… not exactly"Ray/Ellipsoid Intersection Ray/Cylinder Intersection "4!Ray/Cylinder Intersection "§ Is intersection point Pi between -Z0 and Z0?"§ If not, Pi is not valid"§ Also need to do intersection test with z = -Z0 , Z0 plane"§ If (Pix)2 + (Piy)2 ≤ r2, youʼve intersected a “cap”"§ Which valid intersection is closer?"Superquadrics"! xa1" # $ % & ' 2(2+ya2" # $ % & ' 2(2) * + + , - . . (2(1+za3" # $ % & ' 2(1= 1Bezier Patch"n Patch of order (n, m) can be defined in terms of a set of (n + 1)(m + 1) control points Pi+1,j+1 for integer indices i = 0 to n, j = 0 to m."! (u,v) " [0,1]2p(u,v) =i= 0n#Bin(u)Bjm(v)j= 0m#Pi+1, j +1Bin(u) =ni$ % & ' ( ) ui(1* u)n*iTesselate Patches and Superquadrics"Tesselate Patches and Superquadrics"5!Utah Teapot"n Modeled by 32 Bézier Patches"n Control points available at http://www.holmes3d.net/graphics/teapot"SMF Triangle Meshes"v -1 -1 -1 v 1 -1 -1 v -1 1 -1 v 1 1 -1 v -1 -1 1 v 1 -1 1 v -1 1 1 v 1 1 1 f 1 3 4 f 1 4 2 f 5 6 8 f 5 8 7 f 1 2 6 f 1 6 5 f 3 7 8 f 3 8 4 f 1 5 7 f 1 7 3 f 2 4 8 f 2 8 6 vertices triangles Draw data structure!Triangle Meshes (.iv)"Transformations & Hierarchical Models n Add an extra dimension"• in 2D, we use 3 x 3 matrices"• In 3D, we use 4 x 4 matrices"n Each point has an extra value, w"Homogeneous Coordinates"x' y' z' w' =x y z w a e i m b f j n c g k o d h l p p' = M p n Most of the time w = 1, and we can ignore it"Homogeneous Coordinates"x' y' z' 1 =x y z 1 a e i 0 b f j 0 c g k 0 d h l 16!Translate (tx, ty, tz)"n Why bother with the !extra dimension?!Because now translations !can be encoded in the matrix!"Translate(c,0,0) xypp' c x' y' z' 1 = x y z 1 1 0 0 0 0 1 0 0 0 0 1 0 tx ty tz 1 x' y' z' Scale (sx, sy, sz)"n Isotropic (uniform) !scaling: sx = sy = sz!n You only have to implement uniform scaling!x' y' z' 1 = x y z 1 sx 0 0 0 0 sy 0 0 0 0 sz 0 0 0 0 1 Scale(s,s,s) xpp' qq' yRotation"n About z axis"x' y' z' 1 = x y z 1 cos φ sin φ 0 0 -sin φ cos φ 0 0 0 0 1 0 0 0 0 1 ZRotate(φ) xyz pp' θ Rotation"n About !x axis:"n About !y axis:"x' y' z' 1 =x y z 1 0 cos α sin α 0 0 -sin α cos α 0 1 0 0 0 0 0 0 1 x' y' z' 1 =x y z 1 cos θ 0 -sin θ 0 sin θ 0 cos θ 0 0 1 0 0 0 0 0 1 Rotation"n About (kx, ky, kz), an " arbitrary unit vector " (Rodrigues Formula)"x' y' z' 1 = x y z 1 kxkx(1-c)+c kykx(1-c)+kzs kzkx(1-c)-kys 0 0 0 0 1 kykx(1-c)-kzs kyky(1-c)+c kzky(1-c)+kxs 0 kxkz(1-c)+kys kykz(1-c)-kxs kzkz(1-c)+c 0 where c = cos θ & s = sin θ Rotate(k, θ) xyz θ k How are transforms combined?"(0,0) (1,1) (2,2) (0,0) (5,3) (3,1) Scale(2,2) Translate(3,1) TS = 2 0 0 2 0 0 1 0 0 1 3 1 2 0 0 2 …