Calculating Cubic Bezier Bounds

When working with path nodes, one very useful operation is rendering a Bezier curve. In most cases you don't really care about the bounds of the curve itself because it is a line, and usually the drawing area is of fixed size, or the view is movable. On the other hand, wanting to size an SVG view box to a Bezier curve means that being able to calculate the precise bounds of the curve is very useful.

Where to begin

Calculating the bounds first requires the equation by which Beziers are defined. The equation for a point on a cubic Bezier $\textbf{B}(t)$ is defined as (notice the presence of the binomial theorem):

$$ \textbf{B}(t) = (1 - t)^3\textbf{P}_0 + 3(1 - t)^2t\textbf{P}_1 + 3(1 - t)t^2\textbf{P}_2 + t^3\textbf{P}_3 $$

The curve itself is officially defined for the $[0,1]$ range. In order to get the bounds we need to find where the curve "turns around" in either the $x$ or $y$ direction. These are called the points of inflection and can easily be found by the proper application of calculus. If you don't want to see how the calculus is done you can skip past it.

Calculus

The particular calculus that needs to be used to find the inflection points is calculating the derivative. Once the derivative has been calculated the inflection points can be found by where the derivative equals zero for each dimension. Due to the nature of the curve, every inflection point that is both a real number and within the $[0,1]$ range will be an excellent candidate for calculating the overall bounds.

Deriving Beziers

The derivative is pretty straightforward if you know how to apply the chain rule, the product rule, remember that the points are constants, and work one chunk at a time.

The first chunk is pretty easy thanks to the chain rule.

\begin{align} \textbf{B}(t) &= (1 - t)^3\textbf{P}_0 + \dots & u &= 1 - t\cr &= u^3\textbf{P}_0 + \dots\cr\cr \textbf{B}'(t) &= 3u^2u'\textbf{P}_0 + \dots & u' &= -1\cr &= -3(1-t)^2\textbf{P}_0 + \dots \cr &= -3(t^2 - 2t + 1)\textbf{P}_0 + \dots \end{align}

The second chunk is a bit more difficult, and at first glance there are actually two ways to do it. One way involves simply expanding the term. The other way uses a combination of the product rule and the chain rule.

By way of expansion there's only a few steps.

\begin{align} \textbf{B}(t) &= \dots + 3(1 - t)^2t\textbf{P}_1 + \dots \cr &= \dots + 3(t^2 -2t + 1)t\textbf{P}_1 + \dots \cr &= \dots + 3(t^3 -2t^2 + t)\textbf{P}_1 + \dots \cr \textbf{B}'(t) &= \dots + 3(3t^2 -4t + 1)\textbf{P}_1 + \dots \end{align}

Using a combination of the product and chain rules is a bit more complex, even though the first step seems like a logical jump.

\begin{align} \textbf{B}(t) &= \dots + 3(1 - t)^2t\textbf{P}_1 + \dots \cr &= \dots + 3u^2t\textbf{P}_1 + \dots & u &= 1 - t \cr \textbf{B}'(t) &= \dots + (6uu't + 3u^2)\textbf{P}_1 + \dots & u' &= -1 \cr &= \dots + 3(u^2 - 2ut)\textbf{P}_1 + \dots \cr &= \dots + 3((1-t)^2 - 2(1-t)t)\textbf{P}_1 + \dots\cr &= \dots + 3(t^2 - 2t + 1 - 2t + 2t^2)\textbf{P}_1 + \dots \cr &= \dots + 3(3t^2 -4t + 1)\textbf{P}_1 + \dots \cr \end{align}

Both ultimately yield the same result, though an initial substitution instinct resulted in a bit more work. Being aware of this while looking at the third term expansion seems like the better choice, especially considering the simplicity.

\begin{align} \textbf{B}(t) &= \dots + 3(1 - t)t^2\textbf{P}_2 + \dots \cr &= \dots + 3(t^2 - t^3)\textbf{P}_2 + \dots \cr \textbf{B}'(t) &= \dots + 3(2t - 3t^2)\textbf{P}_2 + \dots \cr \end{align}

The final term is really easy to derive and is really just one step.

\begin{align} \textbf{B}(t) &= \dots + t^3\textbf{P}_3 \cr \textbf{B}'(t) &= \dots + 3t^2\textbf{P}_3 \end{align}

Adding all the pieces together results in a derivative that is not too much longer than the original equation.
$$ \textbf{B}'(t) = -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3 $$

Rearranging the Derivative

From the previous section we calculated that the derivative is:
$$ \textbf{B}'(t) = -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3 $$ The next step to finding the points of inflection for each dimension $(x, y, z)$ is to solve that equation for the values of $t$ that make $\textbf{B}'(t) = 0$ for that dimension. This seems like an impossible task given the size of the equation, but on closer inspection it's clear that there are no terms of higher order than $t^2$. Perhaps the equation can be rearranged in terms of $t$ so that the quadratic equation can be used to solve it. In point of fact, it can, and that's precisely the way to go.

\begin{align} \textbf{B}'(t) &= -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3\cr 0 &= 3(-(t^2 - 2t + 1)\textbf{P}_0 + (3t^2 -4t + 1)\textbf{P}_1 + (2t - 3t^2)\textbf{P}_2 + t^2\textbf{P}_3)\cr
&= -(t^2 - 2t + 1)\textbf{P}_0 + (3t^2 -4t + 1)\textbf{P}_1 + (2t - 3t^2)\textbf{P}_2 + t^2\textbf{P}_3\cr &= -\textbf{P}_0t^2 + 2\textbf{P}_0t - \textbf{P}_0 + 3\textbf{P}_1t^2 - 4\textbf{P}_1t + \textbf{P}_1 - 3\textbf{P}_2t^2 + 2\textbf{P}_2t + \textbf{P}_3t^2\cr &= -\textbf{P}_0t^2 + 3\textbf{P}_1t^2 - 3\textbf{P}_2t^2 + \textbf{P}_3t^2 + 2\textbf{P}_0t - 4\textbf{P}_1t + 2\textbf{P}_2t - \textbf{P}_0 + \textbf{P}_1\cr &= (-\textbf{P}_0 + 3\textbf{P}_1 - 3\textbf{P}_2 + \textbf{P}_3)t^2 + (2\textbf{P}_0 - 4\textbf{P}_1 + 2\textbf{P}_2)t + (-\textbf{P}_0 + \textbf{P}_1) \end{align}

To make things a little easier, it makes sense to go ahead and save off the groupings in simple variables. This makes composition into the quadratic formula much easier.

\begin{align} 0 &= at^2 + bt + c\cr
\text{where:}\cr a &= \textbf{P}_3 - 3\textbf{P}_2 + 3\textbf{P}_1 - \textbf{P}_0\cr
b &= 2\textbf{P}_2 - 4\textbf{P}_1 + 2\textbf{P}_0\cr
c &= \textbf{P}_1 - \textbf{P}_0
\end{align}

I flipped the order of the points around so the subtraction lines up a little nicer, but other than that it's a simple substitution that plugs nicely into the quadratic formula.

\begin{gather} \Delta = b^2 - 4ac\cr \frac{-b \pm \sqrt\Delta}{2a} \end{gather}

Notice that the delimiter is kept separate because if $\Delta < 0$ there is no real answer.

Application

Now that things are in easy to digest pieces it's time to implement all the hard work into some code. Since the derivative only gives the values int terms of $t$ they will need to be plugged into the Bezier equation in order to get the actual $(x,y)$ points of the inflection.

There will be four functions total. One that accepts the $(x,y)$ points to apply the derivative to, one that accepts just a single dimension for each point to apply the derivative to, one to calculate the result of $(x,y)$ points and a $t$ value with the Bezier equation, and one that calculates the Bezier equation for a single dimension. In JavaScript it looks like this:

function getBezierInflectionPoints(p0, p1, p2, p3) {  
    return getBezierInflectionPointsForDimension(p0.x, p1.x, p2.x, p3.x)
            .concat(getBezierInflectionPointsForDimension(p0.y, p1.y, p2.y, p3.y))
            .map(function(t) {
                return getBezierPoint(p0, p1, p2, p3, t);
            });

}

function getBezierInflectionPointsForDimension(p0, p1, p2, p3) {  
    var a = p3 - 3 * p3 + 3 * p1 - p0,
        b = 2 * p2 - 4 * p1 - 2 * p0,
        c = p1 - p0,
        delimiter = Math.pow(b, 2) - 4 * a * c,
        value = 0,
        values = [];

    if (delimiter > 0) {
        value = (-b + Math.sqrt(delimiter)) / (2 * a);

        if (value > 0 && value < 1) {
            values.push(value);
        }

        value = (-b - Math.sqrt(delimiter)) / (2 * a);

        if (value > 0 && value < 1) {
            values.push(value);
        }
    }

    return values;
}

function getBezierPoint(p0, p1, p2, p3, t) {  
    return {
        x: getBezierPointForDimension(p0.x, p1.x, p2.x, p3.x, t),
        y: getBezierPointForDimension(p0.y, p1.y, p2.y, p3.y, t)
    };
}

function getBezierPointForDimension(p0, p1, p2, p3, t) {  
    return Math.pow(1 - t, 3) * p0
            + 3 * Math.pow(1 - t, 2) * t * p1
            + 3 * (1 - t) * Math.pow(t, 2) * p2
            + Math.pow(t, 3) * p3;
}

Final Thoughts and Observations

The important thing to remember is that rendered Bezier curves have width (otherwise you couldn't see it, unless it's filled in of course). It's a good idea to add and subtract half of the stroke-width to both the $x$ and $y$ coordinates that come back from the function to ensure that the curve isn't "cut in half" at the boundaries.

It is also a good idea to avoid unnecessary calculations whenever possible. This is actually very easy because of how Bezier curves are defined mathematically. If the middle points in the set exist within the bounds of the outer points ($\textbf{P}_1$ and $\textbf{P}_2$ exist within $[\textbf{P}_0, \textbf{P}_3]$) no additional calculation needs to be done beyond the bounds of the outer points (factoring in stroke-width of course). While this may only eliminate a few cases here and there, that's quite a few operations that don't need to happen. The thing to keep in mind is that if either point strays outside the $[\textbf{P}_0, \textbf{P}_3]$ bounds, the full calculations should be run.

Are there any approximations that can be done to save on math? Sure, but this gives you precise boundaries, and number of calculations saved is generally not going to be terribly significant. Besides, how frequently will this code actually be run, and is it really the bottleneck?

Author:

Robert Plante

Coder by design. Designer by code. Thinker, tinkerer, problem solver.

comments powered by Disqus