26

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?

Weather Vane
  • 33,872
  • 7
  • 36
  • 56
user2214913
  • 1,441
  • 2
  • 19
  • 29
  • 2
    See http://stackoverflow.com/a/28764614/107090. – lhf Apr 03 '15 at 19:24
  • @up much to hard to get answer form there (if there is answer here at all, 99% probably no) I need direct answer in c or pseudocode not advanced math papers very hard to read – user2214913 Apr 03 '15 at 19:29
  • many people need that.. (i dont need exact but approximete) .. it is needed when you draw bezier by points in for loop to know how many this points you need to draw.. so i state this questi0n, i thin SO is a place for such questions – user2214913 Apr 03 '15 at 19:47
  • On this site it is more relevant to post code that isn't working properly, to ask why. If you have code that works but you want a more efficient algorithm, you could try Stack Exchange. – Weather Vane Apr 03 '15 at 19:49
  • Knowing the length of the curve isn't going to help you know how many points to draw. – Mark Ransom Apr 03 '15 at 19:52
  • 1
    aproximation not exact length.. is going.. is usable (besides cheap recipe for it may be usable by many other cases ) I use it sometimes for trajectories etc, its good to know the length of given trajectory and i need it possibly quick – user2214913 Apr 03 '15 at 19:56
  • 5
    as the author of http://pomax.github.com/bezierinfo: the most important question here is what you think you need that approximation -rather than correct- arclength *for*, because that determines what error margins are acceptable, and which approximation shortcuts you can even take without losing the information you needed – Mike 'Pomax' Kamermans Apr 03 '15 at 20:20
  • 5
    @MarkRansom to act perhaps as reality check, most vector illustration software has arc length computation baked in. Anything that needs to render dotted or dashed curves, for instance will have some form of arc length computation implemented. It's far more common than your question suggest you believe it is. – Mike 'Pomax' Kamermans Apr 03 '15 at 20:22
  • 1
    You're not going to get an easy solution for this. Good estimations involve numerical methods that require some mathematical maturity to understand. Your choice is to accept the challenge and grow your skills, or hire someone who has those skills. – Codie CodeMonkey Apr 03 '15 at 20:47
  • as i wrote i need something like 1-2% of error in more precise case and anout 10-20 % in another - this shouldnt be so damn hard, I only need something better than lame adding linear segments length maybe – user2214913 Apr 03 '15 at 20:57
  • @user2214913 if you don't know the solution, you really have no basis to claim "this shouldnt be so damn hard" in the slightest. Getting the true arc length for a cubic curve is not just "hard", there is literally no way to compute it generically. It is *impossible*, and so we compute it using numerical techniques. Flattening on the other hand is *super easy*, so the fact that you call length computation using a flattened curve hard already is weird: it's fast, it's inaccurate but at arbitrary error (need more precision? use more segments), what about it is too hard? – Mike 'Pomax' Kamermans Apr 04 '15 at 16:01

6 Answers6

24

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.

Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153
Nic
  • 1,262
  • 2
  • 22
  • 42
  • I'd love to see a performance comparison between this and flattening... once you've computed a curve's LUT, flattening doesn't need to recompute anything, whereas this recursive approach would either have to store the interpolation points at each LUT point up front, taking up a tremendous amount of memory, or compute those to get the new hull at each iteration, making it much slower. – Mike 'Pomax' Kamermans Sep 24 '20 at 14:58
7

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

Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153
2

in my case a fast and valid approach is this. (Rewritten in c# for Unity3d)

public static float BezierSingleLength(Vector3[] points){
    var p0 = points[0] - points[1];
    var p1 = points[2] - points[1];
    var p2 = new Vector3();
    var p3 = points[3]-points[2];

    var l0 = p0.magnitude;
    var l1 = p1.magnitude;
    var l3 = p3.magnitude;
    if(l0 > 0) p0 /= l0;
    if(l1 > 0) p1 /= l1;
    if(l3 > 0) p3 /= l3;

    p2 = -p1;
    var a = Mathf.Abs(Vector3.Dot(p0,p1)) + Mathf.Abs(Vector3.Dot(p2,p3));
    if(a > 1.98f || l0 + l1 + l3 < (4 - a)*8) return l0+l1+l3;

    var bl = new Vector3[4];
    var br = new Vector3[4];

    bl[0] = points[0];
    bl[1] = (points[0]+points[1]) * 0.5f;

    var mid = (points[1]+points[2]) * 0.5f;

    bl[2] = (bl[1]+mid) * 0.5f;
    br[3] = points[3];
    br[2] = (points[2]+points[3]) * 0.5f;
    br[1] = (br[2]+mid) * 0.5f;
    br[0] = (br[1]+bl[2]) * 0.5f;
    bl[3] = br[0];

    return BezierSingleLength(bl) + BezierSingleLength(br);
}
dan_wipf
  • 141
  • 9
0

I worked out the closed form expression of length for a 3 point Bezier (below). I've not attempted to work out a closed form for 4+ points. This would most likely be difficult or complicated to represent and handle. However, a numerical approximation technique such as a Runge-Kutta integration algorithm (see my Q&A here for details) would work quite well by integrating using the arc length formula.

Here is some Java code for the arc length of a 3 point Bezier, with points a,b, and c.

    v.x = 2*(b.x - a.x);
    v.y = 2*(b.y - a.y);
    w.x = c.x - 2*b.x + a.x;
    w.y = c.y - 2*b.y + a.y;

    uu = 4*(w.x*w.x + w.y*w.y);

    if(uu < 0.00001)
    {
        return (float) Math.sqrt((c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y));
    }

    vv = 4*(v.x*w.x + v.y*w.y);
    ww = v.x*v.x + v.y*v.y;

    t1 = (float) (2*Math.sqrt(uu*(uu + vv + ww)));
    t2 = 2*uu+vv;
    t3 = vv*vv - 4*uu*ww;
    t4 = (float) (2*Math.sqrt(uu*ww));

    return (float) ((t1*t2 - t3*Math.log(t2+t1) -(vv*t4 - t3*Math.log(vv+t4))) / (8*Math.pow(uu, 1.5)));
  • Seems to return NaN for coordinates `(-54.2, 45.5, 84.9)` with `(-39.2, 45.5, 84.9)` with `(-25.5, 45.5, 92.7)` – Kari Mar 16 '21 at 22:01
  • @Kari there may be edge cases that need checking for, probably division by zero or log of zero or similar. –  Mar 16 '21 at 23:12
  • In my case it's log of a large negative number at the last line (-161) – Kari Mar 16 '21 at 23:14
  • @Kari a guess but maybe take absolute value. I'll have to check tomorrow. –  Mar 16 '21 at 23:50
0
public float FastArcLength()
{
    float arcLength = 0.0f;
    ArcLengthUtil(cp0.position, cp1.position, cp2.position, cp3.position, 5, ref arcLength);
    return arcLength;
}

private void ArcLengthUtil(Vector3 A, Vector3 B, Vector3 C, Vector3 D, uint subdiv, ref float L)
{
    if (subdiv > 0)
    {
        Vector3 a = A + (B - A) * 0.5f;
        Vector3 b = B + (C - B) * 0.5f;
        Vector3 c = C + (D - C) * 0.5f;
        Vector3 d = a + (b - a) * 0.5f;
        Vector3 e = b + (c - b) * 0.5f;
        Vector3 f = d + (e - d) * 0.5f;

        // left branch
        ArcLengthUtil(A, a, d, f, subdiv - 1, ref L);
        // right branch
        ArcLengthUtil(f, e, c, D, subdiv - 1, ref L);
    }
    else
    {
        float controlNetLength = (B-A).magnitude + (C - B).magnitude + (D - C).magnitude;
        float chordLength = (D - A).magnitude;
        L += (chordLength + controlNetLength) / 2.0f;
    }
}
Tyler Heers
  • 134
  • 4
-2

first of first you should Understand the algorithm use in Bezier, When i was coding a program by c# Which was full of graphic material I used beziers and many time I had to find a point cordinate in bezier , whic it seem imposisble in the first look. so the thing i do was to write Cubic bezier function in my costume math class which was in my project. so I will share the code with you first.

    //--------------- My Costum Power Method ------------------\\

public static float FloatPowerX(float number, int power)
        {
            float temp = number;
            for (int i = 0; i < power - 1; i++)
            {
                temp *= number;
            }
            return temp;
        }

    //--------------- Bezier Drawer Code Bellow ------------------\\

public static void CubicBezierDrawer(Graphics graphics, Pen pen, float[] startPointPixel, float[] firstControlPointPixel
                , float[] secondControlPointPixel, float[] endPointPixel)
        {
            float[] px = new float[1111], py = new float[1111];
            float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0], secondControlPointPixel[0], endPointPixel[0] };
            float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1], secondControlPointPixel[1], endPointPixel[1] };
        int i = 0;

        for (float t = 0; t <= 1F; t += 0.001F)
        {
            px[i] = FloatPowerX((1F - t), 3) * x[0] + 3 * t * FloatPowerX((1F - t), 2) * x[1] + 3 * FloatPowerX(t, 2) * (1F - t) * x[2] + FloatPowerX(t, 3) * x[3];
            py[i] = FloatPowerX((1F - t), 3) * y[0] + 3 * t * FloatPowerX((1F - t), 2) * y[1] + 3 * FloatPowerX(t, 2) * (1F - t) * y[2] + FloatPowerX(t, 3) * y[3];
            graphics.DrawLine(pen, px[i - 1], py[i - 1], px[i], py[i]);
            i++;
        }
    }

as you see above, this is the way a bezier Function work and it draw the same Bezier as Microsoft Bezier Function do( I've test it). you can make it even more accurate by incrementing array size and counter size or draw elipse instead of line& ... . All of them depend on you need and level of accuracy you need and ... .

Returning to main goal ,the Question is how to calc the lenght???

well The answer is we Have tons of point and each of them has an x coorinat and y coordinate which remember us a triangle shape & especially A RightTriabgle Shape. so if we have point p1 & p2 , we can calculate the distance of them as a RightTriangle Chord. as we remeber from our math class in school, in ABC Triangle of type RightTriangle, chord Lenght is -> Sqrt(Angle's FrontCostalLenght ^ 2 + Angle's SideCostalLeghth ^ 2);

and there is this relation betwen all points we calc the lenght betwen current point and the last point before current point(exmp p[i - 1] & p[i]) and store sum of them all in a variable. lets show it in code bellow

//--------------- My Costum Power Method ------------------\\

public static float FloatPower2(float number)
        {
            return number * number;
        }

//--------------- My Bezier Lenght Calculator Method ------------------\\

public static float CubicBezierLenghtCalculator(float[] startPointPixel
            , float[] firstControlPointPixel, float[] secondControlPointPixel, float[] endPointPixel)
        {
            float[] tmp = new float[2];
            float lenght = 0;
            float[] px = new float[1111], py = new float[1111];

            float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0]
                , secondControlPointPixel[0], endPointPixel[0] };

            float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1]
                , secondControlPointPixel[1], endPointPixel[1] };

            int i = 0;

            for (float t = 0; t <= 1.0; t += 0.001F)
            {
                px[i] = FloatPowerX((1.0F - t), 3) * x[0] + 3 * t * FloatPowerX((1.0F - t), 2) * x[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * x[2] + FloatPowerX(t, 3) * x[3];
                py[i] = FloatPowerX((1.0F - t), 3) * y[0] + 3 * t * FloatPowerX((1.0F - t), 2) * y[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * y[2] + FloatPowerX(t, 3) * y[3];
                if (i > 0)
                {
                    tmp[0] = Math.Abs(px[i - 1] - px[i]);// calculating costal lenght
                    tmp[1] = Math.Abs(py[i - 1] - py[i]);// calculating costal lenght
                    lenght += (float)Math.Sqrt(FloatPower2(tmp[0]) + FloatPower2(tmp[1]));// calculating the lenght of current RightTriangle Chord  & add it each time to variable
                }
                i++;
            }
            return lenght;
        }

if you wish to have faster calculation just need to reduce px & py array lenght and loob count.

We also can decrease memory need by reducing px and py to array lenght to 1 or make a simple double variable but becuase of Conditional situation Happend which Increase Our Big O I didn't do that.

Hope it helped you so much. if have another question just ask. With Best regards, Heydar - Islamic Republic of Iran.

Heydar
  • 137
  • 1
  • 8