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).