Cheap way of calculating cubic bezier length

Question

An analytical solution for cubic bezier length seems not to exist, but it does not mean that coding a cheap solution does not exist. By cheap I mean something like in the range of 50-100 ns (or less).

Does someone know anything like that? Maybe in two categories:

1) less error like 1% but more slow code. 2) more error like 20% but faster?

I scanned through google a bit but it doesn't find anything which looks like a nice solution. Only something like divide on N line segments and sum the N sqrt - too slow for more precision, and probably too inaccurate for 2 or 3 segments.

Is there anything better?

Answer 1

Another option is to estimate the arc length as the average between the chord and the control net. In practice:

Bezier bezier = Bezier (p0, p1, p2, p3);  chord = (p3-p0).Length; cont_net = (p0 - p1).Length + (p2 - p1).Length + (p3 - p2).Length;  app_arc_length = (cont_net + chord) / 2; 

You can then recursively split your spline segment into two segments and calculate the arc length up to convergence. I tested myself and it actually converges pretty fast. I got the idea from this forum.

Answer 2

Simplest algorithm: flatten the curve and tally euclidean distance. As long as you want an approximate arc length, this solution is fast and cheap. Given your curve's coordinate LUT—you're talking about speed, so I'm assuming you use those, and don't constantly recompute the coordinates—it's a simple for loop with a tally. In generic code, with a dist function that computes the euclidean distance between two points:

var arclength = 0,     last=LUT.length-1,     i; for (i=0; i<last; i++) {   arclength += dist(LUT[i], LUT[i+1]); } 

Done. arclength is now the approximate arc length based on the maximum number of segments you can form in the curve based on your LUT. Need things faster with a larger potential error? Control the segment count.

var arclength = 0,     segCount = ...,     last=LUT.length-2,     step = last/segCount,     s, i; for (s=0; s<=segCount; s++) {   i = (s*step/last)|0;   arclength += dist(LUT[i], LUT[i+1]); } 

This is pretty much the simplest possible algorithm that still generates values that come even close to the true arc length. For anything better, you're going to have to use more expensive numerical approaches (like the Legendre-Gauss quadrature technique).

If you want to know why, hit up the arc length section of "A Primer on Bézier Curves".