CSCE 441 Lecture 29

« previous | Monday, March 31, 2014 | next »

No class Wednesday

Smooth Curves

Represented as polynomials: $p(t)=(x(t),y(t))$

Power Basis

$\{\begin{array}{ll}x(t)& =a+bt+c{t}^2+d{t}^3+\dots \\ y(t)& =e+ft+g{t}^2+h{t}^3+\dots \end{array}$

We can mess with coefficients, but it's hard to predict what the shape will look like just by modifiying coefficients.

Not intuitive.

Interpolation

Find a polynomial that passes through the specified values

$y(t)=a+bt+c{t}^2+d{t}^3$

$\begin{array}{rl}y(0)& =a=3\\ y(1)& =a+b+c+d=1\\ y(2)& =\dots \end{array}$

Interpolate for each component $x$ and $y$.

Lagrange Interpolation

Identical to matrix method, but uses a (recursive) geometric construction

Start with line from $y_0$ to $y_1$: $f(t)=(1-t)y_0+t{y}_1$

Add line from $y_1$ to $y_2$: $g(t)=(2-t)y_1+(t-1)y_2$

What about quadratic?

Find linear interpolation between two points: given points $t_0$ and $t_1$ with values $y_0$ and $y_1$, respectively, the linear interpolation of $y$ over $t$ is given by

$y(t)=\frac{(t_1-t)y_0+(t-t_0)y_1}{t_1-t_0}$

In our example, $h(t)=\frac{(2-t)f(t)-tg(t)}{2}$

What about cubic through 4 points?

• find quadratic of first 3 points
• find quadratic of last 3 points
• find linear interpolation of both functions

Basis: linear interpolation between two points

Induction:

• Assume we have points $y_i,\dots ,y_{n+1+i}$
• Build polynomial interpolating polynomials $f(t)$, $g(t)$ of degree $n$ for $y_i,\dots ,y_{n+1}$ and $y_{i+1},\dots ,y_{n+1+i}$
• $h(t)=\frac{(n+1+i-t)f(t)+(t-i)g(t)}{n+1}$

Problem: artifacts (oscillation) formed by pulling a single point out of line.

Bezier Curves

Polynomial curves that seek to approximate rather than interpolate.

Bernstein Polynomials

• Degree 1: $(1-t)$, $t^2$
• Degree 2: $(1-t{)}^2$, $2(1-t)t$, $t^2$
• Degree 3: $(1-t{)}^3$, $3(1-t{)}^{2}t$, $3(1-t)t^2$, $t^3$
• Degree $n$: $(\genfrac{}{}{0ex}{}{n}{i})(i-t{)}^{n-i}{t}^i$ for $0\le i\le n$.

Bezier curves are just $p(t)=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})(1-t{)}^{n-1}{t}^i{p}_i$ for control points $p_i$

Properties

• Interpolates endpoints exactly
• tangent at endpoints is in direction of first and last edge
• curve lies within the convex hull of the control points