Re: [RFC PATCH 1/8] d2d1: Store cubic bezier control points.

[Henri Verbeet]

On Tue, 5 May 2020 at 00:23, Connor McAdams  wrote:
> @@ -48,8 +48,10 @@ enum d2d_vertex_type
>  {
>      D2D_VERTEX_TYPE_NONE,
>      D2D_VERTEX_TYPE_LINE,
> - D2D_VERTEX_TYPE_BEZIER,
> - D2D_VERTEX_TYPE_SPLIT_BEZIER,
> - D2D_VERTEX_TYPE_QUADRATIC_BEZIER,
> - D2D_VERTEX_TYPE_CUBIC_BEZIER,
> - D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER,
> - D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER,
>
> };

If I read the patch correctly, you don't actually need
D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER in this patch, and introducing it
in a later patch may simplify this one somewhat.
> +static void d2d_bezier_cubic_to_quad(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1,
> -
>    const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, D2D1_POINT_2F *c0)
>
> +{
> - c0->x =  (p1->x + p2->x) * 0.75f;
> - c0->y =  (p1->y + p2->y) * 0.75f;
> - c0->x -= (p0->x + p3->x) * 0.25f;
> - c0->y -= (p0->y + p3->y) * 0.25f;
>
> +}
> -
>
> +static void d2d_bezier_split_cubic(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1,
> -
>    const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t, D2D1_BEZIER_SEGMENT *left,
> -
>    D2D1_BEZIER_SEGMENT *right, D2D1_POINT_2F *center)
>
> +{
> - D2D1_POINT_2F q[4], r[3], mid;
> -
> - d2d_point_lerp(&q[0], p0, p1, t);
> - d2d_point_lerp(&q[1], p1, p2, t);
> - d2d_point_lerp(&q[2], p2, p3, t);
> -
> - d2d_point_lerp(&r[0], &q[0], &q[1], t);
> - d2d_point_lerp(&r[1], &q[1], &q[2], t);
> - d2d_point_lerp(&mid, &r[0], &r[1], t);
> -
> - if (center)
> -
>    *center = mid;
> -
> - if (left)
> - {
> -
>    left->point1 = q[0];
> -
>    left->point2 = r[0];
> -
>    left->point3 = mid;
> - }
> -
> - if (right)
> - {
> -
>    right->point1 = r[1];
> -
>    right->point2 = q[2];
> -
>    right->point3 = *p3;
> - }
>
> +}
> -
>
> +static BOOL d2d_vertex_type_is_bezier(enum d2d_vertex_type t)
> +{
> - return (t == D2D_VERTEX_TYPE_QUADRATIC_BEZIER || t == D2D_VERTEX_TYPE_CUBIC_BEZIER ||
> -
>        t == D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER || t == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER);
>
> +}
> -
>
> +static BOOL d2d_vertex_type_is_cubic_bezier(enum d2d_vertex_type t)
> +{
> - return (t == D2D_VERTEX_TYPE_CUBIC_BEZIER || t == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER);
>
> +}
> -
>
> +static BOOL d2d_vertex_type_is_split_bezier(enum d2d_vertex_type t)
> +{
> - return (t == D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER || t == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER);
>
> +}
> -
>
> +static BOOL d2d_vertex_type_is_unsplit_bezier(enum d2d_vertex_type t)
> +{
> - return (t == D2D_VERTEX_TYPE_QUADRATIC_BEZIER || t == D2D_VERTEX_TYPE_CUBIC_BEZIER);
>
> +}
> -

Some of these helpers could probably be introduced on their own,
before this patch, again simplifying this one a little.

I don't think you need d2d_vertex_type_is_unsplit_bezier(), all of the
places that use it should work just as well with
d2d_vertex_type_is_bezier(). (E.g., in d2d_geometry_intersect_self(),
there's no reason the D2D_VERTEX_TYPE_BEZIER paths wouldn't apply to
split beziers; we just don't have any at that point.)
> -static BOOL d2d_figure_insert_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p)
> +static BOOL d2d_figure_insert_bezier_controls(struct d2d_figure *figure, size_t idx, size_t count,
> -
>    const D2D1_POINT_2F **p)
>
> {
> - unsigned int i;
> - if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size,
> -
>        figure->bezier_control_count + 1, sizeof(*figure->bezier_controls)))
> -
>        figure->bezier_control_count + count, sizeof(*figure->bezier_controls)))
> {
>        ERR("Failed to grow bezier controls array.\n");
>        return FALSE;
>    }
> - memmove(&figure->bezier_controls[idx + 1], &figure->bezier_controls[idx],
> - memmove(&figure->bezier_controls[idx + count], &figure->bezier_controls[idx],
>         (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls));
> - figure->bezier_controls[idx] = *p;
> - ++figure->bezier_control_count;
> -
> -
>
> for (i = 0; i < count; ++i)
> -
>    figure->bezier_controls[idx + i] = *p[i];
> -
> -
>
> figure->bezier_control_count += count;
>
> return TRUE;
>
> }
>
> -static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p)
> +static BOOL d2d_figure_add_bezier_controls(struct d2d_figure *figure, size_t count, const D2D1_POINT_2F **p)
>  {
> - unsigned int i;
> - if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size,
> -
>        figure->bezier_control_count + 1, sizeof(*figure->bezier_controls)))
> -
>        figure->bezier_control_count + count, sizeof(*figure->bezier_controls)))
> {
>        ERR("Failed to grow bezier controls array.\n");
>        return FALSE;
>    }
> - figure->bezier_controls[figure->bezier_control_count++] = *p;
> -
>
> for (i = 0; i < count; ++i)
> -
>    figure->bezier_controls[figure->bezier_control_count + i] = *p[i];
> -
> -
>
> figure->bezier_control_count += count;
>
> return TRUE;
>
> }

The array of pointers probably isn't worth it. On 64-bit in particular
pointers are the same size as the D2D1_POINT_2F structure, so any
benefit seems questionable. If copying the points was a concern you
could take advantage of the fact that the D2D1_BEZIER_SEGMENT
structure is effectively an array of points, but I don't think it is.
> +static unsigned int d2d_figure_get_bezier_control_count(struct d2d_figure *figure)
> +{
> - unsigned int i, control_count;
> -
> - for (i = control_count = 0; i < figure->vertex_count; ++i)
> - {
> -
>    if (d2d_vertex_type_is_bezier(figure->vertex_types[i]))
> -
>        ++control_count;
> - }
> -
> - return control_count;
>
> +}

This returns the number of Bézier curves in the figure, not the number
of control points. Those are of course equivalent if all curves are of
the same order, but once you can have both quadratics and cubics
that's no longer true.
> @@ -1961,9 +2120,9 @@ static BOOL d2d_geometry_intersect_self(struct d2d_geometry *geometry)
>                  for (idx_q.vertex_idx = 0; idx_q.vertex_idx < max_q; ++idx_q.vertex_idx)
>                  {
>                      type_q = figure_q->vertex_types[idx_q.vertex_idx];
> -
>                if (type_q == D2D_VERTEX_TYPE_BEZIER)
> -
>                if (d2d_vertex_type_is_unsplit_bezier(type_q))
>                {
> -
>                    if (type_p == D2D_VERTEX_TYPE_BEZIER)
> -
>                    if (d2d_vertex_type_is_unsplit_bezier(type_p))
>                    {
>                        if (!d2d_geometry_intersect_bezier_bezier(geometry, &intersections,
>                                &idx_p, 0.0f, 1.0f, &idx_q, 0.0f, 1.0f))

As mentioned above, this should work fine with d2d_vertex_type_is_bezier().
> @@ -2328,7 +2492,7 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry,
>          if (!i)
>          {
>              prev_type = figure->vertex_types[figure->vertex_count - 1];
> -
>        if (prev_type == D2D_VERTEX_TYPE_BEZIER)
> -
>        if (d2d_vertex_type_is_unsplit_bezier(prev_type))
>            prev = &figure->bezier_controls[figure->bezier_control_count - 1];
>        else
>            prev = &figure->vertices[figure->vertex_count - 1];
>
> @@ -2336,19 +2500,22 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry,
>          else
>          {
>              prev_type = figure->vertex_types[i - 1];
> -
>        if (prev_type == D2D_VERTEX_TYPE_BEZIER)
> -
>        if (d2d_vertex_type_is_unsplit_bezier(prev_type))
>            prev = &figure->bezier_controls[bezier_idx - 1];
>        else
>            prev = &figure->vertices[i - 1];
>    }
>
> -
>    if (type == D2D_VERTEX_TYPE_BEZIER)
> -
>    if (d2d_vertex_type_is_unsplit_bezier(type))
>        next = &figure->bezier_controls[bezier_idx++];
>    else if (i == figure->vertex_count - 1)
>        next = &figure->vertices[0];
>    else
>        next = &figure->vertices[i + 1];
>
> -
>    if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
> -
>        bezier_idx++;
> -
>    if (figure_end == D2D1_FIGURE_END_CLOSED || (i && i < figure->vertex_count - 1))
>    {
>        D2D1_POINT_2F q_next, q_prev;
>
> @@ -2372,15 +2539,23 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry,
>              ERR("Failed to add line segment.\n");
>              return FALSE;
>          }
> -
>    else if (type == D2D_VERTEX_TYPE_BEZIER)
> -
>    else if (d2d_vertex_type_is_unsplit_bezier(type))
>    {
>        const D2D1_POINT_2F *p2;
> -
>        D2D1_POINT_2F tmp;
>
>        if (i == figure->vertex_count - 1)
>            p2 = &figure->vertices[0];
>        else
>            p2 = &figure->vertices[i + 1];
>
> -
>        if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
> -
>        {
> -
>            d2d_bezier_cubic_to_quad(p0, &figure->bezier_controls[bezier_idx - 2],
> -
>                &figure->bezier_controls[bezier_idx - 1], p2, &tmp);
> -
>            next = &tmp;
> -
>        }
> -
>        if (!d2d_geometry_outline_add_bezier_segment(geometry, p0, next, p2))
>        {
>            ERR("Failed to add bezier segment.\n");

Like d2d_geometry_intersect_self(), this would work the same with
split curves; we just don't have any here.
> @@ -2581,12 +2757,15 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if
>          p.y = (beziers[i].point1.y + beziers[i].point2.y) * 0.75f;
>          p.x -= (figure->vertices[figure->vertex_count - 1].x + beziers[i].point3.x) * 0.25f;
>          p.y -= (figure->vertices[figure->vertex_count - 1].y + beziers[i].point3.y) * 0.25f;

d2d_bezier_cubic_to_quad(&figure->vertices[figure->vertex_count - 1],
&beziers[i].point1, &beziers[i].point2, &beziers[i].point3, &p);
> @@ -3198,7 +3467,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
>          for (bezier_idx = 0, ++j; j < figure->vertex_count; ++j)
>          {
>              if (figure->vertex_types[j] == D2D_VERTEX_TYPE_NONE
> -
>                || figure->vertex_types[j] == D2D_VERTEX_TYPE_SPLIT_BEZIER)
> -
>                || d2d_vertex_type_is_split_bezier(figure->vertex_types[j]))
>            continue;
>
>        switch (type)
>
> @@ -3209,7 +3478,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
>                      d2d_rect_expand(bounds, &p);
>                      break;
> -
>            case D2D_VERTEX_TYPE_BEZIER:
> -
>            case D2D_VERTEX_TYPE_QUADRATIC_BEZIER:
>                p1 = figure->original_bezier_controls[bezier_idx++];
>                d2d_point_transform(&p1, transform, p1.x, p1.y);
>                p2 = figure->vertices[j];
>
> @@ -3219,6 +3488,20 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
>                      p = p2;
>                      break;
> -
>            case D2D_VERTEX_TYPE_CUBIC_BEZIER:
> -
>                d2d_bezier_cubic_to_quad(&figure->vertices[j - 1],
> -
>                    &figure->original_bezier_controls[bezier_idx],
> -
>                    &figure->original_bezier_controls[bezier_idx + 1],
> -
>                    &figure->vertices[j], &p1);
> -
>                bezier_idx += 2;
> -
>                d2d_point_transform(&p1, transform, p1.x, p1.y);
> -
>                p2 = figure->vertices[j];
> -
>                d2d_point_transform(&p2, transform, p2.x, p2.y);
> -
>                d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
> -
>                d2d_rect_union(bounds, &bezier_bounds);
> -
>                p = p2;
> -
>                break;
> -
>            default:
>                FIXME("Unhandled vertex type %#x.\n", type);
>                p = figure->vertices[j];
>
> @@ -3230,9 +3513,20 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
>              type = figure->vertex_types[j];
>          }
> -
>    if (type == D2D_VERTEX_TYPE_BEZIER)
> -
>    if (d2d_vertex_type_is_unsplit_bezier(type))
>    {
> -
>        p1 = figure->original_bezier_controls[bezier_idx++];
> -
>        if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
> -
>        {
> -
>            d2d_bezier_cubic_to_quad(&figure->vertices[j - 1],
> -
>                &figure->original_bezier_controls[bezier_idx],
> -
>                &figure->original_bezier_controls[bezier_idx + 1],
> -
>                &figure->vertices[0], &p1);
> -
> -
>            bezier_idx += 2;
> -
>        }
> -
>        else
> -
>            p1 = figure->original_bezier_controls[bezier_idx++];
> -

We skipped all the split types above, so if "type" is a Bézier type,
it's not split. You could also consider simply handling
D2D_VERTEX_TYPE_QUADRATIC_BEZIER and D2D_VERTEX_TYPE_CUBIC_BEZIER
individually, as you do inside the preceding loop, and in
d2d_path_geometry_Simplify() below.