Mumbai university > Comp > SEM 4 > Computer Graphics

Marks: 10M

Year: May 2015

• Spline is a flexible strip used to produce a smooth curve through a designated set of points.

• Several small weights are distributed along the length of the strip to hold it in position on the drafting table as the curve is drawn. The term spline curve originally referred to a curve drawn in this manner.

• We can mathematically describe such a curve with a piecewise cubic polynomial function whose first and second derivatives are continuous across the various curve sections.

• In computer graphics, the term spline curve now refers to any composite curve formed with polynomial sections satisfying specified continuity conditions at the boundary of the pieces.

• A spline surface can be described with two sets of orthogonal spline curves. There are several different kinds of spline specifications that are used in graphics applications.

• Each individual specification simply refers to a particular type of polynomial with certain specified boundary conditions.

• Splines are used in graphics applications to design curve and surface shapes, to digitize drawings for computer storage, and to specify animation paths for the objects or the camera in a scene. Typical CAD applications for splines include the design of automobile bodies, aircraft and spacecraft surfaces, and ship hulls.

Steps:

• Given $f, x_0, . . . ,x_n$ as above, find a cubic spline S such that $S(x_i) = f(x_i), i = 0, . . . , n$.

n + 1 points ⇒ n intervals ⇒ 4n coefficients

2n conditions needed to interpolate $f(x_0), . . . , f(x_n)$

2(n − 1) conditions needed to ensure S’, S’’ are continuous at the interior points.

This leaves 2 free conditions. Popular choices are:

• $S’’(x_0) = S’’(x_n) = 0$: the natural cubic spline interpolant

• $S’(x_0) = f’(x_0), S’(x_n) = f’(x_n):$ the clamped cubic spline interpolant

• Given $f(x); x_0, . . . , x_n,$ how to find S(x)?

• EXAMPLE $x_i = ih, h = 1/n, x_0 = 0, x_n = 1$

• STEP 1 (2nd derivative conditions)

  Since $S_i(x)$ is a cubic polynomial, S’’(x) is linear for x

  $S_i’’(x) = a_i ((x_{i+1} - x)/h)+a_{i+1}((x-x_i)/h) , i = 0, . . . , n − 1$ (using Lagrange 1st order interpolating polynomial).

  Then

  $S_i’’ (x_i) = a_i$

  $S_i’’(x_{i+1})=a_{i+1}$

  $S''_{i-1} (x_i) = a_i = S''_i(x_i)$

  Thus, S’’(x) is continuous at the interior nodes.

• STEP 2 (function values)

  Integrate twice

$S_i(x) = \frac{a_i(x_{i+1} - x)^3}{6h} + \frac{a_{i+1}(x - x_i)^3}{6h} + b_i (xi + 1 − x) + ci(x − xi)$

the last two terms are written in this special form just for convenience

$S_i (x_i) = a_i(h^2/6) + b_ih = b_i$

$S_i (x_i + 1) = a_{i+1}(h^2/6) + c_ih = f_i +1$

$b_ih = f_i − a_i(h^2/6)$

$ c_ih = f_{i+1} − a_{i+1}(h^2/6)$

Substitute

$S_i (x) = \frac{a_i (x_{i+1} - x)^3}{6h} + \frac{a_{i+1}(x - x_i)^3}{6h} + (f_i − a_i(h^2/6)) ((x_{i+1} - x)/h) + (f_{i+1} − a_{i+1}(h^2/6)) ((x-x_i)/h)$

• STEP 3 (1st derivative conditions).

• $S'_i (x) = −\frac{a_i (x_{i+1} - x)^2}{2h} + \frac{a_{i+1}(x-x_i)^2}{2h} − ((f_i/ h) − a_i (h /6)) + ( (f_{i+1} /h) − a_{i+1} (h /6))$

• The co-efficient matrix is

  • Tri-diagonal

  • Positive defined

  • Strictly diagonal dominant