I have discussed arc length of a parametic curve before in the blog and the process is well documented online and in this TechNote. In the past, I considered the general case and implemented arc-length parameterization the same way for all parameteric curves.
Degrafa is a bit different in that paths are decomposed into consituents of lines and quad. Beziers (a command stack of moveTo and curveTo commands). Cubic Beziers are subdivided into smaller cubic Beziers (via deCasteljau) that can eventually be approximated by quadratic Beziers. The cubic Bezier spline is composed of multiple cubic Bezier curves (with G-1 continuity). The spline is actually drawn by a sequence of curveTo commands.
So, the problem of general path length decomposes into a summation of line segment length and quadratic Bezier arc length. This post discusses a variety of algorithms for the specific problem of quadratic Bezier arc length. The naive algorithm is to approximate the integration process by summing the length of line segments taken by sampling the curve at regular intervals. As the number of segments increases, the cumulative length should approach the length of the curve.
In general, it is difficult to decide how many segments are enough to obtain an approximation of the curve’s length. If the number of segments is constant, it will be ‘too many’ for smaller curves and ‘not enough’ for much larger ones. Another issue is cumulative roundoff error from a large number of segments. These pale, however, next to the computational inefficiency of the approach.
The current Degrafa geometricLength method uses a variation of this approach and is intended to provide approximate curve length only. For ‘small’ curves, the approximation is suitable for arc-length parameterization. For larger curves, it tends to underestimate.
The elliptic integral for precise arc length generally has no closed-form solution. The integral is solvable (although it is far from trivial) in the case of a quadratic Bezier. The solution is documented here. The computation consists of a modest number of multiplies and adds along with three sqrt functions and a log. It is about as efficient as summing say half a dozen line segments and is accurate for quad. Beziers of any length.
There is another closed-form solution for this problem that derives from the illustration that a quadratic Bezier over [0,1] is a segment of a parabola. This concept is illustrated here. The math behind the computations goes back to the 1970’s and was discussed by my professor in a computational geometry course in 1981. I don’t have an original attribution, though.
Once all parameters pertaining to the parabola are computed, it is possible to compute the equivalent parabolic segment, whose length is known in closed form.
While this is a valuable academic exercise in computational geometry, it is impractical as a means to compute general arc length. A careful examination of the sum total of computations shows that this method is less efficient than the closed-form formula for the integral in the first place. Many of the interim results such as focus, directrix, etc. are of no practical value in most applications.
Although it may seem that solving the integral directly is the clear winner, that is really not the case. Both the parabolic approach and elliptic integral over [0,1] have a shared drawback. These formulas only apply to the length of the curve at t=1. They do not provide the capability to efficiently compute arc length at an aribtrary parameter value in [0,1].
This is where numerical integration is most valuable. Five-point Gaussian quadrature produces a very good approximation to total arc length as well as arc length for any parameter value in [0,1]. This allows the method to be used for arc-length parameterization along the curve (where arc length is sampled at various parameter values for later interpolation).
These methods (minus the parabolic approximation) are illustrated in a Degrafa demo.
Gaussian quadrature does require derivative evaluation, which is most efficient when the polynomial coefficients of the quadratic Bezier are available. Although not currently done in Degrafa, this is easily added and the coefficients only need be computed once when the geometric length is requested. They are invalidated when any control point is changed. This change will be made before addressing the more general problem of arc-length parameterization along a path.
Notice that this demo provides the first illustration of our new math utilities (com.degrafa.utilities.math.Gauss).
The Algorithmist 
Ah! Brilliant stuff! The next thing I’d love to learn is how to find a point along a curve. Got time to write a bit about that as well?
J
Jensa – look into the Degrafa pointAt() method in the Geometry class, which in turn calls the command path pathPointAt() method; – for this example, you can see it used in the arcLengthBySegments() method,
p = bezier.pointAt(t);
Note that for a bezier, this is based on the curve’s natural (not arc length) parameterization.
regards,
– jim
This is great work. I hadn’t heard of gaussian quadrature, perhaps because there is more industry focus on cubic beziers.
In my own code I’m still estimating quadratic bezier intersections through recursive subdivision and boundary collision tests. Do you have any articles on curve-curve intersection?
I should have provided a link.
http://en.wikipedia.org/wiki/Gaussian_quadrature
The methodology works for arc length of any parametric curve – cubic or otherwise. This is how I computed arc length for all curves in the Singularity package.
regards,
– jim
Hi Jim,
Ahh. I found it in the “Origin” branch of the SVN. It’s not in the main trunk.
http://code.google.com/p/degrafa/source/browse/branches/Origin/Degrafa/com/degrafa/geometry/Geometry.as
J
Cool, Do you try to test which is the fastest function in terms of computation?
You can run timing tests, but usually a quick count of floating-point operations and intrinsic function calls gives you a very good idea. These methods have been extensively tested in other environments and programming languages as well. In fact, my first attempt at arc length of a parametric curve was done in Fortran in the early 1980’s 🙂
Arc-length parameterization usually requires multiple computations of arc length as a function of t-parameter. In reality, numerical integration is the most practical approach.
regards,
– jim
Can you help me translate SVG elliptical arc drawing commands to actionscript?
I don’t know the first thing about SVG – sorry.
If I know the parameters of the ellipse as a whole: both radii, X-axis rotation relative to the current coordinate system, 2 points on the ellipse, and direction it was drawn (clockwise, vs counter-clockwise) is that enough to get the center point? If so, can you help me understand how? If I can get the center point, I can calculate the control point.
Max – I’m running real short on time. There is an Ellipse class in Degrafa (com.degrafa.geometry) that probably does everything you want. At least look at the code. I did an Ellipse example in singularity – algorithmist.net/singularity.zip .
Hope that helps.
– jim
Thanks anyway Jim. The ellipse class doesn’t quite do what I need. I’ll keep looking… Appreciate your time!!
Perhaps some brilliant Fortran programmer can give me sample program using Fortran 77 in generating more curves at once using Bezier. Your support & cooperation are much appreciated,
Hmmm … Fortran … haven’t worked with that since the mid 90’s and it was Fortran 90 at that 🙂 Don’t know of any computational geometry resources other than GEOMPACK – http://people.sc.fsu.edu/~burkardt/f_src/geompack/geompack.html and DUTCH, http://people.sc.fsu.edu/~burkardt/f_src/dutch/dutch.html. There is also the possibility of obtaining a C library and then calling C from Fortran, although the specifics will be somewhat environment dependent.
good luck!
– jim
Jim,
Great stuff. Thanks for sharing.
I have a question. How would you render 6 dots in the trajectory of the curve instead of the curve line itself in Degrafa?
First, the curve needs to be formally arc-length parameterized, which is not yet done in Degrafa. Once it is arc-length parameterized, you can sample x- and y-coordinates of the curve in terms of arc length. This is done in the Singularity quadratic Beizer. See
http://www.algorithmist.net/qbparam.html
In Degrafa, we won’t arc-length parameterize single curves. The parameterization will be applied to entire paths, which is a more complex problem.
regards,
– jim
Jim,
Thanks. I believe I can make a good approximation for I need to do with the example in the singularity quadratic bezier.
Take care,
Gilbert