Home > Degrafa, Math > Quad Bezier Arc Length Revisited

Quad Bezier Arc Length Revisited

March 29, 2010

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 🙂

Advertisements
Categories: Degrafa, Math Tags: ,
  1. March 29, 2010 at 12:33 pm

    Thank you for your wonderful articles on spline math. I recently started working on a Flash command (Javascript) that maps arbitrary art onto the selected path and I’ve found your posts on quadratic beziers very useful. I adapted your numerical integration length approximation routines for my tool, and made my own functions to find tangents and perform arc-length parameterization using a linear interpolation table.

    I know you’ve mentioned arc-length parameterization (that is, plug in a length, spit out the point at that location on the curve) in previous posts but I haven’t found anything that addresses it more explicitly. You mentioned using a spline in the approximation but for the moment that’s a little too much for me to wrap my head around. Can you direct me to where I can find an efficient arc-length parameterization algorithm? Or do you think I should just stick with my linear interpolation?

    (I’ve found that with 20 table entries the linear interpolation produces pretty good results, but that means 20 calls to your length approximation function on every bezier in my path. That could get pretty slow for paths with lots of curves).

    By the way, you might be interested in my blog, where I talk (among other things) about the Flash extensions I’ve created. I’ve only posted a few extensions so far but more are on the way.

    • March 29, 2010 at 3:35 pm

      David:

      Linear or quad. interpolation is usually pretty efficient. There are published methods that incorporate the parameterization into polynomial coefficients, but they involve higher-order polynomials, so you’re doing more work every time you evaluate the poly. For the singularity package, I think I used ten points for LI, so 20 sounds a bit high. You may want to consider something adaptive perhaps based on manhattan distance between control points. In many cases, I found ten to be overkill. You can get away with fewer points for cubic spline interpolation, but it’s a more computationally expensive interpolant. Still, the longest quad. in your path should get more LI points than the smallest. They should never be uniform if you’re trying to optimize. Same thing with Gaussian quadrature; you need fewer points in the evaluations for lesser-length curves. Instead of 5- or 8-pt. quadrature, try 3 or 4 for smaller curves.

      There is a technote on my personal site about arc-legnth parameterization (www.algorithmist.net/technotes.html), although it was applied to a Catmull-Rom spline. I hope to be revisiting the problem over the coming months as I get back into work on Degrafa.

      good luck!

  2. March 30, 2010 at 11:20 am

    My implementation has turned out to be faster than I expected. I guess javascript goes a decent speed, making up for any algorithm deficiencies I have (so far, anyway). I’ve got my tool working at about 95% now — just a few glitches to work out in the translation from symbol to brushstroke. I’ll probably do some optimization when I’ve got it working 100% (or as close to 100% as I can get). I’d love to show you the result when I’m done. I honestly think this is going to be super valuable to Flash animators anywhere (if I can get it working to an acceptable level and if I can get the word out).

  1. No trackbacks yet.
Comments are closed.
%d bloggers like this: