Peter Alfeld Department of Mathematics College of Science University of Utah
The Bernstein Bézier Form Home Page Examples
Spline Spaces and Minimal Determining Sets    User's Guide Residual Arithmetic
Triangulations How does it work?    Bibliography


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 cijk are Bézier ordinates (or just coefficients), and A1, A2, and A3 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 Ai 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 AM 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 di, 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 AM. 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 AM 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 M1 is the set of points we have already picked to be in the minimal determining set, and M2 is a set of points whose status is as yet unknown. Initially M1 is empty and M2=M.

Similarly, we write

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

As in the simplex method for the solution of linear programming problems, we think of the rows of AM 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 apq means the entry in M in the location (pi, qj) where pi and qj 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 M2:

Criterion: A point p in I is in I1 if an only if the row of M2 corresponding to p is zero.

The if direction is obvious. The only if direction follows from the observation below that if that row in M2 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 M2. We transfer p from M2 to M1, and check if this implies any additions to I1 (by seeing if we have any new zero rows in the matrix corresponding to the reduced set M2.
  2. p is in I2. In that case we exchange p for a point q in M2 and change the matrix M appropriately. We denote new entries of M by bars.

    First we find a point q in M2 such that

    This is always possible because otherwise p would be in I1, i.e., it would be determined by the points in the set M1 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, dp and apq 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

    awq (3) - apq(4)

    which gives:

    We thus modify the remaining entries of A as follows:

    Finally, we move p to M1, q to I2, and check for an increase in I1 as above.

  3. Retracting a point. To remove a point from M1 we move it to M2 and make any implied moves from I1 to I2.

Residual Arithmetic

Carrying out the operations exactly as described here would quickly lead to an overflow of the integer arithmetic built into Java. Therefore the program actually represents (large) integers by their remainders with respect to one or more large prime numbers.
[30-Jul-2003]