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

[Henri Verbeet]

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?

> +    /*
> +     * 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.