Home

"user manual"

1. position weight normal primary color Programmer responsible for loading data into them Vertex attribute registers are read only Only one v register per instruction e 15 vertex result registers o HPOS Homogeneous clip space position o COLO Primary colour o TEX0 Texture coordinate set 0 Vertex result registers are write only Vertex program must write to o HPOS NVIDIA Vertex Shader Assembly e 12 temporary registers RO R11 Read write e AO x is the address register Write only Used to access constant registers e 96 constant registers c 0 c 95 May also address as c A0 x Read only to normal program Read write to vertex state program Only one constant register per instruction e 17 assembly instructions Operate on scalar s or 4 component register Result is for single register Either 4 component or replicated scalar Opcode Inputs Output Operations MOV yv v move Examples ADD v v v add RSQ S SSSS reciprocal square root DP4 Vv SSss 4 component dot product Scalar input must have modifier x y z or w Swizzle xxyy wzyx etc e Generate id load compile vertex program etc glGenProgramsNV glLoadProgramN V e Web pages http developer nvidia com docs 10 1239 ATT VertexPrograms pdf http www nvidia com dev_content nvopenglspecs GL_NV_vertex_program txt http www nvidia com dev_content nvopenglspecs GL_NV_ve
2. vie Uly 07 U2z U2y o Uza U3y 1 relative to Standard Frame Question What are coordinates of these basis elements relative to F e Frames are usually orthonormal e A point mapped by a change of basis does not change We have merely expressed its coordinates relative to a different frame Readings Watt 1 1 1 Hearn and Baker Section 5 5 not as general as here though Red book 5 9 White book 5 8 Ambiguity 6 7 41 6 8 Ambiguity Ambiguity Three Types of Transformations 1 T At B between two spaces 2 T A gt A warp an object within its own space 3 T change of coordinates Changes of Coordinates e Given 2 frames Fi v1 v2 O orthonormal F 201 202 O orthogonal e Suppose y Fi 1 OE e Then v Fs 1 2 1 2 0 Question What is the length of v Suppose we have P p1 p2 1 and Q m q2 1 e P Q relative to F 01 02 0 e We are given a matrix representation of a transformation T 2 0 0 Mr 0 1 0 0 0 1 e Consider P TP and Q TQ e How do we interpret P and Q How do we interpret P and Q 1 Change of Coordinates v2 v2 i P O vi E O 2 Scale 3D Transformations 6 8 42 3 Transformations between spaces Do we care YES e In 1 nothing changes except the representation 1 3 3 e In 3 we ve completely changed spaces e In distances are preserved while they change
3. inl 0 cost 0 0 0 0 1 5 Rotate d onto the xy plane using R ReO w 23 y 0 6 Compute cos y and sin w where w is the angle of E with the z axis Va 22 yal y 22 V T2 22 y AI ara cos 1 7 Use cos w and sin w to create R 4 cos w sin 4 sin p cos 4 0 oo oO oo ROoo 8 Rotate onto the x axis using R y 9 Rotate about the z axis by 6 Ry 0 10 Reverse z axis rotation Rz w 11 Reverse y axis rotation R The overall transformation is RO a Ry o R w o Ry 0 o Re 4 o Ry 10 3 3D Rotation User Interfaces 3D Rotation User Interfaces Goal Want to specify angle axis rotation directly Problem May only have mouse which only has two degrees of freedom The Virtual Sphere 10 3 73 Solutions Virtual Sphere Arcball pe Virtual Sphere Arcball Comparison 10 4 The Virtual Sphere The Virtual Sphere 1 Define portion of screen to be projection of virtual sphere 2 Get two sequential samples of mouse position S and T 3 Map 2D point S to 3D unit vector p on sphere 4 Map 2D vector ST to 3D tangental velocity d 5 Normalize d gt 6 Axis px d 7 Angle 6 a St Choose a so a 180 rotation can be obtained 8 Save T to use as S for next time Polygons 10 74 11 POLYGONS 75 11 Polygons 11 1 Polygons Introduction Polygons
4. store normalized light vector will be lifted to host ShVector3f light normalize LightVec calculate half angle vector ShVector3f eye 0 0 0 0 1 0 ShVector3f half normalize light eye calculate diffuse component ShAttribif diffuse normal light calculate specular component ShAttribif specular normal half specular pow specular spec_power combine diffuse and specular contributions and output final vertex color Color0 diffuse diffuseMaterial specular specularMaterial SH_END load it into vertex shader shBind vs 19 RAY TRACING 123 19 Ray Tracing 19 1 Fundamentals Ray Tracing Photorealism The Holy Grail e Want to make more realistic images Shadows Reflections e What happens in the real world Problem Many rays never reach the eye e Idea Trace rays backwards Ray Tracing Basic Code foreach pixel ray eye pixel eye Intersect Scene ray end Issues Which pixels e How do we perform intersections e How do we perform shading e How can we speed things up e How can we make things look better Ray Tracing Casting Selecting the initial ray e Setting eyepoint virtual screen an array of virtual pixels and scene are organized in convenient coordinate frames e g all in view or world frames Intersection Computations 19 1 124 e Ray a half line determined by the eyepoint and a point associated with a chos
5. 2 e The Wavelet Transform wavelet decomposition maps from 9 7 3 5 to 6 2 1 1 i e the final scale and all the details The process is called a Filter Bank No data is gained or loss we just have a different representation In general we expect many detail coefficients to be small Truncating these to 0 gives us a lossy compression technique e Basis function for wavelets are called scaling functions For Haar can use hi x 21 i where p 1 1 for 0 lt x lt 1 and 0 otherwise Hes el L JL SL Support of a function refers to the region over which the function is non zero Note that the above basis functions have compact support meaning they are non zero over a finite region e The Haar Wavelets are 11 x 2 i where 1 fr 0 lt zx lt 1 2 v x 4 1 for 1 2 lt xr lt 1 0 otherwise Wavelets 27 8 207 e Example again Originally w r t V I x 969 1 701 2 363 1 503 z Rewriting w r t V and W I x 895 2 401 2 ldo x Dut x Rewriting the Hs in terms of V W I x 6 9 x 209 a 199 1 1 2 9ox Pl sl Lo 6x TI IL 4x_ 2x SzI l ixi x 3x Ix oT Non Haar Wavelets e Haar is simple but doesn t have certain properties e Non Haar wavelets possible e Example Daubechies wavelet starts from The function is not as smooth as it looks Non Photorealistic Rendering 27 208
6. Tee a e i5 oe ss A u4 we3 v3 i4 Oo A 11 2 79 Case 4 Readings Watt 6 1 Hearn and Baker Section 6 8 Red book 3 11 White book 3 14 11 3 Polygon Scan Conversion Scan Conversion e Once mapped to device coordinates want to scan convert polygon e Scan converting a general polygon is complicated e Here we will look at scan conversion of a triangle e Look at y value of vertices Split triangle along horizontal line at middle y value Dos and Don ts 11 3 80 C CO 20 L t A B KS scan later e Step along L1 and L2 together along the scan lines from A to C and from B to C respectively e Scan convert each horizontal line Code for triangle scan conversion e Assume that triangle has been split and that A B C are in device coordinates that A x lt B x and that Ay By 4 Cy y A y dO C x A x C y A y di C x B x C y B y xO A x xi B x while y lt C y do for x x0 to x1 do WritePixel x y end x0 d0 x1 dl ytt end e This is a floating point algorithm Readings Watt 6 4 Hearn and Baker Chapter 3 11 Red book 3 5 more general than above White book 3 6 more general than above 11 4 Dos and Don ts When modelling with polygonal objects remember the following guidelines e Model Solid Objects No facades It s easier to write other software if we can assume polygon faces are oriented e No T ve
7. glPushName 2 Draw2 stack 2 glPopName wrap up stuff here e What you get back If you click on Item 1 hits 1 buffer 1 min z1 max z1 1 If you click on Items 1 1 1 and 1 2 hits 2 buffer 3 min z111 max z111 1 1 1 2 min z12 max z12 1 2 If you click on Items 1 1 2 1 2 and 2 hits 3 buffer 3 min z112 max z112 1 1 2 2 min z12 max z12 1 2 1 min z2 max z2 2 e Important Details 14 99 Make sure that projection matrix is saved with a glPushMatrix and restored with a glPopMatrix glRenderMode GL_RENDER returns negative if buffer not big enough When a hit occurs a flag is set Entry to name stack only made at next gl Name s or glRenderMode call So each draw block can only generate at most one hit Colour and the Human Visual System 14 100 15 COLOUR AND THE HUMAN VISUAL SYSTEM 101 15 Colour and the Human Visual System 15 1 Colour Introduction to Colour Light sources emit intensity I A assigns intensity to each wavelength of light Humans perceive J A as a colour navy blue light green etc Experiments show that there are distinct J perceived as the same colour metamers Normal human retina have three types of colour receptors which respond most strongly to short medium or long wavelengths Sensitivity diagram Note the low response to blue One theory is that sensitivity to blue is recently evolved
8. gluPickMatrix x y w h viewport glMatrixMode GL_MODELVIEW ViewMatrix glLoadName 1 Drawi glLoadName 2 Draw2 glMatrixMode GL_PROJECTION glPopMatrix glMatrixMode GL_MODELVIEW hits glRenderMode GL_RENDER e Hits stored consecutively in array e In general if h is the number of hits the following is returned hits h h hit records each with four parts 1 The number of items q on the name stack at the time of the hit 1 int 2 The minimum z value among the primitives hit 1 int 3 The maximum z value among the primitives hit 1 int 4 The contents of the hit stack deepest element first q ints e At most one hit between each call glRenderMode or a change to name stack e In our example you get back the following If you click on Item 1 only hits 1 buffer 1 min z1 max z1 1 If you click on Item 2 only hits 1 buffer 1 min z2 max z2 2 If you click over both Item 1 and Item 2 hits 2 buffer 1 min z1 max z1 1 1 min z2 max z2 2 e More complex example Colour and the Human Visual System initialization stuff goes here glPushName 1 Drawi stack 1 glPushName 1 Draw1_10 stack 1 1 glPushName 1 Draw1_1_10 stack 1 1 1 glPopName glPushName 2 Draw1_1_20 stack 1 1 2 glPopName glPopName glPushName 2 stack 1 2 Draw1i_2 glPopName glPopName
9. Different animals have different number of wavelengths that they are sensitive to Dogs 1 Primates 2 or 3 Pigeon 4 Birds up to 18 hummingbird Different Regions of the eye are designed for different purposes Center fine grain colour vision Sides night vision and motion detection Tri Stimulus Colour Theory Tri stimulus Colour Theory models visual system as a linear map V A C where is a continuous function of wavelength C is a three dimensional vector space colour space V I A mm s7 where oe J sora where L M and S are weight functions Reflection and Light Source Models 15 102 Colour Systems e RGB Red Green Blue Additive Prism to RBG CMY wheel e CMY Cyan Magenta Yellow Subtractive complement of RGB Additive colour scheme Often add K blacK to get better black e HSV Hue Saturation Value Cone shaped colour space HSV colour cone Also HSL double cone e CIE XYZ Colour by committee More complete colour space Also L u v and L a b e YIQ Y Luminance CIE Y IQ encode colour Backwards compatible with black and white TV only show Y 16 REFLECTION AND LIGHT SOURCE MODELS 103 16 Reflection and Light Source Models 16 1 Goals Lighting e What we want Given a point on a surface visible to the viewer through a pixel what colour should we assign to the pixel e Goals Smoothly shade objects in scene Wa
10. Scene Scene q MCS an VCS WCS Projection EA Rasterization ggg re a Et NDCS 30 Image DCS or SCS e Each stage refines the scene converting primitives in modelling space to primitives in device space where they are converted to pixels rasterized e A number of coordinate systems are used MCS Modelling Coordinate System WCS World Coordinate System VCS Viewer Coordinate System NDCS Normalized Device Coordinate System DCS or SCS Device Coordinate System or equivalently the Screen Coordinate System Keeping these straight is the key to understanding a rendering system e Transformation between two coordinate systems represented with matrix e Derived information may be added lighting and shading and primitives may be removed hidden surface removal or modified clipping Primitives 2 2 14 Readings Readings Watt Chapter 5 introduction 5 1 Hearn and Baker Section 6 1 but they give a more detailed version than used here Red book 6 1 6 6 intro White book 8 3 Blinn 16 2 3 Primitives e Models are composed of converted to geometric primitives Typical rendering primitives directly supported in hardware Points single pixels Line Segments Polygons perhaps only convex polygons or triangles Modelling primitives also include Piecewise polynomial spline curves Piecewise polynomial spline surfaces Impli
11. While splines can easily support continuity control velocity control is more difficult Motion Path Spline Interpolation Problems Spline position interpolation gives continuity control over changes position but e Visually notice discontinuities in 2nd derivative need C splines degree 4 e Equal increment in spline parameter does not correspond to equal increment in distance along the spline e Different segments of the spline with the same parametric length can have different physical lengths e If we parameterize the spline directly with time objects will move at a non uniform speed Orientation and Interpolation 29 5 221 Arc Length Parameterization 1 Given spline path P u x u y u z u compute arclength of spline as a function of u s A u 2 Find the inverse of A u u A7 s 3 Substitute u A7 s into P u to find a motion path parameterized by arclength s P s P A 8s Note that u and thus s should be global parameters extending across all segments of the original spline Velocity Control To control velocity along a spline motion path e Let s f t specify distance along the spline as a function of time t e The function f t being just a scalar value can be supported with a functional animation technique i e another spline e The function f t may be specifed as the integral of yet another function v t df t dt the velocity Integral of a spline function can be foun
12. dt gt dt Po Ze dy t a dt dt dt Initial conditions user supplies initial positions of all masses and velocities The user supplies external forces gravity collision forces keyframed forces wind hydrody namic resistance etc as a function of time Simulation Factor second order ODE into two coupled first order ODE s vxi t Vyi t Uzi t dx t dy t dz t d ate d TEN Ae dvyi t aol y dt dt gt dt pato RO FO Mi Human Motion 29 11 232 Solve using your favourite ODE solver The simplest technique is the Euler step Pick a At Then compute the values of all positions at t At from the positions at t by dis cretizing the differential equations attan Loa RO RO Dlt At v t a t At P t At PO U0At 29 12 Human Motion Walking Modeling walking is hard e Human motion walking is extremely complex Fine grained balancing act e Human walking involves more than just the feet and legs Hips body shoulder head e Human perception of walking is very precise Poor walking immediately spotted e Task is still an area of active research We will look at some basics Walk Cycle e Walking is mostly a cycle of motions Have to adapt each time through cycle for terrain etc e In walking at least one foot on ground e Left stance right swing right stance left swing NA A left heel strike right heel strike left h
13. zier Splines 27 2 188 Non negativity B t gt 0 for t 0 1 Proof 0 gt gt Ofr0 lt t lt 1 gt Ofr0 lt t lt 1 Many other nice properties 27 3 B zier Splines Bezier Curves Definition A degree n order n 1 B zier curve segment is P t Y PB 1 0 where the P are k dimensional control points Examples RA XX NV Convex Hull No BP t 1 BE gt 0 for te 0 1 gt P t is a convex combination of the P for t 0 1 gt P t lies within convex hull of P for t 0 1 Affine Invariance e A B zier curve is an affine combination of its control points B zier Splines 27 2 189 e Any affine transformation of a curve is the curve of the transformed control points n n ic E neto YT Pi Bit i 0 i 0 e This property does not hold for projective transformations Interpolation B0 1 BE ob 1 B t gt 0 for t 0 1 B 0 0 ifi 0 BP 1 0ififn P P PS Ph Derivatives 4 BP t n BI t Bit gt P 0 n P Po P 1 MPa Pa 1 Smoothly Joined Segments Ct Let P 1 Pn be the last two control points of one segment Let Qo Q be the first two control points of the next segment Pa Qo Pa Pn 1 Qi Qo Smoothly Joined Segments Gt Pr Qo EPa Rid B Q1 Qo for some B gt 0 Spline Continuity Recurrence Subdivision Bt 1 BP tB t gt de Casteljau s algorithm P t PO P
14. B3 r t B3 r t B3 r t r3 3r7t 3rt t Surfaces Barycentric Blends on Triangles e Formulas P r s t y Pigi BE r 8 1 i j k n i gt 0 j gt 0 k gt 0 is BR r s t are Triangular deCasteljau e Join adjacently indexed P by triangles e Find r s t barycentric point in each triangle Subdivision Surfaces 27 7 201 e Join adjacent points by triangles e Repeat Final point is the surface point P r s t Final triangle is tangent to the surface at P r s t Properties e Each boundary curve is a B zier curve e Patches will be joined smoothly if pairs of boundary triangles are affine images of domain triangles Problems e Continuity between two patches is easy but joining n patches at a corner is hard e In general joining things together with either tensor product or triangular patches is hard Subdivision Surfaces 27 7 202 27 8 Subdivision Surfaces Introduction Hard to piece spline surfaces together Hard to fit splines to arbitrary mesh n sides faces n vertex neighbours Subdivision is an alternative surfacing scheme Fits surface to arbitrary mesh Only a few gotcha s Will look at two simple subdivision schemes Both schemes are simple to implement Neither scheme is one of choice This material is from Chapter 7 of Warren Weimer Subdivision Methods for Geometric Design Polyhedron Start with a description of a polyhedron List of vertice
15. Can use some of the ideas in Liang Barsky to clip points Parametric representation of line L t 1 t A tB or equivalently E t A t B A e Aand B are non coincident points For t R L t defines an infinite line For t 0 1 L t defines a line segment from A to B Good for generating points on a line Not so good for testing if a given point is on a line Implicit representation of line amp Q Q P a e P is a point on the line e 7 is a vector perpendicular to the line L Q gives us the signed distance from any point Q to the line The sign of Q tells us if Q is on the left or right of the line relative to the direction of If Q is zero then Q is on the line Use same form for the implicit representation of a halfspace Clipping Clipping a point to a halfspace e Represent window edge as implicit line halfspace e Use the implicit form of edge to classify a point Q e Must choose a convention for the normal points to the inside e Check the sign of Q If Q gt 0 then Q is inside Otherwise clip discard Q It is on the edge or outside May want to keep things on the boundary Clipping a line segment to a halfspace There are three cases 1 The line segment is entirely inside Keep it 2 The line segment is entirely outside Discard it 3 The line segment is partially inside and partially outside Generate new line to represent part inside Input Specif
16. Texts e D Hearn and M P Baker Computer Graphics 3rd ed required e Course Overview and Notes online or at Bookstore e OpenGL Programming Guide optional Assignments 5 Assignments A0 A4 plus a Project A0 is worth 0 marks Marking Algorithm Assignments 32 Project 24 Midterm 14 Final 30 Must obtain 50 in both Programming and Exam portions to pass Programming Environment C OpenGL Lua Linux PCs General Comments A tough course lots of work Be committed If you don t know C you will have major problems Do NOT take graphics and either real time CS452 or compilers C5444 1 2 Topics Covered e Graphics Pipeline and Hardware e Mathematical Foundations Affine and Projective Geometry Linear Algebra and Transformations Numerical Analysis and Splines Modelling and Data Structures e Hidden Surface Removal e Colour and the Human Visual System Assignments 1 2 10 e Lighting and Shading e Ray Tracing e Global Illumination optional if time permits e Animation optional if time permits 1 3 Assignments Number 5 Assignments A0 A4 plus a Project AO worth 0 marks Environment Linux PCs You are expected to share machines Be nice Code Credit You must request in README For each missed objective in README state what is wrong and how you would attempt to fix it mark up printout of code Hand in At start of class first 5 minutes NO LATES Hand in documenta
17. The Project 30 5 244 Objective List e Your proposal needs to include an Objectives list which we will use to mark you e No objectives from assignments e Roughly 1 3 to 1 2 easy objectives Modelling texture mapping alpha blending A few medium ones L systems reflection 2D collisions 1 or 2 hard ones 3D collisions hardware tricks stuff from papers e Try to break hard objectives into multiple pieces Common Objectives e Modelling scene e Animation User interface more complex interaction Texture mapping Artifical Intelligence sound If your other objectives had enough graphics content e Ray tracer Must tell us your A4 extra feature CSG Reflection refraction anti aliasing Extra primitives torus Warm cold Fuzzies About Objectives e Think about what subjective mark you could get Technical artistic documentation difficulty e Negative subjective marks for not using what you ve learned eg flat shading in OpenGL projects e Get advise from TAs and profs e Beware of too easy too hard projects You can always do extra stuff Assignment 5 The Project 30 5 245 e Make objectives not subjective Good UI is subjective e When wondering if something makes a good project try making an objective list for it OpenGL vs Ray Tracing OpenGL Projects e Interactive e Avoid UI intensive projects e Try to have a purpose game etc Ray Tracing
18. Then ray trace and use stored light to achieve global illumination effects e General steps of photon mapping Emit photons Mostly distribution of n photons around light source Trace photons Bounce off shiny surfaces store at diffuse surfaces Estimate irradiance Ray trace using estimated irradiance as needed e LS D Idea based on bouncing light off shiny surfaces until it hits diffuse surface ile wI Lg sr G e L S D D bounce off both shiny and diffuse surfaces and store information at diffuse surfaces e Shiny surface light leaves in a fixed direction relative to incoming direction Includes transparent refractive surfaces e Similar to ray tracing but cast rays from lights e When light hits shiny surface bounce to next surface Use Russian Roulette to send ray to next surface based on BRDF e When light hits diffuse surface store surface point in data structure kD tree etc Also store surface normal intensity power of light Overview 25 0 174 To estimate irradiance at a point e Doa k nearest neighbour search to find closest stored photon information Usually try to limit search to a local region sphere L l ES IP Average to get irradiance for the point Since kD tree is space not surface based may pick up photons on nearby surface May cause noise in image When ray tracing use radiance information in lighting equation To get caustics use Direct
19. and fragment shader e Single precision float for vertex shader e 24 bit float in fragment shader 15 bit significand GeForce 5x00 e Single precision floating point in vertex shaders e Half and single precision floating point in fragment shaders Floating point textures and rendering targets e Unlimited number of dependent texture reads in fragment shader ATI 8x0 e Single precision float for vertex shader e 24 bit float in fragment shader e Multiple floating point rendering targets supported NVIDIA Vertex Shader Assembly 18 1 117 GeForce 6x00 e Single precision floating point in vertex shaders e Half and single precision floating point in fragment shaders Floating point textures and rendering targets Filtering and interpolation support for half float textures e Multiple rendering targets e Control constructs loops and conditionals in both vertex and fragment programs e Texture access in vertex unit no filtering OpenGL 2 0 e Full single precision floating point in both shaders e Unlimited number of instructions e Conditional execution and loops e High level shading language in driver Full support only available on 3Dlabs Realizm cards so far 18 2 NVIDIA Vertex Shader Assembly Vertex Shader e Sets of four word registers e Data passed in through v c registers Results passed to next stage through o registers 16 vertex attribute registers v 0 v 15 Mnemonic names v OPOS v WGHT V NML
20. but they don t understand the image How can we apply an NPR filter in a meaningful way e Let a person determine importance by having them look at the source image and tracking their eye movements e Not strokes but large regions of constant colour e Edges drawn as well Woman with guitar photo Woman with guitar NPR image Simulating natural media e Implement a physical simulation to approximate the behaviour and appearance of a traditional artistic medium Computer Generated Watercolor Curtis Anderson Seims Fleischer and Salesin SIGGRAPH 1996 e Very realistic simulation of the appearance of watercolour paints e Treat the painting as a big fluid flow simulation Navier Stokes equations to push fluid around on top of the paper e Fluid and paper exchange pigment e Paper propagates water via capillary action Photo of watercolour brush strokes Real paint Simulation of watercolour brush strokes Simulated Samples of watercolour paint simulations Fruit and lots of it 2D NPR 28 0 212 Pencil Rendering Sousa and Buchanan GI 1999 CGF 2000 e Simulation of pencil lead and paper derived from close observation of real materials e Model the geometry of the pencil tip pressure on page e Graphite particles can move to and from paper so system can model pencils erasers and blenders e Pressure affects geometry of paper and therefore appearance of future strokes Real and simulated pencil Crumpled paper phot
21. by patch i is given by Bi E pid FB j As Ei pid Fug Bs A J Bi Bj radiosity in energy unit time unit area Fi light emitted from patch i pi patch 1 s reflectivity Fj Form factor specifying fraction of energy leaving j that reaches accounts for shape orientation occulsion Aj Aj Area of patches Radiosity Full Matrix Solution e The equations are Bi Fi pi y Bj Fi l lt jsn or Bi pi y By Fig Ei I lt jsn Form Factors 24 1 164 e In matrix form La pia pris e PLA B Er p2F21 l p2F22 ie p2F2n B Ez PnFn 1 PnFn 2 a Mi Pnl nn Bn En e B s are only unknowns e If Fii 0 true for polygonal patches then diagonal is 1 e Solve 3 times to get RGB values of B Readings Hearn and Baker in OpenGL 10 12 Watt Chapter 11 24 2 Form Factors Calculation e Form factor specifies fraction of energy leaving one patch that directly arrives at another patch e The differential form factor is given by cos 6 cos 0 Tr where He 0 if dA occluded from dA 1 1 if dA visible from dA Form Factors Calculation e To see how much of dA illuminates patch j we integrate 0 0 OF as i ee dA dA A ar Form Factors 24 1 165 e The form factor from A to A is an area average of the integral over A 1 cos 6 cos 6 y a ij A ls Fna ij OAJO e Typically we approximate this integral Ray tracing Hemi sphere
22. don t notice e When you look at different object you shift projection plane Different sphere looks circular e In painting all spheres drawn as circular When not looking at them they are mathematically wrong but since not focus of attention they are close enough Transformation Applications and Extensions 9 70 e In graphics 10 TRANSFORMATION APPLICATIONS AND EXTENSIONS 71 10 Transformation Applications and Extensions 10 1 Rendering Pipeline Revisited Rendering Pipeline Revisited Modelling SEL Viewing Transformations 3D World 3D View Se Scene Scene MCS VCS WCS Projection je Rasterization 2D Image 2D 3D Device Scene NDCS DCS or SCS Composition of Transforms p PV M p 10 2 Derivation by Composition Derivation by Composition e Can derive the matrix for angle axis rotation by composing basic transformations e Rotation given by x y z and 0 e Assume that 1 General idea Map a onto one of the canonical axes rotate by 6 map back 1 Pick the closest axis to using max e max z y 2 Assume we chose the z axis in the following 2 Project a onto b in the xz plane b 2 0 z 3 Compute cos and sin where is the angle of b with the x axis cost Tas N z sin V2 22 3D Rotation User Interfaces 10 2 72 4 Use cos and sin to create Ry d cos 4 0 sin 9 0 P
23. energy out e depends on incoming and outgoing directions e varies from wavelength to wavelength e Definition Ratio of radiance in the outgoing direction to radiant flux density for the incoming direction L x 0 q A L x 0L pi A cos 64 duit Poa x i Qi i bo Po Ao z L x 0L 9L 11 ne EOS Definitions and Overview 24 0 161 Energy Balance Equation Ea 02 Q2 A x ee 2 2m Amaz I F y Poal x OoN 02 Po A Amin cos 62 L x 8 b A dA sin 6 dei d t L x 02 6 A is the radiance at wavelength A leaving point x in direction 02 p2 L x 0 6 A radiance emitted by surface from point L x 0 pi A incident radiance impinging on the point poa x 0 pi A 02 6 A is the BRDF at the point describes the surface s interaction with light at the point e the integration is over the hemisphere above the point Radiosity Approach to Global Illumination e Assume that all wavelengths act independently poa x Oe Pa A 02 2 X pralz Oz 2 92 2 L x 62 da A L x Ox bx e Assume that all surfaces are purely Lambertian pra 0 d 02 3 LD e As a result of the Lambertian assumption L x bx bz L x B x def fo L x cos 0 dw rL 2 Simple Energy Balance Hemisphere Based Ee lee pat pa cos 0 di Multiplying by z and letting E x TL x B x Elx pal
24. equations by applying the laws of Newtonian physics 3 Define initial conditions i e initial velocities and positions A Supply functions for external forces possibly via keyframing al Solve the differential equations to derive animation i e motion of all objects in scene as a function of time e During solution of the differential equations we have to be prepared to deal with discontinuities due to collisions e We will discuss the simulation of spring mass and point mass models e Both have useful applications and are relatively simple to simulate Physically Based Animation 29 10 231 Spring Mass Models Create a model Composed of a mesh of point masses m connected by springs with spring constants kj and rest lengths Let P t 2 6 y t zi t be the position of mass m at time t Let N be all masses connected to mass mi If j N then m and mj are connected by a spring Springs exert force proportional to displacement from rest length in a direction that tends to restore the rest length ES p E E AO kij G Pi t Py t P t Pit Pe Y RO JEN Masses assumed embedded in a medium that provides a damping force of fa piti t U t is velocity of m at time t Motion of each mass governed by second order ordinary differential equation mi t pit F t FF fe t is the sum of external forces on node 7 and a _ ES d2y t a d
25. gt O then next t wecA wecA wecB if wecA lt 0 then A A t B A else B A t B A endif endfor Note e Liang Barsky Algorithm can clip lines to any convex window e Optimizations can be made for the special case of horizontal and vertical window edges Question Should we clip before or after window to viewport mapping Line clip Algorithm generalizes to 3D e Half space now lies on one side of a plane e Plane also given by normal and point e Implicit formula for plane in 3D is same as that for line in 2D e Parametric formula for line to be clipped is unchanged Readings Watt none Hearn and Baker Sections 6 5 through 6 7 12 5 for 3D clipping Red book 3 9 White Book 3 11 Blinn 13 9 PROJECTIONS AND PROJECTIVE TRANSFORMATIONS 57 9 Projections and Projective Transformations 9 1 Projections Projections Perspective Projection e Identify all points with a line through the eyepoint e Slice lines with viewing plane take intersection point as projection View Plane e This is not an affine transformation but a projective transformation Projective Transformations e Angles are not preserved not preserved under Affine Transformation e Distances are not preserved not preserved under Affine Transformation e Ratios of distances are not preserved e Affine combinations are not preserved Straight lines are mapped to straight lines e Cross ratios are preserved Cros
26. how about interactive e Will consider three methods Projective shadows shadow maps volume shadows 22 2 Projective Shadows For drawing shadows on a plane After drawing scene e Draw ray from light through corners of polygon and intersect with plane e Draw projected polygon as a dark colour with alpha blending Depth test strictly less than Advantages fast simple Disadvantages shadows only on a plane Shadow Maps VU VA qe As fF 2 22 3 Shadow Maps Given a scene Near s Far Screen Uc Render scene from light s viewpoint disable colour write 22 2 148 Shadow Maps 22 2 149 Near ed Far Light Screen _ Screen ES e Store the 2 map this is the shadow map e Possibly render deeper Now render from eye s viewpoint At point P that eye sees on surface e Convert P s coordinates to light s frame e Look up distance from light using shadow map Shadow Volumes 22 3 150 e If distance in shadow map equal to distance from light to P do lighting calculation Oth erwise in shadow e One or more shadow map s per light e Aliasing lots of work on this e Depth test lots of work on this e Needs hardware support Special purpose hardware obsolete Use fragment shader to do look up e If you don t move lights or objects just view then you don t need to rerender shadow
27. in the convex hull of the control points gt Surface patch is affinely invariant Transform the patch by transforming the control points Subdivision Recursion Evaluation e As for curves in each variable separately and independently e Tangent plane is not produced Normals must be computed from partial derivatives Partial Derivatives e Ordinary derivative in each variable separately SP s t DYP Se ro B t i 0 j 0 YE PaB Gao i 0 j 0 e Each is a tangent vector in a parametric direction Tensor Product Patches 27 4 197 e The unnormalized surface normal is given at any regular point by o 0 t P s t P s t LS Pls t x Plot the sign dictates what is the outward pointing normal e In particular the cross boundary tangent is given by e g for the s 0 boundary n Pis Pio B t i 0 and similarly for the other boundaries P0 3 P3 3 PO0 0 P3 0 Smoothly Joined Patches e Can be achieved by ensuring that Pin Pin 1 B Qi1 Qio for B gt 0 and correspondingly for the other boundaries Rendering e Divide up into polygons Barycentric Coordinates 27 5 198 A By stepping s 0 6 26 1 t i Ea ETTR and joining up sides and diagonals to produce a triangular mesh B By subdividing and rendering the control polygon Tensor Product B splines e Could use B splines instead of B zier Automatic continuity between patches Problem with tensor
28. loop e Typically used to track sequence of actions the mouse 4 4 Event Queues Event Queues e Device is monitored by an asynchronous process e Upon change in status of device this process places a record into an event queue e Application can request read out of queue Number of events First waiting event Highest priority event First event of some category All events Application can also Specify which events should be placed in queue Clear and reset the queue Etc Queue reading may be blocking or non blocking e Processing may be through callbacks Events may be processed interruptively e Events can be associated with more than physical devices Windowing system can also generate virtual events like Expose Toolkits and Callbacks 4 4 23 Without interrupts the application will engage in an event loop not a tight loop a preliminary of register event actions followed by a repetition of test for event actions For more sophisticated queue management 4 5 application merely registers event process pairs queue manager does all the rest if event E then invoke process P Events can be restricted to particular areas of the screen based on the cursor position Events can be very general or specific A mouse button or keyboard key is depressed The cursor enters a window The cursor has moved more than a certain amount An Expose event is
29. not enclose a volume then we can t use it Painter s Algorithm 12 2 84 e A HUGE speed advantage if we can use it since the test is cheap and we expect at least half the polygons will be discarded e Usually performed in conjunction with a more complete hidden surface algorithm e Easy to integrate into hardware and usually improves performance by a factor of 2 12 3 Painter s Algorithm Painter s Algorithm e Idea Draw polygons as an oil painter might The farthest one first Sort polygons on farthest z Resolve ambiguities where z s overlap Scan convert from largest z to smallest z e Since closest drawn last it will be on top and therefore it will be seen e Need all polygons at once in order to sort Painter s Algorithm Z overlap e Some cases are easy Warnock s Algorithm 12 3 85 z 1 e A Y y A Z 3 gt z gt Xx Xx e But other cases are nasty YA YA gt gt X X have to split polygons e Q n algorithm lots of subtle detail 12 4 Warnock s Algorithm Warnock s Algorithm e A divide and conquer algorithm Warnock PolyList PL ViewPort VP If PL simple in VP then Draw PL in VP else Split VP vertically and horizontally into VP1 VP2 VP3 VP4 Warnock PL in VP1 VP1 Warnock PL in VP2 VP2 Warnock PL in VP3 VP3 Warnock PL in VP4 VP4 end e What does simple mean No more than one polygon in viewport Scan convert polygon clipped
30. of Ray Tracing Colour and Shading e Some sample code will be provided to get you started e Your raytracer will implement at least spheres cubes polygons and the Phong lighting model e Only primary and shadow rays are required in the basic implementation Additional Features You will also be asked to implement one additional feature of your choice For example you could implement e Secondary rays for reflective surfaces e Depth of field using jittered aperture supersampling Assignment 5 The Project 30 5 243 e Antialiasing using jittered pixel supersampling e A fisheye lens e Texture or bump mapping e CSG operations e Additional object types Screen Shots Sample screen shots Some details may vary term to term 30 6 Assignment 5 The Project e The project submission is distributed over three phases A proposal A revised proposal addressing our comments A final submission and demonstration e Your project should have a significant computer graphics content but is otherwise uncon strained e A project does not have to have an interactive user interface but if not you will have to work harder on the algorithms e You will have to prepare documentation for your project and the quality of this documenta tion will strongly influence your mark e Ask us for project suggestions also it would be wise to run your idea past us before submitting your proposal Assignment 5
31. one matrix to both project and map to NDC How do we set x or y to map to 1 1 We don t want to do both because we may not have square windows OpenGL maps y to 1 1 y P 1 e Want to map distance d to 1 e y gt y z is the current projection Our final matrix is ies co aspect 0 0 0 0 cot 6 2 0 0 n 2 0 0 Lae 0 0 1 0 E is 1 if we look down the z axis and 1 if we look down the z axis where the 4 OpenGL uses a slightly more general form of this matrix that allows skewed viewing pyramids Why Map Z 9 1 61 9 2 Why Map 2 Why Map Z e 3D gt 2D projections map all z to same value e Need z to determine occlusion so a 3D to 2D projective transformation doesn t work Further we want 3D lines to map to 3D lines this is useful in hidden surface removal The mapping 2 y z 1 gt an z yn z n 1 maps lines to lines but loses all depth informa tion e We could use an yn 1 1271 Y z E E ghee Thus if we map the endpoints of a line segment these end points will have the same relative depths after this mapping BUT It fails to map lines to lines P P PP e In this figure P Q R map to P Q R under a pure projective transformation e With the mapping zx y 2 1 gt 7 2 2 1 P Q R actually map to PP QP RP which fail to lie on a straight line Mapping Z 9 2 62 e Now map S to S to SP e Line s
32. points and vectors are Summary of Geometric Spaces 5 4 29 e Different objects e Have different operations e Behave differently under transformation Coordinates Use an an extra coordinate gt e 0 for vectors T vz Vy Vz 0 means T vgt Vy vzk e 1 for points P pz Py Pz 1 means P Pai Pyj Dek O e Later we ll see other ways to view the fourth coordinate e Coordinates have no meaning without an associated frame Sometimes we ll omit the extra coordinate point or vector by context Sometimes we may not state the frame the Standard Frame is assumed 5 5 Summary of Geometric Spaces Space Objects Operators Vector Space Vector U U av Affine Space Vector Point u U aqu P U Euclidean Space Vector Point w v ay P U 4 1 Question where does the cross d P Q Cartesian Space Vector Point v0 Qu P W v O N Frame d P Q i 7 k O product enter Readings Watt 1 1 1 2 White book Appendix A Hearn and Baker A 2 A 3 Affine Geometry and Transformations 5 30 6 AFFINE GEOMETRY AND TRANSFORMATIONS 31 6 Affine Geometry and Transformations 6 1 Linear Combinations Linear Combinations Vectors YV t w at By Extension y au no restriction on a 2 Linear Transformations T 3 0 T 0 T 0 T ait aT i TO aiti 2 aiT i By Extension Points P P P i Q By Extension 6 2 Affine Combinations Affi
33. prim prim gt draw else for vector lt Node gt iterator i children begin i children end i 4 i gt traverse PopMatrix A3 A4 House Code scene gr transform scene Assume we have predefined materials red green and blue house gr transform house prism gr polyhedron prism roof gr transform roof gr add_child roof prism gr set_transform roof gr translation 0 1 0 gr add_child house roof frame gr cube frame gr add_child house frame farmhouse gr transform farmhouse gr add_child farmhouse house gr set_material farmhouse green continued on next slide continuation from previous slide barn gr transform barn gr add_child barn house gr set_material barn red gr set_transform barn gr translation 2 0 3 gr scaling 2 2 2 gr rotation Y 30 doghouse gr transform doghouse gr add_child doghouse house gr set_material doghouse blue gr set_transform doghouse gr translation 1 5 0 0 2 gr scaling 0 2 0 2 0 2 gr rotation Y 15 gr add_child scene farmhouse Hierarchical Data Structures 13 1 94 gr add_child scene barn gr add_child scene doghouse Later in the code gr render scene Improved A3 A4 House Code Assume materials are defined About 30 lines defining ma
34. rendering primitives are transformed usually in a conceptual pipeline from the model to the device However raytracing which we will consider later in the course is a form of backward ren dering In backward rendering we start with a point in the image and work out what model primitives project to it Both approaches have advantages and disadvantages The Graphics Pipeline e Rendering is the conversion of a scene into an image Render 2D Image e Scenes are composed of models in three dimensional space Models are composed of primitives supported by the rendering system e Models entered by hand or created by a program e The image is drawn on monitor printed on laser printer or written to a raster in memory or a file Requires us to consider device independence e Classically model to scene to image conversion broken into finer steps called the graphics pipeline e Parts of pipeline implemented in graphics hardware to get interactive speeds e Modern hardware acceleration supports programmable pipelines Some of pipeline stages are programmable units Pipeline 2 1 13 You can implement your own lighting models or geometric transformations Programmable graphics accelerator GPU You have to know what you re doing i e know the math to use a GPU e The basic forward projection pipeline looks like Modelling Transformations Viewing Transformations M1 3D World 3D View
35. s modified Phong etc e Good empirical model for project Ashikhmin and Shirley An Anisotropic Phong BRDF Model Journal of Graphics Tools AK Peters ACM Volume 5 Number 2 2000 17 SHADING 111 17 Shading 17 1 Introduction e Want to shade surfaces e Lighting calculation for a point Given L and surface properties including surface normal in Compute Lout in direction Y e Need surface normals at every point e Commonly surface is polygonal True polygonal surface use polygon normal Sampled surface sample position and normal create polygonal approximation e Want colour for each pixel in rasterized surface Flat Shading e Shade entire polygon one colour e Perform lighting calculation at One polygon vertex Center of polygon What normal do we use All polygon vertices and average colours e Problem Surface looks faceted e OK if really is a polygonal model not good if a sampled approximation to a curved surface 17 2 Gouraud Shading e Gouraud shading interpolates colours across a polygon from the vertices e Lighting calculations are only performed at the vertices Interpolation well defined for triangles Extensions to convex polygons but not a good idea convert to triangles e Barycentric combinations are also affine combinations Triangular Gouraud shading is invariant under affine transformations Gouraud Shading 17 1 112 APBC AABC B AAPC AABC
36. y AABP AABC a p y 1 A P 04 BB yC C e To implement can use repeated affine combination along edges across spans during rasteri zation e Gouraud shading is well defined only for triangles e For polygons with more than three vertices Sort the vertices by y coordinate Slice the polygon into trapezoids with parallel top and bottom Interpolate colours along each edge of the trapezoid Interpolate colours along each scanline C F lerp A B H lerp D E I lerp H E J lerp B F P lerp 1 J A e Gouraud shading gives bilinear interpolation within each trapezoid Phong Shading 17 2 113 17 3 Since rotating the polygon can result in a different trapezoidal decomposition n sided Gouraud interpolation is not affine invariant Aliasing also a problem highlights can be missed or blurred Not good for shiny surfaces unless fine polygons are used Exercise Provide an example of the above effect Exercise Prove repeated affine combinations the above algorithm is equivalent to barycen tric combinations on triangles Exercise Prove that the extension of the repeated affine combination algorithm to arbitrary polygons is not invariant under affine transformations Common in hardware renderers the model that classic OpenGL supports Linear interpolation in device space not consistent with linear interpolation in world space Modern implementations of OpenG
37. CS 488 688 Winter 2006 Craig S Kaplan Stephen Mann CONTENTS Contents Administration Oopics Covered A ASSISTNIMET S o dat e ee See st Re Se ede BAG e GE o a a E He aed 3 Devices and Device Independence O alligraphic and Raster Devices 2 2 a a UN Device Input Modeg aaa a a A Application structure soaa a Y P p d pling 4 4 JUCUCH Mena de e 2k e eee A A A e e a 4 0 xample for Discussion 2 ee 5b Geometries O Vector Space S a sa a RR ar ee A Afi TE RAEE O uclidean Spaced oao a 9 4 artesian PA A soosoo o a e a a a a a a a O ummary of Geometric paces 6 Athne Geometry and anstormation 0 07 AMDISUICY 00 aca peda a a Wh AAA A A a 0 10 World and Viewing Frames 1 e OLITE Normal os soe eh a OR eR SOR AA A A RA 11 11 12 14 14 15 17 17 17 19 21 21 21 22 22 23 24 27 27 27 28 28 29 CONTENTS Wind V D AD A Window to Viewport Marraco S pping 8 Ji a ge Peak bow Awe oe ee ek oe ewe ee oe we we a t 9 Projections and Projective anstormation 9 PTOJECUONS g cse o aos a a dodoa a Re ok AA dod 9 W VI 9 Vlapp 9 4 D DPIN o eoe de eA RRR ERE Re EE e Rhee ew ew a 9 Homogeneous Clipping aooaa a 9 0 Pinhole amera vs amera vs Perception e 0 ansformation Applications and Extension 0 1 Rendering Pipeline Revisited e 0 2 Derivation b omposition 2 a 0 4 V O ons INTroQU
38. Control e Controlling each flock member with local behaviour rules Computationally desirable Appears to be how flocks work in real world e No reference to global conditions of flock environment e Three things to model Physics Gravity collisions Perception Information flock member has with which to make decisions Reasoning reaction Rules by which flock member decides where to go Assignments 29 238 Perception e Aware of itself and two or three neighbors What s in front of it e Doesn t follow a designated leader e No knowledge of global center Reasoning reaction e Collision avoidance e Flock centering e Velocity matching Try to match velocity of neighbors Helps with flock centering and helps avoid collisions Additional details e Global control Animator needs to direct flock e Flock leader Usually one member whose path is scripted global control Not realistic leader changes in real flocks but usually not noticed and easier to deal with e Splitting and Rejoining Flocks pass around objects splitting them Difficult to balance rejoining with collision avoidance 30 ASSIGNMENTS 239 30 Assignments 30 1 Assignment 0 Introduction The goals of this assignment include e Familiarization with the course computing environment e Setting up your account and directories e Modifying a Ul e A trial assignment submission This assignment is not worth any marks However we strongly suggest you do t
39. GLIOM i 4 6 4 4 hae be Se oS SAE we Ea aaa ES A O on ocan WODVETSION e ae a a aa e A AA Se ae ae d Painter s Algorithm 2 a 4 W Alo Alo 6 Comparison of Algorithms 2 a 4 Picking and D Selectio 4 1 Picking and ID Selection gt i s am scg ee 9 Colour and e Human Visua ste 49 49 50 53 53 57 57 61 62 65 65 67 71 71 71 72 73 75 75 76 79 80 83 83 83 84 85 86 87 89 89 92 97 97 101 CONTENTS 4 6 Reflection and Lig ource Mode 103 103 103 105 106 107 ding 111 O Introduction o oo oa a a 111 d TION hse e sere oe Rp E eh E PR eden ost apy shear eas WAR ec ae 111 P g dO e su i ae tet BAA eee Oe e e ee ee ee et ee ee E e eels 113 8 D Hard e 115 115 117 119 119 121 9 R o 123 123 124 127 128 129 131 133 136 139 20 1 M A A A ee SO ad 139 20 2 Distribution Ka A NN 139 20 3 Bidirectional Pat ACINO cia rc a a et A a a 140 20 4 P MAD oa cio a a Be RE ia A eee e da A 141 21 A o 143 2 A Mi A a ech ae a e ca ee ee EIE a 143 22 Shadows 147 bob ee te A A E ee 147 22 2 Projective Shadows 2 aa 147 2 d aD eee voce EN O 148 PZ4 Shadow Volumed ev ooa Ge ee 150 23 Modeling of Natural Phenomena 155 AAA ss eoo She uk MOK Gps aa a e OS Sk a ee ee 155 23 System Plants o ocios BARE eR a ke we we a 156 23 9 Particle Systems 156 CONTENTS 5 24 Rad Y 159 159 164 24 3 Progressive Refi
40. Hemi cube Compute dFy e Lots of F s may be zero leading to a sparse matrix Form Factors Hemi sphere Form Factors e Place a hemisphere around patch and project patch j onto it Select a point on each patch and look at angles e Project patch j onto hemisphere and project projection into circle Fa qe where Hy is the area of the circle Note that any polygon with same cross section has same form factor e Projecting onto hemisphere is still hard Form Factors Hemi cube Form Factors e Project onto a hemi cube e Subdivide faces into small squares Form Factors e Now determine which squares patch j projects onto Form Factors Delta Form Factors e Each hemi cube cell P has pre computed delta form factor cos 0 cos 0p AFp 5 Tr AAp e Approximate dFy by summing delta form factors e If distance from i to j is large this is good approximation for Fj Form Factors Exact Form Factors e We can compute the exact form factor for point to polygon 24 1 166 Progressive Refinement 24 2 167 The differential form factor is given by Fga A gt gt N T where Nj is the normal to patch j T is the vector in direction R 1 x R with length equal to 0 in radians e Doesn t account for occlusion 24 3 Progressive Refinement e Recall our equation says how much radiosity i
41. INTERFACES 21 4 Device Interfaces 4 1 Device Input Modes Device Input Modes Input from devices may be managed in different ways Request Mode Alternating application and device execution e application requests input and then suspends execution e device wakes up provides input and then suspends execution e application resumes execution processes input Sample Mode Concurrent application and device execution e device continually updates register s memory location s e application may read at any time Event Mode Concurrent application and device execution together with a concurrent queue management service e device continually offers input to the queue e application may request selections and services from the queue or the queue may interrupt the application 4 2 Application Structure Application Structure With respect to device input modes applications may be structured to engage in e requesting e polling or sampling e event processing Events may or may not be interruptive If not interruptive they may be read in a e blocking e non blocking fashion Event Queues 4 3 22 4 3 Polling and Sampling Polling In polling e Value of input device constantly checked in a tight loop e Wait for a change in status Generally polling is inefficient and should be avoided particularly in time sharing systems Sampling In sampling value of an input device is read and then the program proceeds e No tight
42. L actually implement rational linear interpolation which takes perspective into account Phong Shading Phong Shading interpolates lighting model parameters not colours Much better rendition of highlights A normal is specified at each vertex of a polygon Vertex normals are independent of the polygon normal Vertex normals should relate to the surface being approximated by the polygonal mesh The normal is interpolated across the polygon using Gouraud techniques At each pixel Interpolate the normal Interpolate other shading parameters Compute the view and light vectors Evaluate the lighting model The lighting model does not have to be the Phong lighting model Normal interpolation is nominally done by vector addition and renormalization Several fast approximations are possible The view and light vectors may also be interpolated or approximated Problems with Phong shading Distances change under perspective transformation Graphics Hardware 17 114 Where do we do interpolation Normals don t map through perspective transformation Can t perform lighting calculation or linear interpolation in device space Have to perform lighting calculation in world space or view space assuming model view transformation is affine Have to perform linear interpolation in world or view space project into device space Results in rational linear interpolation in device space Interpolate homogene
43. Level Shading Languages e OpenGL DirectX APIs support assembly interface for vertex and fragment programs e Hard to program maintain read assembly e Several high level shading languages now available Cg GLSL Microsoft HLSL Sh 18 4 Cg e Cg is an example of a C like language to create shaders Created and supported by NVIDIA but can target other cards Also API independent OpenGL or DirectX Compile in advance to assembly or at runtime Web page for docs http developer nvidia com Cg Cg example from nvidia Cg Toolkit User s Manual Have to define inputs and outputs define inputs from application struct appin float4 Position POSITION float4 Normal NORMAL define outputs from vertex shader struct vertout float4 Hposition POSITION float4 Color0 COLORO vertout main appin In uniform float4x4 ModelViewProj CO uniform float4x4 ModelViewlT C4 uniform float4 LightVec vertout Out Out Hposition mul ModelViewProj In Position transform normal from model space to view space float4 normal normalize mul ModelViewIT In Normal xyzz store normalized light vector float4 light normalize LightVec calculate half angle vector float4 eye float4 0 0 0 0 1 0 1 0 float4 half normalize light eye calculate diffuse component float diffuse dot normal light calculate specular component float specular dot normal half specular pow sp
44. Many different resolutions for graphics display devices Workstations commonly have 1280x1024 frame buffers A PostScript page is 612x792 points but 2550x3300 pixels at 300dpi And soon Aspect ratios may vary e If we map directly from WCS to a DCS then changing our device requires rewriting this mapping among other changes e Instead use Normalized Device Coordinates NDC as an intermediate coordinate sys tem that gets mapped to the device layer e Will consider using only a square portion of the device Windows in WCS will be mapped to viewports that are specified within a unit square in NDC space e Map viewports from NDC coordinates to the screen Clipping 7 51 Viewport 11 Viewport Window 0 0 World Space NDC Space Screen Space Readings Watt none Hearn and Baker Sections 2 7 6 3 Red book 6 3 White book 6 5 Clipping 7 52 8 CLIPPING 53 8 Clipping 8 1 Clipping Clipping Clipping Remove points outside a region of interest e Discard parts of primitives outside our window Point clipping Remove points outside window e A point is either entirely inside the region or not Line clipping Remove portion of line segment outside window e Line segments can straddle the region boundary e Liang Barsky algorithm efficiently clips line segments to a halfspace e Halfspaces can be combined to bound a convex region e
45. NTS 6 30 A z 239 30 1 Assignment O Introduction a a aoa a 239 90 2 Assignment I Introduction to OpenGl 2 eee 239 30 3 Assignment 2 Frames and Perspective ee 240 90 4 Assignment 3 Hierarchical Modelling ee ee 241 30 5 Assignment 4 A Raytracer s e sp 2 ee 242 90 0 Assignment o O Project e cow ee a a ee we EO ee 243 CONTENTS 7 These notes contain the material that appears on the overhead slides or on the computer shown in class You should however read the course text and attend lectures to fill in the missing details The material in this course is organized around the assignments with the material at the end of the course being a sequence of topics not covered on the assignments Some of the images shown on the slides cannot be included in the printed course notes for copyright reasons The following former CS 488 688 students have images appearing in these notes e Eric Hall e lan McIntyre e Selina Siu e Bryan Chan e Franke Belme e Andrew Lau e Jerome Carri re e Bonnie Liu e Zaid Mian e Ryan Meridith Jones Administration 0 8 1 ADMINISTRATION 1 Administration 1 1 General Information Instructors Craig S Kaplan Stephen Mann Electronic Resources Web http www student cs uwaterloo ca cs488 Newsgroup uw cs cs488 Email cs488 cgl uwaterloo ca When sending email from non uwaterloo account put CG in the subject
46. PV PVBN PVB PVB PV PV Code now looks like Procedure Scene MultMatrix P MultMatrix V PushMatrix MultMatrix B House PopMatrix PushMatrix MultMatrix D House PopMatrix end Procedure House PushMatrix MultMatrix M Prism Popmatrix PushMatrix MultMatrix N Cube Popmatrix end Procedure Cube Procedure Prism end end PVB PV 13 1 91 Hierarchical Data Structures 13 1 92 13 2 Hierarchical Data Structures Hierarchical Data Structures e Don t want to write a program for each scene e Instead develop a data structure and traverse it e Use an external data format to describe model hierarchies e Process many different scenes with the same program DAG data structure lots of variations on the example given here Consider the following DAG e Use one of a variety of data structures to allow an arbitrary number of links from each node Example class Node 4 private Primitive prim vector lt Nodex gt children Hierarchical Data Structures 13 1 93 e We walk through the hierarchy with a preorder traversal e Traversal pseudocode void Node traverse PushMatrix MultMatrix transform if
47. Q Cubic Hermite Interpolation e Problem Given points Po Py and vectors vo UN Find Piecewise C cubic P s t Pli P P for i 0 N e Solution Use one cubic B zier segment per interval Then Pio P U Pa P E D Pia Piy Pis Piy Catmull Rom Splines e When modelling specifying derivatives can be either good or bad but more commonly bad e Want to specify just points e Idea make up derivatives from points and use Cubic Hermite Spline Continuity 27 3 193 e Fori 1 N 1 let vj Piy1 Pi 1 e Need derivatives for i 0 N Discard data Set to 0 Set to P Po perhaps scaled C Piecewise Cubic B zier e With cubics we can have C continuity why not C e A frame construction gives C constraints on B zier segments ZAZ e Too hard to make user place points in this manner so Modelling User places four control points program places next three user places one more program places next three e Could hide program placed control points e Redundant representation C B zier Spline e Suppose we have a Ct B zier spline Po R R Qo Q3 Q Q Spline Continuity 27 3 194 e For Ct cubic B zier spline need only two control points per segment plus one more at start and one more at end Po R Q Q C B zier Spline e Suppose we have a C B zier spline Joints can be computed as described for Ct yy If we keep t
48. R 1 8 PRN tP 2 P t Pi Use to evaluate point at t or subdivide into two new curves e P Ph Pf are the control points for the left half s ae see Pj are the control points for the right half 0 0 Py P 0 0 Po P3 1 P P3 P p p 1 2 3 Po p 0 1 0 Po P3 27 3 190 Spline Continuity 27 3 191 27 4 Spline Continuity Polynomials Inadequate e Weierstrass Approximation Theorem Can approximate any C curve to any tolerance with polynomials But may require high degree e To model complex curves will need high degree e High degree Non local Expensive to evaluate Slow convergence as we increase degree Piecewise Polynomials e Idea Instead of one high degree polynomial piece together lots of low degree polynomials e Benefits Fast to evaluate Good convergence properties Potentially local e Problem Continuity between pieces C Piecewise Cubic B zier e Piecewise cubic e B zier form e B zier Property curve interpolates first control point e B zier Property curve interpolates last control point C Set last control point of one segment to be first control point of next segment 5 P Q Qo C Piecewise Cubic B zier Spline Continuity 27 3 192 e Need parameterizations of intervals to discuss C continuity e Assume uniform parameterization 0 1 1 2 2 3 e Need C to have C P3 Qo e C is P3 P Q1 Qo R 0 Ya Q
49. a 0 using transpose notation A T P Pa 0 e After an affine transformation on P Pp M P Pa MP MP we want Nx to be a normal for some transformation N Ni M P Pa 0 7 N M P Pa and this certainly holds if N M7 Modeling and CSG 19 5 130 e Only the upper 3 by 3 portion of M is pertinent for vectors e Translation 1 0 0 0 fee 0 1 0 0 ae M 0 a gt Ge ok o Ax Ay Az 1 oe vean ltd 010 W EA ES Nz Nz 1 osa 1 gt no change to the normal e Rotation example ee joa 0 0 sin cos 0 0 Cia As 0 0 10 0 0 0 d cos 0 sin 0 0 7 sin 9 cos 0 O 0 0 0 1 0 0 0 0 1 cos sin 0 0 sin 0 cos 0 0 0 1 gt rotation applied unchanged to normal e Scale 1 4 0 0 0 al N 0 0 4 0 Sy dd E 0 a 0 0 0 1 a n Na eee 20 z Ord wisa 0 0 2 de A Pe 0 0 gt reciprocal scale applied to normal Modeling and CSG 19 5 131 19 6 Modeling and CSG Modeling Constructive Solid Geometry e How do we model for a Ray Tracer e Hierarchical modeling works well but we can do more e In Constructive Solid Geometry all primitives are solids New type of internal node Boolean operation Intersection Union Difference Thus our model is a DAG with Leaf nodes representing primitives Interal nodes are transformations materials or boolean operations material E boolean ia Y asta E primitive prim
50. a DAG a directed acyclic graph We can model this procedurally Hierarchical Transformations 13 0 90 Procedure Scene House B House D end Procedure House E Prism E o M Cube E o N end Procedure Cube F end Procedure Prism F end Implementation e Procedure calls are making depth first traversal of tree DAG e Use a matrix stack sometimes maintained in H W e Each time we make an embedding 1 Push the new transformation onto the matrix stack 2 Pop it on return e OpenGL s glPushMatrix call duplicates the top of the stack e OpenGL s glMultMatrix multiplies a matrix with the top of the stack replacing the top of the stack with the result e OpenGL s glPopMatrix pops the stack e Stack starts with identity matrix on bottom e OpenGL also has transformation calls such as glRotate glScale etc that perform basic transformations e These transformations operate on the top of the stack e Put perspective and world to view matrices into the stack e These are pushed on first giving PV on the bottom e Might have more than one stack i e MODEL VIEW and PROJECTION stacks Hierarchical Data Structures PushMatrix MultMatrix PV PV PV PushMatrix MultMatrix PVB PVBM PVB PVB PV PV PopMatrix PushMatrix PVB MultMatrix PV PVBM PVB
51. and 4 are affine spaces Then T is said to be an affine transformation if e T maps vectors to vectors and points to points Affine Transformations 6 2 33 e T isa linear transformation on the vectors e T P u T P T u By Extension T preserves affine combinations on the points T a1Q1 me Pe anQn a T Q1 mored anT Qn If a 1 result is a point If Ya 0 result is a vector Observations e Affine transformations map lines to lines TA t Po tP 1 t T Po tT P e Affine transformations map rays to rays T A td T A tT d e Affine transformations preserve ratios of distance along a line converse is also true preserves ratios of such distances affine e Absolute distances or angles may not be preserved Absolute distances and angles are not affine concepts Examples e translations e rotations e scales e shears e reflections Translations and rotations called rigid body motions Affine vs Linear Which is a larger class of transformations Affine or Linear e All affine transformations are linear transformations on vectors e Consider identity transformation on vectors There is one such linear transformation e Consider Translations Identity transformation on vectors Infinite number different ones based on effect on points Thus there are an infinite number of affine transformations that are identity transformation on vectors e What ma
52. and Device Independence 3 1 Calligraphic and Raster Devices Calligraphics and Raster Devices Calligraphic Display Devices draw polygon and line segments directly e Plotters e Direct Beam Control CRTs e Laser Light Projection Systems Raster Display Devices represent an image as a regular grid of samples e Each sample is usually called a pixel picture element e Rendering requires rasterization algorithms to quickly determine a sampled repre sentation of geometric primitives 3 2 How a Monitor Works How a CRT Works Raster Cathode Ray Tubes CRTs most common display device e Capable of high resolution e Good colour fidelity e High contrast 100 1 e High update rates Electron beam scanned in regular pattern of horizontal scanlines Raster images stored in a frame buffer Frame buffers composed of VRAM video RAM VRAM is dual ported memory capable of e Random access e Simultaneous high speed serial output built in serial shift register can output entire scanline at high rate synchronized to pixel clock Intensity of electron beam modified by the pixel value Burst mode DRAM replacing VRAM in many systems Colour CRTs have three different colours of phosphor and three independent electron guns Shadow Masks allow each gun to irradiate only one colour of phosphor Physical Devices 3 2 18 QNPRORANIUANOUANOIAOAIAON Shadow Mask Colour is specified eithe
53. art q 8 0 s vii vag ugk In vector notation product of two quaternions is qdo 182 U1 U2 1U2 S201 U1 X 02 e Quaternions also have conjugates q s 0 The norm of a quaternion is defined by 5 01 o s 402402403 Quaternions 29 6 225 Unit Quaternions e Unit quaternions have unit norms e Isomorphic to orientations e The unit quaternion given by dr cos 0 sin 0 1 is equivalent to a rotation by an angle of 20 around the unit v Note that qr is equivalent to qr when interpreted as an orientation Rotations and Quaternions e Points in space can be represented by quaternions with a zero scalar part e Point P is represented by the quaternion qP 0 P e The rotation of a point P by q is QP r9PG gt e For unit quaternions the inverse is equivalent to the conjugate Advantages of Quaternions e Doing rotation this way is fairly perverse except for three points 1 For many applications the independent definition of an axis of rotation and an angle makes sense 2 The definition of an orientation by a quaternion is coordinate system independent and isotropic 3 Spherical interpolation of quaternions gives better results than interpolation of Euler angles Interpolating Unit Quaternions e Linear interpolation on all the entries of the quaternion does not have unit norm Angular velocity is not constant if we renormalize e Spherical linear interpolatio
54. ay tracing is slow e Ray intersect object is often expensive e Improve speed two ways Reduce the cost of ray intersect object Intersect ray with fewer objects Bounding Boxes e Idea Place a bounding box around each object e Only compute ray intersect object if the ray intersects the bounding box Bidirectional Tracing 19 137 e If box aligned with coordinate axes ray intersect box is very cheap e Be careful with CSG Hierarchical e Can also use bounding spheres e Most useful when ray intersect object is VERY expensive Example polygonal object with lots of facets e Construction of good bounding box can be difficult Spatial Subdivision e Idea Divide space in to subregions e Place objects from scene in to appropriate subregions e When tracing ray only intersect with objects in sub regions through which the ray passes e Useful when lots of small objects in scene e Determining subdivision is difficult Bidirectional Tracing 19 138 20 BIDIRECTIONAL TRACING 20 Bidirectional Tracing 20 1 Missing Effects e Problem Raytracing and radiosity can t model all effects POS Sl A ma oer ae a e s s 3 s s s s 3 s s A Lens E Caustics o e Some effects requiring tracing light rays from light back to eye e Too many to trace them all How do we select 20 2 Distribution Ray Tracing e Ray trace but at each reflection cast a l
55. cit surfaces quadrics blobbies etc Other Software renderer may support modelling primitives directly or may convert them into polyg onal or linear approximations for hardware rendering 2 4 Algorithms A number of basic algorithms are needed e Transformation Convert representations of models primitives from one coordinate system to another e Clipping Hidden Surface Removal Remove primitives and parts of primitives that are not visible on the display e Rasterization Convert a projected screen space primitive to a set of pixels Later we will look at some more advanced algorithms e Picking Select a 3D object by clicking an input device over a pixel location e Shading and Illumination Simulate the interaction of light with a scene e Animation Simulate movement by rendering a sequence of frames Devices and Device Independence 2 15 2 5 APIs Application Programming Interfaces APIs Xlib GDI 2D rasterization PostScript PDF SVG 2D transformations 2D rasterization OpenGL Direct3D 3D pipeline APIs provide access to rendering hardware via a conceptual model APIs hide which graphics algorithms are or are not implemented in hardware by simulating missing pieces in software For interactive applications we might modify the scene or a model directly or just the viewing information then regenerate the image Devices and Device Independence 16 3 DEVICES AND DEVICE INDEPENDENCE 17 3 Devices
56. ck facing 1 Redraw with light off When more than one polygon ly SS lt E lt Single Polygon Screen Screen Screen Silhoutte Multiple Polygons e Draw shadow faces only for silhouette edges of polyhedra Problem have to detect silhouette edges e Draw shadow volume for each polygon facing away from light Shadow face for two polygons sharing an edge cancel Only silhouette edges have only one of front back pair Downside a lot more drawing than needed e Lots of drawing modes to get right Modeling of Natural Phenomena e Infinite polygons OpenGL tweaks can give you this e Light map may help e Problems if viewpoint inside shadow volume e Need to repeat for each light 22 153 Modeling of Natural Phenomena 22 154 23 MODELING OF NATURAL PHENOMENA 23 Modeling of Natural Phenomena 23 1 Fractal Mountains 1 How do we model mountains e Lots of semi random detail e Difficult to model by hand e Idea Let computer generate random effect in controlled manner 2 Start with triangle refine and adjust vertices e At each step of refinement adjust height of vertices e Use scaled random numbers to adjust height ZO h 1 ZA ZO Z1 2 h 2 AS ATA Z3 Z0 Z2 2 h 2 Zl h 1 1 Z2 h 1 Z5 Z1 Z2 2 h 2 Level 0 Level 1 Level 2 3 Details e What to use for h Random number Gaussian distribution scaled based on level Le for deeper level use smaller scale e May want to
57. cs Xerox PARC Shoup 1976 Jim Blinn develops texture and bump mapping 1977 Star Wars CG used for Death Star plans 1979 Turner Whitted develops ray tracing Mid 70 s 80 s Quest for realism radiosity also mainstream real time applications 1982 Tron Wrath of Khan Particle systems and obvious CG 1984 The Last Starfighter CG replaces physical models Early attempts at realism using CG 1986 First CG animation nominated for an Academy Award Luxo Jr Pixar 1989 Tin Toy Pixar wins Academy Award 11 Pipeline 2 1 12 1995 Toy Story Pixar and Disney the first full length fully computer generated Reboot the 3D animation first fully 3D CG Saturday morning cartoon Babylon 5 the first TV show to routinely use CG models late 90 s Interactive environments scientific and medical visualization artistic rendering image based rendering path tracing photon maps etc 00 s Real time photorealistic rendering on consumer hardware Interactively rendered movies Readings Watt Preface optional Hearn and Baker Chapter 1 optional Red book Foley van Dam et al Introduction to Computer Graphics Chapter 1 optional White book Foley van Dam et al Computer Graphics Principles and Practice 2nd ed Chapter 1 optional 2 2 Pipeline We begin with a description of forward rendering which is the kind of rendering usually sup ported in hardware and is the model OpenGL uses In forward rendering
58. d analytically through a manipulation of the control points e The motion path as a function of time t is thus given by P A 1 f t Problems with Arc Length Parameterization 1 The arc length s A u is given by the integral say EN 2 EN w No analytic solution if the motion path is a cubic spline 2 Since A u has no analytic form A7 s has no analytic form Issues in Real Time Animation e Exact arc length parameterization not feasible e An alternative compute points on the spline at equally spaced parametric values and use linear interpolation along these chords e The linear interpolation should consider the distance between samples to maintain constant velocity Orientation and Interpolation 29 5 222 29 6 Orientation and Interpolation Interpolate angles rather than transformation matrices e In two dimensions only one angle is involved and animation is straightforward e In three dimensions orientation requires three degrees of freedom Interpolation is much nastier and harder to visualize Approaches Two standard approaches to the orientation interpolation problem Both related to problem of specifying orientation in the first place Euler angles Three angles x roll followed by y roll followed by z roll Has defects parameterization singularities anisotropy gimbal lock unpredictable inter polation Hard to solve inverse problem given orientation what are the ang
59. do first step manually Triangular grid place peaks and valleys e Could use different h functions to simulate different effects e Automatic colour generation high white medium brown low green 4 Results e Not physically based but e Look good for little work e Don t look at from directly overhead Readings Red book 9 5 White book 20 3 References Fornier Fussell Carpenter Computer Rendering of Stochastic Models GIP 1982 Particle Systems 23 2 156 23 2 L system Plants 1 L systems Context free plants 2 Idea Model growth structure of plant as CFG 3 CFG Symbols rules e A B C D e A gt CBA B gt BD 4 Start symbol A A CBA CBDCBA gt CBDDCBDCBA 5 Plants need more complex L systems geometry e Thickness e Semi random 3D branching e Leaf model 6 Top three things to make it look good Texture mapping Texture mapping Texture mapping 7 Plants don t grow like this e Grow from top up outside out e Respond to environment context sensitive e Interact with each other 23 3 Particle Systems e How do we model fuzzy objects Objects with soft boundary changing boundary chaotic behavior Examples Clouds fire water grass fur e Could texture map fuzziness but changing shape is hard e Another way is with Particle Systems Basic idea model fuzzy objects as large collection of particles Used to model Genesis effect in Th
60. e Haar often used in practice because it s simple cheap Wavelet Compression e Lossless image compression how do we represent an image using as few bits as possible Pigeon hole principle tells us we ve lost before we start Have to have expectations about image before you can achieve any compression Lossy compression involves two main steps Losing part of the data and then performing lossless compression on what s left e Can use wavelets to perform simple lossy part of compression If we order coefficients in decreasing magnitude then error is minimized 2D Haar and Image Compression e Standard decomposition Apply 1 D Haar to each row Then apply 1 D Haar to each column e Nonstandard decomposition Apply one step of 1 D Haar to each row Then apply one step of 1 D Haar to each column Repeat on quadrant containing averages in both directions e Image compression in similar fashion except it s expensive to sort coefficients 28 NON PHOTOREALISTIC RENDERING 209 28 Non Photorealistic Rendering 28 1 2D NPR e Traditional goal of computer graphics is photorealism e Accurate depiction of reality isn t always the real goal e How can computer graphics help us visualize communicate create art e We ll look at some applications of computer graphics in the creation of art Painterly rendering e Idea create a painterly interpretation of a photograph e Starting with a source image apply a model of strok
61. e Must get 9 10 on A4 to do ray tracing project e Easier to come up with objective list e Design objectives around a scene Photograph or real object you want to ray trace e Nice scene must be one objective Describe it Other Stuff e Technical outline should clarify objectives e You can start before you get proposal back Avoid dynamic memory e See TAs if you have problems Don t spend 2 days hacking at it e If running out of time prof or TA can give advice on what objectives to tackle e Project is marked on objective list of revised proposal
62. e Need an area primitive e Simple polygon Planar set of ordered points v9 Un 1 sometimes we repeat vo at end of list No holes No line crossing Y OK Line Crossing Hole e Normally define an interior and exterior Points ordered in counter clockwise order To the left as we traverse is inside 2 4 3 1 0 e Try to avoid degeneracies but sometimes unavoidable 4 7 3 1 4 2 A S T 4 0 3 1 2 0 4 0 5 0 1 2 3 Polygon Clipping 11 1 76 e Convex and Concave polygons Polygon is convex if for any two points inside polygon the line segment joining these two points is also inside Convex polygons behave better in many operations e Affine transformations may introduce degeneracies Example Orthographic projection may project entire polygon to a line segment 11 2 Polygon Clipping Polygon Clipping Sutherland Hodgman e Window must be a convex polygon e Polygon to be clipped can be convex or not Approach e Polygon to be clipped is given as v1 Un e Each polygon edge is a pair v v 1 i 1 0 Don t forget wraparound v v1 is also an edge e Process all polygon edges in succession against a window edge Polygon in polygon out U1 Un gt W Wm e Repeat on resulting polygon with next sequential window edge Contrast with Line Clipping e Line Clipping Clip only against possibly intersecting window edges Deal with window
63. e Question How do we decide what was picked We could do the work ourselves x Map selection point to a ray Intersect with all objects in scene Let OpenGL graphics hardware do the work e Idea Draw entire scene and pick anything drawn near the cursor Only draw in a small viewport near the cursor Just do clipping no shading or rasterization Need a method of identifying hits OpenGL uses a name stack managed by glInitNames glLoadName glPushName and glPopName Names are unsigned integers When hit occurs copy entire contents of stack to output buffer e Process Set up pick buffer Initialize name stack May need glPushName 1 Save old projective transformation and set up a new one Draw your scene with appropriate use of name stack Restore projective transformation Query for number of hits and process them e A hit occurs if a draw occurs in the small viewport e All information except hits is stored in buffer given with glSelectBuffer e Example Two objects Might pick none Might pick either one Might pick both Picking and 3D Selection 14 0 98 glSelectBuffer size buffer initialize glRenderMode GL_SELECT glInitNames glPushName 1 glGetIntegerv GL_VIEWPORT viewport set up pick view glMatrixMode GL_PROJECTION glPushMatrix glLoadIdentity
64. e Wrath of Kahn Particle Systems 23 2 157 e Animate fuzzy or gaseous objects as a changing cloud of particles e Aim for overall effects by having many simple particles e Each particle has properties Geometry point sphere line segment Position Velocity vector Size Colour Transparency State Lifetime Animating Particles Systems e New particles are born old ones die e State information describes type of particle e At each time step based on state Update attributes of all particles Delete old particles Create new particles Display current state of all particles To anti alias draw line segment from old position to new position To draw grass or fur draw entire trajectory of particle Radiosity Particle System Details Easy to implement state machine Hard part is determining how to make particles act Particles usually independent Don t know about one another Often will model gravity when updating particles Render fire etc using transparency Brighter where particle system denser 23 158 24 RADIOSITY 159 24 Radiosity 24 1 Definitions and Overview Radiosity Radiosity Diffuse interaction of light e Ambient term is an approximation to diffuse interaction of light e Would like a better model of this ambient light e Idea Discretize environment and determine interaction between each pair of pieces e Models ambient light under fo
65. e truncated viewing pyramid But the plane equations are simpler if we clip after projection because all sides of volume are parallel to coordinate plane e Clipping to a plane in 3D is identical to clipping to a line in 2D e We can also clip in homogeneous coordinates Readings Red Book 6 6 4 White book 6 5 4 9 5 Homogeneous Clipping Homogeneous Clipping Projection transform and homogenize e Linear transformation nr 0 0 0 x x 0 ns 0 0 y y 2 E 0 0 fin Le z Z 0 0 1 0 1 w e Homogenization z z X AE A z Z w Z w 1 1 Region mapping Homogeneous Clipping ollo lo 1 1 Clipping not good after homogenization e Ambiguity after homogenization T 1 lt 2 ES IA amp e Numerator can be positive or negative Denominator can be positive or negative e Normalization expended on points that are subsequently clipped Clip in homogeneous coordinates e Compare unnormalized coordinate against w w0 lt 3 9 2 lt El Clipping Homogeneous Coordinates e Assume NDC window of 1 1 x 1 1 9 4 66 Pinhole Camera vs Camera vs Perception 9 5 67 e To clip to X 1 left Projected coordinates Clip to X 1 Homogeneous coordinate Clip to z w 1 Homogeneous plane w 7 0 WwW Point is visible if w 7 gt 0 e Repeat for remaining boundaries X 2 0 Y y w 1 Sy Dl Nea
66. ect Nonlinear transformation New coordinates for every point in space are determined as functions of the old coordi nates Process 1 Place rectangular squish box object to be animated 2 The coordinates of all points within the box are determined relative to the frame given by the box Suppose a vertex P can be expressed as u v w relative to the coordinates of the box 3 The new coordinates of P are given by a tensor product B zier spline B 2 23 u v w with control points P j k 4 If the P j k have coordinates P jk i ma 1 j n2 1 k n3 1 the transformation is given by the identity Ju v w BPs u v w Normally the control points are initially set to these values and are moved to effect a defor mation FFD Issues e Continuity conditions can be enforced Example A hand is being deformed but the arm is not The control points along the edge of the box that cuts the wrist should not be moved nor the next layer This maintains both position and derivative continuity across the wrist e The object should be finely tesselated or radical deformations will not work properly e Not volume preserving For realistic animation typically only small deformations are used e Modeling UI non trivial Manipulating control points inadequate Kinematics and Inverse Kinematics 29 9 229 Skeletons and FFDs e Skeletons and free form deformations can be used simultaneously e The numb
67. ecular 32 blue diffuse material float4 diffuseMaterial float4 0 0 0 0 1 0 1 0 white specular material float4 specularMaterial float4 1 0 1 0 1 0 1 0 18 3 120 Sh 18 4 121 combine diffuse and specular contributions and output final vertex color Dut Color0 diffuse diffuseMaterial specular specularMaterial return Out 18 5 Sh e Sh embeds the shading language in a C API e Developed at the University of Waterloo API independent OpenGL or DirectX e Compiles at runtime Can also generate code for host CPU Can also be used for general purpose computation e Web page http libsh org Sh example following Cg example Have to define global parameters a little more general than Cg shader have converted hard coded values to parameters transformation matrices ShMatrix4x4f ModelViewProj ShMatrix4x4f ModelViewIT light direction vector ShVector3f LightVec blue diffuse material ShColor4f diffuseMaterial 0 0 0 0 1 0 1 0 white specular material ShColor4f specularMaterial 1 0 1 0 1 0 1 0 specular power ShAttribif spec_power 32 ShProgram vs SH_BEGIN_PROGRAM gpu vertex ShInputPosition4f position ShInputNormal3f normal ShOutputPosition4f Hposition ShOutputColor4f Color0 Hposition ModelViewProj position Ray Tracing 18 122 transform normal from model space to view space normal normalize ModelViewIT normal 0 1 2
68. ed under translation e Translation is NOT a linear transformation e Translation is linear on sums of vectors Matrix representation of translation e We can create a matrix representation of translation T Azx Ay 1 0 Az x Ax 0 1 Ay Y y Ay 00 1 1 1 e T Az Ay will mean the above matrix e Note that vectors are unchanged by this matrix e Although more expensive to compute than the other version of translation we prefer this one Uniform treatment of points and vectors Other transformations will also be in matrix form We can compose transformations by matrix multiply Thus the composite operation less expensive if translation composed too Scale about the origin Specified by factors sz Sy R e Applies to points or vectors is linear Compositions of Transformations 6 5 37 e A point z y 1 7 will map to s 2 syy 1 e A vector x y 0 will map to s 2 syy 01 e Matrix representation S Sm Sy Sy 0 0 x Soh 0 sy 0 Y SyY 0 0 1 0 or 1 0 or 1 Rotation Counterclockwise about the origin by angle 8 e Applies to points or vectors is linear e Matrix representation RO _ TF 2 cos 0 sin 0 0 x z sin 9 cos 0 0 y y 0 0 1 0 or 1 0 or 1 Shear Intermixes coordinates according to a 3 ER e Applies to points or vectors is linear e Matrix representation Sh a 8 180 x xz By a 1 0 Y ar y 0 0 1 0 or 1 0 or 1 e Easiest to see if we set one of a or 8 to zer
69. edges in any order Deal with line segment endpoints in either order e Polygon Clipping Each window edge must be used Polygon Clipping 11 1 77 Polygon edges must be handled in sequence Polygon edge endpoints have a given order Stripped down line segment window edge clip is a subtask Notation e s v is the polygon edge starting vertex e p 0 1 is the polygon edge ending vertex e i is a polygon edge window edge intersection point e wj is the next polygon vertex to be output There are four cases to consider Case 1 Polygon edge is entirely inside the window edge e p is next vertex of resulting polygon ep uwjandj 1l j Inside Outside p output Case 1 Case 2 Polygon edge crosses window edge going out e Intersection point i is next vertex of resulting polygon ei wjandj l j Polygon Clipping 11 1 78 Inside Outside i output Case 2 Case 3 Polygon edge is entirely outside the window edge e No output Inside Outside p no output Case 3 Case 4 Polygon edge crosses window edge going in e Intersection point i and p are next two vertices of resulting polygon e i wj and p gt wj and j 2 gt j Polygon Scan Conversion output 2 P Inside i output 1 An Example With a non convex polygon Outside S aS s4 i29 Z wel t4 ssy lp WE e s2 de sl t5 ue WA ve Ai l u2 AA
70. eed to know which one is in front e This map loses all z information so it is inadequate Pseudo OpenGL version of the perspective map e Maps a near clipping plane z n to z 1 Projections 9 0 59 e Maps a far clipping plane z f to 2 1 1 1 1 E 1 1 1 f e The box in world space known as truncated viewing pyramid or frustum Project x y as before To simplify things we will project into the z 1 plane Derivation e Want to map zx to 1 z and similarly for y e Use matrix multiply followed by homogenization 1 0 0 O x x 0 1 0 0 yY _ Y 00a c z E az c 0064 1 bz d x bz d y bz d aZ C bz d 1 e Solve for a b c and d such that z n f maps to z 1 1 e Satisfying our constraints gives us 10 0 0 x 01 0 0 y y in 2 n 2 owe le aes 0 0 1 0 1 2 e After homogenizing we get 2 y Af n 2fn son zz dfn Why Map Z 9 1 60 e Could use this formula instead of performing the matrix multiply followed by the division e If we multiply this matrix in with the geometric transforms the only additional work is the divide The OpenGL perspective matrix uses a 2 and b 1 OpenGL looks down z 1 rather than z 1 Note that when you specify n and f they are given as positive distances down z 1 e The upper left entries are very different OpenGL uses this
71. eel strike Repeat Sensor Actuator Networks e Hip movement rotation e Hip rotation requires knee flexion e Ankle toe joints e Can animate leg motion by specifying angles of all joints as function of time 29 13 Sensor Actuator Networks Sensor Actuator Networks e van de Panne e Model creature as set of Links Sensors Actuators e SAN relates sensors and actuators e Control uses sensor data to apply forces thru actuators Links e Rigid e Have mass e May restrict to planar for simplicity Sensors 4 types e Touch picture e Angle picture e Eye used to find target Length picture Actuators e Length linear push pull points max min strength e Angle create torques max min angle strength Motion e Evaluation metric Distance traveled Don t fall over e Generate random controllers and evaluate with metric e Try lots and fine tune the best 29 12 233 Morphing 29 13 234 SAN Example 29 14 Morphing e Morphing is lerping between images e Nice effects at low cost e Key issues Partitioning images into pieces that correspond E g eyes to eyes etc Lerping pieces geometry Lerping pieces pixels colours Filtering e Developed at NRC in the 1970 s line drawings e Make it quick don t look too closely at intermediate images Motion Capture e Simplest morph linearly interpolates each point Mostly okay but can cause probl
72. egments PP RP and QP SP cross e The map an yn zf 2zn 2fn Gey 21 ER gt 3 ge 2 f n does map lines to lines and it preserves depth information 1 9 3 Mapping Z Mapping Z e It s clear how x and y map How about z Mapping Z e The z map affects clipping numerics zf zn 2fn Tara A e We know P f 1 and P n 1 What maps to 0 P z 0 zftren 2fn _ gt Tam 70 2fn gt z f n Note that f fn gt 2fn gt fn n so 2fn gt gt n e What happens as z goes to 0 or to infinity A 2fn ee 2 f n 00 2fn A Fan 00 _ z f n SS E sien ron E _ f n H Pictorially we have 9 2 63 9 2 64 Mapping Z 2fn 0 n f n f 00 00 V 0 7 00 1 0 1 f n f n e What happens if we vary f and n e o z f n 2fn a 2zn 2n z 0 z 2n a z e o zf my GF e What happens as f and n move away from each other Look at size of the regions n 2fn f n and 2fn f n fl e When f is large compared to n we have 2fn So 3D Clipping 9 3 65 and 2fn 7 f 2n But both intervals are mapped to a region of size 1 9 4 3D Clipping 3D Clipping e When do we clip in 3D We should clip to the near plane before we project Otherwise we might attempt to project a point with z 0 and then x z and y z are undefined e We could clip to all 6 sides of th
73. emes e Boundaries are handled using different rules e Special rules to add creases to surface e Major implementation issue is data structure e Extraordinary vertices pose difficulties Valence other than 4 in quad mesh Valence other than 6 in tri mesh e Mathematics behind the schemes is far more elaborate than the schemes themselves e Parameterizations needed for texture mapping e Normals Wavelets 27 8 205 27 9 Wavelets Wavelets are a discrete form of Fourier series e Take a discrete signal image e Decompose it into a sequence of frequencies e Use compact support basis functions rather than infinite support sin and cos e Construct a vector space using unit pixels as basis elements piecewise constant functions e Average to get low frequencies e Construct detail functions to recover detail Unit pixel bases form nested sequence of vector spaces with the detail functions wavelets being the difference between these spaces 1 D Haar e Suppose we have the coefficients 973 5 where we think of these coefficients as 1 D pixel values The simplest wavelet transform averages adjacent pixels leaving 8 4 e Clearly we have lost information Note that 9 and 7 are 8 plus or minus 1 and 3 and 5 are 4 minus or plus one These are our detail coefficients 1 Wavelets 27 8 206 e We can repeat this process giving us the sequence Resolution Averages Details 4 9 7 3 5 2 8 4 1 1 1 6
74. ems Often tweak by hand to get rid of such problems e More sophisticated morphs introduce other problems e Desired properties Vertex trajectories smooth and continuous Triangles don t cross each other Minimize triangle size variations Linear when other properites not violated 29 15 Motion Capture 29 14 235 e Keyframing complex actions walking etc requires a lot of key frames e Instead capture motion from real objects Creatures and or actors performing the desired motion e The positions of key points on the actor are tracked these motions are mapped to corresponding points in the model tracking is expensive e Tracking technologies include 1 Electromagnetic position and orientation sensors May be necessary to generate secondary actions for the computer model Flocking 29 15 236 Requires a wire to each sensor Readings can be distorted by metal and magnetic fields Limited working volume Ultrasonic rangefinder triangulation Cheaper but less accurate than magnetic sensors Optical triangulation Reflective or emissive markers are attached to objects Two cameras triangulate position Can track more points cheaply without wires Points can be occluded Body suit Fibers in instrumented clothing detect angles of all joints Rotoscoping Arbitrary video from two cameras converted to motion paths manual selection of key points computer visi
75. en pixel e Interpretations Ray is the path of photons that succesfully reach the eye we simulate selected photon transport through the scene Ray is a sampling probe that gathers color visibility information Y 9 scene screen Readings Watt 12 1 Red book 14 7 White book 16 12 19 2 Intersection Computations Intersection Computations General Issues e Ray express in parametric form E t P E where F is the eyepoint and P is the pixel point e Scene Object direct implicit form express as f Q 0 when Q is a surface point where fis a given formula intersection computation is an equation to solve find t such that f E t P E 0 e Scene Object procedural implicit form fis not a given formula fis only defined procedurally A f E t P E 0 yields t where A is a root finding method secant Newton bisection Quadric Surfaces Surface given by Ax Bay Cez Dy Eyz F22 Gr Hy Jz K 0 Intersection Computations 19 1 125 2 2 2 O e Ellipsoid a nas 2 2 Ellipsoid Elliptic paraboloid a 53 l P q Elliptic paraboloid L y 2 Hyperboloid of one sheet 5 3z 1 a b c Hyperboloid of one sheet 2 2 2 y RS es e Cone Pa 0 Cone 2 2 e Elliptic cylinder 1 P q Elliptic cylinder Ray given by tE t xp LE ye t yp yz ze t zp Zp Substitute ray x y z into surface formula quadratic equation resu
76. er may be anywhere and looking in any direction Often x to the right y up and z straight ahead x zis called the viewing direction This is a left handed coordinate system We could instead specify z and y as vectors x zis the the view direction x y is the up vector x Compute z y X z x Get a right handed coordinate system We can do a change of basis Specify a frame relative to the viewer Change coordinates to this frame e Once in viewing coordinates Usually place a clipping box around the scene Box oriented relative to the viewing frame View Frame e An orthographic projection is made by removing the z coordinate World and Viewing Frames 6 9 45 Squashes 3D onto 2D where we can do the window to viewport map The projection of the clipping box is used as the window e Mathematically relative to gt Fy 1 5 k O we map Q q1 02 q3 1 onto Festir as follows Ortho q q27 q3k O qt g7 O or if we ignore the frames l1 42 93 11 gt q1 q2 1 e We can write this in matrix form q 1000 q ol lo100 42 1 0001 A e Question why would we want to write this in matrix form Viewing World Modelling Transformations e Want to do modelling transformations and viewing transformation as in Assignment 2 e If V represents World View transformation and M represents modelling transformat
77. er of control points in a free form deformation can be large e If moved in groups relative to skeleton excellent animation control can be obtained for arbi trary models 29 10 Kinematics and Inverse Kinematics Kinematics and Inverse Kinematics Kinematics The study of motion independent of the forces that cause the motion Includes position velocity acceleration Forward kinematics The determination of the e positions e velocities e accelerations of all the links in an articulated model given the e position e velocity e acceleration of the root of the model and all the transformations between links e Forward kinematics is a necessity for skeletal keyframed animation e Easy to implement Inverse kinematics The derivation of the motion of intermediate links in an articulated body given the motion of some key links Inverse Kinematics e Often nonlinear underdetermined or overdetermined possibly ill conditioned e Complexity of determining solution proportional to number of free links e One free joint between two fixed ones can be solved fairly efficiently for example with only one spare degree of freedom e Extra constraints may be needed to obtain a unique and stable solution Example Requiring a joint to point downwards as a gross approximation to gravity Joint motion constraints hinge vs revolute vs ball are also useful Physically Based Animation 29 10 230 e Additional optimizatio
78. es in model space and store forward transform using modeling transformations Shading 19 2 127 19 3 Shading Shading shadows e How do we use ray to determine shade of pixel e At closest intersection point perform Phong shading Gives same images as polygon renderer but more primitives e Idea Before adding contribution from a light cast ray to light If ray hits object before light then don t shade This gives shadows A 1 x wa te 2 ales A A s v N i wf E gt N fe A DS N AS ae 7 Y N oF Di N NZ ie Reflections e Idea Cast a ray in the mirror direction e Add the colour coming from this ray to the shade of the initial ray e This gives mirror reflections VA aoe ais he ON e We perform a full lighting calculation at the first intersection of this reflected ray Recursive Ray Tracing 19 3 128 Readings Watt 12 1 19 4 Recursive Ray Tracing Ray Tracing Recursive e Eye screen ray is the primary ray e Backward tracking of photons that could have arrived along primary e Intersect with all objects in scene e Determine nearest object e Generate secondary rays to light sources in reflection associated directions in refraction associated directions e Continue recursively for each secondary ray e Terminate after suitably many levels e Accumulate suitably averaged information for primary ray e Deposit information i
79. es to approximate it e Possible goals Closeness of approximation Use as little paint number of strokes total stroke length as possible Coverage of canvas Paint by Relaxation Could try to optimize directly but it s easier to have a kind of greedy approach painting a sequence of strokes 4 photographer images Paint by numbers Haeberli SIGGRAPH 1990 e Interactive stroke placement random displacement from pointer position e Stroke colours sampled from source image 3 face images http thinks com java impressionist Extensions Stroke orientation 2D NPR 28 0 210 Extensions Painterly rendering with curved brushstrokes of multiple sizes Hertzmann SIGGRAPH 1998 e Create painting in layers coarse to fine strokes fill in detail where it s needed e Pick a set of stroke locations draw strokes where painting is unlike source image e Long curved strokes flow along contours of constant colour perpendicular to image gradient e Large set of intuitive customizable parameters to create painting styles e g max stroke length Fast paint texture Hertzmann NPAR 2002 e Can also render a secondary bump map by drawing stroke texture instead of solid colour e Bump map colour image using stroke texture image 4 stroke images 4 palm tree images 6 skeleton images 2D NPR 28 0 211 Stylization and abstraction of photographs Santella and DeCarlo SIGGRAPH 2002 e Stroke models follow image features
80. etail by increasing model complexity then computation cost increases e If detail is surface detail then we can use texture mapping e Idea scan a photo of the detail and paste it on objects Associate texture with polygon Map pixel onto polygon and then into texture map Use weighted average of covered texture to compute colour ZL n Pixel Texture Map Surface polygon e Tile polygon with texture if needed For some textures tiling introduces unwanted pattern Various method to extend textures e Greatly improves images e Not just ray traced image Texture Mapping 19 6 134 Bump Mapping e Textures will still appear smooth i e no shadows e Bump mapping is similiar to texture mapping except that we peturb the normal rather than the colour MASIA VA AL NCAA E e Perturbed normal is used for lighting calculation e Convincing usually fail to notice silhouette is wrong Texture Mapping 19 6 135 Solid Textures e 2D textures can betray 2D nature in images e Hard to texture map onto curved surfaces e Idea Use a 3D texture instead e Usually procedural Example if floor x floor y floor z 2 0 then return RED else return SILVER end Gives a 3D checker board e Turbulence can also be simulated marble Bounding Boxes Spatial Subdivision 19 7 136 Readings Watt 8 19 8 Bounding Boxes Spatial Subdivision Speed ups e R
81. ever r attenuation looks too harsh Harshness because real lighting is from area sources multiple reflections in environment True point sources impossible Commonly we will use gt I L 4 in 4 cy cor c3r e Note that we do NOT attenuate light from P to screen Surface foreshortening when farther away takes care of that Pixel Eye The pixel represents an area that increases as the square of the distance 16 4 Coloured Lights Multiple Lights and Ambient Light Coloured Lights Multiple Lights and Ambient Light e To get coloured lights we perform lighting calculation three times to get an RGB triple Specular Reflection 16 4 107 e More correct to use spectra and better approximations to spectra exist but RGB sufficient for now e To get multiple lights compute contribution independently and sum 5 G n L v o lL out 0 da i ey cor car e Question what do pictures with this illumination look like Ambient Light e Lighting model so far is still too harsh e Problem is that only direct illumination is modeled Global illumination techniques address this but are expensive e Ambient illumination is a simple approximation to global illumination e Assume everything gets uniform illumination in addition to direct illumination lion C1 cari Car Lout 0 Kola De pv 6 I 16 5 Specular Reflection Specular Reflection e Lambertian term models matte s
82. fix vertex gt edge pointers e gt v gt rep e gt sym gt prev e gt sym gt v gt rep e gt prev DeleteFace e gt sym gt f DeleteEdge e e Manifolds with Boundary Half edge allows representation of manifold w boundary Set sym pointer to NULL Allows for lone face Makes some constructions easier e Duality Faces and vertices are dual Representations and r les are identical Can replace each face with a vertex and each vertex with a face 26 2 183 Splines 26 184 If boundaries then dual may not be manifold e Evaluation Faces with arbitrary number of sides Vertices with arbitrary number of neighbours Iterate over everything Not space efficient Painful to write debug code Simpler data structure better unless you need to modify iterate e API Discussions in papers use low level operators Better if user of package does NOT manipulate pointers Higher level safe operators iterators x ForeachMeshVertex ForeachFaceVertex Split 3 1 RemoveEdge Example Split all faces 3 1 ForeachMeshFace m f 4 p SplitFace3to1 f SetPosition P x y zZ Which operations should we provide 27 SPLINES 185 27 Splines 27 1 Constructing Curve Segments Constructing Curve Segments Linear blend e Line segment from an affine combination of points P t 1 t Po tP t 1 t oe ee aia NAS ee RA I O gt 1 Py P 0 P Q
83. ge from coordinates relative to F to coordinates relative to F gt Change of Basis 6 6 39 Know P p x y 1 relative to Fy 5 w2 Ow Want the coordinates of P relative to Fy 01 02 Oy How do we get fij e If F is orthonormal fig Wj Gi fis Ow Oy Ti e If F gt is orthogonal B fj Ui Ui Ow Oy fi E Ui Ui e Otherwise we have to solve a small system of linear equations using Fy F2 M1 2 e Change of basis from Fi to Standard Cartesian Frame is trivial since frame elements normally expressed with respect to Standard Cartesian Frame Example vl w2 P 1 1 1 T w v w1 Ov 311 T Ow wl Ambiguity 6 7 40 where Fw is the standard coordinate frame Generalization to 3D is straightforward Example e Define two frames Fw ti we w3 Ow 1 0 0 0 7 0 1 0 0 E 0 O 1 0 0 0 0 1 Fy 2 03 Ov V2 2 0 V2 2 1 v2 2 0 y2 2 0 7 0 a ee ie 0 an ES 0 0 0 1 e All coordinates are specified relative to the standard frame in a Cartesian 3 space e In this example Fy is the standard frame e Note that both Fw and Fy are orthonormal e The matrix mapping Fw to Fy is given by v2 2 v2 2 0 0 v2 2 V 2 2 0 0 y2 2 3 2 2 1 ooreo e Question What is the matrix mapping from Fy to Fw Notes e On the computer frame elements usually specified in Standard Frame for space Eg a frame F v2 Oy is given by
84. gs White book Appendix A 6 4 Matrix Representation of Transformations Matrix Representation of Transformations Represent points and vectors as n x 1 matrices In 2D y II jo I P2 U1 U2 S IIl lt I This is a Shorthand Coordinates are specified relative to a frame F tj U2 Oy P 51 V2 Oy P2 1 P Fp Technically e Should write the p as pr e The frame F should note what space it s in Usually we re lazy and let p denote both e The point e Its matrix representation relative to an understood frame Transformations e F4 U1 02 Oy is the frame of the domain e Fp W1 W2 Ow is the frame of the range Then P p transforms to p Mp Geometric Transformations 6 4 36 Can also read this as F4 Fg Mr Mr is said to be the matrix representation of T relative to F4 and Fp e First column of Mr is representation of T v in Fp e Second column of Mr is representation of T 02 in Fp e Third column of Mr is representation of T Oy in Fg 6 5 Geometric Transformations Geometric Transformations Construct matrices for simple geometric transformations Combine simple transformations into more complex ones e Assume that the range and domain frames are the Standard Frame e Will begin with 2D generalize later Translation Specified by the vector Az Ay 0 e A point z y 1 will map to z Az y Ay 1 e A vector will remain unchang
85. he gray points we can compute the black points YY e Thus for C cubic B zier spline need only one control point per segment plus two more at start and end Tensor Product Patches e From gray points we can recover B zier control points e The gray points are B spline control points Evaluating B splines e Cubic B splines give us C continuity for little effort e To evaluate a B spline we could convert to B zier and evaluate the B zier curves e There is also a de Casteljau style evaluation The de Boor algorithm e Thus far have considered the case for intervals 0 1 0 2 i e integers One polynomial over each interval e In general B splines can go over arbitrary intervals to t1 t1 to where to lt ti lt t2 lt ti are called knots e B splines have different basis functions 27 5 Tensor Product Patches e Control polygon is polygonal mesh with vertices P j e Patch basis functions are products of curve basis functions Piat y y P Bi5 s t i 0 j 0 where B s t B s BF t AN SS ATATA WY P WN NOR KORN x STARE SA bis ary ASS y y NN f SS ANAS Tensor Product Patches 27 4 196 The Teapot Properties e Patch basis functions sum to one n n 2 2 Bis BF 1 i 0 j 0 e Patch basis functions are nonnegative on 0 1 x 0 1 B s B t 20 for 0 lt s t lt 1 gt Surface patch is
86. ication Clipping 8 0 55 e Window edge implicit Q Q P e Line segment parametric L t A t B A Do the easy stuff first We can devise easy and fast tests for the first two cases e L A lt 0 AND B lt 0 gt Outside e A gt 0 AND B gt 0 gt Inside Need to decide are boundary points inside or outside Trivial tests are important in computer graphics e Particularly if the trivial case is the most common one e Particularly if we can reuse the computation for the non trivial case Do the hard stuff only if we have to If line segment partially in partially out need to clip it e Line segment from A to B in parametric form Lt 1 tA tB A t B A e When t 0 L t A When t 1 L t B e We now have the following 7 k WLS LLL L t A t B A n Recall Q Q P e We want t such that L t 0 L t P A t B A P A P R B A e Solving for t gives us Il Su Sy Projections and Projective Transformations 8 56 e NOTE The values we use for our simple test can be reused to compute t A P A P R B P Clipping a line segment to a window Just clip to each of four halfspaces in turn Pseudo code here wec window edge coordinates Given line segment A B clip in place for each edge P n wecA A P n wecB B P n if wecA lt O AND wecB lt O then reject if wecA gt 0 AND wecB
87. ics hardware has displaced work station graphics Good inexpensive cards for PCs Currently getting faster in excess of Moore s law Many graphics cards are more powerful than CPU in floating point Can be used for general purpose computation too PCI express makes graphics accelerators like coprocessors Traditional OpenGL 1 2 transformed f textured vertices vertices ragments fragment gi ona CR rasterize texturing composite lighting texcoords clipping colour texture memory frame buffer A fragment is a sort of virtual pixel fragment carries colour that is composited onto pixel in frame buffer if it passes depth stencil and alpha tests Clipping done in transform lighting portion Graphics Hardware 18 0 116 OpenGL 2 0 vertex program fragment program f transformed shaded vertices vertex vertices e fragments fragment fragment anipe S AA rasterize A shader e ndal shader clipping texcoords2 prim colour send colour texture memory frame buffer e Vertex Shader and Fragment Shader are programmable by application GeForce 3 4 e 100 s of lines of assembly for vertex shader floating point 4 tuple e Configurable pipeline for fragment shader 4 texture shader stages floating point 8 register combiner stages 10 bit signed int ATI 9700 e 1000 s of lines of assembly for both vertex
88. iff they are defined by differences of points Transforming Normal Vectors Consider non uniform scale of circle and normal to circle Windows Viewports NDC 6 48 A oe Scale 1 2 Why doesn t normal transform correctly Normal vectors ARE NOT defined by differences of points formally they are covectors which are dual to vectors Tangent vectors ARE defined by differences of points Normals are vectors perpendicular to all tangents at a point N T n t 0 Note that the natural representation of N is as a row vector Suppose we have a transformation M a point P p and a tangent T tat P Let My be the linear part of M i e the upper 3 x 3 submatrix p Mp t Mt Met nt n M7 Met Mn Met mt NP Transform normals by inverse transpose of linear part of transformation n My Th If Mr is O N usual case for rigid body transforms M77 Mr Only worry if you have a non uniform scale or a shear transformation Transforming lines Transform implicit form in a similar way Transforming planes Transform implicit form in a similar way Readings Red Book 5 8 White Book 5 6 7 WINDOWS VIEWPORTS NDC 49 7 Windows Viewports NDC 7 1 Window to Viewport Mapping Window to Viewport Mapping Start with 3D scene but eventually project to 2D scene 2D scene is infinite plane Device has a finite visible rectangle What do we do Answer map rectangular region of 2D device
89. imensional spaces 5 2 Affine Spaces Affine Space Definition Set of Vectors V and a Set of Points P e Vectors Y form a vector space e Points can be combined with vectors to make new points P U gt Q with PQ eP and ue V Frame An affine extension of a basis Requires a vector basis plus a point O the origin F v1 tos ese Un O Dimension The dimension of an affine space is the same as that of V Cartesian Space 5 3 28 5 3 Euclidean Spaces Euclidean Spaces Metric Space Any space with a distance metric d P Q defined on its elements Distance Metric e Metric d P Q must satisfy the following axioms aP Q gt 0 d P Q 0 iff P Q d P Q d Q P 4 d P Q lt d P R d R Q e Distance is intrinsic to the space and not a property of the frame w Ne Euclidean Space Metric is based on a dot inner product d P Q P Q P Q Dot product 1 0 0 U U 0U Y a u 1 a g av Uv T Norm u vi Angles u y cos 4uv lullu Perpendicularity u v 0 gt 4u L4u Perpendicularity is not an affine concept There is no notion of angles in affine space 5 4 Cartesian Space Cartesian Space Cartesian Space A Euclidean space with an standard orthonormal frame 7 7 k O gt gt Orthogonal 7 7 7 k k T 0 Normal 7 7 k 1 gt Notation Specify the Standard Frame as Fs 7 7 k O As defined previously
90. in 2 and the question has no meaning 1 B Consider the meaning of P P 1 P P 0 2 P P y Qpi pi po pa pr 3 P P has no meaning To fully specify a transformation we need 1 A matrix 2 A domain space 3 A range space 4 A coordinate frame in each space 6 9 3D Transformations 3D Transformations Assume a right handed coordinate system Points P z y z 1 7 Vectors Y x y z 0 7 Translation 1 0 0 Az 010 Ay T Az Ay A2 OIA 000 1 Scale About the origin Ss 0 0 0 O0 sy 0 0 Ssmsw32d 9 9 0 0 0 0 1 World and Viewing Frames Rotation About a coordinate axis cos 0 sin 9 0 R 0 P po i 0 0 0 1 0 0 _ 0 cos sin 0 Rr 9 y sin 9 cos 0 0 0 0 cos 9 0 sin Gh HE 0 Ry 0 sin 0 0 cos 0 0 0 0 Shear see book Reflection see book Composition works same way but order counts when composing rotations y Rx 90 Rz 90 Z x y x y X Z Z y X X Rz 90 Rx 90 y Z Z x Z y Readings Hearn and Baker Chapter 11 Red book 5 7 White book 5 6 6 10 World and Viewing Frames World and Viewing Frames e Typically our space S is a Cartesian space Call the standard frame the world frame The world frame is typically right handed O O O 4000 re Oooo 6 9 43 World and Viewing Frames 6 9 44 Our scene description is specified in terms of the world frame e The view
91. indows e FLTK e AWT e Swing e XUL e UI toolkits recommended for projects Gtkmm GLUT SDL 4 6 Example for Discussion Example for Discussion include lt gtkmm h gt include lt iostream gt void test std cout lt lt Hello World lt lt std endl int main int argc char argv Gtk Main kit argc argv Gtk Window hw hw set_border_width 10 Gtk Button b Click me Geometries 4 25 b signal_clicked connect test hw add b b show Gtk Main run hw 1 Where is the definition of the event 2 What constitutes the event 3 What process is associated with the event 4 Who manages the event loop Geometries 4 26 5 GEOMETRIES 27 5 Geometries 5 1 Vector Spaces Vector Spaces Definition e Set of vectors V e Two operations For y wu V Addition u vE V Scalar multiplication at V where a is a member of some field F i e R Axioms Addition Commutes U U U Addition Associates 0 w U 0 w Scalar Multiplication Distributes a v a av Unique Zero Element 0 i Field Unit Element lu w Span e Suppose B 01 U2 Un e B spans V iff any Y V can be written as 0 Do iti Xia Qu is a linear combination of the vectors in B Basis e Any minimal spanning set is a basis e All bases are the same size Dimension e The number of vectors in any basis e We will work in 2 and 3 d
92. ing in OpenGL e Perform diffuse lighting computation at every vertex in software e Use diffuse brightness as parameter to a one dimensional texture map Map has only two or three colours e Sample the texture with nearest neighbour interpolation deliberately not blended e Could definitely be implemented directly on the GPU as a fragment program celishading Recent work e WYSIWYG NPR SIGGRAPH 2002 e Coherent Stylized Silhouettes SIGGRAPH 2003 e Suggestive Contours SIGGRAPH 2003 Animation 28 216 29 ANIMATION 217 29 Animation 29 1 Overview Computer Animation Animation Rapid display of slightly different images create the illusion of motion Conventional approach Keyframed animation Keyframes inbetween frames Computer Assisted e Human key frames computer inbetweening e Supporting techniques Squish box deformations and skeletons motion capture kinematics and inverse kine matics e Other animation approaches Physically based dynamics constraint based animation procedural animation behav ioral animation 29 2 Traditional 2D Cel Animation Traditional 2D Cel Animation e Traditional animation is labor intensive Start with story board Master artist draws keyframes to define action Sweat shop artists draw inbetween frames to complete animation e A few traditional animation rules Stretch and squash anti aliasing timing secondary actions Exaggeration appeal follow
93. ion then VM transforms from modelling coordinates to viewing coordinates Note M is performing both modelling transformation and Model to World change of basis e Question If we transform the viewing frame relative to viewing frame how do we adjust V e Question If we transform model relative to modelling frame how do we adjust M Viewing Transformations e Assume all frames are orthonormal e When we transform the View Frame by T apply T7 to anything expressed in old view frame coordinates to get new View Frame coordinates World and Viewing Frames 6 9 46 T Trans 1 5 5 C F p 1 5 1 wrtF Pp 50 1 wrt T F T e To compute new World to View change of basis need to express World Frame in new View Frame Get this by transforming World Frame elements represented in old View Frame by T71 e Recall that the columns of the World to View change of basis matrix are the basis ele ments of the World Frame expressed relative to the View Frame e If V is old World to View change of basis matrix then T7 V will be new World to View change of basis matrix since each column of V represents World Frame element and the corresponding column of T V contains T7 of this element Modelling Transformations e Note that the columns of M are the Model Frame elements expressed relative to the World Frame e Want to perform modelling transformation relative to modelling coordinates e If we have previously transf
94. itive CSG The primitives We will want a rich set of primitives How do we specify them e As a canonical primitive X Sphere Scale 2 2 2 Translate x y z e As a transformed canonical primitive Sphere r x y z Cube x y z dx dy dz Cone width height x y z dx dy dz CSG Traversing the transformation tree e After transformation applied primitives will be warped Modeling and CSG 19 5 132 e Rather than intersect ray with warped primitive we transform the ray e On the way down apply inverse transformation to ray e On the way back apply transformation to the point normal Caution see notes on transforming normals E a ot At x Cea Tz Tei at x Ty fea J pe a Primitive CSG Boolean operations e Could apply boolean operations to transformed primitives Problem representation too complex e Idea perform a complete ray intersect object with each primitive This gives us a set of line segment s Next perform boolean operations on line segments A B C D A AB U CD m AB CD AB CD CD AB e Note that if we transform the ray on the way down then we must transform the entire segment on the way back e Also we must be careful with normals they flip for difference Texture Mapping 19 6 133 Examples Union Intersection Difference Difference Complex Model 19 7 Texture Mapping e If we add d
95. ke_ functions left out here Build a group node whose children are the arguments to the function house make_group make_cube make_poly prism_data transform gr translation 0 1 0 farmhouse make_instance house material green barn make_instance house material red transform gr translation 2 0 3 gr scaling 2 2 2 gr rotation Y 30 doghouse make_instance house material blue transform gr translation 1 5 0 0 2 gr scaling 0 2 0 2 0 2 gr rotation Y 15 scene make_group farmhouse barn doghouse gr render scene e Note Conceptually DAG is e Primitives only occur at leaf nodes e Transformations only occur at internal nodes e Rendered scene Picking and 3D Selection e How to associate materials with objects e For assignments just associate with primitives e More complex Material assigned to inner nodes Who has precedence lower or higher in hierarchy Parameterized materials x Subtree with materials house with white paint green roof x Might want instances of house to have different materials cream paint black roof x Have to parameterize materials on creation x Have to have method for setting materials in subtree 13 95 Picking and 3D Selection 13 96 14 PICKING AND 3D SELECTION 97 14 Picking and 3D Selection 14 1 Picking and 3D Selection Picking and 3D Selection e Pick Select an object by positioning mouse over it and clicking
96. kes affine transformations a bigger class than linear transformation is their transla tional behaviour on points Affine Transformations 6 2 34 Extending Affine Transformations to Vectors Suppose we only have T defined on points Define T 5 as follows e There exist points Q and R such that Y Q R e Define T 0 to be T Q T R Note that Q and R are not unique The definition works for P v Pa S PLOR T P T Q T R POET Can now show that the definition is well defined Theorem Affine transformations map parallel lines to parallel lines Mapping Through an Affine Transformation Need to pick a numerical representation use coordinates Let A and B be affine spaces e Let T At B be an affine transformation e Let F4 v1 U2 Oy be a frame for A e Let Fg 1 02 Ow be a frame for B e Let P be a point in A whose coordinates relative F4 are p1 p2 1 P pit pote 10y Oy and Oy are called the origins of their respective frames Question What are the coordinates p p5 1 of T P relative to the frame Fg Fact An affine transformation is completely characterized by the image of a frame in the domain T P T piti pote Op piT 61 p2T v2 T Oy If U1 t 10 te1We T v2 t1201 to2We T Oy tr gw te 302 Ow then we can find p ph 1 by substitution and gathering like terms Matrix Representation of Transformations 6 3 35 A NG vi i p Y y Readin
97. ld Changing the aperture size has the effect of changing the depth of field i e the range of depths over which objects can be considered to be in focus Camera Cinematics e An animated zoom changes perspective which can be disturbing Use dolly to enlarge the image of an object of interest e The camera should almost never be rotated about its view direction Unless a seasick audience is the objective e Changing the focal depth can be used to track objects of interest but a sophisticated renderer is required to simulate focus e Depth of field is rarely changed in real cinematography due to technical limitations but might be useful in computer animation Tools for Shape Animation 29 8 227 Use smooth spline animation for camera animation Quick camera moves should normally be replaced by cuts instantaneous changes of scene unless a special effect is desired Animation of spotlight sources is similar to the animation of a camera Support of a light s eye view therefore is often useful Camera Animation Specification With a camera usually more interested in what it s looking at than its exact orientation Camera animation may be specified by A motion path for the camera itself A motion path for a lookat point possibly derived from the motion of an object of interest Camera moved along the motion path and the orientation of camera determined by the lookat point Ideally focus would be pulled to
98. les Widely used in practice Easy to implement Inexpensive computationally Quaternions Four dimensional analogs of complex numbers Isotropic avoid the problems of Euler angles Inverse problem easy to solve The user interface tends to be simpler More involved mathmatically Interpolation can be expensive in practice Euler Angles e With ca cos a and sa sin 0 e SxSyCz CrSz SgzSySz CrCz SgCy 0 R 05 04 02 CaSyCz SeSz CaSySz Salz Caly 0 0 0 0 1 Ra 07 Ry 0y R 0 where Ry 07 Ry 0 and R 0 are the standard rotation matrices e Given a point P represented as a homogeneous row vector the rotation of P is given by P PR 04 02 e Animation between two rotations involves simply interpolating independently the three angles Oz Oy and 0z Quaternions 29 6 223 Problems with the Euler angle approach include Parametric Singularity A degree of freedom can suddenly vanish Anisotropy The order of the axes is important Nonobviousness The parameters lack useful geometric significance Inversion Finding the Euler angles for a given orientation is difficult not unique Coordinate system dependence The orientation of the coordinate axes is important Gimbal Lock An Example e Gimbal lock is an example of a parametric singularity e Gimbal lock is a mechanical problem that arises in gyroscopes as well as quaternions e Set 6 1 2 90 and set 6 and 0 a
99. lf e Painter s algorithm device independent but details tough and algorithm is slow e Warnock s algorithm easy to implement but not very fast and is semi device dependent e Z buffer online fast and easy to implement but device dependent and memory intensive Algorithm of choice for hardware Comparison of no hidden surface removal backface culling and hidden surface removal WY DX YNNN A WZ NOGAL VE Pk OEI DEAN PASION INIA Y ONES ZN ANA INS Ny 3 KN A y PIES NSA N N N Ma SIALL AA WANA WES EIN DATO S ANDIZ G TAY g E SN KY IDA DEIA KY TODA CFS Hierarchical Models and Transformations 12 88 13 HIERARCHICAL MODELS AND TRANSFORMATIONS 89 13 Hierarchical Models and Transformations 13 1 Hierarchical Transformations Hierarchical Transformations How do we model complex objects and scenes e Describing everything as a single complex model is a Bad Idea e Use hierarchical modeling instead Start with basic set of 3D primitives Cubes spheres prisms e Each is defined in a nice way in its own space e To put primitives together use transformations e Each transformation embeds one space in another e Use a whole hierarchy of spaces to build up complex models e Not just one Model space but one for each model and part of a model Suppose we want two houses SN WCS Pictorially we have
100. light mirror refraction ambient irradiance est e To use for global illumination use Direct light mirror refraction irradiance est but photon tracing is performed differently Overview 25 0 175 e Need to work harder or smarter to get global illumination e Harder trace a LOT more rays from light e Smarter trace rays from light Russian Roulette and trace rays from eye Monte Carlo and meet in the middle Eye Monte Carlo During ray tracing N During photon tracing Light Polyhedral Data Structures 25 176 e Number of photons to cast from light Parameters in irradiance estimate value of k radius of limiting volumes etc e Monte Carlo vs Russian Roulette e Noise noise noise 26 POLYHEDRAL DATA STRUCTURES 26 Polyhedral Data Structures 26 1 Storage Models Polyhedra e How do we store a polyhedron in memory Must consider the following Memory Efficiency Operations e Will look at three formats Ray Tracer Generalized Ray Tracer Winged edge variations Ray Tracer Format e We already saw one ASCII format for the ray tracer e Data structure for this is simple Array of points triples of floats Array of faces with pointers to points Vo Vo Vi Compact simple to get face information x y 2 x y 2 x y 2 x y 2 0112 177 Storage Models e Advantages Space efficient Easy to ge
101. line types will have different tradeoffs and capabilities B splines Give automatic continuity control but only approximate their control points Non uniform B splines Are needed to break continuity Non uniform Rational B splines NURBS Provide additional local control over the shape of a curve Hermite splines Require tangent vectors at each keyframe Catmull Rom splines Provide only first derivative continuity Motion Path Animation 29 4 220 Transformation Matrix Animation e One way to support an animation capability interpolate a transformation matrix e Keyframes would be poses of objects given by the animator e Functional animation would be applied independently to all entries of the transformation matrix Unfortunately does not support animation of rigid bodies e Given two poses of an object that differ by a 180 rotation e Under linear interpolation object will not rotate but will turn inside out collapses to a plane in the middle of the interpolation Rigid Body Animation e Rigid body transformations only have 6 degrees of freedom General affine transformations have 12 e To obtain good interpolation we have to consider separately three degrees of freedom from translation three that result from orientation 29 5 Motion Path Animation We would like to translate a point through space along a given path We would like e Independent control of velocity along path e Continuity control
102. lines are useful for representing functions e Continuity control is a must both its automatic maintenance and selective breaking e The functions can be edited both explicitly as graphs or implicitly through a direct manip ulation interface Linear Interpolation e Basic interpolation technique for supporting animation is linear interpolation or the lerp e Given two parameters po and p at times to and t an intermediate value is t tit t to Pp hege hone Functional Animation 29 3 219 e Advantages and Disadvantages Discontinuities in derivative exist at all key frame points The rate of change within a segment is constant and so can easily be controlled Controlling Velocity Given a constant rate of change can create variable rate of change Given any function 7 f t reparameterize with 7 For the lerp 10 0 FO Ha Ft Fl Fo p T p f t Spline Interpolation Instead of linear interpolation spline interpolation can be used Continuity control can be obtained Fewer keyframes may be required for a given level of quality Control points for the splines may have to be computed based on interpolation constraints at the control points Extra information may be required at keyframes such as tangent vectors Splines are more expensive to evaluate Splines are more difficult to implement Spline Types for Animation Different sp
103. llowing assumptions Conservation of energy in closed environment Only diffuse reflection of light All energy emitted or reflected accounted for by its reflection or absorption elsewhere e All light interactions computed once in a view independent way Multiple views can then be rendered just using hidden surface removal No mirror specular reflections Ideal for architectural walkthroughs Radiance Electromagnetic energy flux the amount of energy traveling e at some point x e ina specified direction 0 e per unit time e per unit area perpendicular to the direction e per unit solid angle e for a specified wavelength A e denoted by L x 0 A Spectral Properties Total energy flux comes from flux at each wavelength e L 2 0 6 frm L z 0 6 A dA Picture For the indicated situation L x 6 dx cos Odwdt is e energy radiated through differential solid angle dw sin 9d0dgo e through from differential area dx e not perpendicular to direction projected area is dx cos 0 e during differential unit time dt Definitions and Overview 24 0 160 Power Energy per unit time as in the picture e L x 0 dzx cos 0dw Radiosity Total power leaving a surface point per unit area e fo L x 9 p cos dw fo x 0 Q cos 0 sin Od dd integral is over the oo above the surface point Bidirectional Reflectance Distribution Function e is a surface property at a point e relates energy in to
104. lts for t organize expression terms for numerical accuracy ie to avoid x cancellation combinations of numbers with widely different magnitudes Polygons e The plane of the polygon should be known Ar By C2 D 0 A B C 0 is the normal vector Shading 19 2 126 pick three succesive vertices tr AMA v i Yi Zi Vil Tiis Yi 1 Zi 1 should subtend a reasonable angle bounded away from 0 or 180 degrees normal vector is the cross product vi vi x vi 1 vi D Ax By Cz for any vertex x y z 1 of the polygon e Substitute ray x y z into surface formula linear equation results for t e Solution provides planar point 1 Y Z is this inside or outside the polygon Planar Coordinates e Take origin point and two independent vectors on the plane O xo yo 20 1 bo uo Vo wo 0 by u1 v1 W1 0 e Express any point in the plane as P 0 aobo ab intersection point is Qo 41 1 clipping algorithm against polygon edges in these coordinates Alternatives Must this all be done in world coordinates e Alternative Intersections in model space form normals and planar coordinates in model space and store with model backtransform the ray into model space using inverse modeling transformations perform the intersection and illumination calculations e Alternative Intersections in world space form normals and planar coordinat
105. maps each frame e Works best with directional and spot lights With point light source in viewing volume have to put cube around light and render 6 shadow maps Near Far Screen 22 4 Shadow Volumes e Multiple drawing passes to render shadows e Uses stencil buffer to determine where shadows are Stencil buffer store per pixel data do operations and tests on stencil data and use to affect drawing to frame buffer Shadow Volumes 22 3 151 e Idea assume one light source For each point P on surface consider shadow planes cast by silhouette edges Count each front facing shadow plane as 1 and each rear facing plane as 1 If sum is gt 0 then P in shadow otherwise light reaches P e We can use graphics hardware for shadow volumes as described on next slide NA qs AY AZ as 1 Draw scene normally 2 Draw in stencil buffer front facing shadow polygons using prev depth buffer do not update depth buffer Increment stencil buffer on draws 3 Draw in stencil buffer backfacing polygons polygons Decrement stencil buffer on draws 4 Redraw scene with light off but only update pixels that e have exact depth match e have non zero stencil value Shadow Volumes 22 3 152 DA DE g ee Q Q DN p E EA O O 1 Dn Dn lt lt Scene Shadow Volume W We ay g oO A oO 2 nS 2 Q g Q Dn 7 Dn 0 0 7 lt q 0 i 0 N Shadow Front facing 1 Ba
106. match the distance to object of interest Tilt might be constrained to lie within certain bounds 29 9 Tools for Shape Animation Skeletons Given a model with large number of vertices vertices can be grouped and manipulated as a unit Example in an arm all points describing the forearm move more or less as a rigid body Connectivity between groups can be represented by tying each group to a bone and arrang ing bones in an articulated skeleton The bone and all its associated vertices are treated as a single rigid object for the purposes of transformation Movement of the bones is constrained by the joints in the skeleton Different kinds of joints revolute hinge ball can support specific types of motion An animation can be previewed using only the bones speeding rendering time In the final rendering the model is shown without bones Enhancement vertices may be influenced by more than one bone Results in more flexible and realistic surface near joints Example a kneecap and its skin surface affected by both the femur and shinbone and assume a position halfway between either Tools for Shape Animation 29 8 228 Free Form Deformations e Sometimes skelton cannot capture desired shape change of an object e Example The sqaush and stretch of a bouncing ball as it hits the ground e Such global changes in shape can be expressed using a deformation e A deformation Changes the space around an obj
107. n slerp Consider the quaternions as vectors and find the angle between them w cos q1 q2 Given a parameter u 0 1 the slerp is sin 1 u w x sin uw q u q sin w sin w Animating Camera Motion 29 7 226 e Numerical difficulties when w 0 In such as case replace the slerp with a lerp e Also problems with w n7 2 This should probably be flagged with an error and or a request for more keyframes 29 8 Animating Camera Motion e Requirements for camera motion are different from object motion Specification of camera motion has a long cinematic tradition that should be respected The camera should always be level unless we specify otherwise The image of objects of interest should be stable on the film plane Camera Cinematic Terminology Dolly Move forward along the line of sight of the camera towards the object of interest Track Move horizontally perpendicular to the line of sight of the camera More generally move in a horizontal plane Crane Raise the camera vertically Tilt Bank Rotate about the horizontal axis perpendicular to the line of sight of the camera Pan Yaw Rotate about the vertical axis of the camera after tilt In addition cameras have other parameters that can be animated Zoom in out Change the angular field of view of the camera Focus Change the focal depth i e the distance at which objects are in focus Depth of Fie
108. n objectives Resulting optimization problem solved iteratively as an animation proceeds Example optimization objectives minimize the kinetic energy of structure minimize the total elevation of the structure x minimize the maximum or average angular torque 29 11 Physically Based Animation Idea to obtain a physically plausible animation simulate the laws of Newtonian physics In contrast to kinematics this is called a dynamics approach e Have to control objects by manipulating forces and torques either directly or indirectly e Animated objects may be passive bouncing balls jello wall of bricks falling down etc Inverse dynamics is difficult e Finding forces to move a physical object along a desired path e Most current applications are passive variety e Useful for secondary effects in keyframe animation a mouse character s ears should flap when it shakes its head a T Rex s gut should sway while it runs a feather in a cap should wave when wind blows on it cloth should drape around an actor and respond to his her its movements a wall of bricks should fall down when a superhero crashes into it Caution simulated secondary effects can make bad keyframed animation look even worse Simulation Setting up and solving a physically based animation proceeds as follows 1 Create a model with physical attributes mass moment of inertia elasticity etc 2 Derive differential
109. n pixel Ray Casting Non recursive e As above for ray tracing but stop before generating secondary rays e Apply illumination model at nearest object intersection with no regard to light occlusion e Ray becomes a sampling probe that just gathers information on visibility color Readings Watt 12 2 Surface Information 19 4 129 19 5 Surface Information Surface Normals e Illumination models require surface normal vectors at intersection points ray surface intersection computation must also yield a normal light source directions must be established at intersection shadow information determined by light ray intersections with other objects e Normals to polygons provided by planar normal provided by cross product of adjacent edges Or use Phong normal interpolation if normals specified at vertices e Normals to any implicit surface eg quadrics move from x y z to x Az y Ay z Az which is maximally far from the surface direction of greatest increase to f x y z e Taylor series of Ox f x Az y Ay z Az f x y 2 Az Ay Az a ES Of Oz maximality for the gradient vector of f not normalized e Normal to a quadric surface 2Ax By Cz G Bx 2Dy Ez H Cx Ey 2Fz J 0 Normal Transformations How do affine transformations affect surface normals e Let P and P be any two points on object arbitrarily close P P
110. ne Combinations Define Point Subtraction Q P means v Y such that Q P v for P Q EP By Extension So a P is a vector iff y a 0 Define Point Blending Q 1 a Q1 aQ2 means Q Q a Q2 Q1 with QE P Alternatively we may write Q a1Q1 a2Q2 where aj a2 1 So aiP is a point iff So ai 1 By Extension Geometrically e The following ratio holds for Q a1Q a2Qa aja HAD Affine Transformations 6 2 32 a ay Q gt Q Q e If Q breaks the line segment Q1Q2 into the ratio ba b then b1Q1 b2Q2 Gs b1 be b bo 4 0 Legal vector combinations Vectors can be formed into any combinations gt gt a a linear combination Legal point combinations Points can be formed into combinations gt gt a P iff e The coefficients sum to 1 The result is a point an affine combination e The coefficients sum to 0 The result is a vector a vector combination Parametric Line Equation has geometric meaning in an affine sense L t A t B A 1 t A tB The weights t and 1 t create an affine combination The result is a point on the line Parametric Ray Equation Same as above but t gt 0 Will write as R t A td Where A is the point of origin and d is the direction of the ray Used in ray tracing Readings White book Appendix A 6 3 Affine Transformations Affine Transformations Let T Ay 4 where A
111. nement 2 2 2 0 2 ee 167 24 4 Meshing in Radiosity e e hee ce Oe ee ee Ae Re eee 168 25 P Map 173 MOL OVETVIEW ei A BO Go a a he A Se a e ee 173 26 Polyhedral Data Structure 177 26 1 Storage Models s i c sa a esteri ee 177 ADMITA lt lt e sa coate eaa a E a p a a E a a a 179 20 9 Winged Edga oaoa a 180 21 Splines 185 2 onstructing Curve Segments a oaa a a e 185 bey a Oe Bes we das A 187 2 B DINGS g iaa doe doe Se ee a a e G RG a e e a GH e 188 27 4 Spline Continuity a aoaaa ee 191 Do Tensor Product Patches 2 a 195 27 6 Barycentric Coordinates a aa a 198 27 langular Patches ooa ee 200 Sa Seba pth SS A Se es ee Sh ee de 202 PCI WAVES lt a ye eA are is A a eee ee Be Be A ees He ees 205 28 Non Photorealistic Rendering 209 Soa ads ds dh BS ao 2 AAA ee 209 Boe eth ee ee EEN IA oe 213 29 Animation 217 he heyy ok oh ede oe Re ee ee i 217 29 2 Traditional 21 Cel Animation 29 6 Orientation and Interpolation ee 222 20 QUATeriiona Y ix Se a A ee A a Be a Ea 224 29 5 Animating Camera Motion e 226 29 9 Tools for Shape Animation s e gs sopo sacs eb oewre eose peta Ep e e e a 227 29 11Physically Based Animation a a a a a a a 230 29 2Human Motionl e s se s sa a w da ios a aUi oa oao daona a a a ea aa a pa 232 EL A Gn TO Se eee Gee A 233 AE sos e recaia samm a goha aa E a Aa R a o i a aa y a 234 29 VI A A E TE E E E oe Re E E eae Gt E E TE EE E E TEE 235 CONTE
112. nerate parse build data structure e Disadvantages Vertex neighbours Modify the data structure Example What if we want to know faces surround a vertex Radiosity might want this e Solution For each point have a list of pointers to surrounding faces Can use same ASCII input format Build lists when reading data Question Where do these lists come from e Problems still remain How do we modify a polyhedron Easy to move vertex x y z x y z x y z x y z 26 0 17 8 Euler s Formula 26 1 179 Add face or vertex is easy Split face not too hard 0 U 1 2 l 2 0 1 2 gt 0 1 3 123 2 0 3 Delete is hard O n or leaves holes in our list Readings Hearn and Baker in OpenGL 8 1 not very useful Watt 2 1 26 2 Euler s Formula e Closed polyhedron V E F H 2 C G Number of vertices Number of edges Number of faces N umber of holes Number of connected components QQrRA EB lt Number of genus sphere 0 torus 1 e Examples Winged Edge Cube Torus 1 V E F G Torus 2 V E F G 26 3 Winged Edge e Operations Want to traverse x Neighbouring faces of a face vertex x Neighbouring vertices of a face vertex Edges of a face Want to modify add delete the polyhedron e Key ideas of winged edge Edge is important topological data structure Also se
113. nt shading done quickly Interactive speeds Begin with a simple lighting model at a single point on a surface Not going to worry too much about the physics Later we will improve lighting model Initial Assumptions Linearity of reflection outgoing energy proportional to incoming Energy conservation no more outgoing energy than incoming Full spectrum of light can be represented by three floats Red Green Blue Readings Watt 6 2 Red book 14 1 White book 16 1 16 2 Lambertian Reflection Lambertian Reflection e Assume Incoming light is partially absorbed then remainder of energy propagated equally in all directions Light e Approximates the behavior of matte materials Lambertian Reflection 16 1 104 e Want an expression for Lout 0 the radiance light energy transported along a ray reflected in some direction Y given the incoming direction A incoming radiance Lip and the material properties reflectance e Given radiance Lin striking surface from direction Z e Want to determine Lout U reflected in direction 7 N Light AA out M in AA surf e Energy received at surface irradiance E depends on projection of incoming beam orientation onto surface s orientation Buone aO e iF surf e Want to compute projected area AAsurf where f is the surface normal and points towards the light Attenuation 16 2 105 e Our view of
114. o Reflection Through a line e Applies to points or vectors is linear e Example through z axis matrix representation is 1 0 0 XL 0 1 0 y y 0 0 1 0 or 1 0 or 1 e See book for other examples Note Vectors map through all these transformations as we want them to Readings Hearn and Baker 5 1 5 2 and 5 4 Red book 5 2 5 3 White book 5 1 5 2 Change of Basis 6 6 38 6 6 Compositions of Transformations Compositions of Transformations Suppose we want to rotate around an arbitrary point P z y 1 e Could derive a more general transformation matrix e Alternative idea Compose simple transformations 1 Translate P to origin 2 Rotate around origin 3 Translate origin back to P e Suppose P zo Yo 1 7 e The the desired transformation is T Zo Yo R 0 2 Sa Yo 1 0 To cos 0 0 1 0 0 1 yo o sin f cos 0 0 0 1 E 00 1 0 1 00 1 cos 0 sin 0 xo 1 cos 0 yosin 0 sin 9 cos 0 Yyo l Lo 20 0 0 e Note where P maps to P e Won t compute these matrices analytically Just use the basic transformations and run the matrix multiply numerically Order is important T Azx Ay 0 T Az Ay o R 0 R 0 T Az Ay o R 0 o T Az Ay Readings Hearn and Baker Section 5 3 Red book 5 4 White book 5 3 6 7 Change of Basis Change of Basis Suppose e We have two coordinate frames for a space F and F gt e Want to chan
115. o and 2 NPR pencil sketches of girl Batik Moose Pen and Ink Illustration e Problem each stroke must simultaneously convey texture and tone Stroke textures Example textures Approximately constant Wall images ae View dependent rendering of surface texture Wall im a g es Wall images Lighting dependent rendering for shadows and accenting House Two more houses Indication Interactive pen and ink Examples 3D NPR 28 1 213 Examples Examples Examplesixamples Orientable textures Paint bushes Racoon 28 2 3D NPR e Support real time non photorealistic rendering of 3D scenes via hardware acceleration HijackGL and NPRQuake NPR Quake NPR Quake NPR Quake Real time hatching Six examples Image space silhouettes e Silhouettes are discontinuities in the depth image e Creases are second order discontinuities in the depth image H ex nut ex ampl e The right image on which to do edge detection Funky box examples e Creases can also be seen as discontinuities in the normal image Bust Object space silhouettes e Given a polyhedral mesh and a camera position find and draw all visible silhouettes e Two subproblems Find all possible silhouettes relative to the current viewpoint Process these silhouettes to determine visibility 3D NPR 28 1 214 Silhouettes e What is a silhouette For a smooth object it s a point where the vector from the camera just grazes the point e In
116. on Prone to error and occlusion Tedious if done manually Puppetry Real time data collected from an arbitrary input device Mapped to an computer model which is displayed in real time during capture A special purpose input device in the shape of the object being animated may be built e Motion capture tends to require more or less exotic technology e Even puppetry requires at least real time graphics e Problems with motion capture include How do we map motion paths to objects of a different shape and scale the ostrich to T Rex problem How do we deal with noise and missing data How can we reduce the number of samples How can we generalize motion I e we have a walk and a turn How do we get an actor to follow a path Flocking 29 15 237 29 16 Flocking e Want to animate groups of animals Birds fish herds e Motion of individuals is semi independent Too many individuals to key frame each one e Fewer elements than particle systems but more interelement interaction e Relative placing not rigid Flock of birds vs airplanes in formation migrating geese etc being more like the latter Two main forces at work e Collision avoidance Avoid hitting objects trees buildings etc Avoid hitting one another e Flock centering Each member trying to remain a member of flock Global flock centering too restricting Does not allow flock splitting to pass around objects Local
117. ormed Model Frame then we next transform relative to transformed Model Frame e Example If E Lo T3 A M Y Y3 Ya 21 22 Z3 Z4 0 0 0 1 and we translate one unit relative to the first Model Frame basis vector then we want to translate by 21 y1 21 0 relative to the World Frame e Could write this as 1 0 0 t 21 T2 3 T4 T1 mal 10 n yal mM Y Y vary 001 21 Zi 22 23 Zatz 0 0 0 1 0 0 0 1 Normals Readings 6 6 6 10 47 But this is also equal to E 0 0 y he T2 T3 3 M M 0 1 00 _ Yy ye y Ya y 0 0 1 21 22 23 Lat zy E 0 0 1 0 0 0 1 In general if we want to transform by T our model relative to the current Model Frame then MT yields that transformation Summary Modelling transformations embodied in matrix M World to View change of basis in matrix V VM transforms from modelling coordinates to viewing coordinates If we further transform the View Frame by T relative to the View Frame then the new change of basis matrix V is given by Vary If we further transform the model by T relative to the modelling frame the new modelling transformation M is given by M MT For Assignment 2 need to do further dissection of transformations but this is the basic idea Hearn and Baker Section 6 2 first part of Section 12 3 Red book 6 7 White book 6 11 Normals Transforming Normals The Truth Can really only apply affine transforms to points Vectors can be transformed correctly
118. ot of rays e Cast with distribution function to represent reflection properties 139 Bidirectional Path Tracing 20 2 140 e Distributing rays over reflected direction gives soft reflections similar effect if distributed over transmission direction Distributing rays over light area gives soft shadows Distributing rays over aperature gives depth of field Distributing rays over time gives motion blur Can use to model caustics but need lots of rays 20 rays per reflection e Can model many effects simply but often very expensive Example Distributed reflection Example Distributed aperture 20 3 Bidirectional Path Tracing e Idea trace paths from eye and from light and connect them up Trace paths single reflected ray e Reflect with distribution function e When far enough connect them up e Problem A whole lot of rays e Low error high noise e Less expensive than distribution ray tracing Aliasing 20 141 20 4 Photon Maps Cast rays from light Global illumination view independent Create a photon map wherever this light hits The use standard ray casting no secondary rays look at photon map s to determine special lighting Use density estimation to convert photon map to intensity Fast easy to program low noise Errors Example caustics Aliasing 20 142 21 ALIASING 143 21 Aliasing 21 1 Aliasing Aliasing and Anti Aliasing e Raster Image is a sampling of a continuous f
119. other words p c n 0 Where p is the point on the surface cis the location of the camera and n is the normal at point p Silhouettes on meshes e A mesh with face normals is not smooth e Approximate silhouettes by finding mesh edges that separate a front face from a back face e Slow to check all edges every frame so use some kind of acceleration edge buffer probabilistic checking e Can also identify silhouettes on smooth mesh one with vertex normals Silhouette visibility e Just because an edge is a silhouette doesn t mean it s visible Occlusion by another object Occlusion by another part of the same object Partially visible e Need to decide for every silhouette edge which parts are visible Image space visibility processing e Turn on depth buffering e Draw all mesh faces in background colour e Draw all silhouette edges give every edge a unique colour that identifies it e Frame buffer now holds pixel accurate image of which pieces of silhouettes are visible Stylized silhouettes e Use visibility to guide placement of stylized strokes along paths e Parameterization and temporal coherence are still problems Animation 28 215 Toon shading e Cartoons typically use a small range of colours for each object in a scene Shadow body and sometimes highlight e Easy to simulate in ray tracer or real time Quantize by diffuse attenuation to two or three colours Elf girl Roses Toon shad
120. ous coordinates do per pixel divide Can be organized so only need one division per pixel regardless of the number of pa rameters to be interpolated e Phong shading and many other kinds of advanced shading can be simulated with pro grammable vertex and fragment shaders on modern graphics hardware Classic Gouraud shading is linear in device space Modern graphics hardware performs rational linear interpolation looks like interpo lation happens in world space Interpolate normals view vectors and light vectors using generic interpolation hardware Usually also interpolate diffuse term after computing it in vertex shader Write fragment shader to renormalize normals to unit length compute lighting model and assign colour to pixel Can also use texture maps as lookup tables 18 GRAPHICS HARDWARE 115 18 Graphics Hardware 18 1 Graphics Hardware Graphics hardware has been evolving over the past several decades In the 60 s 70 s vector displays costing millions of dollars US military was main only customer Raster displays started appearing in the 70 s In the 80 s raster displays and graphics hardware cost 10 s to 100 s of thousands of dollars Cost low enough that companies could afford the hardware SGI won the battle of work station graphics OpenGL became standard In the 90 s graphics hardware started moving to PC s DirectX is MicroSoft s challenge to OpenGL In the 00 s PC graph
121. parate topology from geometry e Edge is the primary data structure 26 2 180 Winged Edge 26 2 181 e 4 a ie ae 2 eerie next left T prev right fl f2 prev left next right lio VO E IA y 1 N e Pictorially Polygon and neighbors Data Structures for F Lots of pointers Variations e Some operations simplified by splitting edge into half edges e Uses a lot of space Time space trade off Winged Edge Data types struct he 4 struct struct struct struct struct he sym hex next he prev vert v facex f void data struct vert struct he rep void data oa Winged Edge Half edge Minimal Edge struct face struct he rep void data e Example Neighbouring faces of f struct face f struct hex e struct hex s struct face f1 LOTS int dy e f gt rep 0 26 2 182 Winged Edge do f1 i e gt sym gt f e e gt next while e s e Example Removing an edge RemoveEdge struct he e fix edge gt edge pointers e gt prev gt next e gt sym gt next e gt next gt prev e gt sym gt prev e gt sym gt next gt prev e gt prev e gt sym gt prev gt next e gt next fix edge gt face pointers ee e gt sym gt next while ee e gt sym ee gt f e gt f ee ee gt next fix face gt edge pointers e gt f gt rep e gt prev
122. product patches e Work well for rectilinear data e Problems arise when filling non rectangular holes Suitcase Corner e A lot of data is non rectangular Triangular A ZO N N 27 6 Barycentric Coordinates Coordinate Frames e Vector oriented Derived from linear space basis e One point and n vectors in space of dimension n Dn Uo Un 1 Vectors v are linearly independent Coordinates are weights of vectors with weight of 1 for point Barycentric Frames Triangular Patches 27 6 199 e Point oriented e n 1 points in space of dimension n Do Dn Points are in general position Coordinates are weights of points with coordinates summing to 1 Frames of Both Types Are Equivalent e Express each v as Di Dn for Dj Dn vi n 1 P Dat pit 1 0 n 1 Dnt gt pi Di Dn i 0 n 1 n 1 1 Y pi Da X Di i 0 i 0 n n y w D where y w 1 1 0 i 0 e And of course conversely Yi Triangular Patches 27 6 200 27 7 Triangular Patches deCasteljau Revisited Barycentrically e Linear blend expressed in barycentric terms 1 t Po tP rP tP where r t 1 e Higher powers P t Er pee Symmetric Form of Bernstein Polynomials n fd P r t bD P 55 tr where r t 1 i j n 1 gt 0 3 gt 0 gt y PijBi r t t 7 n 1 gt 0 3 gt 0 Examples Boo r t 1 B r t Blo r 0 r t B8 r t Bi r t Bono r 2rt t B8 r t
123. r e Directly using three independent intensity channels or e Indirectly using a Colour Lookup Table LUT In the latter case a colour index is stored in the frame buffer Sophisticated frame buffers may allow different colour specifications for different portions of frame buffer Use a window identifier also stored in the frame buffer How Liquid Crystal Displays Work Liquid Crystal Displays LCDs e Flat panels e Flicker free e Decreased viewing angle Works as follows e Random access to cells like memory e Cells contain liquid crystal molecules that align when charged e Unaligned molecules twist light e Polarizing filters allow only light through unaligned molecules e Subpixel colour filter masks used for RGB Readings Watt none Hearn and Baker Chapter 2 Red book Chapter 4 White book Chapter 4 LCD reference http www cgl uwaterloo ca pogilhul present lcd Device Interfaces 3 19 3 3 Physical Devices Physical Devices Physical input devices include e Dials Potentiometers e Sliders e Pushbuttons e Switches e Keyboards collections of pushbuttons called keys e Trackballs relative motion e Mice relative motion e Joysticks relative motion direction e Tablets absolute position e Etc Need some abstractions to keep organized Readings Watt none Hearn and Baker Chapter 8 Red book 8 1 White book 8 1 Device Interfaces 3 20 4 DEVICE
124. r and far clipping planes 9 6 Pinhole Camera vs Camera vs Perception Pinhole Camera vs Camera e Lines map to lines can t be true because I ve seen pictures that curve lines e Camera is not a pinhole camera e Wide angle lens suffers from barrel distortion Vertical Convergence e Is vertical convergence a pinhole camera effect or another kind of distortion Slanted apartments e Vertical convergence is a perspective projection effect Occurs when you tilt the camera view up Pinhole Camera vs Camera vs Perception 9 5 68 e You can get rid of it if view plane parallel to up axis Kil AL Projection Projection Plane Plane e Pinhole camera ray tracer Mathematically correct but looks wrong Spheres cylinders same size on a plane parallel to view plane Spheres on cylinders Art e Painting Sculpture Mathematically incorrect but looks right Skew eyed David What s going on Pinhole Camera vs Camera vs Perception 9 5 69 Distortion Lateral Distortion View Plane Top of spheres Plane Center of Projection Eye Spheres Spheres and lots of them Occurs in Computer Graphics Images Ben hur races in front of distorted columns In Real Life e Eye attention only on small part of field of view Sphere looks circular e Rest of field of view is there Peripheral spheres not circular but not focus of attention and you
125. rbitrarily Then cy 0 sy 1 and the matrix R 6 7 2 0 can be reduced to 0 0 1 0 a SaCz CxSz SzSz Col 0 0 Re 0 04 Calz SzSz CrSzx Setz 0 0 0 0 0 1 0 0 AN 7 sin 0 0 cos 0x 02 0 0 E cos 0 0 sin z 0 0 0 0 0 0 1 e A y roll by 7 2 rotates the x axis onto the negative z axis and so a x roll by 9 has the same effect as a z roll by 0 y 90 e Gimbal lock can be very frustrating in practice During interactive manipulation the object will seem to stick Certain orientations can be hard to obtain if approached from the wrong direction Interpolation through these parametric singularities will behave strangely Quaternions 29 6 224 29 7 Quaternions e Four dimensional analogs of complex numbers e Can be used to represent orientation without a directional selectivity e Recall multiplication of complex numbers represents orientation and rotation in the plane The rectangular and polar form of a complex number p are p a bi Ae Multiplication is a rotation about the origin pipz Ay Age 01 02 Quaternions Definitions e Quaternions defined using three imaginary quantities 2 7 and k q a bi cj dk Rules for combining these imaginary quatities P k i ij ji k iaa These rules are sufficient to define multiplication for quaternions e Quaternion multiplication does not commute A quaternion can be broken into a scalar and a vector p
126. rtex_program1_1 txt Example Phong Lighting X Vertex position LP Light position EP Eye position L Normalized light vector E Normalized eye vector R n Reflection vector Specular exponent Parameters c 0 3 Modelview times projection matrices c 10 Diffuse color 18 1 118 High Level Shading Languages 18 2 119 c 11 Specular color c 12 Light position c 13 Eye position c 14 n 0 0 0 0 0 0 c 16 2 0 2 0 2 0 2 0 GLubyte vpPhong_str tyP1 0 n DP4 o HPOS x c 0 v OPOS Apply modelview and DP4 o HPOS y cli v OPOS projection matrices DP4 o HPOS z c 2 v OPOS DP4 o HPOS w c 3 v OPOS o ADD RO c 12 v OPOS RO LP X DP3 R1 RO RO Ri ILP X172 RSQ R2 Ri w R2 1 LP Xl MUL RO RO R2 RO L DP3 R3 RO v NRML R3 N L ADD R4 c 13 v OPOS R4 EP X DP3 R5 R4 R4 R5 EP X 72 RSQ R6 R5 w R6 1 lEP XI MUL R4 R4 R6 R4 E DP3 R7 R4 v NRML RT E N MUL R7 R7 c 16 RT 2 E N MAD R8 R7 v NRML R4 R8 2 E N N E R DP3 R9 RS RO R9 R L LOG R10 R9 x R10 z LOG R L MUL R9 c 14 x R10 z R9 n LOG R L EXP R11 R9 z R11 EXP n LOG R L R L n MUL R10 R3 c 10 R10 Cd N L MAD o COLO c 11 Rii z R10 o COLO Cd N L Cs R L 7n END 18 3 High
127. rtices These cause shading anomalies and pixel dropout e No overlapping co planar faces Violates solid object constraint If different colours then psychedelic effect due to floating point roundoff Hidden Surface Removal 11 81 e Well shaped polygon Equilateral triangle is best Long skinny triangles pose problems for numerical algorithms Bad Polygon Examples E A1 M Hidden Surface Removal 11 82 12 HIDDEN SURFACE REMOVAL 83 12 Hidden Surface Removal 12 1 Hidden Surface Removal Hidden Surface Removal e When drawing lots of polygons we want to draw only those visible to viewer e There are a variety of algorithms with different strong points e Issues Online Device independent Fast Memory requirements Easy to implement in hardware Readings Watt 6 6 Red book 13 White book 15 Hearn and Baker Chapter 13 12 2 Backface Culling Backface Culling Backface Culling e A simple way to perform hidden surface is to remove all backfacing polygons e If polygon normal facing away from the viewer then it is backfacing e For solid objects this means the polygon will not be seen by the viewer e Thus if N V gt 0 then cull polygon e Note that V is vector from eye to point on polygon You cannot use the view direction for this Backface Culling Not a complete solution e If objects not convex need to do more work e If polygons two sided i e they do
128. s list of faces Example A cube Vertices 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 Faces 1 4 3 2 1 2 6 5 2 3 7 6 3 4 8 7 4 1 5 8 5 6 7 8 Valence v number of faces containing v Triangle mesh all faces are triangles Quad mesh all faces are quads Topological Subdivision First step in subdivision is to split each face into new set of faces Will consider two types of splits others exist Triangular linear splits e Quad bilinear subdivision Subdivision Surfaces 27 7 203 A TH Bilinear Subdivision Plus Averaging 1 Perform bilinear subdivision of mesh 2 Compute centroid cf of each quad face f 3 For each vertex v of subdivided mesh set v to D fent Cf n v where n v is the set of faces neighbouring v and Hn v is the number of faces neighbouring v DARA different rules used for mesh boundaries Catmull Clark Example Wavelets 27 8 204 e Start with a cube e Repeatedly subdivide e Do something to get normals Linear Subdivision Plus Triangle Averaging 1 Perform linear subdivision of each triangle in mesh 2 For each vertex v of subdivided mesh a For each triangle f neighbouring v compute cp 0 4 30 8 30 8 where v and uv are the other two vertices of f b Set v to Details Issues e The two schemes shown here are simple but give poor surfaces Catmull Clark and Loop are examples of better sch
129. s Ratios e Cross ratio AC a1 CD a2 AB b BD be then ay a2 rae b1 b3 b b This can also be used to define a projective transformation ie that lines map to lines and cross ratios are preserved Projections 9 0 58 Comparison Affine Transformations Projective Transformations Image of 2 points on a line determine image of line Image of 3 points on a line determine image of line Image of 3 points on a plane determine image of plane Image of 4 points on a plane determine image of plane In dimension n space image of n 1 points vectors defines affine map In dimension n space image of n 2 points vectors defines projective map Vectors map to vectors v Q R R S A Q A R A R A S S A A S Rf Ao A R Q A Q Mapping of vector is ill defined P Q P R A P R P S S P AD Q P Q P S Can represent with matrix multiply sort of Perspective Map Can represent with matrix multiply and normalization e Given a point S we want to find its projection P S x z 0 0 0 Q 0 d Z Projection plane z d e Similar triangles P xd z d e In 3D x y z gt xd z yd z d e Have identified all points on a line through the origin with a point in the projection plane x y z ka ky kz k 0 e These are known as homogeneous coordinates e If we have solids or coloured lines then we n
130. s comes from patch j to patch 7 B due to B pi Bj Fiji Light is being gathered at patch 2 e Instead we can ask how much radiosity is shot from patch i to patch j B due to B pj Bi Fi A pi Bik iG e Idea Choose a patch shoot its radiosity to all other patches repeat Progressive Refinement Code Keep track of total radiosity B and unshot radiosity dB Procedure Shoot i For all j calculate all Fji Foreach j drad pj dBi FjixAi Aj dBj drad Bj drad endfor dBi 0 Meshing in Radiosity 24 3 168 Call from while unshot gt eps do Choose patch i with highest dB Shoot i end Progressive Refinement Analysis Shoot lights first Can stop and look at partial results e Can be formulated as a matrix equation Lots of cute tricks Add initial ambient to all patches so that initial results more viewable Can move objects and lights after calculation has started Technically it is slower than full matrix methods but Form factors usually not stored since they are computed on the fly Advantage save storage space Disadvantage some form factors may need to be computed multiple times Radiosity Issues Questions e How big should we make initial patches e When do we stop Progressive Refinement Problems e T vertices and edges cause light shadow leakage e Occlusions and shadows hard to model e Form factor estimations often cause aliasing Extensions e Me
131. scene to device Window rectangular region of interest in scene Viewport rectangular region on device Usually both rectangles are aligned with the coordinate axes Viewport XVI y vt Window XWI y wt XW yW S xwl ywb xvl yvb XV yV Window point w Yw maps to viewport point v Yv Length and height of the window are Lu and Hy Length and height of the viewport are L and Hy Proportionally map each of the coordinates according to ATu AZ AYw z Ayy Ly Lo Hy H To map w to vy Tw Iwl _ Ty Tol L Ly Ly gt Ly zw Tul F Tyl Ly and similarily for yy If Hy Lw A Hy Ly the image will be distorted These quantities are called the aspect ratios of the window and viewport Normalized Device Coordinates 7 1 50 Readings Watt none Hearn and Baker Section 6 3 Red book 5 5 White book 5 4 Blinn 16 Intuitively the window to viewport formula can be read as e Convert x to a distance from the window corner e Scale this w distance to get a v distance e Add to viewport corner to get y 7 2 Normalized Device Coordinates Normalized Device Coordinates e Where do we specify our viewport e Could specify it in device coordinates BUT suppose we want to run on several platforms devices Two common conventions for DCS Origin in the lower left with x to the right and y upward Origin in the top left with x to the right and y downward
132. t e It s easy e You have to learn most of it eventually anyways e It ll save you from losing marks over dumb mistakes in protocol 30 2 Assignment 1 Introduction to OpenGL In this assignment you will learn how to use OpenGL to render a polygonal model e Draw polygons e Lighting e Transformations e Ul Screen Shots Fle Draw Mode Lighting Buffering Sample screen shots Some details may vary term to term Assignment 2 Frames and Perspective 30 2 240 30 3 Assignment 2 Frames and Perspective This assignment includes e Modeling Viewing and Perspective Transformations e 3D Line Plane Clipping e Menus and Valuators Your program will manipulate a cube and 3 sets of coordinate frames The cube is in a modelling frame is transformed to a world frame and then into a viewing frame which is projected onto a window You will draw gnomons for the modelling and world frames Frames There are six entities you need to consider The Cube Model Defined on the unit points 1 1 1 The Cube Model Frame For entering the initial coordinates of the Cube Model The Cube Model Gnomon A graphic representation of the Cube Model Frame The World Frame A coordinate system for describing the position and orientation of objects in the scene The World Frame Gnomon A graphic representation of the World Frame The Viewing Frame A coordinate system for representing a view of the scene relative to
133. the eyepoint and window Features Your program will support the following features Menus Selection of transformation mode and coordinate system Valuators Mouse movement to specify scalar parameters Modelling Transformations Rotation translation scale Viewing Transformations Camera rotation and translation perspective 3D Line Clipping To avoid divide by zero you need to clip all lines to the near plane Viewport Clip the drawing to a 2D viewport OpenGL may be used for only 2D line drawing You must implement all transformations and clipping yourselves Assignment 3 Hierarchical Modelling 30 3 241 Screen Shots Po Mode me wai Current Mode Model Rotate Current Mode Viewport l Sample screen shots Some details may vary term to term 30 4 Assignment 3 Hierarchical Modelling This assignment includes e Hierarchical Models and data structures e Matrix Stacks e 3D Picking e Z Buffer Hidden Surface Removal e Lighting Models and Shaded Polygons e Display Lists e Virtual Sphere or Arcball You may use any feature of OpenGL you desire including transformations and lighting models to implement this assignment Lua should be used as the modelling language Assignment 4 A Raytracer 30 4 242 Screen Shots Current Mode Joints Sample screen shots Some details may vary term to term 30 5 Assignment 4 A Raytracer e In this assignment you will investigate the implementation
134. the surface will include a corresponding factor for cos pyt e Outgoing radiance proportional to incoming irradiance but proportionality may depend on view vector Y and light vector gt Lout p t Fin 0 e Have assumed outgoing radiance is equal in all directions so p must be a constant e The Lambertian lighting model is therefore Lout kaBin 0 kaLin JL nt e For complete environment Lambertian lighting model is gt gt gt Lot f hala Lin 5 Em dol where Q is the hemisphere of all possible incoming directions and do is the solid angle measure e If k4 0 1 then factor of m is necessary to ensure conservation of energy e Often convert integral to a sum over light sources 16 3 Attenuation Attenuation Attenuation e We will model two types of lights Directional Point Want to determine Lin at surface for each e Directional light source has parallel rays Most appropriate for distant light sources the sun No attenuation since energy does not spread out Coloured Lights Multiple Lights and Ambient Light 16 3 106 Point light sources e Light emitted from a point equally in all directions Screen o we Eye Light Surface e Conservation of energy tells us gt I where r is the distance from light to P energy is spread over surface of a sphere and I is light source intensity e For empirical graphics usually ignore m factors e How
135. thods for adding specular but expensive e Substructuring improves quality without increasing big O e Smarter substructuring reduces big O 24 4 Meshing in Radiosity Issues e Initial Mesh Size e T vertices etc e Shadow Boundaries Meshing in Radiosity 24 3 169 e Soft Shadows Two Techniques e Split along shadow boundaries e Adaptive Subdivision Split Along Shadow Boundaries 2D 3 regions e Lit e Unlit e Linear Source Occluder Split Along Shadow Boundaries 3D Lots of regions e Lit e unlit e Linear Quadratic Source Adaptive Subdivision e Make initial Meshing Guess e Point sample a patch e Average and check variance Meshing in Radiosity Low gt Good estimate High gt Poor estimate Subdivide and repeat Problems with Adaptive Subdivision e Radiosity has O n run time Subdivision increases n e Ideas Shoot from big patches Receive at small patches Sub problems sub patch to big patch association T vertices Quad Tree e Store as 24 3 170 Photon Maps 24 171 DEF G e Traverse up to find parent e Traverse up down to find neighbor e Anchoring Photon Maps 24 172 25 PHOTON MAPS 173 25 Photon Maps 25 1 Overview e Radiosity too expensive doesn t do caustics etc e Photon mapping idea trace rays from lights bounce off shiny surfaces store light information where light hits diffuse surfaces
136. through Anticipation staging Be careful with camera Smooth changes x Few changes e Disney was the most successful but it was high risk Functional Animation 29 3 218 29 3 Automated Keyframing e Replace the human inbetweener with interpolation algorithms e Keyframes correspond to settings of parameters at different points in time The computer provides repeatability and automatic management of keyframes Interpolation is not as smart as a human inbetweener Animator may have to provide more key frames and or additional information to get a good result Utility A good keyframe system limits the number and maximizes the utility of key parameters e Parameters should have immediate geometric or visible significance Entries in a transformation matrix are not good parameters Static properties maintained automatically Relationships between parts of articulated objects maintained automatically Interpolation routines geared towards parameter types Motion paths orientation camera attitude and surface properties different types of control e Real time interface to interactively set parameters and iteratively improve the animation 29 4 Functional Animation e Independent scalar function specified for each keyframed parameter e Functional animation is a basic capability that supports all others e Most useful for truly scalar quantities brightness of a light source for example e Sp
137. till vanish Increased CPU spent on extra pixels can be put to better use e Smarter sampling Area Sampling Rather than sample we could integrate For lines this means treating them as boxes e Colour shades of gray based on fraction of pixel covered e Gives better looking images at a sufficiently far distance Look close and it looks blurry Weighted Sampling e Unweighted sampling is a box filter T L dI eBox No contribution outside of pixel All contributions are equal e Weighted sampling Give different weights depending on position in pixel VS Filter may extend outside of pixel Avoids certain temporal aliasing problems Correct filter is infinite 21 0 145 Shadows 21 146 Anti aliasing in Ray Tracing e Can t always integrate area under pixel e For ray tracing we want to point sample the image e Super Sampling Take more samples and weight with filter If sampling pattern regular we still get aliasing e Stochastic Sampling Idea Eye easily detects coherent errors aliasing Eye is poor at detecting incoherent errors noise Rather than regular supersampling we jitter the samples in one of several ways Choose random location within pixel Displace small random distances from regular grid 22 SHADOWS 147 22 Shadows 22 1 Overview e Shadows help viewer to locate objects e Already seen shadows in ray tracer
138. tion only code read online Documentation Requirements Title page with name student ID userid Signed objective list 10 points you are graded on see course notes e README and Manual e Annotated hardcopy only if code broken Checksum run u gr cs488 bin grsubmit to obtain Assignment Format e Very strict e Read assignment policies in course notes e Do AO to avoid losing marks later See and use checklist Code Run u gr cs488 bin setup e All files need to be cs488 group owned and group readable e See course notes for assignment specs and objectives 2 INTRODUCTION 2 Introduction 2 1 History A Brief History of Computer Graphics Early 60s Computer animations for physical simulation Edward Zajac displays satellite research using CG in 1961 1963 Sutherland MIT Sketchpad direct manipulation CAD Calligraphic vector display devices Interactive techniques Douglas Englebart invents the mouse 1968 Evans amp Sutherland founded 1969 First SIGGRAPH Late 60 s to late 70 s Utah Dynasty 1970 Pierre B zier develops B zier curves 1971 Gouraud Shading 1972 Pong developed 1973 Westworld The first film to use computer animation 1974 Ed Catmull develops z buffer Utah First Computer Animated Short Hunger Keyframe animation and morphing 1975 Bui Tuong Phong creates Phong Shading Utah Martin Newell models a teapot with B zier patches Utah Mid 70 s Raster graphi
139. to viewport Viewport only 1 pixel in size Shade pixel based on closest polygon in the pixel Z Buffer Algorithm 12 4 86 Warnock s Algorithm Runtime O p x n p number of pixels n number of polygons 12 5 Z Buffer Algorithm Z Buffer Algorithm Perspective transformation maps viewing pyramid to viewing box in a manner that maps lines to lines This transformation also maps polygons to polygons Idea When we scan convert step in z as well as x and y In addition to framebuffer we ll have a depth buffer or z buffer where we write z values Initially z buffer values set to oo Depth of far clipping plane usually 1 will also suffice Step in z both in the while loop and in the for loop Scan convert using the following WritePixel WritePixel int x int y float z colour if z lt zbuf x y then zbuf x y z frambuffer x y colour end Comparison of Algorithms 12 5 87 e Runtime O pe n pe number of scan converted pixels n number of polygons Z buffer in Hardware Z buffer is the algorithm of choice for hardware implementation Easy to implement Simple hardware implementation Online algorithm i e we don t need to load all polygons at once in order to run algorithm Doubles memory requirements at least But memory is cheap Scale device dependent 12 6 Comparison of Algorithms Comparison of Algorithms e Backface culling fast but insufficient by itse
140. triggered under X when a window becomes visible A Configure event is triggered when a window is resized A timer event may occur after a certain interval Simple event queues just record a code for event Iris GL Better event queues record extra information such as time stamps X windows Toolkits and Callbacks Toolkits and Callbacks Event loop processing can be generalized Instead of switch use table lookup Each table entry associates an event with a callback function When event occurs corresponding callback is invoked Provide an API to make and delete table entries Divide screen into parcels and assign different callbacks to different parcels X Windows does this Event manager does most or all of the administration Modular UI functionality is provided through a set of widgets Example for Discussion 4 5 24 e Widgets are parcels of the screen that can respond to events Graphical representation that suggests function e Widgets may respond to events with a change in appearance as well as issuing callbacks e Widgets are arranged in a parent child hierarchy Event process definition for parent may apply to child and child may add additional event process definitions Event process definition for parent may be redefined within child e Widgets may have multiple parts and in fact may be composed of other widgets in a hierarchy Some UI toolkits e Tk e Tkinter e Motif e Gtk e Qt e WxW
141. uadratic blend e Quadratic segment from an affine combination of line segments PCS 1 t Po tP P t 1 tP tP PEt 1 t Pilt tPi e P 1 P 1 pi 2 0 Po Py P Cubic blend Constructing Curve Segments 27 0 186 e Cubic segment from an affine combination of quadratic segments Pot 1 t Pot tPy Prt 1 Pi tPa PEt 1 1 0 tP Pit 1 P tPa Pi t 1 t Pa tP P 1 t PEE tP t P 1 1 P5 0 tP 0 1 Py pl 2 p 0 P P 3 Po p2 Po P P 0 e The pattern should be evident for higher degrees Geometric view deCasteljau Algorithm e Join the points P by line segments Join the t 1 t points of those line segments by line segments e Repeat as necessary The t 1 t point on the final line segment is a point on the curve e The final line segment is tangent to the curve at t Bernstein Polynomials 27 1 187 Expanding Terms Basis Polynomials e The original points appear as coefficients of Bernstein polynomials PG 1 Pt 1 t P tP P 1 t P 2 1 tP P P3 t 1 t 3Po 3 1 t tP 3 1 tt Pa tP oO Vino RBA where Brit ma prit E 1 t r it e The Bernstein polynomials of degree n form a basis for the space of all degree n poly nomials 27 2 Bernstein Polynomials Bernstein Polynomial Properties Partition of Unity gt _ B t 1 Proof 1 t4 1 t a te 20 B
142. unction e If samples spaced too far apart then don t get true representation of scene a e In graphics a variety of bad things happen Stairstep or jaggies Moire Patterns Loss of small objects Temporal Sampled too far apart in time Backwards rotating wheels x Crawling jaggies x Appearing dissappearing objects flashing objects Image as a signal e Signal processing signal is function of time e Scene is a function of space Spatial domain f u e Raster image is a sampling of this signal e Can represent signal as sum of sine waves Frequency domain F u Aliasing 21 0 144 0 5 1 0 5 0 5 0 0 0 0 0 5 1 0 5 0 5 5 10 0 5 10 5 10 5 10 0 5 1 1 2 0 0 0 0 a 0 5 24 29 2 5 10 0 5 10 0 5 10 0 5 10 e Regular sampling restricts frequencies at which we sample Nyquist Limit e Theory tells us that we must sample at twice the highest frequency in the image to avoid aliasing e This sampling rate is known as the Nyquist Limit ni e Problem Man made objects have distinct edges Distinct edges have infinite frequency What to do e After we get image run through low pass filter This helps but not a full solution e Get a Higher Resolution Monitor This helps but Not usually feasible Alleviates jaggies but x Moire patterns merely shifted Aliasing x Small objects s
143. urface but not shiny ones e Shiny surfaces have highlights because energy reflected depends on viewer s position Phong Bui Tuong developed an empirical model Lout kala kall La ks F 0PL e Using our previous notation Oo O 3 O ot O wR 3 S r O Eb O O ct O A gt lt ct gt O uN f ai y O O Specular Reflection 16 4 108 Light P e This is the classic Phong lighting model e Specular term at a maximum ks when 0 F e The exponent p controls sharpness of highlight Small p gives wide highlight Large p gives narrow highlight ST IL Small p Large p Specular Reflection 10 20 50 PHONG COEFF 20 30 PHONG COE oO 20 50 Se co ZO 50 PHONG COEFF 29 30 PHONG COEF 20 50 PHONG COE PHONG CO Ti e Blinn introduced a variation the Blinn Phong lighting model Dont 0 kala kall Ma ks h TPL Compare to Phong model of Lout kala kal na ks F aL e The halfway vector h is given by Ss el h SI e e Value h 7 measures deviation from ideal mirror configuration of Y and A e Exponent works similarily to Phong model e OpenGL uses Blinn Phong model e Blinn Phong better motivated physically e BUT both models break several laws of physics conservation of energy for instance Shading 16 110 e Better physically based and empirical models exist Cook Torrance He Ward Lafortune
144. x J Li x cos 0 diw But in general E L x 07 br L y 0 dy for some y So we let bry 09 Bye and Li a BW Y T gi x for the appropriate point y Picture Scene Based Energy Balance Definitions and Overview 24 0 162 Nx av dA y dA x Visibility We use a term to pick out the special y _ J 1 if y is visible from x By 0 otherwise Area We convert dw to surface area COS Oya dw _dA y lz yl Simple Energy Balance Scene Based COS Ory COS Oya Bla Ela pala f Bly H y dA y 2 yes ma yl Piecewise Constant Approximation e Approximate the integral by breaking it into a summation over patches e Assume a constant average radiosity on each patch B y B for y P COS Ory COS Oya B x Elx x B H x y dA 2 Oraa Y ifa Gao ml yll e Solve only for a per patch average density Definitions and Overview 24 0 163 Piecewise Constant Radiosity Approximation 1 0 cos 0j Bi Ei Pi SB f f EP Hod Aad j BS EP JyeP Tllz yll Form Factor Fij 1 i cos OF J cos 0 cos H dA dA A xEP yeP Trll yll Note by symmetry that we have AiFij Aj Fyi Linear Equations by Summetry By Fi pi gt Fi B j As Bi Fi a Fag Bi 2 j Radiosity Summary e Discretize scene into n patches polygons each of which emits and reflects light uniformly under its entire area e Radiosity emitted

"user manual"

Contents

Download Pdf Manuals

Related Search

Related Contents

&quot;user manual&quot;

Contents

Download Pdf Manuals

Related Search

Related Contents

"user manual"