Old polygon

One application of the rules (a step) leads to the construction of a refined polygon. When we are talking about later steps the input to that step is called the old polygon and the output from it the new polygon. 

These new vertices are joined together, in the sequence matching the sequence of the edges and vertices of the old polygon, to form the new polygon. 

At the ends it can be convenient for a new v-vertex, which does not have three old vertices to apply the weights to, merely to be placed at the same position as the end vertex of the old polygon. Much later in the book we shall see why this is an unfortunate end-condition, but for now it provides a simple way of tying up the loose end. 

In this scheme, which is called the quadratic B-spline scheme, because its limit is indeed a quadratic B-spline curve, new vertices are constructed at points one quarter and three quarters of the way along each edge of the old polygon. At the first step they get labels which are half-integers. 

All the previous examples have the property that the corners are smoothed off the original polygon. It is also possible for a scheme to have the property that the new polygon has new v-vertices which lie exactly at the corresponding old polygon vertices. If this is true after one step it will also be true after two, or three, or more, and indeed it is true, by induction, of the limit curve. 

This is not an obvious thing to do, but it turns out to be incredibly powerful. The immediate application is that convolution of the mask with the old polygon becomes multiplication of the generating function of the old polygon by the generating function of the mask. 

What the choice of a diagonal does is to imply a labelling, giving a correspondence between a sequence of points of the old polygon and a sequence of the refined one. In particular it implies a mark point which is an abscissa value which maps into itself under the map from old abscissa values to new ones. In the case of a primal binary scheme, the mark point is at a point of both new and old polygons. In the case of a dual scheme the mark point is at a mid-edge in both old and new. 

A nice example is the dual of the quadratic B-spline, which turns into a primal interpolating scheme (because each old line in the old polygon is retained in the new one). The limit curve (the envelope of the lines in the limit polygon) turns out to be a concatenation of conic section pieces. 

When this is done at both ends, the matrix becomes a finite one which can be applied to a finite old polygon. The result is a new polygon with... 

For the cubic B-spline this can be achieved in an ad-hoc way by just retaining the first control point of the old polygon in the new polygon. This is very easily achieved and implemented, but it has the unfortunate effect that the curvature is always zero at the end of the limit curve. 

The third is obviously equivalent to the first approach because the modification can be expressed as a premultiplication of the old polygon by a matrix, which can alternatively be combined with the standard subdivision matrix to give a modified matrix. 

This first example has approximately twice as many vertices in the new polygon as in the old. We call it a binary scheme. If there had been three times as many it would have been a ternary scheme, and such generalisations will be discussed in a few pages time. In principle at each refinement we can multiply the number of vertices by whatever we choose, and this number is called the arity and denoted by the letter a. It is also called the dilation factor, which stems from generating function usage. 

The dyadic fractions are those which have a finite representation as binary numbers. Rationals which are not dyadic have a binary fraction representation which after a while repeats some pattern to infinity. Irrationals do not have any such pattern in their infinite binary representation nThis is not quite true, because some schemes have special rules at the ends which allow for definition of new vertices which don t have old vertices on both sides. Others do not, and then each new polygon covers a slightly shorter parametric range than the previous one. This distinction can be ignored until we come to the chapter on end-conditions at page 175. 

We consider first ternary schemes which are both primal, in the sense that there is a vertex in the new polygon corresponding to each vertex of the old, and dual, in that there is an edge of the new polygon matching each each of the old. 

The question is whether we can bound the values of f(x + Sx) — f(x) in terms of the original control points, and the answer is yes , using the neat idea of a difference scheme, which relates the first differences of the new polygon to the first differences of the old. 

All of this can be applied easily, at least in the two-dimensional case, to give a complete parallel theory in which a polygon is a sequence of edges (lines) rather than a sequence of points. A new polygon can be created from an old one by taking linear combinations of the lines to make new lines, and the vertices of the new ones just pop out as the places where consecutive new lines intersect. 

The corresponding row eigenvectors are the same length as the rows, and so the derivatives depend only on the first few old control points at the start of the polygon. 

Figure 11.5 We have created two new nets (grey) from the (4,4) and (3 4,5) nets by placing new nodes in the centre of each polygon and then connecting these nodes by links intersecting the old links at their midpoints. These are the dual nets and we see that in the first place we obtain the same net as we started with, but in the second case we get a different net.

---