10

I am trying to find an algorithm to calculate the bounding box of a given cubic bezier curve. The curve is in 3D space.

Is there a mathematic way to do this except of sampling points on the curve and calculating the bounding box of these points?

Erik Sapir
  • 23,209
  • 28
  • 81
  • 141
  • http://stackoverflow.com/questions/2587751/an-algorithm-to-find-bounding-box-of-closed-bezier-curves – JAre Jul 17 '14 at 17:52

3 Answers3

8

Most of this is addressed in An algorithm to find bounding box of closed bezier curves? except here we have cubic Beziers and there they were dealing with quadratic Bezier curves.

Essentially you need to take the derivatives of each of the coordinate functions. If the x-coord is given by

x = A (1-t)^3 +3 B t (1-t)^2 + 3 C t^2 (1-t) + D t^3

differentiating with respect to t.

dx/dt =  3 (B - A) (1-t)^2 + 6 (C - B) (1-t) t + 3 (D - C) t^2
      =  [3 (D - C) - 6 (C - B) + 3 (B - A)] t^2
       + [ -6 (B - A) - 6 (C - B)] t
       + 3 (B - A) 
      =  (3 D - 9 C + 9 B - 3 A) t^2 + (6 A - 12 B + 6 C) t + 3 (B - A)

this is a quadratic which we can write at a t^2 + b t + c. We want to solve dx/dt = 0 which you can do using the quadratic formula

- b +/- sqrt(b^2-4 a c)
-----------------------
        2 a

Solving this will either gives two solutions t0, t1 say, no solutions or in rare case just one solution. We are only interest in solutions with 0 <= t <= 1. You will have a maximum of four candidate points, the two end points and the two solutions. Its a simple matter to find which of these give the extreme points.

You can repeat the same process for each coordinate and then get the bounding box.

I've put this for the 2D case in a js fiddle http://jsfiddle.net/SalixAlba/QQnvm/4/

Community
  • 1
  • 1
Salix alba
  • 7,536
  • 2
  • 32
  • 38
  • Awesome, thanks! I noticed an instability, though, when `a==0`, it gives incorrect bounds, as `t1` and `t2` both turn out to be infinity. I fixed it with a hack that seems to work: `if (a==0) a = 0.0000001;` an example: http://jsfiddle.net/QQnvm/38/ (actually a quadratic.) – Jeff Ward Jan 12 '17 at 15:40
  • 2
    That hack is kinda pointless, though. Rather than using hacks, you could just check the formula for how to handle that case. If a == 0, you can simply solve the equation `b t + c = 0` which gives you `t = -c / b`. – Stefan Fabian Dec 29 '17 at 11:11
6

Finding the bounding box of a cubic Bezier curve (or even B-spline curve of any degree) is typically done by finding the bounding box of the curve's control polygon. Since the curve is always bounded by its control polygon, the bounding box obtained via the control polygon is guaranteed to enclose the curve. You can also perform knot insertion to the curve and make the control polygon become closer to the curve itself. So, the general algorithm will go like this:

1) Find the bounding box (denoted as BBox1) of the current B-spline curve from its control polygon.
2) Insert knot at the mid-parameter of each Bezier segment in the B-spline curve.
3) Find the bounding box (denoted as BBox2) of the new B-spline curve.
4) Compare BBox2 against BBox1. If BBox2 is pretty much the same size as BBox1, we are done. If BBox2 is considerably smaller than BBox1, repeat step 2 to 4 until convergence.

fang
  • 3,473
  • 1
  • 13
  • 19
  • This is the better answer. Specifically, a cubic Bezier curve (or any Bezier curve) is completely enclosed by the convex hull defined by its control points. – Brett Hale Jul 18 '14 at 08:12
5

this article explain the details and also has a live html5 demo:
Calculating / Computing the Bounding Box of Cubic Bezier

I found a javascript in Snap.svg to calculate that: here
see the bezierBBox and curveDim functions.

I rewrite 2 javascript functions, for cubic and quadratic bezier.

//For cubic bezier.
//(x0,y0) is start point; (x1,y1),(x2,y2) is control points; (x3,y3) is end point.
function cubicBezierMinMax(x0, y0, x1, y1, x2, y2, x3, y3) {
    var tArr = [], xArr = [x0, x3], yArr = [y0, y3],
        a, b, c, t, t1, t2, b2ac, sqrt_b2ac;
    for (var i = 0; i < 2; ++i) {
        if (i == 0) {
            b = 6 * x0 - 12 * x1 + 6 * x2;
            a = -3 * x0 + 9 * x1 - 9 * x2 + 3 * x3;
            c = 3 * x1 - 3 * x0;
        } else {
            b = 6 * y0 - 12 * y1 + 6 * y2;
            a = -3 * y0 + 9 * y1 - 9 * y2 + 3 * y3;
            c = 3 * y1 - 3 * y0;
        }
        if (Math.abs(a) < 1e-12) {
            if (Math.abs(b) < 1e-12) {
                continue;
            }
            t = -c / b;
            if (0 < t && t < 1) {
                tArr.push(t);
            }
            continue;
        }
        b2ac = b * b - 4 * c * a;
        if (b2ac < 0) {
            if (Math.abs(b2ac) < 1e-12) {
                t = -b / (2 * a);
                if (0 < t && t < 1) {
                    tArr.push(t);
                }
            }
            continue;
        }
        sqrt_b2ac = Math.sqrt(b2ac);
        t1 = (-b + sqrt_b2ac) / (2 * a);
        if (0 < t1 && t1 < 1) {
            tArr.push(t1);
        }
        t2 = (-b - sqrt_b2ac) / (2 * a);
        if (0 < t2 && t2 < 1) {
            tArr.push(t2);
        }
    }

    var j = tArr.length, mt;
    while (j--) {
        t = tArr[j];
        mt = 1 - t;
        xArr[j] = (mt * mt * mt * x0) + (3 * mt * mt * t * x1) + (3 * mt * t * t * x2) + (t * t * t * x3);
        yArr[j] = (mt * mt * mt * y0) + (3 * mt * mt * t * y1) + (3 * mt * t * t * y2) + (t * t * t * y3);
    }

    return {
        min: {x: Math.min.apply(0, xArr), y: Math.min.apply(0, yArr)},
        max: {x: Math.max.apply(0, xArr), y: Math.max.apply(0, yArr)}
    };
}


//For quadratic bezier.
//(x0,y0) is start point; (x1,y1) is control points; (x2,y2) is end point.
function quadraticBezierMinMax(x0, y0, x1, y1, x2, y2) {
    var xArr = [x0, x2], yArr = [y0, y2], a, b, c, t;
    for (var i = 0; i < 2; ++i) {
        a = i == 0 ? x0 - 2 * x1 + x2 : y0 - 2 * y1 + y2;
        b = i == 0 ? -2 * x0 + 2 * x1 : -2 * y0 + 2 * y1;
        c = i == 0 ? x0 : y0;
        if (Math.abs(a) > 1e-12) {
            t = -b / (2 * a);
            if (0 < t && t < 1) {
                [xArr, yArr][i].push(a * t * t + b * t + c);
            }
        }
    }
    return {
        min: {x: Math.min.apply(0, xArr), y: Math.min.apply(0, yArr)},
        max: {x: Math.max.apply(0, xArr), y: Math.max.apply(0, yArr)}
    };
}
cuixiping
  • 24,167
  • 8
  • 82
  • 93
  • Hey, is there version of this for quadratic curves? – Sergey Rudenko Nov 11 '17 at 20:45
  • you can easily convert quadratic bezier curve to cubic. The code for quadratic is much shorter. – cuixiping Nov 17 '17 at 09:41
  • Thank you SO MUCH! Works perfectly and saved me after hours of search – Kobi Hari Jul 13 '20 at 18:50
  • I'm using this for quadratic too, but it's not accurate in some case (like control point far from start/end points) – Doubidou Jun 09 '21 at 14:13
  • My bad, I think I'm wrongly convert quadratic to cubic :/ – Doubidou Jun 09 '21 at 14:23
  • @cuixiping, while it is true it's easily convertable, claiming the quadratic version is much slower is nonsense. (except you have a well coded version for cubic and a bad coded for quadratic). Of course it's easier if you having to deal with an order less. It's not a big difference tough, since finding the BB is setting derivatives 0, its solving a quadratic equation in case of cubic beziers vs. a linear equation in case of quadratic beziers. – axkibe Jun 29 '23 at 07:41
  • @axkibe What I said is "much shorter" (less code lines), not "much slower". – cuixiping Jun 30 '23 at 12:19
  • @cuixiping fair point I did misread that. Albeit generally speaking the code for solving the quadratic case is also less code than the cubic (as mathematically simpler). Except of course you have already the code for cubic in your program and the code for converting, you might not bother to write the code version for quadratic if you do not care about the speed loss either. – axkibe Jul 03 '23 at 05:54
  • I added a function for quadratic bezier. – cuixiping Aug 03 '23 at 07:21