Computer Graphics CSI4130 – Winter 2019
Jochen Lang
EECS, University of Ottawa Canada
Introduction to Splines
– Introduction
– Bézier curves
• Subdivision
• Bernstein-Bézier formula • De Casteljau algorithm
– Splines
• Canonical form, constraint and basis matrix • Catmull-Rom splines
CSI4130 Computer Graphics
Reminder:
Curve Representations
• Parametric
– Line equation
• Implicit
– Line equation
• Generative or procedural – E.g., subdivision
CSI4130 Computer Graphics
Free-Form Curves
• Line segments
– Easy to specify and draw – Mathematically
• segments are linear in parameter t – But just “straight” lines
• Polynomials
– Quadratic, cubic and higher order curves look nicer – Still relatively easy to handle
– Mathematically
• curves are a polynomial in parameter t
CSI4130 Computer Graphics
Polynomial via Subdivision, e.g.: Quadratic Bézier Curve
• Defined by 3 control points 𝟎 𝟏and 𝟐
• Recursive construction by subdivision function subdivide( p0, p1, p2 ) p01 = (p0+p1)/2
p12 = (p1+p2)/2
pM = (p01+p12)/2
subdivide( p0, p01, pM )
subdivide( pM, p12, p2 )
Note: Typically, function in 2D-4D.
CSI4130 Computer Graphics
Midpoints
• The midpoints will not be moved by subsequent subdivision, they are on the limit curve.
CSI4130 Computer Graphics
Control Points of Bézier Curve
– Set of points pi are called control points
– Control polygon is set of lines connecting adjacent control points
– Bézier curves are a weighted average of their control points→ curve is contained by the convex hull of the control points
– Control points can be in 1D, 2D or 3D
CSI4130 Computer Graphics
Aside: Convex Hull
– Convex hull encloses all points of a set
• 2D Intuitive explanation: elastic band around a point set
• Points can be on
the convex hull
• Often meshes are considered
• Verticies and edges (or
faces in 3D can be on the convex hull).
CSI4130 Computer Graphics
Convex Hull
– Formal definition
– Explanation:
• real positive weights that sum to 1
• Any weighted addition of points stays within convex hull • Consider line segment or barycentric coordinates
– Aside:
• Convex point-set or mesh has only points on the convex hull.
• Opposite of convex is concave.
CSI4130 Computer Graphics
Bézier Curves and de Casteljau Algorithm
– French engineer Pierre Bézier publicized Bézier curves in 1962. He was working for the French car maker Renault.
©Wikimedia Commons
– However, working for the French car maker Citroën, mathematician Paul de Casteljau had already developed an algorithm to evaluate Bézier curves in 1959.
CSI4130 Computer Graphics
Bézier Curve:
De Casteljau Algorithm
• Points on the Curve: Control
Points
Line Equations
Quadratic Equation
• PM is on the curve!
CSI4130 Computer Graphics
t=0.5
t=0.75
Bézier Curve:
De Casteljau Algorithm
• Derive base functions (e.g., cubic Bézier Curve):
CSI4130 Computer Graphics
Use of de Casteljau Algorithm
– Previous slides:
• Calculation of a specific point t on the curve • Geometric definition of Bézier curve
– Subdivision rules, binary subdivision with t=1/2
Right Subdivision
Left Subdivision
CSI4130 Computer Graphics
Basis Matrix Representation
• Example 2nd order Bézier curve:
Basis Matrix CSI4130 Computer Graphics
Bernstein-Bézier Formula
– Example: Quadratic Bezier curve ( control points)
• Bernstein-Bézier formula
Degree of basis functions
Number of control points CSI4130 Computer Graphics
• Basis/Blending functions:
– with control points and basis functions 𝟏
𝒏𝟏 𝒏𝟏 𝒋𝟎 𝒋 𝒋
Properties of Bézier Curves
– Degree of Bézier curve is the number of control points minus one
– All blending functions are positive in and sum to for
– No interpolation of control points (Bézier curve only goes through endpoints but not through the other control points)
– Beginning and end of curve are tangent to the control polygon
• Cubic Example
CSI4130 Computer Graphics
Bézier Curves Disadvantages
– Complex curves need high number of control points
– Higher number of control points leads to higher order polynomials
– No local control, moving one point moves the complete curve
CSI4130 Computer Graphics
Splines Idea
• Represent complex curve with simple segments
– Line segments
– What happens at ?
CSI4130 Computer Graphics
Cubic Bezier Curves in PPT
See also http://www.vis.uni-stuttgart.de/~kraus/LiveGraphics3D/cagd/ and http://www.rose-hulman.edu/~finn/CCLI/applets.htm
CSI4130 Computer Graphics
Spline Continuity
• Parametric continuity – C0 Continuity
– C1 Continuity
– C2 Continuity if curve is C1 continuous and
• Geometric continuity
– Only the sign of the derivatives need to match – G1 Continuity, G2 Continuity, etc.
CSI4130 Computer Graphics
Different Spline Sections
– Line segments
• discontinuous (C0 continuity)
– Polynomials
• Bezier curves can be joined to form a spline
– C0 at the segment boundary
– Discontinuities in first derivative at segment boundary
• Need better way to join polynomials
– Need to look at canonical form, constraint and basis matrix
CSI4130 Computer Graphics
Canonical Form
– Line segment
– Re-group and write in Canonical form
– Re-write
as a matrix equation with a constraint matrix C (only for linear relationships!)
CSI4130 Computer Graphics
Constraint Matrix
– Constraint matrix
• Example line segment
• How to find constraints?
– E.g., consider endpoints
– Recall basis matrix; line segment
– rewrite in canonical form
• Inverse of constraint matrix is basis matrix!
CSI4130 Computer Graphics
Specifying Constraints
– End points as constraints
– Consider quadratic
– Define constraint matrix at start, middle and end
CSI4130 Computer Graphics
Derivatives as Constraints
– Consider quadratic again
– So far points as constraints
– Alternative: Use middle point and derivatives
CSI4130 Computer Graphics
Hermite Cubics
– Consider cubic
– Use point and derivatives at beginning and end
CSI4130 Computer Graphics
Catmull-Rom Spline
– Idea: Join up Hermite cubics and calculate derivatives based on simple difference formula
First Section
– Specify for first Section
Second Section
– Catmull-Rom splines are C1 continuous!
CSI4130 Computer Graphics
Second section has same derivative at its start-point!
Basis Matrix for Catmull-Rom Spline
– Constraint matrix
CSI4130 Computer Graphics
Next Lecture
• Surfaces
CSI4130 Computer Graphics