This preview shows page 1-2-3-4-5-6-7-52-53-54-55-56-57-58-59-104-105-106-107-108-109-110 out of 110 pages.
#20: ReviewCSE167: Computer GraphicsInstructor: Ronen BarzelUCSD, Winter 20061Final Covers all material from all quarter: Lectures & Notes, Projects Will re-cover some of same material as midterm Will cover material from class but not in projects Same format as midterm: Short answers No OpenGL Closed book No cheat sheets2Outline for Today: Quick summary of main topics… Basics• See also the midterm review, class 9 Curves & Surfaces Culling & Clipping Scan Conversion Lighting Shading Texture Mapping Antialiasing Ray Tracing33-D Graphics Rendering PipelineNormalized view spaceModeling TransformationViewing TransformationLighting & ShadingClippingProjectionScan conversion, HidingPrimitivesImageObject spaceWorld spaceCamera spaceImage space, Device coordinatesCulling4The complete transform Composing the modeling matrix M, the camera matrix C,the projection matrix P, and the viewport matrix D, wehave, for some point p:pixel = (D P C-1 M) p5Mathematical Foundation Coordinate Systems, Coordinate Frames Vectors, Points Dot Products Cross Products Homogeneous Coordinates Transforms Composition of Transforms Inverses Triangles, Planes Normals6Geometric Computations Normal to an object Object in view cone Alignment to target Distance to plane Sphere Inside/Outside plane Lookat transform etc.7Hierarchical Transforms Current Transformation Matrix (CTM) Matrix Stack Local Matrix vs Local-to-World8Scene Graphs Node types Recursive traversal for drawing Computing Local-to-World Pictorial Composition Animating by updating properties Instantiation Bounding Nodes, Culling Nodes, LOD Nodes9Cameras Camera matrix Lookat Transform Object-to-camera transform Perpsective and Orthographics Transforms View Volumes Normalized View Space Viewport Transform10Models Common representation: Indexed Triangle Set Per-Facet or Per-Vertex data Model classes Know how to tessellate themselves to a triangle set e.g. sphere, bicubic patch, sweep, …11Tessellation Given a description of a surface Construct a triangle set (typically a mesh) Triangle set is an approximation Fewer triangles: Faster, but less accurate•Polygonal artifacts• Especially at silhouettes More triangles: slower, but more accurate In the extreme, make each triangle the size of a pixel (or less) Fancy algorithms: adaptive E.g., Make smaller triangles near silhouettes E.g., Use fewer triangles when objects are far away But must update/recompute tessellation each frame• Balance between cost of adaptive tessellation vs. rendering savings12E.g. Topological structure for spherePij! P (i-1)N+1+j[ ]13CURVES & SURFACES Bézier Curves Piecewise (multi-segment) curves Surface patches14Bézier Curves Can consider a higher-order extension of Lerp Cubic Bézier: 4 points Interpolates the endpoints Midpoints are “handles” that control the tangent at the endpointsp0p1p0p1p2p0p1p2p3Linear Quadratic Cubic15Convex Hull Property Construct a convex polygon around a set of points The convex hull of the control points Any weighted average of the points, with the weights all between 0 and 1: Known as a convex combination of the points Result always lies within the convex hull (including on the border) Bézier curve is a convex combination of the control points Curve is always inside the convex hull Very important property!• Makes curve predictable• Allows culling• Allows intersection testing• Allows adaptive tessellationp0p1p2p316de Casteljau Algorithmp0p1p2p3 Start with the control points And given a value of t In the drawings, t≈0.2517de Casteljau Algorithmp0q0p1p2p3q2q1q0(t) = Lerp t,p0,p1( )q1(t) = Lerp t,p1,p2( )q2(t) = Lerp t,p2,p3( )18de Casteljau Algorithmq0q2q1r1r0r0(t) = Lerp t,q0(t),q1(t)( )r1(t) = Lerp t,q1(t),q2(t)( )19de Casteljau Algorithmr1xr0•x(t) = Lerp t,r0(t),r1(t)( )20x = Lerp t, r0, r1( )r0= Lerp t,q0, q1( )r1= Lerp t,q1, q2( )q0= Lerp t, p0, p1( )q1= Lerp t, p1, p2( )q2= Lerp t, p2, p3( )p0p1p2p3!!!!!!!! p1q0r0p2x q1r1p3q2p4Recursive Linear Interpolation21 Notice: Weights always add to 1 B0 and B3 go to 1 -- interpolating the endpoints!!!!!!!!!!!!!!!!!!!!x(t) = B0t( )p0+ B1t( )p1+ B2t( )p2+ B3t( )p3The cubic Bernstein polynomials :!!!!!!!!!!!!!!!!!!!! B0t( )= !t3+ 3t2! 3t + 1!!!!!!!!!!!!!!!!!!!! B1t( )= 3t3! 6t2+ 3t!!!!!!!!!!!!!!!!!!!! B2t( )= !3t3+ 3t2!!!!!!!!!!!!!!!!!!!! B3t( )= t3!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Bi(t) = 1"B0(t ) B1(t ) B2(t ) B3(t )Weighted Average of Control Points22Polynomial, Matrix, Notation • Polynomial in t :!!!!!!!!x(t ) =!at3+!bt2+!ct + d!!x (t) = 3!at2+ 2!bt +!c!!!!!a = "p0+ 3p1" 3p2+ p3( )!b = 3p0" 6p1+ 3p2( )!c = "3p0+ 3p1( )d = p0( )•!Matrix form:!!!!!!!!x(t ) = p0p1p2p3[ ]GBez" #$$$ %$$$"1 3 "3 13 "6 3 0"3 3 0 01 0 0 0#$%%%%&'((((BBez" #$$$ %$$$t3t2t1#$%%%%&'((((T&!!!!!!!!!!!x (t) = GBezBBez3t22t10#$%%%%&'((((•!Notation:!!!!!!!!Bez(t, p0,p1,p2,p3) = x(t) for the given control points!!!!!!!!Be!z (t, p0,p1,p2,p3) =!!x (t) for the given control points23Tangent The derivative of a curve represents the tangent vector tothe curve at some point !!x (t ) =dxdtt( )x t( )24Piecewise Bézier curvex0(t)x1(t)x2(t)x3(t)x(0.3)x(0.71)x(0.25)x(0.0)x(0.5)x(0.75)x(1.0) !!!!!!!!!!!x (u) =x0(Nu), 0 ! u !1Nx1(Nu " 1),1N! u !2N! !xN "1(Nu " (N " 1)),N "1N! u ! 1#$%%&%%!!!!!!!!!!!x (u) = xiNu " i( ),!where i = Nu'()*,u < 1;= Bez(Nu " i, p3i,p3i +1,p3i + 2,p3i + 3)x(1) = p3N= Bez(1,p3i,p3i +1,p3i + 2,p3i + 3)25Continuity For the whole curve to look smooth, we need to consider continuity: C0 continuity: no gaps. The segments must match at the endpoints C1 continuity: no corners. The tangents must match at the endpoints C2 continuity: tangents vary smoothly. (makes smoother curves.) Note also: G1, G2, etc. continuity• Looks at geometric continuity without considering parametric continuity• Roughly, means that the tangent directions must match, but not the magnitudes• Gets around “bad” parametrizations• Often it’s what we really want, but it’s harder to compute26B-spline Need at least 4 points, i.e. N+3 points B-spline curve uses given N+3 points as is Always C2 continuous• no intermediate points needed Approximates rather than interpolates• doesn’t reach the endpoints• not a
View Full Document
Unlocking...