Quad Bezier Arc Length Revisited

This question comes up quite regularly.  While in general, the elliptic integral for arc length of a parametric curve has no closed-form solution, the problem is tractable for a quadratic Bezier.  The integral is quite involved.  It is discussed in this post, including a reference to the solution.

Now, just because you have a formula for something does not necessarily mean you should always use it.  There are several divisions in the equation and some quads. can result in near-zero divisors.  There are other numerical issues, some of which can be exposed by exploring the Degrafa demo provided in the above post.

Computationally, the closed-form solution is close to a wash with numerical integration.  While the latter does have some subtle issues, I tend to use the numerical approach as it works for all parameteric curves and all values of the natural parameter.  The closed-form solution for the quad. only works for quadratic Beziers at t=1.   The numerical method can be used for arc-length parameterization as well as the segment problem; that is, computing the arc length of a segment of a curve from t=t1 to t=t2.

If you are a calculus student, you should study the derivation of the closed-form formula as it’s a great example of integration 🙂

Quad. Bezier Interpolation

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.

Bezier Y at X Algorithm

A few requests for the algorithm behind the Bezier y-at-x and x-at-y methods have been received.  The code is self-contained in the com.degrafa.geometry.AdvancedQuadraticBezier and AdvancedCubicBezier classes.  Both classes accept control points in their constructors and use classes from com.degrafa.utilities.math .  The latter classes are independent from any internal Degrafa architecture.  So, people who maintain their own Bezier class libraries have a path to include the y-at-x and x-at-y capability.

Finding the y-coordinates at a given x or the x-coordinates at a given y is an exercise in root-finding.  Suppose the Bezier curve is B(t) which is quadratic or cubic in t.  For the cubic Bezier, the vector equation for the curve produces two scalar equations, one for the x-coordinates and one for the y-coordinates, i.e.

Bx(t) = c0x + c1xt + c2xt2 + c3xt3

By(t) = c0y + c1yt + c2yt2 + c3yt3

For the y-at-x case, the required y-coordinates are found at the t-parameters corresponding to the intersection of B(t) with the vertical line x = a, or

c0x + c1xt + c2xt2 + c3xt3 – a = 0

The problem reduces to one of finding roots of a cubic polynomial. This starts by finding one root.  Synthetic division is used to factor out the single root leaving a quadratic polynomial.  The two possible roots of that polynomial are found with the venerable quadratic formula.  Only roots in [0,1] are valid solutions to the y-at-x problem.  The roots (values of t) are used to compute the y-coordinates using the equation for By(t).  With a quadratic Bezier, roots are found directly with the quadratic formula.

The x-at-y problem is similar in that the required x-coordinates are the intersection of B(t) with the horizontal line y = a.  There is one degenerate case where the Bezier curve is a segment of a horizontal or vertical line and the single parameter describing the line is the input value.  For example, a cubic Bezier curve is the line x = a and the y-coordinates for x = a are desired.  Theoretically, there are an infinite number.  The Degrafa code does not currently handle this case.  Some argue that no values should be returned while otheres argue that perhaps t = 0, t = 1/2 and t = 1 should be returned.

Given the rarity of this case actually occurring, the argument is postponed in lieu of more important developments.  Tomorrow, I’ll post some code from the demos.

New Degrafa Bezier Methods

I have received a couple requests for x-at-y methods in the advanced quadratic and cubic Bezier classes to complement the existing y-at-x methods.  Fortunately, the algorithm is the same, just a different set of coefficients, so it was an easy addition.

The x-at-y problem is typically used to distribute sprites left-to-right and top-to-bottom along the contour of a Bezier curve.  The y-coordinate of the first sprite is fixed.  The horizontal location is determined by the x-coordinate of the Bezier curve corresponding to the specified y-coordinate (plus some offset).  Sprites are ‘stacked’ along the contour of the curve by incrementing the y-coordinate based on the height of the previous sprite plus some offset, then repeating the algorithm.

The following diagrams illustrate the quadratic and cubic cases.

Quadratic Bezier x-at-y
Quadratic Bezier x-at-y
Cubic Bezier x-at-y
Cubic Bezier x-at-y

These methods are in the AdvancedQuadraticBezier and AdvancedCubicBezier classes.  Update SVN and enjoy.

Degrafa Spline Approximation Over An Interval

Due to severe lack of spare time, Degrafa work is moving very slowly these days.  I just added the cartesian spline approximation over an arbitrary interval.  For the natural cubic spline, defined over an interval [a,b], this method produces a quadratic Bezier approximation in the interval [x1, x2], where the input interval is contained in [a,b].  This allows some interesting applications, including smooth animation of an area under a spline.  This is illustrated in a new demo.  A screenshot is shown below.

Approximating a natural cubic spline over an arbitrary interval
Approximating a natural cubic spline over an arbitrary interval

Next step is to add a parametric spline and work over the architecture so that the computational core of a spline is separated from the Degrafa geometry pipeline.  Over the long term, this should allow anyone to add (interpolative) splines to Degrafa with little, if any, understanding of the internal Degrafa architecture and geometry pipeline.

The demo shows the entire area under the spline statically highlighted using the normal quad. approximation (which is always exact at the knots).  Click the ‘Animate’ button to see the area dynamically highlighted over an arbitrary range.

View demo.

View source.

Spline To Bezier Preview

This is something I started many years ago and put on the shelf because I never had an immediate use for it.  Two utilities are forthcoming in Degrafa; spline->Bezier anad function->Bezier.  These utilities approximate functions and specific splines over an interval with quadratic Bezier curves.  With these utilities, splines such as natural cubic, parametric, and Catmull-Rom will be easily plottable in the normal Degrafa geometry pipeline.

Following is a screen shot of work in progress on a natural cubic spline.  This was originally a derivative test as the spline slope at various points is required for the algorithm.  The derivative formula is covered in this TechNote.  There is no overlap between successive knot intervals.  The blue curve shows a simple point-to-point plot of the natural cubic spline.  The red curve shows the quadratic Bezier approximation.

Approximating a natural cubic spline with quadratic Beziers
Approximating a natural cubic spline with quadratic Beziers

Well over a hundred small lines are used in the traditional plot.  There are ten quads. in the above example.

Instead of trying to minimize the total number of quad. Bezier curves, the algorithm produces a modest number of quads in exchange for exact representation at knots and an integral number of quads.  per spline segment.  This makes it very easy to create specific shapes out of the quad. approximation between knots which could be useful in charting applications.

More to come!

Parametric Spline vs. Cubic Bezier Spline

Not as entertaining as Celebrity Deathmatch, but it is interesting to compare the two splines fitting the same set of knots.  The demo used in the previous post introducing the parametric (cubic) spline has been modified to fit the Degrafa cubic Bezier spline to the same set of knots, as shown below.

Comparing Parametric and cubic Bezier splines
Comparing Parametric and cubic Bezier splines

The parametric spline is drawn in blue, as before.  The cubic Bezier spline is drawn in red.  There is a technical reason why the parametric spline tends to take the ‘less roundabout’ path through knots, which I may discuss in future posts.  Neither drawing is more or less ‘correct’ than the other.  They are just different tools that can be used by artists.  In order for the parametric spline to be efficiently integrated into the Degrafa command stack, I will eventually  work on a methodology to approximate general splines with quad. Bezier segments.  Yet another item on that Degrafa ‘to do’ list 🙂

You may view the new demo and source code from the same links as in the parametric spline post.