Re: [RFC PATCH 2/5] d2d1: Add cubic bezier bounds functions.

[Connor McAdams]

On Tue, Mar 17, 2020 at 09:04:18PM +0330, Henri Verbeet wrote:
> On Sun, 15 Mar 2020 at 23:20, Connor McAdams  wrote:
> > +static void d2d_rect_get_cubic_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
> > -
> >    const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3)
> >
> > +{
> > - D2D1_POINT_2F p, v1, v2, v3, a, b, c;
> > - float root, sq_root;
> > -
> > - if (d2d_check_if_cubic_is_quad(p0, p1, p2, p3))
> > - {
> > -
> >    d2d_bezier_cubic_to_quad(p0, p1, p2, p3, &p);
> > -
> >    d2d_rect_get_quadratic_bezier_bounds(bounds, p0, &p, p3);
> > -
> >    return;
> > - }
>
> Is that test worth it?

Yes, because trying to get the roots of a quadratic that's been upped to
a cubic with the cubic root functions won't get the correct values. You
need to get the derivative of a quadratic for a quadratic, even if it's
been upped to a cubic.
> > - /*
> > -
> > * f(t)  = (1 - t)³P₀ + 3(1 - t)²tP₁ + 3(1 - t)t²P₂ + t³P₃
> > -
> > * f'(t) = 3(1 - t)²(P₁ - P₀) + 6(1 - t)t(P₂ - P₁) + 3t²(P₃ - P₂)
> > -
> > *
> > -
> > * Or, from https://pomax.github.io/bezierinfo/#extremities
> > -
> > * V₁ = 3(P₁ - P₀)
> > -
> > * V₂ = 3(P₂ - P₁)
> > -
> > * V₃ = 3(P₃ - P₂)
> > -
> > * f'(t) = V₁(1 - t)² + 2V₂(1 - t)t + V₃t²
> > -
> > *       = (V₁ - 2V₂ + V₃)t² + 2(V₂ - V₁)t + V₁
> > -
> > *
> > -
> > * And new quadratic coefficients a, b, and c are:
> > -
> > * a = V₁ - 2V₂ + V₃
> > -
> > * b = 2(V₂ - V₁)
> > -
> > * c = V₁
> > -
> > *
> > -
> > * f'(t) = 0
> > -
> > * t = (-b ± √(b² - 4ac)) / 2a
> > -
> > */
>
> ...
> > - /* If the square root in the equation is negative, there are no roots. */
> > - if ((sq_root = sqrtf(b.x * b.x - 4.0f * a.x * c.x)) >= 0.0f)
> > - {
> > -
> >    root = (-b.x + sq_root) / (2.0f * a.x);
> > -
> >    if (root < 1.0f && root > 0.0f)
> > -
> >    {
> > -
> >        d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root);
> > -
> >        d2d_rect_expand(bounds, &p);
> > -
> >    }
> > -
> > -
> >    root = (-b.x - sq_root) / (2.0f * a.x);
> > -
> >    if (root < 1.0f && root > 0.0f)
> > -
> >    {
> > -
> >        d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root);
> > -
> >        d2d_rect_expand(bounds, &p);
> > -
> >    }
> > - }
>
> Passing a negative value to sqrtf() won't return a negative result.
> (And it shouldn't, of course.) It'll return NaN.
>
> When the value of √(b² - 4ac) is close to b (i.e., if b² is much
> larger than 4ac), -b + √(b² - 4ac) will have a relatively large error.
> Fortunately, this particular formula has another well-known variant:
> 2c / (-b ∓ √(b² - 4ac))
>
> It has the same issue, but in the opposite case, so you can use one
> calculation or the other depending on the sign of b.

Okay, I will change this. Thanks for the insight.