[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 <conmanx360 at gmail.com> 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.