DOC PREVIEW
CMU CS 15462 - Splines

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CMU CS 15462 - Splines

Download Splines
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Splines and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Splines 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?