How Does it Work?

Let's denote the underlying spline space by S and suppose that the polynomial degree is d and the degree of smoothness is r.

We need to analyze smoothness conditions of the form

(1)

The c_ijk are Bézier ordinates (or just coefficients), and A₁, A₂, and A₃ are barycentric coordinates of a vertex of a triangle with respect to the opposite triangle.

It is crucial that the coordinates of the vertices of the underlying triangles are the coordinates of pixels and thus integers. The barycentric coordinates A_i are therefore rational and indeed all the coefficients in the system (1) are rational. We may assume (after multiplying with a common denominator) that our homogeneous linear system has integer coefficients.

The reason this is important is that the dimension of a spline space S and the composition of minimal determining sets depends discontinuously on the coefficients in (1). There are examples and subtleties that render the ordinary floating point arithmetic unsuitable for this application.

On this page we analyze the system (1) as an integer system for convenience, but the actual arithmetic is carried out modulo one or more large prime numbers.

Thus we consider the homogeneous system

(2)

Each Bézier ordinate corresponds to a unique domain point and vice versa. The usual terminology refers to domain points rather than corresponding Bézier ordinates and we adopt it here. Thus a a determining set is a set of domain points which is such that if the corresponding coefficients are set to zero than all other coefficients of the spline must also be zero. A minimal determining set is one that's no larger than any other determining set. The number of points in a minimal determining set equals the dimension of S.

Some Bézier ordinates (those at a distance greater than r from any edge) do not enter the smoothness conditions at all. They correspond to zero columns of A in (2). We call these Bézier ordinates inactive and the others active. We omit columns corresponding to inactive points from A. Thus A is a u by v matrix where u is the number of smoothness conditions of the form (1) and v is the number of active domain points.

The dimension of S equals i+v-m where i is the number of inactive domain points and m is the rank of A.

The nearby figure illustrates these concepts. Inactive points are marked with yellow or red square boxes. Active points in the minimal determining set are indicated by red, blue and yellow plus signs. Active points not in the minimal determining set are indicated by colored circles. The number of points in the minimal determinng set, and thus the dimension of S is 33.

Note: The colors illustrate the way the minimal determining set is constructed, red points go with boundary vertices, blue points go with the interior vertex, and yellow points go with nearby edges. For more information read about the Morgan-Scott Idea.

Initialization

We begin by using Gaussian Elimination to transform A into a block matrix

where D is an m by m nonsingular diagonal matrix and A_M is an m by n matrix. As above, m is the rank of A and n is the number of active points in a minimal determining set. (There may be additional inactive points which are in every determining set).

We denote the nonzero (i,i) entry of D by d_i, i.e.,

The Gaussian elimination process uses total pivoting, but since we are using integer arithmetic we are not concerned about stability. So we pick the first non-zero element in the part of the matrix that has not yet been reduced. Since we cannot use division the usual process has to be modified and is described (for the u by v matrix A) in the nearby box. That process is followed by a similar one that reduces D to diagonal form.

In this manner we obtain an initial minimal determining set containing all the points corresponding to the columns of A_M. The user of the applet does not know of that set but it is used internally by the applet to construct the set actually wanted by the user.

Adding and Removing Points

We denote by M the set of points corresponding to the columns of A_M and by I the set of remaining active points (corresponding to the columns of the diagonal matrix D).

We now think of I and M as each being composed of two sets:

where M₁ is the set of points we have already picked to be in the minimal determining set, and M₂ is a set of points whose status is as yet unknown. Initially M₁ is empty and M₂=M.

Similarly, we write

where I₁ is the set of points that we know to be determined by our growing minimal determining set M₁, and I₂ is a set of points whose status we do not yet know. Initially, I₁ is empty, and I₂ = I.

As in the simplex method for the solution of linear programming problems, we think of the rows of A_M as labeled by the indices in I and the columns by the points in M. For points p in I and q in M the notation a_pq means the entry in M in the location (p_i, q_j) where p_i and q_j are the physical row and column indices associated with i and j.

It is now easy to tell whether a point p in I is determined by the points in M₂:

Criterion: A point p in I is in I₁ if and only if the row of M₂ corresponding to p is zero.

The if direction is obvious. The only if direction follows from the observation below that if that row in M₂ has non-zero entries then we can add p to our growing minimal determining set.

We now examine what happens when a user adds a point or removes one from the growing minimal determining set. Consider these cases:

1. p is in M₂. We transfer p from M₂ to M₁, and check if this implies any additions to I₁ (by seeing if we have any new zero rows in the matrix corresponding to the reduced set M₂.
2. p is in I₂. In that case we exchange p for a point q in M₂ and change the matrix M appropriately. We denote new entries of M by bars.

   First we find a point q in M₂ such that

   

   This is always possible because otherwise p would be in I₁, i.e., it would be determined by the points in the set M₁ that we have already picked.

   The equation in the row corresponding to p reads:

   (3)

   In this row we make no change, except that since we will exchange p and q, d_p and a_pq exchange their roles (and maintain their numerical value).

   The equation corresponding to w different from p (or q after the exchange of p and q) reads similarly:

   (4)

   We want to eliminate the entries in the column corresponding to q. To this end we replace the equation (4) with

   a_wq (3) - a_pq(4)

   which gives:

   

   We thus modify the remaining entries of A as follows:

   

   Finally, we move p to M₁, q to I₂, and check for an increase in I₁ as above.

3. Retracting a point. To remove a point from M₁ we move it to M₂ and make any implied moves from I₁ to I₂.

Residual Arithmetic