 \documentclass[12pt]{article}

\def\vg{{\bf g}}
\def\vf{{\bf f}}

\title{Compulsory assignment 4\\ INF-MAT 5340\\ Spring 2009}
\author{}
\date{Deadline, 27 April 2009}

\begin{document}
\maketitle
\paragraph{Problem 1. Modelling cross sections of a heart.}
 In the data folder there are 9 files that contain data taken from
 contours of different cross sections of a heart. The file {\tt hj1.dat} is the smallest one
 and this cross section is taken from the 'bottom' of the heart while the file
 {\tt hj9.dat} is largest one with a cross section taken from the 'top' of the heart.
 The data were obtained by cutting a heart into thin slices and photographing each slice.
 The contours were then obtained via image processing techniques.
 Every contour is in the form $(x_i,y_i,z_i)_{i=1}^n$ where the number of points $n$ varies between the
 cross sections, and $z_i$ is constant for each cross section. Every cross section corresponds to
 a closed curve so the first point is identical to the last point. In this problem you are going
 to determine spline approximations to the cross sections.

Before we can approximate the data with splines, we must determine a parameter
value for each point. In other words, we want to augment the data set to
$(u_i,x_i,y_i,z_i)_{i=1}^n$ where
$(u_i)_{i=1}^n$ is an increasing sequence of numbers with $u_1=0$.
In this problem
we will use chord length parameterization, i.e., we use
$$u_i=u_{i-1} + \sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2+(z_i-z_{i-1})^2}$$ for
$i=2$, \dots, $n$.

The next step is to approximate the data by a cubic spline by
using least squares approximation.
For this, you need to choose a suitable knot vector.
Experiment by letting the length of the knot vector be $5\%$, $10\%$
and $20\%$ of the number of data points in the cross section and distribute the knots uniformly.
From earlier assignments you should have routines available for computing points on,
and plotting, spline functions. These must be adapted to computing points on, and plotting, spline curves. Present your results in three 3D plots that each show all the
cross sectional curves for a certain length of the knot vector.

\paragraph{Problem 2. Tensor products spline representation of the heart data.}
\noindent This problem is a continuation of problem 1.
The aim is to compute a parametric tensor product spline surface with the property that all of the 9 given
data sets are close to the surface. The construction is based on the theory in
Chapter~7 of the lecture notes.

In order to efficiently determine a tensor product spline surface, we need the data to be rectangular,
i.e., the data must be in the form
$(x_{i,j}, y_{i,j}, z_{i,j})_{i,j=1}^{m,n}$ for suitable $m$ and $n$.
From this we can compute a parametric tensor product spline surface
$\vf(u,v)$ where the $u$-variable runs along the $i$-index and
the $v$-variable runs along the $j$-index.

The solution of the problem can naturally be divided into three parts:
\begin{itemize}
\item[(a)] Generate a rectangular data set.
\item[(b)] Find parameter values for the data set and compute a spline surface.
\item[(c)] Plot the surface
\end{itemize}
\noindent Let us consider each of these steps in turn.

{(a)} In problem~1 you approximated the data with spline curves with knot vectors of different lengths.
We will
now take one of the sets of curves as a starting point, namely the one that
you think best fits the 9 given data sets. In other words, we start with 9 spline curves
that provide good representations of the 9 cross sections of the heart.
By sampling each of the nine curves at 20 points we obtain a data set $(x_{i,j},y_{i,j},z_{i,j})_{i,j=1}^{20,9}$. Here the
$i$-index runs along the curves while the $j$-index runs across the curves.
The question is which 20 values to pick along each curve.
We will use a simple (but not always very good) strategy: we pick values with {\sl uniform} parameter distance.
If curve no.~$j$ is $\vg_j(u)$ and the parameter $u$ varies in the interval $[0,U_j]$, we choose $(x_{i,j},y_{i,j})=\vg(i*U_j/19)$ for
$j=0$, $1$, \dots, $19$. The third component $z_{i,j}$ is constant for curve $j$
and explicitly known. The idea behind this is that if we now fix $i$, then $(x_{i,j},y_{i,j},z_{i,j})_{j=1}^9$
will be points on the 9 cross sectional curves that should be naturally linked by a curve across these curves.

Generate the 180 points as described above.
\medskip

{(b)}
In order to compute a tensor product spline surface we need two knot vectors.
Because of the way in which we obtained the data, it is natural to use uniform
parameterization so that the point
$(x_{i,j},y_{i,j},z_{i,j})$ is assigned the parameter value
$(u_i,v_j)=(i/19,j/8)$.
This will give you enough data to compute the three components of a parametric, tensor product
cubic spline surface with the least squares method, as explained in Section~7.2 in the notes.
Use a uniform $4$-regular knot vector with 7 interior knots in the
$u$-direction and a uniform $4$-regular knot vector with 1 interior knot in the  $v$-direction.

Determine the spline surface.
\medskip

{(c)} By using standard spline procedures you can compute points on the spline surface that you determined in (b), as shown in Section~7.1 of the lecture notes. Do this (try with a uniform
$30\times30$-grid) and plot the result.

\bigskip
\centerline{Knut M{\o}rken and Michael Floater}



\end{document}
