程序代写代做代考 scheme flex algorithm cse3431-lecture15-paramcurves

cse3431-lecture15-paramcurves

Curves and Surfaces

Curve Design

Representing curves
Explicit: y = f(x), z=g(x)
• Cannot get multiple values for single x, infinite slopes
• E.g. cannot represent a circle

Implicit (2D): f(x,y) = 0
• Cannot easily compare tangent vectors at joints
• Above/below test, normals from gradient

Parametric: x=fx(t), y = fy(t), z= fz(t)
• Often the most convenient formulation
• Tangent of curve (f(t),g(t),h(t)) is (f’(t), g’(t),h’(t)) where ’

indicates derivative wrt to t

Describing curves by means of
polynomials

Reminder:
Lth degre polynomial

Parametric and implicit forms are linear
x(t) = at +b
y(t) = ct +d
F(x,y) = kx + ly+m

Polynomial Curves of Degree 1

y(x)

y(t)

x(t)

Polynomial Curves of Degree 2
Parametric
x(t) = at2+2bt+c
y(t) = dt2+2et+f
t in R
For any choice of constants

a,d,c,d,e,f →parabola

Implicit
F(x,y) = Ax2+2Byx+Cy2+Dx+Ey+G
Let d = AC-B2
d > 0 → F(x,y) = 0 is an ellipse
d = 0 → F(x,y) = 0 is a parabola
d < 0 → F(x,y) = 0 is a hyperbola 1. Parabola 2. Circle and Ellipse 3. Hyperbola Courtesy of Pbroks13, Wikipedia http://commons.wikimedia.org/wiki/User:Pbroks13 Polynomial curves of degree 2 Common Vertex form: Rational Quadratic Parametric Curves w < 1 ellipse w = 1 parabola w > 1 hyperbola

Other kinds of curves
Sinusoidal
Exponential
Complex
Fractals

Differential Geometry Concepts
Tangent vector
• Given a parameterized curve  

p(t): τ(t) = p’(t) = dp(t)/dt 
defines the forward orientation of the curve and the
parametric velocity

• Notice that it is a function of t and that it is a vector
• It defines locally (instantaneously) the shape of the

curve at each point and can be used for interactive
design tools

• Unit tangent: T(t) = τ(t) / ||τ(t)||

Differential Geometry Concepts
Normal vector (AKA curvature vector)
• Given the unit tangent vector T(t):

•  

• Indicates how far from a straight line the curve is 
(Line has 0 curvature)

• Normal to the tangent vector T 

e2(t) = p
00(t)� (p00(t) ·T(t))T(t)

N(t) =
e2(t)

||e2(t)|| N

Differential Geometry Concepts
Binormal
• Normal to both tangent and normal vectors
• In 3D:  

B = T ⊗ N

Frenet frame
The three vectors together form the Frenet
frame

Osculating plane
defined by N,T

Curve design in graphics and
animation

• In graphics we often want to interpolate or
approximate a set of values in an efficient and
predictable way

• We use parametric polynomials and constrain them to
create desired types of curves

Geometric approach

P0, …,PL→ → P(t)

Constraints Polynomial Curve

Parametric polynomial curve
design in graphics

Curve
generation

Any t

Interpolation vs
Approximation

Geometric approach

P0, …,PL→ → P(t)

Constraints Polynomial Curve

Pi control points

P0 …PL control polygon

Parametric polynomial curve
design in graphics

Curve
generation

Any t

Interpolation vs
Approximation

Tweening
Two points=line

A(t) = (1-t)P0 + tP1

De Casteljau Algorithm

A(t)

Tweening
Three points

A(t) = (1-t)P0 + tP1
B(t) = (1-t)P1 + tP2

De Casteljau Algorithm

P1
P2

A(t)

B(t)

Tweening
Three points
(parabola)

A(t) = (1-t)P0 + tP1
B(t) = (1-t)P1 + tP2
P(t) = (1-t) A(t) + tB(t) = (1-t)2P0 +2t(1-t)P1+t2P2

De Casteljau Algorithm

A(t)

B(t)

P(t)

P1
P2

Tweening
Three points
(parabola)

A(t) = (1-t)P0 + tP1
B(t) = (1-t)P1 + tP2
P(t) = (1-t) A(t) + tB(t) = (1-t)2P0 +2t(1-t)P1+t2P2

De Casteljau Algorithm

A(t)

B(t)

P(t)

P1
P2

De Calsteljau (cont)
Tweening with four points

P(t) = (1-t)3P0+3(1-t)2tP1+3(1-t)t2P2+t3P3

P1
P2

A(t)

B(t)

P(t)
P3

One of the most fundamental concepts in
curve design

P(t) = (1-t)3P0+3(1-t)2tP1+3(1-t)t2P2+t3P3

Bezier Curves

P1
P2

P(t)
P3

Visualization
• Courtesy of Phil Tregoning, Wikipedia

Coefficients of Bezier Curves:
Berstein polynomials

P(t) = (1-t)3P0+3(1-t)2tP1+3(1-t)t2P2+t3P3
B30 (t) = (1- t)3

B31 (t) = 3(1- t)2t

B32 (t) = 3(1-t)t2

B33 (t) = t3

Expansion of [(1- t) + t]3 = (1- t)3 +3(1- t)2t + 3(1- t)t2 +t3 →
Σ B3k (t) = 1, k = 0,1,2,3

Affine combination of points

L + 1 control points, Pk

Expansion of [(1-t) + t]L

Berstein Polynomials of L
degree

P (t) =
LX

k=0

BLk (t)Pk where

BLk (t) =

✓
L
K

◆
(1� t)L�ktk

✓
L
K

◆
=

k!(L� k)!
, for L � k

A�ne combination:
LX

k=0

BLk (t) = 1, for all t

Other Berstein Polynomials
Properties

Allways positive
Zero only at t =0 or 1

Degree 3

Properties of Bezier curves
• End point interpolation
• Affine Invariance:
• Invariance under affine transformation of the

parameter
• Convex Hull property 

for t in [0,1]
• Linear precision by collapsing convex hull
• Variation Diminishing property: No straight line cuts

the curve more times than it cuts the control polygon

Derivatives of Bezier curves
It can be shown that:
Any derivative also a Bezier curve of lower degree

Which degree is best?
Cubic curves
• Lower order not enough flexibility
• Higher order too many wiggles and computationally

expensive
• Cubic curves are lowest degree polynomial curves

that are not planar in 3D

More complex curves
• Piecewise cubics

The general case for Cubic
Parametric Curves (piece)

• Bezier Cubic Curves are only one possible family of
cubic curves.

• We want more control of the constraints on the curves
– location
– shape

•

General form of Cubic
parametric curves

Matrix Form

Derivative of Cubic Parametric
Curves – tangent vector

Where the curve goes for  
some t

How the curve is shaped
for some t

For a given set of constraints we get a family
of curves

Constraints
Endpoints and a tangent at midpoint

Setting up the curve
Constraints

Solving for A
Constraints

Final form
Basis matrix

For the example

Blending functions
T*M

For the example

Each blending function  
weights the contribution
of one of the constraints

Hermite Curves
Constraints
Two points and two tangents

Hermite Curves
Blending functions

What does the magnitude of the
tangent do?

Interactive demo

Bezier Curves
Special case of Hermite
curves

Transforming between
representations

Just like Bezier and Hermite curves can be
transformed into each other with a matrix
multiplication, other families of curves can
do so as well

Bezier to Interpolating curves
• Curve must interpolate 

Pi0,Pi1,Pi2,Pi3

Pi0

Pi3
Pi1 Pi2

Bezier to Interpolating curves
• Curve must interpolate 

Pi0,Pi1,Pi2,Pi3
• How can we find the

Bezier points Pb from the
Pis so that the resulting
Bezier curve interpolates
the Pi points?

Pi0

Pb1
Pb2

Pi3
Pi1 Pi2

Bezier to Interpolating curves
For the next three slides
points are row vectors!!

Pb1
Pb2

Pi1 Pi2

Pi0

Pi3

Bezier to Interpolating curves

Pb1
Pb2

Pi1 Pi2

Pi0

Pi3

Bezier to Interpolating curves

Pi0

Pb1
Pb2

Pi3
Pi1 Pi2

Piecewise cubic curves

Connection?

Continuity
Geometric Gk-continuity
P(i)(t-) = ciP(i)(t+) ∀t in [a,b]

for i = 0,…,k and
for some ci positive

constants

(P(i) is the i-th derivative)

Parametric Ck-continuity
P(i) exists and is continuous ∀t

in [a,b], for i = 0,…,k
Terminology:
P is k-smooth
P has kth-order continuity

Is a Ck-continuous function GK continuous as well?

Examples
C1

C1
C2

Piecewise Cubic Hermite Curves

What are the conditions for G1 continuity?

Piecewise Cubic Hermite Curves

R’1 = kR4

P1’= P4

Catmull-Rom splines

Fit a piece wise cubic curve to the points
• Pi, i = 0,1,…,n-1

P1xt

Pn-1xt
P2xt

Catmull-Rom splines

Fit a piece wise hermite curve to the points
• Pi, i = 0,1,…,n-1

Second order accurate tangents
• Ti = (Pi+1 – Pi-1)/2.0 for i = 1,…,n-2
• T0 = 2(P1 – P0) – (P2-P0)/2, similarly for Tn-1

P1xt

Pn-1xt
P2xt

Uniform BSplines

Matrix form
For a bspline curve with:
• m+1 control points P0, …, Pm
• m-2 segments Q3,…, Qm
• t in [3,…,m]

Properties
C2 continuous
Convex hull property
NO invariace under perspective projection!

NURBS: Nonuniform Rational B-
splines

X(t) = X(t) / W(t)
Y(t) = Y(t) / W(t)
Z(t) = Z(t) / W(t)
• Exact conic sections
• Invariance under perspective projection

Summary: General problem

P0, …,PL→ → P(t)Curve generation

P (t) =
3X

i=0

Bi(t)Pi, t 2 [a, b], a, b 2 < where Bi(t) : Blending functions Pi, i = 1, · · · , L : Control Points Blending functions Weight the influence of each constraint (e.g. control point) on the curve created. B1 B2 B3 t Wish list for blending functions • Easy to compute and stable • Sum to unity for every t in [a,b] • Support over portion of [a,b] • Interpolate certain control points • Sufficient smoothness P (t) = LX k=0 BLk (t)Pk where BLk (t) = ✓ L K ◆ (1� t)L�ktk ✓ L K ◆ = L! k!(L� k)! , for L � k A�ne combination: LX k=0 BLk (t) = 1, for all t Example: Bezier curves • Sum up to unity • Smooth • Interpolate first and last • Expensive to compute for large L • No local control Rendering parametric curves Transform into primitives we know how to handle • Line segments Single cubic segment C(t): t in [0,1] C(0) C(1) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Draw as lines C(0) C(1) C(0) C(dt) C(2dt) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Here n = 2 and dt = 1/(n-1) = 1 C(0*dt = 0) C((n-1)*dt=1) Two points Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Here n = 3 and dt = 1/(n-1)= 0.5 C(0*dt = 0) C((n-1)*dt=1) Three points C(1*dt = 0.5) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) Here n = 4 and dt = 1/(n-1) = 0.33 Four points C(0) C((n-1)*dt=1) C(0.66) C(0.33) Converting to Lines Straightforward Uniform subdivision Evaluate C(t) at n points spaced by dt=1/(n-1) C(0), C(dt), C(2dt),…,C((n-1)*dt=1) All together for comparison Many points Three points Four points C(0) C((n-1)*dt=1) C(dt) C(2dt) Two points How many evaluation points are enough for Bezier curves? Not too few Not too many Ok, how many? Subdivision schemes Uniform Non-uniform • Adaptive Error metrics that define how much information we are losing An example... Adaptive Subdivision of Bezier Curves de Casteljau subdivision One Bezier curve becomes 2 flatter curves Original points 1,2,3,4 à Midpoints 12, 23, 34 Midpoints of midpoints: 123, 234 Midpoints of midpoints of midpoints, 1234 Remember: tweening for t = 0.5 Can chose any t we want Ok, how many times do we subdivide? Images courtesy of   Maxim Shemanarev Error metrics Examples: Point distance Tangent distance Images courtesy of   Maxim Shemanarev

Published by admin

Leave a Reply Cancel reply