Bounded Bézier

It’s possible to analytically find an axis-aligned bounding box (AABB) for Bézier curves. I wanted to try doing that math for myself,¹ and ended up writing a solver in Haskell, along with a few animations to show it off. All animations here were built with Reanimate.

In Reanimate, we can tween the value of a Double variable x over the course of time t using tweenVar and a Signal.

fork $ tweenVar x t $ \orig -> fromToS orig new . curveS 2

This lets us cycle through a bunch of different curves by interpolating between the sets of variables that define them.

A cubic Bézier curve is defined by four points—call them start, end, control start, and control end. We can use these points to define an SVG that will draw our Bézier curve for us. In Reanimate this is done with the CurveTo instruction on a Path.

We can also draw the control points as little circles if we want to visualize them. Defining these as sprites lets us use Vars to control them, and then Reanimate will handle all the variable updating behind the scenes for us, which is pretty nice for focusing on the math.

cubicBezier
  :: V2 Double
  -> V2 Double
  -> V2 Double
  -> V2 Double
  -> SVG
cubicBezier
  (V2 startX startY)
  (V2 controlStartX controlStartY)
  (V2 controlEndX controlEndY)
  (V2 endX endY)
 =
  PathTree $ Path mempty
    [ MoveTo OriginAbsolute [V2 startX startY]
    , CurveTo OriginAbsolute
      [
        ( V2 controlStartX controlStartY
        , V2 controlEndX controlEndY
        , V2 endX endY
        )
      ]
    ]

point :: Double -> Double -> SVG
point x y =
  CircleTree $ Circle mempty (Num x, Num y) (Num 0.1)

In two dimensions, an axis-aligned bounding box is defined by four numbers—min X, min Y, max X and max Y (this is equivalent to using two corner points).

We can find these numbers by solving the quadratic formula to end up with time values t to test, then plugging these ts back into our cubic Bézier to find minima and maxima.

These equations give us the a b and c that we’ll be plugging into the quadratic formula, and the overall strategy comes from taking the derivative of our cubic curve to find its roots (the derivative of a cubic is a quadratic). We can apply these equations independently to the X and Y parts of our four points that define the Bézier curve.²

sol_a start controlStart controlEnd end =
  3 * (-start + 3 * controlStart - 3 * controlEnd + end)
sol_b start controlStart controlEnd =
  6 * (start - 2 * controlStart + controlEnd)
sol_c start controlStart =
  3 * (controlStart - start)

We need to be slightly careful here to return only valid roots and only valid values of t. Since t ranges from 0 to 1, we throw out anything outside that range, as well as ignoring cases where we would otherwise perform division by zero.

quadratic a b c =
  if a == 0 then []
  else filter (\t -> t > 0 && t < 1)
    [ (-b + radicand) / (2 * a)
    , (-b - radicand) / (2 * a)
    ]
  where radicand = sqrt (b * b - 4 * a * c)

We now have a bunch of options for t values to try, including 0 and 1 (the start and end points of the curve, respectively).

allTsToTry = [0, 1] <> xRoots <> yRoots

We can plug that list back into the cubic Bézier equation to find extreme points, e.g. the minimum X value. Again we can treat X and Y separately.

solveCubicBezierX t =
  start * (1 - t) * (1 - t) * (1 - t) + 3 * controlStart * t * (1 - t) * (1 - t) + 3 * controlEnd * t * t * (1 - t) + end * t * t * t

minX = minimum $ map solveCubicBezierX allTsToTry

Typing out that formula was where I made this project’s mistake that was hardest to debug: I should have written the second line here instead of the top for controlStart.

t * (1 - t) * (1 - t)
t * t * (1 - t)

After spotting that, we now have a nice Bézier-in-a-box, solved entirely analytically, and complete with animations.

Because of the amount of math involved, I think Haskell was an excellent choice for this little project. Animating by hand would have been painful. Reanimate took some getting used to, but once I realized I could write my math functions as plainly as possible, but make use of the Applicative instance for Frames to get tweening almost “for free”, it got a lot nicer.