CSCE 441 Lecture 29

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

No class Wednesday

Smooth Curves

Represented as polynomials: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(t) = \left( x(t), y(t) \right)}

Power Basis

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} x(t) &= a + b\,t + c\,t^2 + d\,t^3 + \dots \\ y(t) &= e + f\,t + g\,t^2 + h\,t^3 + \dots \end{cases}}

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+b\,t+c\,t^{2}+d\,t^{3}$

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

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)-t\,g(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},\ldots ,y_{n+1+i}$
• Build polynomial interpolating polynomials $f(t)$, $g(t)$ of degree $n$ for $y_{i},\ldots ,y_{n+1}$ and $y_{i+1},\ldots ,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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-t)^3} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3(1-t)^2\,t} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3(1-t)\,t^2} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t^3}
• Degree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{n}{i} \, (i-t)^{n-i} \, t^i} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \le i \le n} .

Bezier curves are just Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(t) = \sum_{i=0}^n \, \binom{n}{i} \, (1-t)^{n-1} \, t^i \, p_i} for control points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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