11

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?

1

3 Answers 3

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/

2
  • 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: jsfiddle.net/QQnvm/38 (actually a quadratic.)
    – Jeff Ward
    Commented Jan 12, 2017 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. Commented Dec 29, 2017 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.

1
  • 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
    Commented Jul 18, 2014 at 8: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)}
    };
}
9
  • Hey, is there version of this for quadratic curves? Commented Nov 11, 2017 at 20:45
  • you can easily convert quadratic bezier curve to cubic. The code for quadratic is much shorter.
    – cuixiping
    Commented Nov 17, 2017 at 9:41
  • Thank you SO MUCH! Works perfectly and saved me after hours of search
    – Kobi Hari
    Commented Jul 13, 2020 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
    Commented Jun 9, 2021 at 14:13
  • My bad, I think I'm wrongly convert quadratic to cubic :/
    – Doubidou
    Commented Jun 9, 2021 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.