September 30, 2003Doug JamesCarnegie Mellon Universityhttp://www.cs.cmu.edu/~djames/15-462/Fall03/Parametric RepresentationsCubic Polynomial FormsHermite CurvesBezier Curves and Surfaces[Angel 10.1-10.6]Parametric RepresentationsCubic Polynomial FormsHermite CurvesBezier Curves and Surfaces[Angel 10.1-10.6]Curves and SurfacesCurves and Surfaces15-462 Computer Graphics ILecture 109/30/2003 15-462 Graphics I 2GoalsGoals• How do we draw surfaces?– Approximate with polygons– Draw polygons• How do we specify a surface?– Explicit, implicit, parametric• How do we approximate a surface?– Interpolation (use only points)– Hermite (use points and tangents)– Bezier (use points, and more points for tangents)• Next lecture: splines, realization in OpenGL9/30/2003 15-462 Graphics I 3Explicit RepresentationExplicit Representation• Curve in 2D: y = f(x)• Curve in 3D: y = f(x), z = g(x)• Surface in 3D: z = f(x,y)• Problems:– How about a vertical line x = c as y = f(x)?– Circle y = (r2– x2)1/2two or zero values for x• Too dependent on coordinate system• Rarely used in computer graphics9/30/2003 15-462 Graphics I 4Implicit RepresentationImplicit Representation• Curve in 2D: f(x,y) = 0– Line: ax + by + c = 0– Circle: x2+ y2– r2= 0• Surface in 3d: f(x,y,z) = 0– Plane: ax + by + cz + d = 0– Sphere: x2+ y2+ z2– r2= 0• f(x,y,z) can describe 3D object:– Inside: f(x,y,z) < 0– Surface: f(x,y,z) = 0– Outside: f(x,y,z) > 09/30/2003 15-462 Graphics I 5What Implicit Functions are Good ForWhat Implicit Functions are Good ForF < 0 ? F = 0 ? F > 0 ?Inside/Outside TestXX + kVF(X + kV) = 0Ray - Surface Intersection Test9/30/2003 15-462 Graphics I 6Isosurfaces of Simulated TornadoIsosurfaces of Simulated Tornado9/30/2003 15-462 Graphics I 7Generate complex shapes with basic building blocksmachine an object - saw parts off, drill holesglue pieces togetherThis is sensible for objects that are actually made that way (human-made, particularly machined objects)Constructive Solid Geometry (CSG)Constructive Solid Geometry (CSG)9/30/2003 15-462 Graphics I 8A CSG TrainA CSG TrainBrian Wyvill & students, Univ. of Calgary9/30/2003 15-462 Graphics I 9•Use point-by-point boolean functions– remove a volume by using a negative object– e.g. drill a hole by subtracting a cylinderSubtractFromTo getInside(BLOCK-CYL) = Inside(BLOCK) And Not(Inside(CYL))CSG: Negative ObjectsCSG: Negative Objects9/30/2003 15-462 Graphics I 10CSGCSG9/30/2003 15-462 Graphics I 11CSGCSG9/30/2003 15-462 Graphics I 12Algebraic SurfacesAlgebraic Surfaces• Special case of implicit representation• f(x,y,z) is polynomial in x, y, z• Quadrics: degree of polynomial 2• Render more efficiently than arbitrary surfaces• Implicit form often used in computer graphics• How do we represent curves implicitly?9/30/2003 15-462 Graphics I 13Parametric Form for CurvesParametric Form for Curves• Curves: single parameter u (e.g. time)• x = x(u), y = y(u), z = z(u)• Circle: x = cos(u), y = sin(u), z = 0• Tangent described by derivative• Magnitude is “velocity”9/30/2003 15-462 Graphics I 14Parametric Form for SurfacesParametric Form for Surfaces• Use parameters u and v• x = x(u,v), y = y(u,v), z = z(u,v)• Describes surface as both u and v vary• Partial derivatives describe tangent plane at each point p(u,v) = [x(u,v) y(u,v) z(u,v)]T9/30/2003 15-462 Graphics I 15Assessment of Parametric FormsAssessment of Parametric Forms• Parameters often have natural meaning• Easy to define and calculate– Tangent and normal– Curves segments (for example, 0 u 1)– Surface patches (for example, 0 u,v 1)9/30/2003 15-462 Graphics I 16Parametric Polynomial CurvesParametric Polynomial Curves• Restrict x(u), y(u), z(u) to be polynomial in u• Fix degree n• Each ckis a column vector9/30/2003 15-462 Graphics I 17Parametric Polynomial SurfacesParametric Polynomial Surfaces• Restrict x(u,v), y(u,v), z(u,v) to be polynomial of fixed degree n• Each cikis a 3-element column vector• Restrict to simple case where 0 u,v 19/30/2003 15-462 Graphics I 18Approximating SurfacesApproximating Surfaces• Use parametric polynomial surfaces• Important concepts:– Join points for segments and patches– Control points to interpolate– Tangents and smoothness– Blending functions to describe interpolation• First curves, then surfaces9/30/2003 15-462 Graphics I 19OutlineOutline• Parametric Representations• Cubic Polynomial Forms• Hermite Curves• Bezier Curves and Surfaces9/30/2003 15-462 Graphics I 20Cubic Polynomial FormCubic Polynomial Form• Degree 3 appears to be a useful compromise• Curves:• Each ckis a column vector [ckxckyckz]T• From control information (points, tangents) derive 12 values ckx, cky, ckzfor 0 k 3• These determine cubic polynomial form• Later: how to render9/30/2003 15-462 Graphics I 21Interpolation by Cubic PolynomialsInterpolation by Cubic Polynomials• Simplest case, although rarely used• Curves:– Given 4 control points p0, p1, p2, p3– All should lie on curve: 12 conditions, 12 unknowns• Space 0 u 1 evenly p0= p(0), p1= p(1/3), p2= p(2/3), p3= p(1)9/30/2003 15-462 Graphics I 22Equations to Determine ckEquations to Determine ck• Plug in values for u = 0, 1/3, 2/3, 1Note:pkand ckare vectors!9/30/2003 15-462 Graphics I 23Interpolating Geometry MatrixInterpolating Geometry Matrix• Invert A to obtain interpolating geometry matrix9/30/2003 15-462 Graphics I 24Joining Interpolating SegmentsJoining Interpolating Segments• Do not solve degree n for n points• Divide into overlap sequences of 4 points• p0, p1, p2, p3then p3, p4, p5, p6, etc.• At join points– Will be continuous (C0continuity)– Derivatives will usually not match (no C1continuity)9/30/2003 15-462 Graphics I 25Blending FunctionsBlending Functions• Make explicit, how control points contribute• Simplest example: straight line with control points p0and p3• p(u) = (1 – u) p0+ u p3• b0(u) = 1 – u, b3(u) = u 11b3(u)b0(u)u9/30/2003 15-462 Graphics I 26Blending Polynomials for InterpolationBlending Polynomials for Interpolation• Each blending polynomial is a cubic• Solve (see [Angel, p. 427]):9/30/2003 15-462 Graphics I 27Cubic Interpolation PatchCubic Interpolation Patch• Bicubic surface patch with 4 4 control pointsNote: each cikis3 column vector(48 unknowns)[Angel, Ch. 10.4.2]9/30/2003 15-462 Graphics I
View Full Document