Cubic Bezier 4-point Interpolation Part IV

Previously, we saw that to computing the x-coordinates of P1 and P2 involved solving a 2×2 system of equations,

a11*P1x + a12*P2x = b1
a21*P1x+ a22*P2x = b2

where P1x represents the x-coordinate of P1, for example.

Cramer’s rule expresses the solution of a system of linear equations in terms of determinants. The determinant, det(A), is particularly simple for a 2×2 system,

det(A) = a11*a22 – a12*a21

from which the solution is

x = (a22*b1 – a12*b2)/det(A)
y = (a11*b2 – a21*b1)/det(A)

which can be used to solve for (P1x, P2x) followed by a new system of equations with the same coefficients to solve for (P1y, P2y). Cramer’s rule is very efficient for this case since the determinant has already been computed.

You should see that if det(A) is close to or exactly zero, the solution is either undefined or very unreliable.  We won’t get into a discussion of ill-conditioning here, although the upcoming Singularity solver accepts a zero tolerance for the solution of any 2×2 system using this method.

The question at hand is will we ever have to consider this issue in Bezier interpolation?  The answer is yes.  The specific case is that of nearly or exactly coincident interior interpolation points.  The automatic chord-length parameterization in such cases yields either t1 = t2 or |t1-t2| < e, where e is a very small number.  The two equations are nearly or exactly redundant.

Handling this situation is left as an exercise; you can either test the interior interpolation points or test the determinant.  When the demo is posted tomorrow, as an exercise try the following interpolation points,

(133, 303), (163, 219), (164, 219), (253, 323)

and trace the determinant (query the determinant from the solver inside the interpolate() method of the Bezier3 class).  Change the 164 to 163.5, 163.1, 163.05, etc. and continue tracing the determinant.  Then, set it to exactly 163 and watch the determinant go to zero and see what happens.

There are other variations to this type of test, which will be discussed tomorrow when the demo is presented.


One thought on “Cubic Bezier 4-point Interpolation Part IV

Comments are closed.