February 18, 2003Frank PfenningCarnegie Mellon Universityhttp://www.cs.cmu.edu/~fp/courses/graphics/Cubic B-SplinesNonuniform Rational B-SplinesRendering by SubdivisionCurves and Surfaces in OpenGL[Angel, Ch 10.7-10.14]Cubic B-SplinesNonuniform Rational B-SplinesRendering by SubdivisionCurves and Surfaces in OpenGL[Angel, Ch 10.7-10.14]SplinesSplines15-462 Computer Graphics ILecture 1102/18/2003 15-462 Graphics I 2ReviewReview• Cubic polynomial form for curve• Each ckis a column vector [ckxckyckz]T• Solve for ckgiven control points• Interpolation: 4 points• Hermite curves: 2 endpoints, 2 tangents• Bezier curves: 2 endpoints, 2 tangent points02/18/2003 15-462 Graphics I 3SplinesSplines• Approximating more control points• C0continuity: points match• C1continuity: tangents (derivatives) match• C2continuity: curvature matches• With Bezier segments or patches: C002/18/2003 15-462 Graphics I 4B-SplinesB-Splines• Use 4 points, but approximate only middle two• Draw curve with overlapping segments0-1-2-3, 1-2-3-4, 2-3-4-5, 3-4-5-6, etc.• Curve may miss all control points• Smoother at joint points02/18/2003 15-462 Graphics I 5Cubic B-SplinesCubic B-Splines• Need m+2 control points for m cubic segments• Computationally 3 times more expensive than simple interpolation• C2continuous at each interior point• Derive as follows:– Consider two overlapping segments– Enforce C0and C1continuity– Employ symmetry– C2continuity follows02/18/2003 15-462 Graphics I 6Deriving B-SplinesDeriving B-Splines• Consider points– pi-2, pi-1, pi, pi+1– p(0) approx pi-1, p(1) approx pi– pi-3, pi-2, pi-1, pi– q(0) approx pi-2, q(1) approx pi-1• Condition 1: p(0) = q(1)– Symmetry: p(0) = q(1) = 1/6(pi-2+ 4 pi-1+ pi)• Condition 2: p’(0) = q’(1)– Geometry: p’(0) = q’(1) = 1/2 ((pi– pi-1) + (pi-1– pi-2)) = 1/2 (pi– pi-2)02/18/2003 15-462 Graphics I 7B-Spline Geometry MatrixB-Spline Geometry Matrix• Conditions at u = 0– p(0) = c0= 1/6 (pi-2+ 4pi-1+ pi)– p’(0) = c1= 1/2 (pi– pi-2)• Conditions at u = 1– p(1) = c0+ c1+ c2+ c3= 1/6 (pi-1+ 4pi+ pi+1)– p’(1) = c1+ 2c2+ 3c3= 1/2 (pi+1– pi-1)02/18/2003 15-462 Graphics I 8Blending FunctionsBlending Functions• Calculate cubic blending polynomials• Note symmetries02/18/2003 15-462 Graphics I 9Convex HullConvex Hull• For 0 · u · 1, have 0 · bk(u) · 1• Recall:p(u) = bi-2(u)pi-2+ bi-1(u)pi-1+ bi(u)pi+ bi+1(u)pi+1• So each point p(u) lies in convex hull of pk02/18/2003 15-462 Graphics I 10Spline Basis FunctionsSpline Basis Functions• Total contribution Bi(u)piof piis given by02/18/2003 15-462 Graphics I 11Spline SurfaceSpline Surface• As for Bezier patches, use 16 control points• Start with blending functions• Need 9 times as many splines as for Bezier02/18/2003 15-462 Graphics I 12Assessment: Cubic B-SplinesAssessment: Cubic B-Splines• More expensive than Bezier curves or patches• Smoother at join points• Local control– How far away does a point change propagate?• Contained in convex hull of control points• Preserved under affine transformation• How to deal with endpoints?– Closed curves (uniform periodic B-splines)– Non-uniform B-Splines (multiplicities of knots)02/18/2003 15-462 Graphics I 13General B-SplinesGeneral B-Splines• Generalize from cubic to arbitrary order• Generalize to different basis functions• Read: [Angel, Ch 10.8]• Knot sequence umin= u0· ... · un= umax• Repeated points have higher “gravity”• Multiplicity 4 means point must be interpolated• {0, 0, 0, 0, 1, 2, ..., n-1, n, n, n, n} solves boundary problem02/18/2003 15-462 Graphics I 14Nonuniform Rational B-Splines (NURBS)Nonuniform Rational B-Splines (NURBS)• Exploit homogeneous coordinates• Use perspective division to renormalize• Each component of p(u) is rational function of u• Points not necessarily uniform (NURBS)02/18/2003 15-462 Graphics I 15NURBS AssessmentNURBS Assessment• Convex-hull and continuity props. of B-splines• Preserved under perspective transformations– Curve with transformed points = transformed curve• Widely used (including OpenGL)02/18/2003 15-462 Graphics I 16OutlineOutline• Cubic B-Splines• Nonuniform Rational B-Splines (NURBS)• Rendering by Subdivision• Curves and Surfaces in OpenGL02/18/2003 15-462 Graphics I 17Rendering by SubdivisionRendering by Subdivision• Divide the curve into smaller subpieces• Stop when “flat” or at fixed depth• How do we calculate the sub-curves?– Bezier curves and surfaces: easy (next)– Other curves: convert to Bezier!02/18/2003 15-462 Graphics I 18Subdividing Bezier CurvesSubdividing Bezier Curves• Given Bezier curve by p0, p1, p2, p3• Find l0, l1, l2, l3and r0, r1, r2, r3• Subcurves should stay the same!02/18/2003 15-462 Graphics I 19Construction of Bezier SubdivisionConstruction of Bezier Subdivision• Use algebraic reasoning • l(0) = l0= p0• l(1) = l3= p(1/2) = 1/8(p0+ 3p1+ 3p2+ p3)• l’(0) = 3(l1– l0) = p’(0) = 3/2 (p1– p0)• l’(1) = 3(l3 – l2) = p’(1/2) = 3/8(-p0– p1+ p2+p3)• Note parameter substitution v = 2u so dv = 2du02/18/2003 15-462 Graphics I 20Geometric Bezier SubdivisionGeometric Bezier Subdivision• Can also calculate geometrically• l1= ½(p0+ p1), r2= ½ (p2+ p3)• l2= ½ (l1+ ½ (p1+ p2)), r1= ½ (r2+ ½(p1+ p2))• l3= r0= ½ (l2+ r1), l0= p0, r3= p302/18/2003 15-462 Graphics I 21Recall: Bezier CurvesRecall: Bezier Curves• Recall• Express02/18/2003 15-462 Graphics I 22Subdividing Other CurvesSubdividing Other Curves• Calculations more complex• Trick: transform control points to obtain identical curve as Bezier curve!• Then subdivide the resulting Bezier curve• Bezier: p(u) = uTMbp• Other curve: p(u) = uTM q, M geometry matrix• Solve: q = M-1Mbp with p = Mb-1M q02/18/2003 15-462 Graphics I 23Example ConversionExample Conversion• From cubic B-splines to Bezier:• Calculate Bezier points p from q• Subdivide as Bezier curve02/18/2003 15-462 Graphics I 24Subdivision of Bezier SurfacesSubdivision of Bezier Surfaces• Slightly more complicated• Need to calculate interior point• Cracks may show with uneven subdivision• See [Angel, Ch 10.9.4]02/18/2003 15-462 Graphics I 25OutlineOutline• Cubic B-Splines• Nonuniform Rational B-Splines (NURBS)• Rendering by Subdivision• Curves and Surfaces in OpenGL02/18/2003 15-462 Graphics I 26Curves and Surface in OpenGLCurves and Surface in OpenGL• Central
View Full Document