Parametric Curves & Surfaces

OverviewPart 1: CurvesPart 2: SurfacesParametricCurves & SurfacesAdam FinkelsteinPrinceton UniversityCOS 426, Spring 2002Przemyslaw PrusinkiewiczCurvesMany applications in graphics Splines: mathematical way to express curves Motivated by “loftsman’s spline”ooooLong, narrow strip of wood/plasticUsed to fit curves through specified data pointsShaped by lead weights called “ducks”Gives curves that are “smooth” or “fair” Have been used to design:o Automobileso Ship hullso Aircraft fuselage/wingGoals Some attributes we might like to have:oooooPredictable controlMultiple valuesLocal controlVersatilityContinuity We’ll satisfy these goals using:o Piecewiseo Parametrico Polynomials FontsABC Animation paths Shape modelingAnimation(Angel, Plate 1) etc Shell(Douglas Turnbull,CS 426, Fall99)Parametric curvesA parametric curve in the plane is expressed as:x x(u)y y(u)Example: a circle with radius r centered at origin:x r cos uy r sin uIn contrast, an implicit representation is:x2 y2 r21

Parametric polynomial curvesPiecewise parametric polynomials A parametric polynomial curve is described: Use different polynomial functionson different parts of the curvenx (u ) ai u ii 0ny (u ) bi uo Provides flexibilityo How do you guarantee smoothness at “joints”?(continuity)ii 0 In the rest of this lecture, we’ll look at: Advantages of polynomial curveso Bézier curves: general class of polynomial curveso Splines: ways of putting these curves togethero Easy to computeo Infinitely differentiableBézier curvesBasic properties of Bézier curves Developed independently in 1960s by Endpoint interpolation:o Bézier (at Renault)o deCasteljau (at Citroen)Q (0) V0Q (1) Vn Curve Q(u) is defined by nested interpolation: Convex hull:V1o Curve is contained within convex hull of control polygonV2Q(u)V0 SymmetryV3Q (u ) defined by {V0 ,.,Vn } Q (1 u ) defined by {Vn ,.,V0 }Vi’s are control points{V0, V1, , Vn} is control polygonExplicit formulationMore properties Let’s indicate level of nesting with superscript j: General case: Bernstein polynomials An explicit formulation of Q(u) is given by:Vi (1 u )Vijj 1n n Q (u ) Vi u i (1 u )n ii 0 i j 1i 1 uV Case n 2 (quadratic): Degree: polynomial of degree nQ (u ) V20 (1 u )V01 uV11 (1 u )[(1 u )V00 uV10 ] u[(1 u )V10 uV20 ] Tangents:Q ' (0) n (V1 V0 )Q ' (1) n(Vn Vn 1 ) (1 u ) 2V00 2u (1 u )V10 u 2V202

Cubic curvesMatrix formBézier curves may be described in matrix form: From now on, let’s talk about cubic curves (n 3) In CAGD, higher-order curves are often used In graphics, piecewise cubic curves will don n Q (u ) Vi u i (1 u )n ii 0 i (1 u )3V0 3u(1 u ) 2V1 3u 2 (1 u )V2 u 3V3o Specified by points and tangentso Allows specification of a curve in space (u 3 u 2 All these ideas generalize to higher-order curves 1 3 3 3 6 3u 1) 0 3 3 00 11 V0 0 V1 0 V2 0 V3 MBezierDisplayDisplayQ: How would you draw it using line segments?A: Recursive subdivision!V1V2V0V3FlatnessPseudocode for displaying Bézier curves:procedure Display({Vi}):if {Vi} flat within εthenoutput line segment V0Vnelsesubdivide to produce {Li} and {Ri}Display({Li})Display({Ri})end ifend procedureSplinesQ: How do you test for flatness? For more complex curves, piece together BéziersA: Compare the length of the control polygonto the length of the segment between endpoints We want continuity across joints:V1 Q: How would you satisfy continuity constraints?V2V0o Positional (C0) continuityo Derivative (C1) continuityV3 V1 V0 V2 V1 V3 V2 1 ε V3 V0 ( or, compare dot products ) Q: Why not just use higher-order Bézier curves? A: Splines have several of advantages: Numerically more stable Easier to compute Fewer bumps and wiggles3

Catmull-Rom splines PropertiesCatmull-Rom Splines Catmull & Rom use:o Interpolate control pointso Have C0 and C1 continuityo half the magnitude of the vector between adjacent CP’s Derivationo Start with joints to interpolateo Build cubic Bézier between each jointo Endpoints of Bézier curves are obvious What should we do for the otherBézier control points?Matrix formulation Many other formulations work, for example:ooooUse an arbitrary constant τ times this vectorDefault is 1/2Gives a “tension” controlCould be adjusted for each jointPropertiesConvert from Catmull-Rom CP’s to Bezier CP’s: Catmull-Rom splines have these attributes:o C1 continuity B0 0 B1 1 1 B 6 0 2 0 B3 0 V0 0 V1 1 6 1 V2 0 6 0 V3 6 06 1o Interpolationo Locality of controlo No convex hull property(Proof left as an exercise.)Exercise: Derive this matrix.(Hint: in this case, τ is not 1/2.)B-splinesMatrix formulation for B-splines We still want local control Now we wantC2 Grind through some messy math to get:continuity Give up interpolation It turns out we get convex hull property Constraints:Q (u ) (u3u2 1 3 3 1 3 6 3u 1) 36 3 0 41 11 V0 0 V1 0 V2 0 V3 o Three continuity conditions at each joint j» Position of two curves same» Derivative of two curves same» Second derivatives sameo Local control» Each joint affected by 4 CPs4

Curved SurfacesCurved Surfaces Motivation What makes a good surface representation?o Exact boundary representation for some objectso More concise representation than polygonal meshooooooooooAccurateConciseIntuitive specificationLocal supportAffine invariantArbitrary topologyGuaranteed continuityNatural parameterizationEfficient displayEfficient intersectionsH&B Figure 10.46Curved Surface RepresentationsCurved Surface Representations Polygonal meshes Polygonal meshes Subdivision surfaces Subdivision surfaces Parametric surfaces Parametric surfaces Implicit surfaces Implicit surfacesParametric SurfacesSurface of revolution Boundary defined by parametric functions: Idea: take a curve and rotate it about an axiso x fx(u,v)o y fy(u,v)o z fz(u,v) Example: ellipsoidx rx cos φ cosθy ry cos φ sin θz rz sin φH&B Figure 10.10Demetri Terzopoulos5

Swept surfaceParametric SurfacesIdea: sweep one curve along path of another curveAdvantage: easy to enumerate points on surface.vuDisadvantage: need piecewise-parametric surfaceto describe complex shape.Demetri TerzopoulosPiecewise Parametric SurfacesParametric PatchesSurface is partitioned into parametric patches:Same ideas as parametric splines!FvDFH Figure 11.42 Each patch is defined by blending control pointsWatt Figure 6.25Parametric PatchesSame ideas as parametric curves!FvDFH Figure 11.44Parametric Bicubic Patches Point Q(u,v) on the patch is the tensor product ofparametric curves defined by the control pointsQ(0,1)Q(u,v)Q(1,1)Q(0,0)Q(1,0)Watt Figure 6.21Point Q(u,v) on any patch is defined by combiningcontrol points with polynomial blending functions: P1,1 PQ(u, v ) UM 2,1 P3,1 P4,1[U u3u2P1, 2P2, 2P3, 2P4, 2]u 1P1,3P2,3P3,3P4,3P1, 4 P2, 4 T T M VP3, 4 P4, 4 [V v3v2]v 1Where M is a matrix describing the blending functionsfor a parametric cubic curve (e.g., Bezier, B-spline, etc.)6

B-Spline PatchesBezier Patches P1,1 PQ(u, v ) UM B Spline 2,1 P3,1 P4,1P1, 2P2, 2P3, 2P4, 2 1 6 1 2 1 2 1 61 6 0 0 0 M B Spline12 1023 11112226P1,3P2,3P3,3P4,3P1, 4 P2, 4 TV MP3, 4 B SplineP4, 4 P1,1 PQ(u, v ) UM Bezier 2,1 P3,1 P4,1P1, 2P2, 2P3, 2P4, 2 1 3 3M Bezier 3 6 3 3 3000 1P1, 4 P2, 4 TV MP3, 4 BezierP4, 4 1 0 0 0 FvDFH Figure 11.42Watt Figure 6.28Bezier PatchesP1,3P2,3P3,3P4,3Bezier Surfaces Properties: Continuity constraints are similar to thecontraints Bezier splineso Interpolates four corner pointso Convex hullo Local controlFvDFH Figure 11.43Watt Figure 6.22Bezier SurfacesBezier Surfaces C0 continuity requires aligning boundary curvesWatt Figure 6.26a C1 continuity requires aligning boundary curvesand derivatives (a reason to prefer subdiv. surf.)Watt Figure 6.26b7

Drawing Bezier SurfacesDrawing Bezier Surfaces Simple approach is to loop throughuniformly spaced increments of u and v Better approach is to use adaptive subdivision:DrawSurface(surface){if Flat (surface, epsilon) {DrawQuadrilateral(surface);}else {SubdivideSurface(surface, wSurface(void){for (int i 0; i imax; i ) {float u umin i * ustep;for (int j 0; j jmax; j ) {float v vmin j * vstep;DrawQuadrilateral(.);}}}Uniform subdivisionAdaptive subdivisionWatt Figure 6.32Drawing Bezier SurfacesWatt Figure 6.32Parametric Surfaces One problem with adaptive subdivision is avoidingcracks at boundaries between patches at differentsubdivision levelsCrack Advantages:o Easy to enumerate points on surfaceo Possible to describe complex shapes Disadvantages:o Control mesh must be quadrilateralso Continuity constraints difficult to maintaino Hard to find intersectionsAvoid these cracks by adding extra vertices and triangulatingquadrilaterals whose neighbors are subdivided to a finer level.Watt Figure 6.33Blender (www.blender.nl)8

Surface is partitioned into parametric patches: Watt Figure 6.25 Same ideas as parametric splines! Parametric Patches Each patch is defined by blending control points Same ideas as parametric curves! FvDFH Figure 11.44 Parametric Patches Point Q(u,v) on the patch is the tensor product of parametric curves defined by the control points