SVG path bounding box: cubic Bézier curves

TL;DR

SVG path bounding box for cubic Bézier curves.

I guess you saw it coming.

After describing the SVG path bounding box: quadratic Bézier curves, it’s about time to move on to the cubic Bézier curves:

sub cubic_bezier_bb ($P0, $P1, $P2, $P3) {
  my %retval = (min => {}, max => {});
  for my $axis (qw< x y >) {
     my ($p0, $p1, $p2, $p3) = map { $_->{$axis} } ($P0, $P1, $P2, $P3);
     my ($a_, $b2_, $c_) = (    # a, c divided by 3, b divided by -6
        -$p0 + 3 * $p1 - 3 * $p2 + $p3,
        $p0 - 2 * $p1 + $p2,
        -$p0 + $p1
     );
     my @candidates = (0, 1);
     my $det = $b2_**2 - $a_ * $c_;    # (b/2)^2 - ac
     if ($det > THRESHOLD && abs($a_) > THRESHOLD) {
        my $sdet = sqrt($det);
        for my $s ($sdet, -$sdet) {
           my $t = (-$b2_ + $s) / $a_;
           push @candidates, $t if 0 <= $t && $t <= 1;
        }
     } ## end if ($det > THRESHOLD...)
     for my $pt (@candidates) {
        my $mt = 1 - $pt;
        my $v =
          $mt**3 * $p0 +
          3 * $mt**2 * $pt * $p1 +
          3 * $mt * $pt**2 * $p2 +
          $pt**3 * $p3;
        $retval{min}{$axis} //= $retval{max}{$axis} //= $v;
        if    ($v < $retval{min}{$axis}) { $retval{min}{$axis} = $v }
        elsif ($v > $retval{max}{$axis}) { $retval{max}{$axis} = $v }
     } ## end for my $pt (@candidates)
  } ## end for my $axis (qw< x y >)
  return \%retval;
} ## end sub cubic_bezier_bb

There is nothing really different from the previous post, actually: we still go through the axes separately (line 3) and take all relevant values in that direction (line 4), only we work with different parameters for the derivative, that is now a second-degree equation with parameters $a$, $b$, and $c$ (lines 5 to 9).

As before, we’re not using the actual values that would come from the relevant equation:

\[\begin{bmatrix} \mathbf{c} \\ \mathbf{b} \\ \mathbf{a} \end{bmatrix} = \begin{bmatrix} c_x & c_y \\ b_x & b_y \\ a_x & a_y \end{bmatrix} = 3 \cdot \begin{bmatrix} - \mathbf{P}_1 + \mathbf{P}_2 \\ 2 \cdot (\mathbf{P}_1 - 2 \cdot \mathbf{P}_2 + 1 \cdot \mathbf{P}_3) \\ - \mathbf{P}_1 + 3 \cdot \mathbf{P}_2 -3 \cdot \mathbf{P}_3 + \mathbf{P}_4 \end{bmatrix}\]

We’re disregarding the $3$ (we’re after the zeros, so it can be canceled out) and we’re also using the simplified form for the roots of a second-degree polynomial, so we’re leveraging $\frac{b}{2}$, which is easily calculated because the formula for $b$ above has a factor 2 that can be ignored:

\[t_{\pm} = \frac{-\frac{b}{2} \pm \sqrt{\left(\frac{b}{2}\right)^2 - a \cdot c}}{a}\]

Just to be paranoid, we take into account possible numerical instabilities and other amenities and ignore the solution if the determinant is too low or negative, as well as $a_ (lines 11 and 12); otherwise, it’s pretty much the same approach as that for quadratic curves.

Edits

2020-07-18 fixed bug, not taking absolute value of determinant and ignoring negative ones!

ETOOBUSY 🚀 minimal blogging for the impatient