a coder named Floris

Goal: Showing an algo that computes the Bounding box of a cubic bezier.
Audience: Needs some basic Math, Derivative, solving parabola, knowledge of computer language.
Sample in c# : coming soon, at bottom of article.

This is also my first usage of a HTML5 element, so IE users sorry!

If you are NOT familiar with what a cubic bezier is, please look at this wiki page.

If you use the start and end point of a cubic bezier and both of the controlpoints, you will end up with a box. This box will contain the bezier, but it’s not really tight. You want a tight bb (bounding box). The controlpoints of the bezier may lay outside the bb.

This example is shows a working example (if the HTML5 canvas element is supported you’ll see a interactive demonstration) :

So how to do this?

You’ll need to know the function of the cubic bezier. Defined as:
f(t) = a*t^3 + b*t^2 + c*t +d
where
d = P0
c = 3*P1-3*P0
b = 3*P2-6*P1+3*P0
a = P3-3*P2+3*P1-P0

p0 and p3 are the begin and end point of the bezier, p1 & p2 the control points. This function is defined for t=[0..1] so (0, 0.00001, 0.00002, … 0.99999)

Code to draw bezier point by point

protected override void OnPaint(PaintEventArgs pe)
{
  Func<double, double, double, double, double, double> bezierSpline = (p0, p1, p2, p3, t) =>
                (p3 - 3 * p2 + 3 * p1 - p0) * Math.Pow(t, 3)
                + (3 * p2 - 6 * p1 + 3 * p0) * Math.Pow(t, 2)
                + (3 * p1 - 3 * p0) * t
                + (p0);


  for (double t = 0; t <= 1; t += 0.001) //adjust if you want
  {
    double x = bezierSpline(_points[0].X, _points[1].X, _points[2].X, _points[3].X, t);
    double y = bezierSpline(_points[0].Y, _points[1].Y, _points[2].Y, _points[3].Y, t); ;

    var p = new PointF((float)x, (float)y);
    drawPoint(pe.Graphics, p, Color.Orange, 2);
  }
}

private void drawPoint(Graphics g, PointF p, Color color, float size)
{
  Brush b = new SolidBrush(color);
  float w = size;
  RectangleF r = new RectangleF(p.X-(w/2f),p.Y-(w/2f),w,w);
  g.FillEllipse(b,r);
  b.Dispose();                
}//this code snippet has been cut-n-pasted from project, may contain some err..

A possible way to compute bb is to add each point to bb evaluation, and you need plenty to ensure the exactness of the bb! Don't do this! Unless you want to do TDD and test if the bb is nearly the same as the bb you are about to compute for testing purposes.

Derivative

The exact solution can be found by using math. if you derivative the bezier function you can find local extremes.

so
f(t) = a*t3 + b*t2 + c*t +d
becomes :
f(t)' = 3a*t^2 + 2b*t + c

Do not forget the values of a,b and c! as defined above.

If you find the where f(t)'=0 then you'll find local extremes. To do this you'll need to find where the parabola equals 0 for each of the axises. You'll need to solve the parabola (f(t)' is now a parabola!) for the x and y values of your points.

To find out if there is a solution we'll use the discriminant (Quadratic formula) b^2-4ac. This will tell you if there is a solution.

Example:
suppose points:
p0 = (30,70)
p1 = (0,270)
p2 = (290,110)
p3 = (200, 100)

f(t)' = 3a*t^2 + 2b*t + c

with:

a = P3-3*P2+3*P1-P0
b = 3*P2-6*P1+3*P0
c = 3*P1-3*P0

becomes:

f(t)' = 3(P3-3*P2+3*P1-P0)*t^2 + 2(3*P2-6*P1+3*P0)*t + (3*P1-3*P0)

//solution for x values:
a = 3(200-3*290+3*0-30) = -2100
b = 2(3*P2-6*P1+3*P0) = 1920
c = (3*P1-3*P0) = -90

with D = b^2-4ac
D=2930400
D>0 so there are 2 solutions

you can calculate the solution with (-b + sqrt(b^2 - 4ac)) / 2a and (-b - sqrt(b^2 - 4ac)) / 2a.

s1 = 0.04956 s2 = 0.86472

do the same for the Y values
you'll come to:
a=1530
b=-2160
c=600

D=993600 so 2 solutions

s1=1.03163
s2=0.38013

!!You'll need to throw away the first solution of 1.03163, since the bezier function is only defined between 0 and 1!

us the solutions you came up as params for the original bezier function.
so :
//s1 = 0.04956 s2 = 0.86472
x1 = f(0.04956) => 27.8
y1 = f(0.04956) => 97.1

x2 = f(0.86472) => 217.3
y2 = f(0.86472) => 111.0

//s1=1.03163 s2=0.38013
x3 = f(0.38013) => 96.0
y3 = f(0.38013) => 170.0

ok,.. now you have the local extremes! And evaluation of the bb is next.

The Bounding Box

Take the start and end point, include the local extremes.

find the smallest x and y value
find the largest x and y value.

there you have your bb!

Now there is a small trap,..
your p0..p3 can be placed in such a way that for the f(t)' a becomes 0. When this happens the function is no longer a parabola, but a line.
f(t)' = at^2 + bt + c
f(t)' = at^2 + bt + c
f(t)' = bt + c
-bt= c
-t = c/b
t = -c/b

that is all you'll need to solve the bb of a bezier!

Here is some c# code :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace BoundingBoxTestProject
{
public static class BezierOp
{
    public delegate TResult Func<T1, T2, T3, T4, T5, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5);

    //cubic polinomal
    //x = At^3 + Bt^2 + Ct + D
    //where A,B,C,D:
    //A = p3 -3 * p2 + 3 * p1 - p0
    //B = 3 * p2 - 6 * p1 +3 * p0
    //C = 3 * p1 - 3 * p0
    //D = p0            
    public static Func<double, double, double, double, double, double> bezierSpline = (p0, p1, p2, p3, t) =>
                                                                        (p3 - 3 * p2 + 3 * p1 - p0) * Math.Pow(t, 3)
                                                                        + (3 * p2 - 6 * p1 + 3 * p0) * Math.Pow(t, 2)
                                                                        + (3 * p1 - 3 * p0) * t
                                                                        + (p0);

    //X = At^3 + Bt^2 + Ct + D
    //where A,B,C,D:
    //A = (p3 -3 * p2 + 3 * p1 - p0)
    //B = (3 * p2 - 6 * p1 +3 * p0)
    //C = (3 * p1 - 3 * p0)
    //D = (p0)

    //We would like to know the values of t where X = 0
    //X  = (p3-3*p2+3*p1-p0)t^3 + (3*p2-6*p1+3*p0)t^2 + (3*p1-3*p0)t + (p0)
    //Derivetive :
    //X' = 3(p3-3*p2+3*p1-p0)t^(3-1) + 2(6*p2-12*p1+6*p0)t^(2-1) + 1(3*p1-3*p0)t^(1-1)              [f(x)=aX^n => f'(x)=a*n*X^(n-1)  remember?]
    //simplified:
    //X' = (3*p3-9*p2+9*p1-3*p0)t^2 + (6*p2-12*p1+6*p0)t + (3*p1-3*p0)
    //**!!reusing a,b,and c!!!***
    //taken as aX^2 + bX + c  a,b and c are:          
    public static Func<double, double, double, double, double> A = (p0, p1, p2, p3) => 3 * p3 - 9 * p2 + 9 * p1 - 3 * p0;
    //ommitting power 2 for now            
    public static Func<double, double, double, double> B = (p0, p1, p2) => 6 * p2 - 12 * p1 + 6 * p0;
    public static Func<double, double, double> C = (p0, p1) => 3 * p1 - 3 * p0;

    //b^2 - 4ac = Determinant
    public static Func<double, double, double, double> Determinant = (a, b, c) => Math.Pow(b, 2) - 4d * a * c;

    public static Func<double, double, double, double[]> Solve = (a, b, c) =>
                                                       {
                                                           Func<double, double, double, bool, double> _Solve =
                                                               (a_, b_, c_, s) =>
                                                               (-b_ +
                                                                (Math.Sqrt((b_ * b_) - (4d * a_ * c_)) *
                                                                 ((s) ? 1d : -1d))) / (2d * a_);

                                                           double d = Determinant(a, b, c);
                                                           if (d < 0)
                                                               return new double[] { };

                                                           if (a == 0)
                                                               //aX^2 + bX + c well then then this is a simple line
                                                               //x= -c / b
                                                               return new double[] { -c / b };

                                                           if (d == 0)
                                                           {
                                                               return new double[] { _Solve(a, b, c, true) };
                                                           }
                                                           else
                                                               return new double[]
                                                                  {
                                                                      _Solve(a, b, c, true),
                                                                      _Solve(a, b, c, false)
                                                                  };
                                                       };

    public static RectangleF GetRect(PointF p1, PointF c1, PointF c2, PointF p2)
    {
        double aX = A(p1.X, c1.X, c2.X, p2.X);
        double bX = B(p1.X, c1.X, c2.X);
        double cX = C(p1.X, c1.X);

        double aY = A(p1.Y, c1.Y, c2.Y, p2.Y);
        double bY = B(p1.Y, c1.Y, c2.Y);
        double cY = C(p1.Y, c1.Y);

        var resX = Solve(aX, bX, cX).Where(t => (t >= 0) && (t <= 1)); //solve for t ==0 & filter
        var resY = Solve(aY, bY, cY).Where(t => (t >= 0) && (t <= 1)); //solve for t ==0 & filter

        //Draw min and max;

        List<PointF> _BBox = new List<PointF>();
        _BBox.Add(p1); //Add Begin and end point not the control points!
        _BBox.Add(p2);

        foreach (var e in resX.Union(resY))
        {
            double x = bezierSpline(p1.X, c1.X, c2.X, p2.X, e);
            double y = bezierSpline(p1.Y, c1.Y, c2.Y, p2.Y, e);

            PointF p = new PointF((float)x, (float)y);
            _BBox.Add(p);
        }

        float minX = float.MaxValue;
        float minY = float.MaxValue;
        float maxX = float.MinValue;
        float maxY = float.MinValue;

        foreach (var e in _BBox) //find the bounding box.
        {
            minX = Math.Min(e.X, minX);
            minY = Math.Min(e.Y, minY);
            maxX = Math.Max(e.X, maxX);
            maxY = Math.Max(e.Y, maxY);
        }

        return new RectangleF(minX, minY, maxX - minX, maxY - minY);
    }

}

}

3 Responses to “Calculating / Computing the Bounding Box of Cubic Bezier”