As I’m winding down on a long gig, I hope to return to answering questions and doing more work on Degrafa. The backlog of questions is in the hundreds, so I’m going to start with recent topics first. This question involves quadratic Bezier interpolation or fitting a quad. Bezier through three points. It seems to involve selection of the t-parameter at the inner control point. The first and last control points, P0 and P2 are fixed at t=0 and t=1. The problem involves selection of the inner control point, P1, so that the Bezier curve passes through some specified point, P.
This problem is actually over-determined; that is, there are more degrees of freedom than constraints. The online demo is here, including a link to TechNotes providing the equations. P1 is not uniquely determined given P. We must also choose the t-parameter at which the quad. Bezier passes through P. This selection influences the shape of the curve. Although the so-called midpoint formula has been floated around in the Flash community, the Singularity code uses a chord-length parameterization to choose t.
The same problem exists for fitting a cubic Bezier through four points, although now we are free to choose two t-parameters at inner interpolation points. This is implemented in Degrafa using a uniform parameterization.
Hope this helps.
I remember my professor in my first numerical analysis course talking about Lagrange interpolating polynomials and sampling the test function f(x) = 1/(1 + x2). We already knew about oscillations in higher-order polynomials, so this discussion was about sampling increments. The natural thought is to sample in equal increments across an interval. Thus started a discussion about Chebyshev polynomials and Chebyshev nodes. I actually found a good blog post about this very topic at John Cook’s blog. John has a great blog on math and computation, btw.
I wanted one more demo showing how to create cubic spline nodes in script and highlight sections of the spline that were not necessarily in-between knots. The new demo samples the above function at Chebyshev nodes in [-5,5] and fits a natural cubic spline to the nodes. The area under the curve in [-1,1] is highlighted as shown in the screenshot below (by clicking the ‘Show Highlight’ button.
Click on the ‘Show Function’ button to show the original function plotted point-to-point to see a visual comparison of the spline approximation. If you are interested, change the interpolation points and study the change in quality of fit.
Now that my trip down memory lane is complete, next step is to complete the Degrafa spline architecture (which is only about halfway there) and add a parametric spline. I did correct a typo in the code, so you will need to update SVN.
Continuing from Part I, we are discussing how to interpolate a set of data points with a smooth curve. Depending on your experience or college studies, you may have been introduced to the concept of polynomial interpolation, that is fitting a set of n points with a polynomial of degree no larger than n-1. You can read the Wikipedia article here. Looking at the example picture in the article, that looks pretty good and it’s a well-known algorithm, so why are we even talking about this spline stuff?
As it happens, there are two issues with the general polynomial interpolation algorithm. As the number of interpolation points increases, there is a tendency for the polynomial to oscillate (sometimes wildly) between points. The second, and somewhat more subtle, issue is what happens if you want to create a closed shape? Will the curve look as if it were smoothly ‘drawn’ between all the points or will there be an abrupt change in the slope of the curve at the first/last points where the curve closes?
Primarily for the former reason, the textbook polynomial interpolation is undesirable. The idea behind a spline is to use multiple polynomial curves to fit the entire data set. There is one polynomial curve between each set of data points or knots. So, if three points were interpolated with cubic curves, there would be one cubic curve fit between the first and second data points. A second cubic curve would be fit between the second and third data points.
Interior knots are sometimes called joins as these knots indicate where separate polynomial curves join together. This is illustrated in the following diagram for a cubic Bezier spline.
In this case, the spline contains four separate cubic Bezier curves. One cubic Bezier curve interpolates knots 0 and 1. The second interpolates knots 1 and 2. The third interpolates knots 2 and 3. The final cubic Bezier curve interpolates knots 3 and 4. These separate curves are sometimes called ‘segments’ of the spline.
Each Bezier curve is constructed in a manner that meets certain continuity conditions at the joins. These conditions will be discussed in part III.
A couple of the questions I received regarding this post were how well the arc-length parameterization performs in the event the path is rapidly redrawn (i.e. knots are continuously modified) and how it works if the spline degenerates to a line. The intended application was along the lines of using a path to simulate a wave and then have the text move along the wave. It would eventually decay into a line, then the text would be animated along the line, off screen.
Well, that’s a good question because the cubic spline interpolation uses a minimal number of interior interpolation points, but is somewhat expensive to setup and compute. It requires assembling and solving a tridiagonal system of equations, so it is best suited for situations where arc-length is computed once and then sampled many times. If the knots are continuously changed, then the spline’s arc-length also changes continuously, forcing expensive recomputation.
The approach also assumes a smooth transition from knot to knot in terms of t vs s. For splines that are straight lines, the interpolated data is piecewise linear, so the spline tends to over- or under-estimate arc length in regions just past interior knots.
Linear interpolation is faster to setup but requires many interior interpolation points. A scheme that assigns the same number of points per segment easily creates too many points for one segment and too few for another.
I’m currently overhauling the arc-length parameterization for the cubic Bezier spline to use an adaptive algorithm for assigning interior interpolation points. Along with some additional information to speed lookup, this should allow linear interpolation to work reasonably well across a wide variety of knot distributions. It should also perform well with splines that are continuously redrawn with new knot placement.
The image below shows an example of the algorithm (still under development).
Although the knots form a straight line, the spline creates two cubic Bezier curves with C-1 continuity at the interior knot. So, the two straight lines are actually two cubic Bezier curves that happen to have zero quadratic and cubic coefficients.
The distribution of parameter value vs. arc length is not linear along the entire spline because the knots are not equally spaced along the line. The piecewise linear distribution would cause a slight difference in kerning among any letters that happened to lie just beyond that interior point in the previous approach.
The new algorithm handles this case nicely. I still have some work to do on making it more efficient. The tangent and normal calculations will also be overhauled for efficiency. After that, I need to resolve issues like how to handle text that extends beyond the extent of the spline. Lots and lots of details 🙂
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.
I finished the basic version of the demo, but it’s evident that several aspects require some discussion. I don’t have time for a full TechNote, so I’ll go over each issue in a separate blog post. This will make it a lot easier to understand the code.
To review, the problem is as follows. Given four vectors, V0, V1, V2, and V3, find the control points, P0, P1, P2, and P3 of a cubic Bezier curve, B(t), so that the curve passes through V0, V1, V2, and V3. The first decision is how to parameterize the curve. In other words, what are the parameter values of B(t) at each of the interpolation points? Uniform parameterziation makes the following assignments.
B(0) = V0, B(1/3) = V1, B(2/3) = V2, B(1) = V3.
In fact, any parameterization would have B(0) = V0 and B(1) = V3, so the two ‘interesting’ parameter values are B(t1) = V1 and B(t2) = V2. It’s helpful to have an automatic means for selecting these parameter values and uinform parmeterization is the easiest approach.
An alternative, which is better if you do not require precise velocity control along the curve, is chord-length parameterization. It is a bit more expensive to compute, but that is not an issue if the curve is parameterized once and then sprites are animated along the curve over and over.
Let d1 = d(V0,V1), where d(a,b) is the Euclidean distance between vectors a and b. Let d2 = d(V1,v2) and d3 = d(V2,V3). If d = d1 + d2 + d3, then select t1 = d1/d and t2 = (d1+d2)/d. This method selects parameter values that are proportional to the cumulative distance along the chords from vector to vector.
It should be evident that P0 = V0 and P3 = V3, so the problem reduces to computing P1 and P2. There are four unknowns; the x- and y-coordinates of P1 and P2. To solve, we need four equations. The parameter values come into play here. The equation for B(t) is evaluated at t1 and t2 and set equal to V1 and V2, respectively. Since the parameter values are known, this yields two vector equations (or four scalar equations). The derivation of these equations will be presented tomorrow.
The next online demo will be four-point interpolation for a cubic Bezier curve. This TechNote shows the general algorithm for three-point interpolation using a quadratic Bezier. It may seem as if the only variable is where to place the middle control point so that the quadratic Bezier passes through the specified second point. The classic midpoint algorithm (the formula you may have seen making its way around the Flash community) causes the curve to pass through the interior interpolation point at t = 0.5.
Selection of a parameter value is arbitrary as the shape of the interpolated curve depends on the t-parameter at the second interpolation point. This issue is discussed in the TechNote and illustrated in this online demo.
The situation is similar, although more complex for a cubic Bezier curve. Four control points must be determined so that the cubic curve passes through four specified points. The two endpoints are trivial, so the problem reduces to finding the two middle control points. The parameter values at the interpolation points must be specified in order to solve for the control point placement. Uniform parameterization selects t = 0 for the first interpolation point, t = 1/3 for the second, t = 2/3 for the third and t = 1 for the final point.
If the four control points are P0, P1, P2, and P3, then there are four unknowns; the x- and y-coordinates of P1 and P2. The upcoming demo will illustrate a chord-length parameterization of the interpolating Bezier. Given the parameter values at the two interior interpolation points, the equation for a cubic Bezier can be used to create a system of equations in P1 and P2.
These equations can be solved with a variety of methods, although there are some numerical issues with nearly or exactly overlapping interior interpolation points.
I hope to work on the code over the weekend, with a new demo up some time early next week.