\input header
\input epsf

\title{Subdivision Curve Definitions}

These notes are a continuation of those on the nature of subdivision
curves previously issued.  We start with some small print defining
things, then classify curve subdivisions according to the pattern the
refinement makes, and then explore two major families of refinements.
These two families do not exhaust the possiblilities, but provide a
base from which to work.


\section{Limitations to the treatment here}

We limit ourselves here to:-

\pop stationary schemes, in which the same mask is used in all iterations.

{\narrower 
{The same mask is also used at all places of the curve.  In
my view the eventual standard methods will not be stationary in either
sense, the mask being dependent on the geometry of the defining
control polygon.  However, such schemes will tend towards a stationary
limit as the recursion proceeds, and so understanding the stationary
case is an essential grounding.}

}

\pop symmetric schemes, in which the mask is palindromic.

{\narrower 
{Making the mask depend on the local geometry will also
spoil this property, but we can define the dependence in such a way
that this property, also, applies in the limit.}

}

\section{Characterisation of subdivision schemes}

The scheme is basically defined by the matrix equation
$$P' = S.P$$ 
where $S$ is higher than it is wide, so that $P'$
contains more points than $P$.

$S$ is called the {\bf subdivision matrix}.

\filbreak
All the columns of $S$ are identical (except as perturbed by end
conditions), but shifted by a number of rows called the {\bf arity}.
The arity gives the number of new polygon edges corresponding to each
old edge.

Each column contains a sequence of numbers called the {\bf
coefficients} and the number of them is called the {\bf width} of the
scheme.

The column is called the {\bf mask}, or the {\bf coefficient map}.

\filbreak
The rows of $S$ are called the {\bf stencils}, or {\bf templates}.
There are arity different rows, and so it is clearest to regard the
matrix $S$ as being defined by the mask, (its columns) and the arity.

The stencils are then implicit.

\filbreak
Most schemes have coefficients which are ratios of small numbers, and
it is convenient to take the least common multiple of their
denominators outside the matrix, which can then be recorded in print
as a matrix of integers with a common denominator outside.  This makes
the printed form much less fussy.

\section{Four Patterns}

For univariate schemes there are four patterns, depending on whether
the width, $w$, and the arity, $a$, are even or odd.

\subsection{$w$ odd, $a$ even}

If the width is odd and the arity even, we find that each old vertex
finds itself opposite a new vertex.  Each old mid-edge is also
opposite a new vertex.

We call such schemes {\bf primal}.

\subsection{$w$ even, $a$ even}

If the width is even and the arity even, we find that each old vertex
finds itself opposite a new mid-edge.  Each old mid-edge is also
opposite a new mid-edge.

We call such schemes {\bf dual}.

\subsection{$w$ odd, $a$ odd}

If the width is odd and the arity odd, we find that each old vertex
finds itself opposite a new vertex.  Each old mid-edge is opposite a
new mid-edge.

We call such schemes {\bf both}, since both vertices and mid-edges
preserve their nature under subdivision.

\subsection{$w$ even, $a$ odd}

If the width is even and the arity odd, we find that each old vertex
finds itself opposite a new mid-edge, and each old mid-edge is
opposite a new vertex.

We call such schemes {\bf neither}.

\subsection{Squaring}

If a scheme is applied twice we may regard the effect as being that of
a new scheme, called the {\bf square} of the original.

\subsection {Exercise}

Determine the width and arity of the square, as functions of the width
and arity of the original scheme.  Hence determine the classification
of the square.

\section{Box-Splines}

Box-Splines are a generalisation of equal interval B-splines to
multiple dimensions, which coincide with the equal interval B-splines
in the case of univariate functions.

They were observed by Sommerfeld, when exploring the nature of the
distribution of the sum of large numbers of random variables, and he
used them to prove that this distribution was the Gaussian.

A {\bf Box} is the outer product of $d$ intervals, and we can imagine
it as a hypercube in a space of $d$ dimensions.

Consider a subspace of $d-1$ dimensions, perpendicular to the main
diagonal of the box, and take the hypervolume of its intersection with
the box.  Consider this volume as a function of the position in which
the subspace cuts the diagonal.  As the subspace moves, the size and
the shape of the intersection alter, but it turns out that the volume
is a $C^{d-2}$ piecewise polynomial of degree $d-1$, non-zero only
inside a region of $d$ pieces.

The functions by which the volume varies are therefore exactly the
equal interval B-splines.

This visualisation of the B-splines leads directly to two standard
results:

 \pop Because we may visualise a row of boxes forming a beam of
 constant cross-sectional 'area', we see at once that the sum of the
 translates of the B-spline is constant.  By suitable choice of area
 units we can make it unity.

\pop All 'areas' are non-negative.

\subsection{Refinement of Box-splines}

We can also see that Box-splines must support a refinement definition,
because an interval can always be subdivided into two equal halves.
The outer product of such divisions cuts the Box into $2^d$ sub-boxes,
each similar to the original.  If we are refining by a factor of $a$
rather than by 2, the box is split into $a^d$ sub-boxes.

This makes evident that a box-spline function can be expressed as the
sum of appropriate weights times the narrower copies of the functions
associated with the sub-boxes.

$$f_i(t) = \sum_j S_{ij}f'_j(t)$$

\filbreak
Now when we use these functions to define a curve we do so by an
equation of the form
$$\eqalign{
P(t)  &= \sum_i P_i f_i(t)\cr
&= \sum_i \sum_j P_i S_{ij}f'_j(t)\cr
&= \sum_j \sum_i P_i S_{ij}f'_j(t)\cr
&= \sum_j  P'_j f'_j(t)
}$$
provided that $P'_j = \sum_i P_iS_{ij}$.

The equation linking the basis functions before and after subdivision
gives the equation linking the control points before and after.

Because of the translational invariance of the functions (due to our
equal interval limitation), all the columns of $S$ are the same, but
shifted through an appropriate shift, the arity.

\subsection {Determining $S$}

The numbers in a column can be determined by counting the number of
subcells in each cross section of the subdivided box.

It is easier, however, to determine them by use of a recurrence.
Suppose that we have the mask for dimension $d$.  Then we may form a
box of dimension $d+1$ by assembling $a$ extrusions of the subdivided
box of dimension $d$.

The first row has exactly the counts of the $d$-mask; the second the
same mask shifted by 1; the third shifted by 2, etc., and the
$d+1$-mask can be computed by just summing these contributions.

\filbreak
There is an operation which has exactly the same pattern: this is the
long multiplication of polynomials.  We can invoke this similarity by
defining the {\bf generating function} of a sequence of values $s_i$
to be the polynomial $\sum_i s_iz^i$.

The generating functions of the binary box-splines are therefore
$$(1+z)^d/2^d,$$ and those of $a$-ary ones $$[(1-z)^a/(1-z)]^d/a^d$$.

\section{The Dubuc-Deslauriers interpolating refinements}

For some purposes it is more convenient to be able to define a curve
which passes through some points that we know.

This can be achieved in a refinement context by arranging that 1 in
$a$ of the stencils (rows of the subdivision matrix) should contain a
single unit value and all the rest zero.

The intermediate rows can be chosen to give good properties for the
refinement.

\filbreak
Dubuc and Deslauriers chose to use Lagrange interpolation for their schemes.

If we use 2-point Lagrange, the scheme results in the polygon joining
the original points.

If we use 4-point Lagrange, the binary scheme results in a C1 curve
through the points.

If we use 6-point Lagrange, the binary scheme results in a C2 curve
through the points.

But the pattern stops here.  Higher Lagrange schemes do increase the
continuity but only very slowly.

\filbreak
However, Lagrange is not the only option open to us.  The 4-point
scheme is actually very nearly C2 (in a sense which will be explained
later in the course), and a 4-point ternary scheme can be set up which
is C2 for a rather narrow range of coefficients.  The Lagrange
solution does not lie in this range.

\section{Interpolating schemes for other patterns}

The Dubuc-Deslauriers binary family gives only primal subdivisions.

The same idea, of imposing the interpolation requirement by forcing
one of the stencils to contain a unit element, can be applied in the
'primal' and 'both' scenarios.  Choice of the other stencils is then
made by identifying equations between the coefficients which give
desirable properties.

In the 'neither' case, the square is 'both', and so the conditions can
be set up for the square and then echoed back into the single stage.
This involves a set of quadratic equations, but leads to a ternary
4-point scheme which is only C1 and in fact behaves rather badly.

In the 'dual' case, however, the curve never has a new vertex
corresponding to the original vertices at any stage, and so we cannot
make an interpolating scheme quite so easily.

I think I have a proof that it is not possible to make a binary dual
interpolating scheme, but this is not properly articulated. Whether
dual interpolating schemes of higher arity exist is an open question.






\end
