Curve & Surface design
Lecture: 8
Fall 2016
Computer Graphics (CS3388) Department of Computer Science
University of Western Ontario
Curve & Surface design
Outline
triangular meshes: limitations Parametric curves & continuity de Casteljau algorithm Bernstein polynomial
B-spline
Beta Spline
B ́ezier surface patch
materials from Ulf Assarsson (Chalmers Univ.), Frank Pfenning (CMU), Alla Sheffer (UBC), Stanford graphics class, MIT open course materials
1
Curve & Surface design
What are the problems with triangular meshes?
Need a lot of polygons to represent smooth shapes Need a lot of polygons to represent detailed shapes Hard to edit
Need to move individual vertices
Intersection test? Inside/outside test?
2
Examples
3
Geometry Modelling
Approaches:
Fixed set of primitives
Curves: lines, circles, rectangles,… Surfaces: spheres, cylinders,…
Freeform curves/surfaces
Single representation for arbitrarily complex geometry
Curves and surfaces as functions with built-in smoothness properties Be ́zier curves, splines
Discrete: meshes
4
Geometry Modelling
How do we specify a surface?
Explicit Implicit Parametric
5
Modelling with Curves
6
What makes a good representation?
There are many ways to represent curves and surfaces, we want a representation that is:
Stable
Smooth
Easy to evaluate
Must we interpolate or can we just come close to data? Do we need derivatives?
7
Review: curve continuity
0th order continuity: curves meet (sharp kink): C0 continuous
1st order continuity: 1st order derivatives are the same, i.e., tangent lines have same slope at the joining point: C1 continuous
2nd order continuity: 2nd order derivatives are the same at the joining point: C2 continuous
8
Parametric vs. Geometric continuity
Geometric continuity is often called “visual continuity”
Ex: smooth motion of a car is parametric continuity, whereas
smoothness of the track is geometric continuity
G1: Tangents point to the same direction C1: Tangents are the same
9
Explicit curve representation
Most familiar form of curve in 2D: y = f (x ) Ex: straight line: y = mx + b
In 3D: y = f (x), z = g(x) Surface in 3D: z = g(y) Problems:
vertical lines, circles (two or zero values of x)
Too dependent on coordinate system
Can’t model every curve in 2D
No true 3D curves possible (all curves confined to a plane)
Rarely used in computer graphics
10
Implicit curve representation
Curve in 2D: f (x , y ) = 0
Ex: straight line: ax +by +c = 0, circle x2 +y2 −r2 = 0
Surface in 3D: f (x , y , z ) = 0
Ex: plane: ax + by + cz + d = 0
3D surface
Inside: f(x,y,z)<0 Surface: f(x,y,z)=0 Outside: f(x,y,z)>0
Problems:
No 3D curve (Every implicit function in 3D describes a surface!) Often unintuitive
Difficult to render
useful to some extent
11
Parametric Curves for the rescue
Why parametric?
Flexible
Not required to be functions
Arbitrary curves in arbitrary dimensions
Problems:
Try to find a formula for a specific curve you have in mind! Hard to implement arbitrary mathematical functions
Solution:
Restrict yourself to specific class of functions
12
Parametric Curves
Separate equation for each spatial variable:
x = x(u) y = y(u) z = z(u)
p(u) = [x(u), y(u), z(u)]T
For umin ≤ u ≤ umax , we trace out a curve in two or three dimensions
13
Parametric Curves
Parametric Lines: Let 0 ≤ u ≤ 1. Line connecting two points p0 and p1:
p(u) = (1−u)p0 +up1
Parametric Circles:
x = cos(u),y = sin(u),z = 0
Parametric Surfaces:
p(u, v) = [x(u, v), y(u, v), z(u, v)]T
14
Designing a curve
Let’s assume that a curve is given by (u is normalized from 0 to 1):
p(u) = [x(u), y(u), z(u)]T
In classical numerical methods, we design a single global curve
In computer graphics and CAD, it is better to design small connected curve segments
15
What type of functions to choose?
Usually we can select “good” functions
Want functions which are easy to evaluate Want functions which are easy to differentiate Want functions which are smooth Approximate or interpolate known data
Not unique for a given spatial curve
16
We choose polynomials
Why polynomials?
Easy to evaluate
Continuous and differentiable everywhere
Must worry about continuity at join points including continuity of derivatives
17
Interactive curve design
18
Interactive curve design
Interactive design process:
1 Lay down the initial control points
2 Use the algorithm to generate the curve
3 If the curve is satisfactory, stop
4 Adjust the control points
5 Gotostep2
19
Be ́zier Curve
was developed by Paul de Casteljau in & Pierre Be ́zier initially used in the design of car bodies
given a set of input control points, the approximating curve (spline) is formed by adding a sequence of polynomial functions together that are formed from the control points
control points & control polygon have clear geometric meaning and are intuitive to use
widely used in computer graphics
20
de Casteljau algorithm
Input: sequence of points P0, P1, · · ·
Output: a curve P(t) at each value of t from 0 to 1
Let’s consider 3 points first
A(t) = (1−t)P0 +tP1 B(t)=(1−t)P1 +tP2
Repeat the interpolation on these points. The point P(t) that lies fraction t of the way between A & B:
P(t) = (1−t)A+tB
21
de Casteljau algorithm
The final expression for P(t) becomes:
P(t) = (1−t)2P0 +2t(1−t)tP1 +t2P2
How about 4 control points?
P(t) = (1−t)3P0 +3(1−t)2tP1 +3(1−t)t2P2 +t3P3
22
Bernstein Polynomial
The terms involved with the following equation are called Bernstein Polynomials,
P(t)=(1−t)3P0 +3(1−t)2tP1 +3(1−t)t2P2 +t3P3
B03(t) = (1 − t)3 B13(t) = 3(1 − t)2t B23(t) = 3(1 − t)t2 B3(t) = t3
23
Bernstein Polynomial
The terms of Bernstein Polynomial can be obtained by raising the expression a(t)=(1-t+t) to the third power by collecting terms in various powers of (1-t) & t
((1−t)+t)3 = (1−t)3 +3(1−t)2t +3(1−t)t2 +t3 This gives the following property of Bernstein Polynomials:
3
B k3 ( t ) = 1 k=0
Hence, P(t) is an Affine combination of points
24
de Casteljau algorithm
Generalization of de Casteljau algorithm
P4(t) = (1 − t)3P3(t) + tP3 (t) i i i+1
···
P4(t) = (1 − t)3PL−1(t) + tPL−1(t)
L i i+1
A B ́ezier curve of degree L is defined as,
where
P(t)=(1−t)LP0 +Lt(1−t)L−1P1 +···+tLPL
L
P ( t ) = P k B kL ( t )
k=0
BkL(t) = L! (1 − t)L−ktk k!(L − k)!
25
Be ́zier Curves
Are we done with designing curves?
Hell, NO!!!
But Be ́zier Curves provide endless variety of smooth curves by placing control points appropriately!
We want more !!!
26
Be ́zier Curves: Limitations
High degree polynomials are expensive to compute. (L+1) control points is a combination of L-degree polynomials!
Problem of Local Control
27
Be ́zier Curves: Limitations
So what’s exactly the problem?
All the points are “active” over the interval [0,1] Because the curve is a blend of all these functions!
Solution:
Use different blending functions for different intervals
28
Blending functions for local control
Say we incorporate 5 blending functions: R0(t), R1(t), …, R5(t) Support of R0(t) is [0,0.25]
Support of R1(t) is [0.25,0.50], …
V(t) = 5k=0 PkRk(t)
29
Blending functions
Desired properties of blending functions:
easy to controll & numerically stable
sum to 1 at every t in [a,b]
have small support for local control
interpolate certain points, chosen by the designer be smooth enough
30
polynomials as blending functions
Let’s try a simple cubic polynomial as blending function:
R(t)=at3 +bt2 +ct+d
Let’s see if there is a choice of coefficients that makes 1st derivatives to be
both 0 at t-0 & t=1:
R(0) = d = 0
R(1) = a + b + c + d = 0 R′(0) = c = 0 R′(1)=3a+2b+c =0
These conditions force a=b=c=d=0, which means there is no shape at all!!!
31
piecewise polynomials as blending functions
Let’s try piecing together several low-degree polynomials, called piecewise polynomials
g(t) consists of 3 polynomial segments: a(t), b(t) & c(t) a(t) = 1t2
2
b(t) = 3 − (t − 3)2 42
c(t) = 1(3 − t)2 2
32
piecewise polynomials as blending functions
Knots: values of t where segments meet
Joints: point where individual segments meet
Continuity test: a(1) = b(1) = 1/2, b(2) = c(2) = 1/2 1-smoothness test: a’(1) = b’(1) = 1, b’(2) = c’(2) = -1 2nd derivative is not continuous
33
Spline function
g(t) is an example of a spline function
Spline function: An M-th degree spline function is a piecewise
polynomial of degree M that is (M-1) – smooth at each knot g(t) is a quadratic spline
piecewise polynomial of degree 2 having first order derivatives continuous everywhere
34
Blending function
building a blending function out of g(t):
translate by integer amounts: gk (t ) = g (t − k ), k=0,1,… 6
V (t ) = Pk g (t − k ) k=0
Observation: exactly 3 blending functions are active at any value of t (at t=2,3,…,7 only two functions are active & have values 0.5, which means V(t) will lie at the midpoint of the line between two of the control points)
35
B-Spline
The general form of the blending function for (L+1) control points is:
L
P(t) = PkRk(t)
k=0
We can generalize b-spline of any order & write the above equation
for k-th order B-spline of order m as,
L
P(t) = Pk Nk,m(t)
k=0
k = 0, 1, …, L. If m=3, the polynomial is of order 3 & has degree 2
36
B-Spline
B-spline curve equation:
L
P(t) = Pk Nk,m(t)
k=0
The B-spline function is defined recursively as,
Nk,m(t) = t − tk Nk,m−1(t) + tk+m − t Nk+1,m−1(t) tk+m−1 − tk tk+m − tk+1
The first order function is defined as,
1,tk