Report

CS 352: Computer Graphics Chapter 4: Geometric Objects and Transformations Chapter 4 - 2 Interactive Computer Graphics Sensational Solar System Simulator Chapter 4 - 3 Interactive Computer Graphics Perspective How is it that mathematics can model the (ideal) world so well? Chapter 4 - 4 Interactive Computer Graphics Overview Scalars and Vectors Coordinates and frames Homogeneous coordinates Rotation, translation, and scaling Concatenating transformations Transformations in Canvas Projections A virtual trackball Chapter 4 - 5 Interactive Computer Graphics Background: linear algebra Quick review of important concepts Point: location (x, y) or (x, y, z) Vector: direction and magnitude <x, y, z> Chapter 4 - 6 Interactive Computer Graphics Vectors Magnitude of a vector: |v| ^ Direction of a vector, unit vector: v Affine sum: P = (1-a) Q + a R Chapter 4 - 7 Interactive Computer Graphics Dot Product Def: u • v = ux vx + uy vy+ uz vz u • v = |u| |v| cos θ Uses: Angle between two vectors? Are two vectors perpendicular? Do two vectors form acute or obtuse angle? Is a face visible? (backface culling) Chapter 4 - 8 Interactive Computer Graphics Cross Product u v = <uyvz - uzvy, uzvx - uxvz, uxvy - uyvx> Direction: normal to plane containing u, v (using right-hand rule in right-handed coordinate system) Magnitude: |u||v| sin θ Uses: Angle between vectors? Face outward normal? Chapter 4 - 9 Interactive Computer Graphics Face outward normals Why might I need face normals? How to find the outward normal of a face? Assume that vertices are listed in a standard order when viewed from the outside -- counterclockwise Cross product of the first two edges is outward normal vector Note that first corner must be convex Chapter 4 - 10 Interactive Computer Graphics Ouch! How can I tell if I have run into a wall? Walls, motion segments, intersection tests How to tell if two line segments (p1, p2) and (p3, p4) intersect? Looking from p1 to p2, check that p3 and p4 are on opposite sides Looking from p3 to p4, check that p1 and p2 are on opposite sides Chapter 4 - 11 Interactive Computer Graphics Sensational Solar System Simulator How do you get the earth to go around the sun? How do you get the moon to do that fancy motion? Chapter 4 - 12 Interactive Computer Graphics Coordinate systems and frames A graphics program uses many coordinate systems, e.g. model, world, screen Frame: origin + basis vectors (axes) Need to transform between frames Chapter 4 - 13 Interactive Computer Graphics Transformations Changes in coordinate systems usually involve Translation Rotation Scale 3-D Rotation and scale can be represented as 3x3 matrices, but not translation We're also interested in a 3-D to 2-D projection We use 3-D "homogeneous coordinates" with four components per point For 2-D, can use homogeneous coords with three components Chapter 4 - 14 Interactive Computer Graphics Homogeneous Coordinates A point: (x, y, z, w) where w is a "scale factor" Converting a 3D point to homogeneous coordinates: (x, y, z) (x, y, z, 1) Transforming back to 3-space: divide by w (x, y, z, w) (x/w, y/w, z/w) (3, 2, 1): same as Where is the point (3, 2, 1, 0)? (3, 2, 1, 1) = (6, 4, 2, 2) = (1.5, 1, 0.5, 0.5) Point at infinity or "pure direction." Used for vectors (vs. points) Chapter 4 - 15 Interactive Computer Graphics Homogeneous transformations Most important reason for using homogeneous coordinates: All affine transformations (line-preserving: translation, rotation, scale, perspective, skew) can be represented as a matrix multiplication You can concatenate several such transformations by multiplying the matrices together. Just as fast as a single transform! Modern graphics cards implement homogeneous transformations in hardware (or used to) Chapter 4 - 16 Interactive Computer Graphics Translation é x'ù é1 ê ú ê y' 0 ê ú=ê êz' ú ê0 ê ú ê ë1 û ë0 0 0 dx ù é x ù úê ú 1 0 dy ú ê y ú 0 1 dz ú ê z ú úê ú 0 0 1 ûë1 û Chapter 4 - 17 Interactive Computer Graphics Scaling é x'ù ésx ê ú ê y' 0 ê ú=ê êz' ú ê 0 ê ú ê ë1 û ë 0 0 sy 0 0 0 0 sz 0 0ùé x ù úê ú 0úê y ú 0úê x ú úê ú 1û ë1 û Note that the scaling fixed point is the origin Chapter 4 - 18 Interactive Computer Graphics Rotation 0 1 0 cos 0 sin 0 0 General rotation: about an axis v by angle u with fixed point p With origin as fixed point, about x, y, or z-axis: 0 sin cos 0 0 0 0 1 cos 0 sin 0 0 sin 1 0 0 cos 0 0 0 0 0 1 cos sin 0 0 sin cos 0 0 0 0 1 0 0 0 0 1 Chapter 4 - 19 Interactive Computer Graphics Rotating about another point How can I rotate around another fixed point, e.g. [1, 2, 3]? Translate [1, 2, 3] -> 0, 0, 0 (T) Rotate (R) Translate back (T-1) T-1 R T P = P' Chapter 4 - 20 Interactive Computer Graphics Rotating about another axis How can I rotate about an arbitrary axis? Can combine rotations about z, y, and x: Rx Ry Rz P = P' Note that order matters and angles can be hard to find Chapter 4 - 21 Interactive Computer Graphics Concatenating transformations Many transformations can be concatenated into one matrix for efficiency Canvas: transformations concatenate Set the transformation to the identity to reset Or, push/pop matrices (save/restore state) Chapter 4 - 22 Interactive Computer Graphics Example: Orbiting the Sun How to make the earth move 5 degrees? How to animate a continuous rotation? Set appropriate modeling matrix before drawing image Rotate 5 degrees, then translate What Canvas code to use? Every few ms, modify modeling matrix and redisplay Reset to original and concatenate rotation and translation How to make it spin on its own axis too? rotate, translate, rotate, draw Chapter 4 - 23 Interactive Computer Graphics Earth & Moon solar.cx.save(); solar.cx.rotate(timefrac/365); solar.cx.translate(250,0); solar.cx.save(); solar.cx.rotate(timefrac); // earth around the sun solar.cx.drawImage(earth, -earth.width/2, –earth.height/2); solar.cx.restore(); solar.cx.save(); // moon around earth solar.cx.rotate(timefrac/28); solar.cx.translate(56, 0); solar.cx.drawImage(moon, -moon.width/2, -moon.height/2); solar.cx.restore(); Chapter 4 - 24 Interactive Computer Graphics Moon River, wider than a mile… How to make the moon follow that crazy path? Try it… Chapter 4 - 25 Interactive Computer Graphics Project 4: Wonderfully Wiggly Working Widget Write a program to animate something that has moving parts that have moving parts Use both translation and rotation It should save/restore state Examples: Walking robot Person pedaling a unicycle Person waving in a moving convertible Spirograph Chapter 4 - 26 Interactive Computer Graphics Accelerometer events Many browsers now support the DeviceOrientation API (W3C draft) [demo] window.ondevicemotion = function(event) { var accelerationX = event.accelerationIncludingGravity.x var accelerationY = event.accelerationIncludingGravity.y var accelerationZ = event.accelerationIncludingGravity.z } Chapter 4 - 27 Interactive Computer Graphics 3D: Polgyons and stuff Chapter 4 - 28 Interactive Computer Graphics How to display a complex object? You don't want to put all those teapot triangles in your source code… Chapter 4 - 29 Interactive Computer Graphics A JSON object format Object description with vertex positions and faces { "vertices" : [ 40,40,40, 60,0,60, 20,0,60, 40,0,20], "indices" : [ 0,1,2, 0,2,3, 0,3,1, 1,3,2] } ________________________________ x = data.vertices[0]; Chapter 4 - 30 Interactive Computer Graphics Loading an object via AJAX What do you think of this code? trackball.load = function() { var objectURL = $('#object1').val(); $.getJSON(objectURL, function(data) { trackball.loadObject(data); }); trackball.display(); } Remember the first 'A' in AJAX! Wait for the object to load before displaying it $.getJSON(objectURL, function(data) { trackball.loadObject(data); trackball.display(); }); Chapter 4 - 31 Interactive Computer Graphics Question How to move object into the sphere centered at the origin with radius 1? Chapter 4 - 32 Interactive Computer Graphics Point normalization Find min and max values of X, Y, Z Find center point, Xc, Yc, Zc Translate center to origin (T) Scale (S) P' = S T P Modeling matrix M = S T Note apparent reversed order of matrices Chapter 4 - 33 Interactive Computer Graphics Question How to draw a 3-D object on a 2-D screen? Chapter 4 - 34 Interactive Computer Graphics Orthographic projection Zeroing the z coordinate with a matrix multiplication is easy… x 1 y 0 0 0 1 0 0 1 0 0 0 0 0 0 0 x 0 y 0 z 1 1 Or, just ignore the Z value when drawing Chapter 4 - 35 Interactive Computer Graphics Perspective projection Can also be done with a single matrix multiply using homogeneous coordinates Uses the divide-by-w step We'll see in next chapter Chapter 4 - 36 Interactive Computer Graphics Transformations in the Pipeline Three coordinate frames: World coordinates (e.g. unit cube) Eye (projection) coordinates (from viewpoint) Window coordinates (after projection) Two transformations convert between them Modeling xform * world coords -> eye coords Projection xform * eye coords -> window coords Chapter 4 - 37 Interactive Computer Graphics Transformations in Canvas Maintain separate 3-D model and project matrices Multiply vertices by these matrices before drawing polygons Vertices are transformed as they flow through the pipeline Chapter 4 - 38 Interactive Computer Graphics Transformations 2 If p is a vertex, pipeline produces Cp (postmultiplication only) Can concatenate transforms in CTM: CI C T(4, 5, 6) C R(45, 1, 2, 3) C T(-4, -5, -6) [C = T-1 S T] Note that last transform defined is first applied Chapter 4 - 39 Interactive Computer Graphics Putting it all together Load vertices and faces of object. Normalize: put them in (-1, 1, -1, 1, -1, 1) cube Put primitives into a display list Set up viewing transform to display that cube Set modeling transform to identity To spin the object, every 1/60 second do: Add 5 degrees to current rotation amount Set up modeling transform to rotate by current amount Chapter 4 - 40 Interactive Computer Graphics Virtual Trackball Imagine a trackball embedded in the screen If I click on the screen, what point on the trackball am I touching? Chapter 4 - 41 Interactive Computer Graphics Trackball Rotation Axis If I move the mouse from p1 to p2, what rotation does that correspond to? Chapter 4 - 42 Interactive Computer Graphics Virtual Trackball Rotations Rotation about the axis n = p1 x p2 Fixed point: if you use the [-1, 1] cube, it is the origin Angle of rotation: use cross product |u v| = |u||v| sin θ (or use Sylvester's built-in function) n = p1.cross(p2); theta = p1.angleFrom(p2); modelMat = oldModelMat.multiply(1); // restore old matrix modelMat = Matrix.Rotation(theta,n).multiply(modelMat); Chapter 2 - 43 Interactive Computer Graphics Hidden surface removal What's wrong with this picture? How can we prevent hidden surfaces from being displayed? Chapter 2 - 44 Interactive Computer Graphics Hidden surface removal How can we prevent hidden surfaces from being displayed? Painter's algorithm: paint from back to front. How can we do this by computer, when polygons come in arbitrary order? Chapter 4 - 45 Interactive Computer Graphics Poor-man's HSR Transform points for current viewpoint Sort back to front by the face's average Z Does this always work? Chapter 2 - 46 Interactive Computer Graphics HSR Example Which polygon should be drawn first? We'll study other algorithms later Chapter 4 - 47 Interactive Computer Graphics A better HSR algorithm Depth buffer algorithm Chapter 4 - 48 Interactive Computer Graphics Data structures needed An array of vertices, oldVertices An array of normalized vertices, vertices[n][3], in the [-1, 1] cube An array for vertices in world coordinates An array of faces containing vertex indexes, int faces[n][max_sides]. Use faces[n][0] to store the number of sides. Set max_sides to 12 or so. Chapter 4 - 49 Interactive Computer Graphics Virtual Trackball Program Stage 1 Read in, normalize object Display with rotation, HSR Stage 2 Virtual trackball rotations Perspective Lighting/shading