Subject: TTF to PS curve conversion (3/5)

From: "L.S.Ng" <[email-masked]>
Date: Sat, 28 May 1994 16:29:34 BST

Problems of Evaluating B-spline function at Whole Number
========================================================

The value of a B-spline function at whole number is useful in
determining break points of a long Bezier B-spline Approximation Curve.

Unfortuantely, it was found that a B-spline function behaves badly with
whole number, especially when the knot set is a progression of whole
number. Such knot set is often chosen in Bezier B-spline Approximation.

One suggested way to get around this problem is to evaluate the B-spline
function at a real number very close to the whole number.

The nature of this problem is not due to floating point representation
of real number, but rather with the definition of the B-spline function
itself.

A B-spline function is evaluated recursively such that in C langauge.
Here i is the knot number, t is the knot set, n is the degree, and x is
the value at which the function is evaluated.

double B(int i, int n, double x, double *t)
{
     if (n==0) {
       if (x>= t[i] && x <= t[i+1]) return (double) 1;
        return (double) 0;
        }
    else return (double) DIV((x - t[i])*B(i, n-1, x, t), t[i+n] - t[i])
         + DIV((t[i+n+1] - x)*B(i+1, n-1, x, t), t[i+n+1] - t[i+1]);
}

double DIV(double a, double b)
{
     if (a==0 && b==0) return 0;
     if (a!=0 && b==0) return DBL_MAX;
     return a/b;
}

For example

B(2,2,0.99,t)           0.49005
B(2,2,1.00,t)           1.00000
B(2,2,1.01,t)           0.5099

where t[]={0,0,0,1,2,3,4,4,4}

You can see that (I hope), if we approach 1 from either direction, we
are expected to get 0.5 at B(2,2,1.0,t).

If you do the arithmetic by hand, you will notice that

B(2,0,1.00,t) = 1 because t[2] <= x <= t[3] or 0 <= x <= 1, here x=1.
B(3,0,1.00,t) = 1 because t[3] <= x <= t[4] or 1 <= x <= 2, here x=1.

If both are 1, then B(2,1,1.0,t) = 2 so B(2,2,1.0,t) = 1.

If you put x=0.99, one of the condition will fail, i.e.

B(2,0,x,t) = 1
B(3,0,x,t) = 0

So this gives you only half the value. Hence B(2,2,0.99,t) is about 0.5.

If you put x=1.01, the same will happen:

B(2,0,x,t) = 0
B(3,0,x,t) = 1

Either but not both is 1. It is when x=1.00 both are 1 which gives a
value double the expected.

In general, such case happen to all terms B(i,n,x,t) where
t[i-1], t[i], t[i+1] form a progression of
t[i] - 1, t[i], t[i] + 1.
This happens only in the middle of the knot set.

At both end of the knot set where they are repeated, the B-spline
evaluated to zero anyway, so masking this 'whole number problem'.

A solution will be to evaluate the B-spline at values close to the whole
number and take the limiting value.

In practice, choosing a value that is about 0.01% difference from the
whole number is good enough.  For better approximation, we can evaluate
the B-spline at both side of the whole number and interpolate to get it.

Another quick way will be to evaluate the value at the whole number and
take the half, as in the previous example. But this may work only for
special case such as above where it is quadratic. For higher degree, the
fraction could be different, thought there might be a uniform pattern of
the fraction.

It should be expected to give 'nice' number such as 0.5, 0.333 etc. So
precision does not matter.

It is interesting however to note that, if you specify a number such
that x=0.95+0.05, and evaluate the B-spline at x, you will get a nice
and clean answer. The reason for that is I think, 0.95+0.05 != 1.00
exactly but a real number very close to 1, due to the floating point
representation. So the floating point representation actually 'helps'.