[PATCH 00/12] [RFC] d2d1: Implement cubic bezier filling.

[Connor McAdams]

This patch series implements cubic bezier filling. Looking for feedback
on any obvious issues/tests that should be created.

Connor McAdams (12):
  d2d1: Store cubic bezier control points.
  d2d1: Add cubic bezier bounds functions.
  d2d1: Update bezier-bezier intersect functions.
  d2d1: Update bezier-line intersection for cubics.
  d2d1: Update apply_intersections for cubic beziers.
  d2d1: Update path geometry Simplify for cubic beziers.
  d2d1: Add functions for cubic bezier triangulation.
  d2d1: Add function for getting figure orientation.
  d2d1: Add cubic bezier fill side detection.
  d2d1: Update bezier overlap checking for cubics.
  d2d1: Add cubic bezier texture coordinate functions.
  d2d1: Render cubic beziers.

 dlls/d2d1/d2d1_private.h |    2 +-
 dlls/d2d1/device.c       |  350 ++++-----
 dlls/d2d1/geometry.c     | 1467 +++++++++++++++++++++++++++++++++-----
 3 files changed, 1458 insertions(+), 361 deletions(-)

-- 
2.20.1

[PATCH 01/12] d2d1: Store cubic bezier control points.

[Connor McAdams]

Store cubic bezier control points alongside quadratic control points.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 102 +++++++++++++++++++++++++++++--------------
 1 file changed, 70 insertions(+), 32 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index e7bb809359..a8e6a3f2b7 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -59,6 +59,12 @@ struct d2d_segment_idx
     size_t control_idx;
 };
 
+struct d2d_bezier_controls
+{
+    D2D1_POINT_2F c0, c1;
+    D2D1_POINT_2F cq0;
+};
+
 struct d2d_figure
 {
     D2D1_POINT_2F *vertices;
@@ -67,11 +73,11 @@ struct d2d_figure
     size_t vertex_types_size;
     size_t vertex_count;
 
-    D2D1_POINT_2F *bezier_controls;
+    struct d2d_bezier_controls *bezier_controls;
     size_t bezier_controls_size;
     size_t bezier_control_count;
 
-    D2D1_POINT_2F *original_bezier_controls;
+    struct d2d_bezier_controls *original_bezier_controls;
     size_t original_bezier_control_count;
 
     D2D1_RECT_F bounds;
@@ -409,6 +415,15 @@ static void d2d_point_normalise(D2D1_POINT_2F *p)
         d2d_point_scale(p, 1.0f / l);
 }
 
+static void d2d_bezier_quad_to_cubic(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1,
+        const D2D1_POINT_2F *p2, D2D1_POINT_2F *c0, D2D1_POINT_2F *c1)
+{
+    c0->x = p0->x * (1.0f / 3.0f) + (2.0f / 3.0f) * p1->x;
+    c0->y = p0->y * (1.0f / 3.0f) + (2.0f / 3.0f) * p1->y;
+    c1->x = p2->x * (1.0f / 3.0f) + (2.0f / 3.0f) * p1->x;
+    c1->y = p2->y * (1.0f / 3.0f) + (2.0f / 3.0f) * p1->y;
+}
+
 /* This implementation is based on the paper "Adaptive Precision
  * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
  * associated (Public Domain) code by Jonathan Richard Shewchuk. */
@@ -613,7 +628,8 @@ static BOOL d2d_figure_add_vertex(struct d2d_figure *figure, D2D1_POINT_2F verte
     return TRUE;
 }
 
-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_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *c0,
+        const D2D1_POINT_2F *c1, const D2D1_POINT_2F *cq0)
 {
     if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size,
             figure->bezier_control_count + 1, sizeof(*figure->bezier_controls)))
@@ -624,13 +640,16 @@ static BOOL d2d_figure_insert_bezier_control(struct d2d_figure *figure, size_t i
 
     memmove(&figure->bezier_controls[idx + 1], &figure->bezier_controls[idx],
             (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls));
-    figure->bezier_controls[idx] = *p;
+    figure->bezier_controls[idx].cq0 = *cq0;
+    figure->bezier_controls[idx].c0 = *c0;
+    figure->bezier_controls[idx].c1 = *c1;
     ++figure->bezier_control_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_control(struct d2d_figure *figure, const D2D1_POINT_2F *c0, const D2D1_POINT_2F *c1,
+        const D2D1_POINT_2F *cq0)
 {
     if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size,
             figure->bezier_control_count + 1, sizeof(*figure->bezier_controls)))
@@ -639,7 +658,9 @@ static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_
         return FALSE;
     }
 
-    figure->bezier_controls[figure->bezier_control_count++] = *p;
+    figure->bezier_controls[figure->bezier_control_count].cq0 = *cq0;
+    figure->bezier_controls[figure->bezier_control_count].c0 = *c0;
+    figure->bezier_controls[figure->bezier_control_count++].c1 = *c1;
 
     return TRUE;
 }
@@ -1727,7 +1748,7 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
 
     figure = &geometry->u.path.figures[idx_p->figure_idx];
     p[0] = &figure->vertices[idx_p->vertex_idx];
-    p[1] = &figure->bezier_controls[idx_p->control_idx];
+    p[1] = &figure->bezier_controls[idx_p->control_idx].cq0;
     next = idx_p->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
@@ -1805,7 +1826,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
 
     figure = &geometry->u.path.figures[idx_p->figure_idx];
     p[0] = &figure->vertices[idx_p->vertex_idx];
-    p[1] = &figure->bezier_controls[idx_p->control_idx];
+    p[1] = &figure->bezier_controls[idx_p->control_idx].cq0;
     next = idx_p->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
@@ -1813,7 +1834,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
 
     figure = &geometry->u.path.figures[idx_q->figure_idx];
     q[0] = &figure->vertices[idx_q->vertex_idx];
-    q[1] = &figure->bezier_controls[idx_q->control_idx];
+    q[1] = &figure->bezier_controls[idx_q->control_idx].cq0;
     next = idx_q->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
@@ -1864,7 +1885,7 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry,
     enum d2d_vertex_type vertex_type;
     const D2D1_POINT_2F *p[3];
     struct d2d_figure *figure;
-    D2D1_POINT_2F q[2];
+    D2D1_POINT_2F q[2], c[2];
     float t, t_prev;
 
     for (i = 0; i < intersections->intersection_count; ++i)
@@ -1898,7 +1919,7 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry,
         }
 
         p[0] = &figure->vertices[inter->vertex_idx + vertex_offset];
-        p[1] = &figure->bezier_controls[inter->control_idx + control_offset];
+        p[1] = &figure->bezier_controls[inter->control_idx + control_offset].cq0;
         next = inter->vertex_idx + vertex_offset + 1;
         if (next == figure->vertex_count)
             next = 0;
@@ -1907,8 +1928,13 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry,
         d2d_point_lerp(&q[0], p[0], p[1], t);
         d2d_point_lerp(&q[1], p[1], p[2], t);
 
-        figure->bezier_controls[inter->control_idx + control_offset] = q[0];
-        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1])))
+        d2d_bezier_quad_to_cubic(p[0], &q[0], &inter->p, &c[0], &c[1]);
+        figure->bezier_controls[inter->control_idx + control_offset].cq0 = q[0];
+        figure->bezier_controls[inter->control_idx + control_offset].c0 = c[0];
+        figure->bezier_controls[inter->control_idx + control_offset].c1 = c[1];
+
+        d2d_bezier_quad_to_cubic(&inter->p, &q[1], p[2], &c[0], &c[1]);
+        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &c[0], &c[1], &q[1])))
             return FALSE;
         ++control_offset;
 
@@ -2285,7 +2311,7 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry,
         {
             prev_type = figure->vertex_types[figure->vertex_count - 1];
             if (prev_type == D2D_VERTEX_TYPE_BEZIER)
-                prev = &figure->bezier_controls[figure->bezier_control_count - 1];
+                prev = &figure->bezier_controls[figure->bezier_control_count - 1].cq0;
             else
                 prev = &figure->vertices[figure->vertex_count - 1];
         }
@@ -2293,13 +2319,13 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry,
         {
             prev_type = figure->vertex_types[i - 1];
             if (prev_type == D2D_VERTEX_TYPE_BEZIER)
-                prev = &figure->bezier_controls[bezier_idx - 1];
+                prev = &figure->bezier_controls[bezier_idx - 1].cq0;
             else
                 prev = &figure->vertices[i - 1];
         }
 
         if (type == D2D_VERTEX_TYPE_BEZIER)
-            next = &figure->bezier_controls[bezier_idx++];
+            next = &figure->bezier_controls[bezier_idx++].cq0;
         else if (i == figure->vertex_count - 1)
             next = &figure->vertices[0];
         else
@@ -2541,7 +2567,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if
         d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
                 &p, &beziers[i].point3);
 
-        if (!d2d_figure_add_bezier_control(figure, &p))
+        if (!d2d_figure_add_bezier_control(figure, &beziers[i].point1, &beziers[i].point2, &p))
         {
             ERR("Failed to add bezier control.\n");
             geometry->u.path.state = D2D_GEOMETRY_STATE_ERROR;
@@ -2661,7 +2687,7 @@ static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
 
     figure = &geometry->u.path.figures[idx_p->figure_idx];
     a[0] = &figure->vertices[idx_p->vertex_idx];
-    a[1] = &figure->bezier_controls[idx_p->control_idx];
+    a[1] = &figure->bezier_controls[idx_p->control_idx].cq0;
     if (idx_p->vertex_idx == figure->vertex_count - 1)
         a[2] = &figure->vertices[0];
     else
@@ -2669,7 +2695,7 @@ static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
 
     figure = &geometry->u.path.figures[idx_q->figure_idx];
     b[0] = &figure->vertices[idx_q->vertex_idx];
-    b[1] = &figure->bezier_controls[idx_q->control_idx];
+    b[1] = &figure->bezier_controls[idx_q->control_idx].cq0;
     if (idx_q->vertex_idx == figure->vertex_count - 1)
         b[2] = &figure->vertices[0];
     else
@@ -2747,19 +2773,19 @@ static float d2d_geometry_bezier_ccw(struct d2d_geometry *geometry, const struct
         next = 0;
 
     return d2d_point_ccw(&figure->vertices[idx->vertex_idx],
-            &figure->bezier_controls[idx->control_idx], &figure->vertices[next]);
+            &figure->bezier_controls[idx->control_idx].cq0, &figure->vertices[next]);
 }
 
 static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx)
 {
     const D2D1_POINT_2F *p[3];
     struct d2d_figure *figure;
-    D2D1_POINT_2F q[3];
+    D2D1_POINT_2F q[3], c[2];
     size_t next;
 
     figure = &geometry->u.path.figures[idx->figure_idx];
     p[0] = &figure->vertices[idx->vertex_idx];
-    p[1] = &figure->bezier_controls[idx->control_idx];
+    p[1] = &figure->bezier_controls[idx->control_idx].cq0;
     next = idx->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
@@ -2769,8 +2795,15 @@ static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struc
     d2d_point_lerp(&q[1], p[1], p[2], 0.5f);
     d2d_point_lerp(&q[2], &q[0], &q[1], 0.5f);
 
-    figure->bezier_controls[idx->control_idx] = q[0];
-    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &q[1])))
+    d2d_bezier_quad_to_cubic(p[0], &q[0], &q[2], &c[0], &c[1]);
+
+    figure->bezier_controls[idx->control_idx].cq0 = q[0];
+    figure->bezier_controls[idx->control_idx].c0 = c[0];
+    figure->bezier_controls[idx->control_idx].c1 = c[1];
+
+    d2d_bezier_quad_to_cubic(&q[0], &q[1], p[2], &c[0], &c[1]);
+
+    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &c[0], &c[1], &q[1])))
         return FALSE;
     if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2])))
         return FALSE;
@@ -2841,7 +2874,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
 
         figure = &geometry->u.path.figures[idx_p.figure_idx];
         p[0] = &figure->vertices[idx_p.vertex_idx];
-        p[1] = &figure->bezier_controls[idx_p.control_idx];
+        p[1] = &figure->bezier_controls[idx_p.control_idx].cq0;
 
         i = idx_p.vertex_idx + 1;
         if (d2d_path_geometry_point_inside(geometry, p[1], FALSE))
@@ -2940,6 +2973,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr
 {
     struct d2d_geometry *geometry = impl_from_ID2D1GeometrySink(iface);
     struct d2d_figure *figure = &geometry->u.path.figures[geometry->u.path.figure_count - 1];
+    D2D1_POINT_2F p0, p1, p2, c[2];
     unsigned int i;
 
     TRACE("iface %p, beziers %p, bezier_count %u.\n", iface, beziers, bezier_count);
@@ -2954,11 +2988,15 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr
     {
         D2D1_RECT_F bezier_bounds;
 
-        d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
-                &beziers[i].point1, &beziers[i].point2);
+        p0 = figure->vertices[figure->vertex_count - 1];
+        p1 = beziers[i].point1;
+        p2 = beziers[i].point2;
+        d2d_bezier_quad_to_cubic(&p0, &p1, &p2, &c[0], &c[1]);
+
+        d2d_rect_get_bezier_bounds(&bezier_bounds, &p0, &p1, &p2);
 
         figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER;
-        if (!d2d_figure_add_bezier_control(figure, &beziers[i].point1))
+        if (!d2d_figure_add_bezier_control(figure, &c[0], &c[1], &p1))
         {
             ERR("Failed to add bezier.\n");
             geometry->u.path.state = D2D_GEOMETRY_STATE_ERROR;
@@ -3165,7 +3203,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
                     break;
 
                 case D2D_VERTEX_TYPE_BEZIER:
-                    p1 = figure->original_bezier_controls[bezier_idx++];
+                    p1 = figure->original_bezier_controls[bezier_idx++].cq0;
                     d2d_point_transform(&p1, transform, p1.x, p1.y);
                     p2 = figure->vertices[j];
                     d2d_point_transform(&p2, transform, p2.x, p2.y);
@@ -3187,7 +3225,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
 
         if (type == D2D_VERTEX_TYPE_BEZIER)
         {
-            p1 = figure->original_bezier_controls[bezier_idx++];
+            p1 = figure->original_bezier_controls[bezier_idx++].cq0;
             d2d_point_transform(&p1, transform, p1.x, p1.y);
             p2 = figure->vertices[0];
             d2d_point_transform(&p2, transform, p2.x, p2.y);
@@ -3369,7 +3407,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i
                     break;
 
                 case D2D_VERTEX_TYPE_BEZIER:
-                    p1 = figure->original_bezier_controls[bezier_idx++];
+                    p1 = figure->original_bezier_controls[bezier_idx++].cq0;
                     if (transform)
                         d2d_point_transform(&p1, transform, p1.x, p1.y);
                     p2 = figure->vertices[j];
@@ -3393,7 +3431,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i
 
         if (type == D2D_VERTEX_TYPE_BEZIER)
         {
-            p1 = figure->original_bezier_controls[bezier_idx++];
+            p1 = figure->original_bezier_controls[bezier_idx++].cq0;
             if (transform)
                 d2d_point_transform(&p1, transform, p1.x, p1.y);
             p2 = figure->vertices[0];
-- 
2.20.1

[PATCH 01/12] d2d1: Store cubic bezier control points.

[Marvin]

Hi,

While running your changed tests, I think I found new failures.
Being a bot and all I'm not very good at pattern recognition, so I might be
wrong, but could you please double-check?

Full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=65738

Your paranoid android.


=== debian10 (32 bit Chinese:China report) ===

Report validation errors:
d2d1:d2d1 is missing some skip messages

[PATCH 01/12] d2d1: Store cubic bezier control points.

[Henri Verbeet]

Hi Connor,

It will probably take me a while to go through the entire series, but
here are some comments/questions on the first two patches.

On Tue, 25 Feb 2020 at 06:03, Connor McAdams <conmanx360(a)gmail.com> wrote:
> +struct d2d_bezier_controls
> +{
> +    D2D1_POINT_2F c0, c1;
> +    D2D1_POINT_2F cq0;
> +};
> +
> Why do you need this structure? It seems more convenient to rename
> D2D_VERTEX_TYPE_BEZIER to D2D_VERTEX_TYPE_QUADRATIC_BEZIER, and
> introduce D2D_VERTEX_TYPE_CUBIC_BEZIER, while keeping the control
> point arrays the way they are. Not in the least because
> d2d_path_geometry_Stream() will need to know the original segment
> types.
> @@ -1907,8 +1928,13 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry,
>          d2d_point_lerp(&q[0], p[0], p[1], t);
>          d2d_point_lerp(&q[1], p[1], p[2], t);
>
> -        figure->bezier_controls[inter->control_idx + control_offset] = q[0];
> -        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1])))
> +        d2d_bezier_quad_to_cubic(p[0], &q[0], &inter->p, &c[0], &c[1]);
> +        figure->bezier_controls[inter->control_idx + control_offset].cq0 = q[0];
> +        figure->bezier_controls[inter->control_idx + control_offset].c0 = c[0];
> +        figure->bezier_controls[inter->control_idx + control_offset].c1 = c[1];
> +
> +        d2d_bezier_quad_to_cubic(&inter->p, &q[1], p[2], &c[0], &c[1]);
> +        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &c[0], &c[1], &q[1])))
>              return FALSE;
>          ++control_offset;

...
> @@ -2769,8 +2795,15 @@ static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struc
>      d2d_point_lerp(&q[1], p[1], p[2], 0.5f);
>      d2d_point_lerp(&q[2], &q[0], &q[1], 0.5f);
>
> -    figure->bezier_controls[idx->control_idx] = q[0];
> -    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &q[1])))
> +    d2d_bezier_quad_to_cubic(p[0], &q[0], &q[2], &c[0], &c[1]);
> +
> +    figure->bezier_controls[idx->control_idx].cq0 = q[0];
> +    figure->bezier_controls[idx->control_idx].c0 = c[0];
> +    figure->bezier_controls[idx->control_idx].c1 = c[1];
> +
> +    d2d_bezier_quad_to_cubic(&q[0], &q[1], p[2], &c[0], &c[1]);
> +
> +    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &c[0], &c[1], &q[1])))
>          return FALSE;
>      if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2])))
>          return FALSE;
> Likewise, you wouldn't need these awkward bits of code.

[PATCH 01/12] d2d1: Store cubic bezier control points.

[Connor McAdams]

Ah, okay. That makes sense. In my original patch, I had just stored
everything as a cubic in the same way everything was previously stored
as a quadratic.

If both are to co-exist, should the functions for detecting
intersections between beziers all be cubic, or should they be
temporarily promoted to a cubic in that instance? Same goes with
bezier-line intersections. One of the nice things about storing them
all with both cubic and quadratic coordinates was that it meant that
things that used one or the other could do so interchangeably, but I
guess it can be done that way too with them as separate types with a
little more work.

Also, when they're eventually sent to the pixel shader, would you like
there to be separate paths for cubics and quadratics? Or can I promote
a quadratic to a cubic in that case? It kind of gets a little messy
supporting both, but if that's what's best, I can do that.

On Tue, Feb 25, 2020 at 9:45 AM Henri Verbeet <hverbeet(a)gmail.com> wrote:
> Hi Connor,
>
> It will probably take me a while to go through the entire series, but
> here are some comments/questions on the first two patches.
>
> On Tue, 25 Feb 2020 at 06:03, Connor McAdams <conmanx360(a)gmail.com> wrote:
> > +struct d2d_bezier_controls
> > +{
> > +    D2D1_POINT_2F c0, c1;
> > +    D2D1_POINT_2F cq0;
> > +};
> > +
> > Why do you need this structure? It seems more convenient to rename
> > D2D_VERTEX_TYPE_BEZIER to D2D_VERTEX_TYPE_QUADRATIC_BEZIER, and
> > introduce D2D_VERTEX_TYPE_CUBIC_BEZIER, while keeping the control
> > point arrays the way they are. Not in the least because
> > d2d_path_geometry_Stream() will need to know the original segment
> > types.
> > @@ -1907,8 +1928,13 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry,
> >          d2d_point_lerp(&q[0], p[0], p[1], t);
> >          d2d_point_lerp(&q[1], p[1], p[2], t);
> >
> > -        figure->bezier_controls[inter->control_idx + control_offset] = q[0];
> > -        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1])))
> > +        d2d_bezier_quad_to_cubic(p[0], &q[0], &inter->p, &c[0], &c[1]);
> > +        figure->bezier_controls[inter->control_idx + control_offset].cq0 = q[0];
> > +        figure->bezier_controls[inter->control_idx + control_offset].c0 = c[0];
> > +        figure->bezier_controls[inter->control_idx + control_offset].c1 = c[1];
> > +
> > +        d2d_bezier_quad_to_cubic(&inter->p, &q[1], p[2], &c[0], &c[1]);
> > +        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &c[0], &c[1], &q[1])))
> >              return FALSE;
> >          ++control_offset;
>
> ...
> > @@ -2769,8 +2795,15 @@ static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struc
> >      d2d_point_lerp(&q[1], p[1], p[2], 0.5f);
> >      d2d_point_lerp(&q[2], &q[0], &q[1], 0.5f);
> >
> > -    figure->bezier_controls[idx->control_idx] = q[0];
> > -    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &q[1])))
> > +    d2d_bezier_quad_to_cubic(p[0], &q[0], &q[2], &c[0], &c[1]);
> > +
> > +    figure->bezier_controls[idx->control_idx].cq0 = q[0];
> > +    figure->bezier_controls[idx->control_idx].c0 = c[0];
> > +    figure->bezier_controls[idx->control_idx].c1 = c[1];
> > +
> > +    d2d_bezier_quad_to_cubic(&q[0], &q[1], p[2], &c[0], &c[1]);
> > +
> > +    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &c[0], &c[1], &q[1])))
> >          return FALSE;
> >      if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2])))
> >          return FALSE;
> > Likewise, you wouldn't need these awkward bits of code.

[PATCH 01/12] d2d1: Store cubic bezier control points.

[Henri Verbeet]

On Tue, 25 Feb 2020 at 22:46, Connor McAdams <conmanx360(a)gmail.com> wrote:
> Also, when they're eventually sent to the pixel shader, would you like
> there to be separate paths for cubics and quadratics? Or can I promote
> a quadratic to a cubic in that case? It kind of gets a little messy
> supporting both, but if that's what's best, I can do that.

I think it shouldn't be too hard to handle them individually, but
there's no fundamental reason you couldn't promote quadratics to
cubics at that point, no.

[PATCH 02/12] d2d1: Add cubic bezier bounds functions.

[Connor McAdams]

Add functions for calculating the bounds of a cubic bezier.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 185 +++++++++++++++++++++++++++++++++++--------
 1 file changed, 152 insertions(+), 33 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index a8e6a3f2b7..4ec0f16d07 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -399,12 +399,14 @@ static void d2d_point_lerp(D2D1_POINT_2F *out,
 }
 
 static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
-        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float t)
+        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t)
 {
     float t_c = 1.0f - t;
+    float t_c_cube = t_c * t_c * t_c, t_cube = t * t * t;
+    float t_c_sq = t_c * t_c, t_sq = t * t;
 
-    out->x = t_c * (t_c * p0->x + t * p1->x) + t * (t_c * p1->x + t * p2->x);
-    out->y = t_c * (t_c * p0->y + t * p1->y) + t * (t_c * p1->y + t * p2->y);
+    out->x = t_c_cube * p0->x + 3.0f * t_c_sq * t * p1->x + 3.0f * t_c * t_sq * p2->x + t_cube * p3->x;
+    out->y = t_c_cube * p0->y + 3.0f * t_c_sq * t * p1->y + 3.0f * t_c * t_sq * p2->y + t_cube * p3->y;
 }
 
 static void d2d_point_normalise(D2D1_POINT_2F *p)
@@ -424,6 +426,28 @@ static void d2d_bezier_quad_to_cubic(const D2D1_POINT_2F *p0, const D2D1_POINT_2
     c1->y = p2->y * (1.0f / 3.0f) + (2.0f / 3.0f) * p1->y;
 }
 
+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;
+}
+
+/*
+ * This value is useful for many different cubic bezier operations, including
+ * root finding, derivative checking, and texture coordinate calculations.
+ */
+#define D2D1_CUBIC_BEZIER_EPSILON 0.00005f
+static float d2d_cubic_bezier_round_to_zero(float a)
+{
+    if (a < 0.00005f && a > -0.00005f)
+        return 0.0f;
+
+    return a;
+}
+
 /* This implementation is based on the paper "Adaptive Precision
  * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
  * associated (Public Domain) code by Jonathan Richard Shewchuk. */
@@ -521,44 +545,131 @@ static BOOL d2d_rect_check_overlap(const D2D_RECT_F *p, const D2D_RECT_F *q)
     return p->left < q->right && p->top < q->bottom && p->right > q->left && p->bottom > q->top;
 }
 
-static void d2d_rect_get_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
-        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2)
+static void d2d_rect_get_quad_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;
+    D2D1_POINT_2F p, c;
     float root;
 
-    bounds->left = p0->x;
-    bounds->top = p0->y;
-    bounds->right = p0->x;
-    bounds->bottom = p0->y;
-
-    d2d_rect_expand(bounds, p2);
+    d2d_bezier_cubic_to_quad(p0, p1, p2, p3, &c);
 
     /* f(t) = (1 - t)²P₀ + 2(1 - t)tP₁ + t²P₂
      * f'(t) = 2(1 - t)(P₁ - P₀) + 2t(P₂ - P₁)
      *       = 2(P₂ - 2P₁ + P₀)t + 2(P₁ - P₀)
      *
      * f'(t) = 0
-     * t = (P₀ - P₁) / (P₂ - 2P₁ + P₀) */
-    root = (p0->x - p1->x) / (p2->x - 2.0f * p1->x + p0->x);
+     * t = (P₀ - P₁) / (P₂ - 2P₁ + P₀)
+     */
+    root = (p0->x - c.x) / (p3->x - 2.0f * c.x + p0->x);
     if (root > 0.0f && root < 1.0f)
     {
-        d2d_point_calculate_bezier(&p, p0, p1, p2, root);
+        d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root);
         d2d_rect_expand(bounds, &p);
     }
 
-    root = (p0->y - p1->y) / (p2->y - 2.0f * p1->y + p0->y);
+    root = (p0->y - c.y) / (p3->y - 2.0f * c.y + p0->y);
     if (root > 0.0f && root < 1.0f)
     {
-        d2d_point_calculate_bezier(&p, p0, p1, p2, root);
+        d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root);
         d2d_rect_expand(bounds, &p);
     }
 }
 
+static void d2d_rect_get_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;
+
+    bounds->left = p0->x;
+    bounds->top = p0->y;
+    bounds->right = p0->x;
+    bounds->bottom = p0->y;
+
+    d2d_rect_expand(bounds, p3);
+
+    /*
+     * 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
+     */
+    v1.x = 3.0f * (p1->x - p0->x);
+    v1.y = 3.0f * (p1->y - p0->y);
+
+    v2.x = 3.0f * (p2->x - p1->x);
+    v2.y = 3.0f * (p2->y - p1->y);
+
+    v3.x = 3.0f * (p3->x - p2->x);
+    v3.y = 3.0f * (p3->y - p2->y);
+
+    /* This will check if the cubic bezier is actually a quadratic, in which
+     * case we need the second derivative to get the extremities. */
+    a.x = v1.x - 2.0f * v2.x + v3.x;
+    a.y = v1.y - 2.0f * v2.y + v3.y;
+    if ((d2d_cubic_bezier_round_to_zero(a.x) == 0.0f) && (d2d_cubic_bezier_round_to_zero(a.y) == 0.0f))
+    {
+        d2d_rect_get_quad_bezier_bounds(bounds, p0, p1, p2, p3);
+        return;
+    }
+    b.x = 2.0f * (v2.x - v1.x);
+    b.y = 2.0f * (v2.y - v1.y);
+    c.x = v1.x;
+    c.y = v1.y;
+
+    /* 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_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_bezier(&p, p0, p1, p2, p3, root);
+            d2d_rect_expand(bounds, &p);
+        }
+    }
+
+    if ((sq_root = sqrtf(b.y * b.y - 4.0f * a.y * c.y)) >= 0.0f)
+    {
+        root = (-b.y + sq_root) / (2.0f * a.y);
+        if (root < 1.0f && root > 0.0f)
+        {
+            d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root);
+            d2d_rect_expand(bounds, &p);
+        }
+
+        root = (-b.y - sq_root) / (2.0f * a.y);
+        if (root < 1.0f && root > 0.0f)
+        {
+            d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root);
+            d2d_rect_expand(bounds, &p);
+        }
+    }
+}
+
 static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
         const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float start, float end)
 {
-    D2D1_POINT_2F q[3], r[2];
+    D2D1_POINT_2F q[3], r[2], c[2];
 
     d2d_point_lerp(&r[0], p0, p1, start);
     d2d_point_lerp(&r[1], p1, p2, start);
@@ -569,7 +680,8 @@ static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_PO
     d2d_point_lerp(&r[0], &r[1], p2, end);
     d2d_point_lerp(&q[2], &q[1], &r[0], end);
 
-    d2d_rect_get_bezier_bounds(bounds, &q[0], &q[1], &q[2]);
+    d2d_bezier_quad_to_cubic(&q[0], &q[1], &q[2], &c[0], &c[1]);
+    d2d_rect_get_bezier_bounds(bounds, &q[0], &c[0], &c[1], &q[2]);
 }
 
 static BOOL d2d_figure_insert_vertex(struct d2d_figure *figure, size_t idx, D2D1_POINT_2F vertex)
@@ -1715,10 +1827,12 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
         struct d2d_geometry_intersections *intersections, const struct d2d_segment_idx *idx_p,
         const D2D1_POINT_2F **p, const struct d2d_segment_idx *idx_q, const D2D1_POINT_2F **q, float s)
 {
-    D2D1_POINT_2F intersection;
+    D2D1_POINT_2F intersection, c[2];
     float t;
 
-    d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], s);
+
+    d2d_bezier_quad_to_cubic(p[0], p[1], p[2], &c[0], &c[1]);
+    d2d_point_calculate_bezier(&intersection, p[0], &c[0], &c[1], p[2], s);
     if (fabsf(q[1]->x - q[0]->x) > fabsf(q[1]->y - q[0]->y))
         t = (intersection.x - q[0]->x) / (q[1]->x - q[0]->x);
     else
@@ -1820,7 +1934,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
     const D2D1_POINT_2F *p[3], *q[3];
     const struct d2d_figure *figure;
     D2D_RECT_F p_bounds, q_bounds;
-    D2D1_POINT_2F intersection;
+    D2D1_POINT_2F intersection, c[2];
     float centre_p, centre_q;
     size_t next;
 
@@ -1851,7 +1965,8 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
 
     if (end_p - start_p < 1e-3f)
     {
-        d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], centre_p);
+        d2d_bezier_quad_to_cubic(p[0], p[1], p[2], &c[0], &c[1]);
+        d2d_point_calculate_bezier(&intersection, p[0], &c[0], &c[1], p[2], centre_p);
         if (start_p > 0.0f && end_p < 1.0f && !d2d_geometry_intersections_add(intersections,
                 idx_p, centre_p, intersection))
             return FALSE;
@@ -2565,7 +2680,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if
         figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER;
 
         d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
-                &p, &beziers[i].point3);
+                &beziers[i].point1, &beziers[i].point2, &beziers[i].point3);
 
         if (!d2d_figure_add_bezier_control(figure, &beziers[i].point1, &beziers[i].point2, &p))
         {
@@ -2993,7 +3108,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr
         p2 = beziers[i].point2;
         d2d_bezier_quad_to_cubic(&p0, &p1, &p2, &c[0], &c[1]);
 
-        d2d_rect_get_bezier_bounds(&bezier_bounds, &p0, &p1, &p2);
+        d2d_rect_get_bezier_bounds(&bezier_bounds, &p0, &c[0], &c[1], &p2);
 
         figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER;
         if (!d2d_figure_add_bezier_control(figure, &c[0], &c[1], &p1))
@@ -3162,7 +3277,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
         const struct d2d_figure *figure = &geometry->u.path.figures[i];
         enum d2d_vertex_type type = D2D_VERTEX_TYPE_NONE;
         D2D1_RECT_F bezier_bounds;
-        D2D1_POINT_2F p, p1, p2;
+        D2D1_POINT_2F p, p1, p2, p3;
         size_t j, bezier_idx;
 
         if (figure->flags & D2D_FIGURE_FLAG_HOLLOW)
@@ -3203,13 +3318,15 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
                     break;
 
                 case D2D_VERTEX_TYPE_BEZIER:
-                    p1 = figure->original_bezier_controls[bezier_idx++].cq0;
+                    p1 = figure->original_bezier_controls[bezier_idx].c0;
                     d2d_point_transform(&p1, transform, p1.x, p1.y);
-                    p2 = figure->vertices[j];
+                    p2 = figure->original_bezier_controls[bezier_idx++].c1;
                     d2d_point_transform(&p2, transform, p2.x, p2.y);
-                    d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
+                    p3 = figure->vertices[j];
+                    d2d_point_transform(&p3, transform, p3.x, p3.y);
+                    d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3);
                     d2d_rect_union(bounds, &bezier_bounds);
-                    p = p2;
+                    p = p3;
                     break;
 
                 default:
@@ -3225,11 +3342,13 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
 
         if (type == D2D_VERTEX_TYPE_BEZIER)
         {
-            p1 = figure->original_bezier_controls[bezier_idx++].cq0;
+            p1 = figure->original_bezier_controls[bezier_idx].c0;
             d2d_point_transform(&p1, transform, p1.x, p1.y);
-            p2 = figure->vertices[0];
+            p2 = figure->original_bezier_controls[bezier_idx++].c1;
             d2d_point_transform(&p2, transform, p2.x, p2.y);
-            d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
+            p3 = figure->vertices[0];
+            d2d_point_transform(&p3, transform, p3.x, p3.y);
+            d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3);
             d2d_rect_union(bounds, &bezier_bounds);
         }
     }
-- 
2.20.1

[PATCH 02/12] d2d1: Add cubic bezier bounds functions.

[Henri Verbeet]

On Tue, 25 Feb 2020 at 06:03, Connor McAdams <conmanx360(a)gmail.com> wrote:
> static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
> -        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float t)
> +        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t)
>  {
>      float t_c = 1.0f - t;
> +    float t_c_cube = t_c * t_c * t_c, t_cube = t * t * t;
> +    float t_c_sq = t_c * t_c, t_sq = t * t;
>
> -    out->x = t_c * (t_c * p0->x + t * p1->x) + t * (t_c * p1->x + t * p2->x);
> -    out->y = t_c * (t_c * p0->y + t * p1->y) + t * (t_c * p1->y + t * p2->y);
> +    out->x = t_c_cube * p0->x + 3.0f * t_c_sq * t * p1->x + 3.0f * t_c * t_sq * p2->x + t_cube * p3->x;
> +    out->y = t_c_cube * p0->y + 3.0f * t_c_sq * t * p1->y + 3.0f * t_c * t_sq * p2->y + t_cube * p3->y;
>  }
> Careful with that. Consider the relative size of the error in "t_c =
> 1.0f - t" for values of t close to 1.0f. However bad that error may
> be, "t_c_cube = t_c * t_c * t_c" raises it to the third power.
> +/*
> + * This value is useful for many different cubic bezier operations, including
> + * root finding, derivative checking, and texture coordinate calculations.
> + */
> +#define D2D1_CUBIC_BEZIER_EPSILON 0.00005f
> +static float d2d_cubic_bezier_round_to_zero(float a)
> +{
> +    if (a < 0.00005f && a > -0.00005f)
> +        return 0.0f;
> +
> +    return a;
> +}
> This looks fairly arbitrary; what makes it worse is defining the
> constant and then not using it.

[PATCH 02/12] d2d1: Add cubic bezier bounds functions.

[Connor McAdams]

Is there anything that can be done in the case of t_c_cube to lower
the possibility of that happening?

I didn't even notice that I wasn't using the constant in that function
specifically, that value gets used in a later patch. Good catch. I'll
fix that. Is it a good idea to have a macro constant for values like
that, or is it better to just make them literals?

On Tue, Feb 25, 2020 at 9:45 AM Henri Verbeet <hverbeet(a)gmail.com> wrote:
> On Tue, 25 Feb 2020 at 06:03, Connor McAdams <conmanx360(a)gmail.com> wrote:
> > static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
> > -        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float t)
> > +        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t)
> >  {
> >      float t_c = 1.0f - t;
> > +    float t_c_cube = t_c * t_c * t_c, t_cube = t * t * t;
> > +    float t_c_sq = t_c * t_c, t_sq = t * t;
> >
> > -    out->x = t_c * (t_c * p0->x + t * p1->x) + t * (t_c * p1->x + t * p2->x);
> > -    out->y = t_c * (t_c * p0->y + t * p1->y) + t * (t_c * p1->y + t * p2->y);
> > +    out->x = t_c_cube * p0->x + 3.0f * t_c_sq * t * p1->x + 3.0f * t_c * t_sq * p2->x + t_cube * p3->x;
> > +    out->y = t_c_cube * p0->y + 3.0f * t_c_sq * t * p1->y + 3.0f * t_c * t_sq * p2->y + t_cube * p3->y;
> >  }
> > Careful with that. Consider the relative size of the error in "t_c =
> > 1.0f - t" for values of t close to 1.0f. However bad that error may
> > be, "t_c_cube = t_c * t_c * t_c" raises it to the third power.
> > +/*
> > + * This value is useful for many different cubic bezier operations, including
> > + * root finding, derivative checking, and texture coordinate calculations.
> > + */
> > +#define D2D1_CUBIC_BEZIER_EPSILON 0.00005f
> > +static float d2d_cubic_bezier_round_to_zero(float a)
> > +{
> > +    if (a < 0.00005f && a > -0.00005f)
> > +        return 0.0f;
> > +
> > +    return a;
> > +}
> > This looks fairly arbitrary; what makes it worse is defining the
> > constant and then not using it.

[PATCH 02/12] d2d1: Add cubic bezier bounds functions.

[Henri Verbeet]

On Tue, 25 Feb 2020 at 22:51, Connor McAdams <conmanx360(a)gmail.com> wrote:
> Is there anything that can be done in the case of t_c_cube to lower
> the possibility of that happening?

One of the advantages of using de Casteljau is that it's one of the
more numerically stable ways to evaluate Bézier curves. So that's the
easy option. It may also be possible to do something clever by
rewriting things to eliminate the (1 - t) factors, and using something
along the lines of Kahan summation to add things together. (I'm
clearly doing some handwaving here.) That's probably the harder
option.
> I didn't even notice that I wasn't using the constant in that function
> specifically, that value gets used in a later patch. Good catch. I'll
> fix that. Is it a good idea to have a macro constant for values like
> that, or is it better to just make them literals?

Well, ideally you'd avoid this kind of function or constant entirely,
and either use something based on the tolerance provided through the
API where applicable, or based on the magnitudes of the values you're
working with.

[PATCH 02/12] d2d1: Add cubic bezier bounds functions.

[Connor McAdams]

I'm kind of stuck on the epsilon value thing.

Running the bounds checking function through all possibilities of a
quadratic with points 0-100 (i.e p0 = 0-100, p1 = 0-100, p3 = 0-100),
I've calculated the maximum and minimum values of the coefficient a in
the derivative, with the maximum value being 0.000076 and the minimum
being -0.000076. So even with the epsilon value in this patch, it
looks like it'd fail certain quadratics upped to cubics.

I guess the question is, would rounding to 0 if it is less than 0.0005
and greater than -0.0005 be appropriate? How would I go about
calculating that value? It doesn't seem to be exactly clear cut.

On Wed, Feb 26, 2020 at 1:32 PM Henri Verbeet <hverbeet(a)gmail.com> wrote:
> On Tue, 25 Feb 2020 at 22:51, Connor McAdams <conmanx360(a)gmail.com> wrote:
> > Is there anything that can be done in the case of t_c_cube to lower
> > the possibility of that happening?
>
> One of the advantages of using de Casteljau is that it's one of the
> more numerically stable ways to evaluate Bézier curves. So that's the
> easy option. It may also be possible to do something clever by
> rewriting things to eliminate the (1 - t) factors, and using something
> along the lines of Kahan summation to add things together. (I'm
> clearly doing some handwaving here.) That's probably the harder
> option.
> > I didn't even notice that I wasn't using the constant in that function
> > specifically, that value gets used in a later patch. Good catch. I'll
> > fix that. Is it a good idea to have a macro constant for values like
> > that, or is it better to just make them literals?
>
> Well, ideally you'd avoid this kind of function or constant entirely,
> and either use something based on the tolerance provided through the
> API where applicable, or based on the magnitudes of the values you're
> working with.

[PATCH 03/12] d2d1: Update bezier-bezier intersect functions.

[Connor McAdams]

Update functions for handling bezier-bezier intersection to now handle
cubic bezier curves.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 74 ++++++++++++++++++++++++++++++++------------
 1 file changed, 54 insertions(+), 20 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 4ec0f16d07..8dad84fca3 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -448,6 +448,38 @@ static float d2d_cubic_bezier_round_to_zero(float a)
     return a;
 }
 
+static void d2d_cubic_bezier_split(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;
+    }
+}
+
 /* This implementation is based on the paper "Adaptive Precision
  * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
  * associated (Public Domain) code by Jonathan Richard Shewchuk. */
@@ -667,21 +699,22 @@ static void d2d_rect_get_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *
 }
 
 static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
-        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float start, float end)
+        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3,
+        float start, float end)
 {
-    D2D1_POINT_2F q[3], r[2], c[2];
+    D2D1_BEZIER_SEGMENT left, right;
+    D2D1_POINT_2F mid;
 
-    d2d_point_lerp(&r[0], p0, p1, start);
-    d2d_point_lerp(&r[1], p1, p2, start);
-    d2d_point_lerp(&q[0], &r[0], &r[1], start);
+    /* First part: Create a new cubic bezier with control points on the right
+     * side of the start t-value split. */
+    d2d_cubic_bezier_split(p0, p1, p2, p3, start, NULL, &right, &mid);
 
+    /* Now, create another cubic bezier from the previous one, this time on
+     * the left side of the end value t-split. */
     end = (end - start) / (1.0f - start);
-    d2d_point_lerp(&q[1], &q[0], &r[1], end);
-    d2d_point_lerp(&r[0], &r[1], p2, end);
-    d2d_point_lerp(&q[2], &q[1], &r[0], end);
+    d2d_cubic_bezier_split(&mid, &right.point1, &right.point2, p3, end, &left, NULL, NULL);
 
-    d2d_bezier_quad_to_cubic(&q[0], &q[1], &q[2], &c[0], &c[1]);
-    d2d_rect_get_bezier_bounds(bounds, &q[0], &c[0], &c[1], &q[2]);
+    d2d_rect_get_bezier_bounds(bounds, &mid, &left.point1, &left.point2, &left.point3);
 }
 
 static BOOL d2d_figure_insert_vertex(struct d2d_figure *figure, size_t idx, D2D1_POINT_2F vertex)
@@ -1931,31 +1964,33 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
         const struct d2d_segment_idx *idx_p, float start_p, float end_p,
         const struct d2d_segment_idx *idx_q, float start_q, float end_q)
 {
-    const D2D1_POINT_2F *p[3], *q[3];
+    const D2D1_POINT_2F *p[4], *q[4];
     const struct d2d_figure *figure;
     D2D_RECT_F p_bounds, q_bounds;
-    D2D1_POINT_2F intersection, c[2];
+    D2D1_POINT_2F intersection;
     float centre_p, centre_q;
     size_t next;
 
     figure = &geometry->u.path.figures[idx_p->figure_idx];
     p[0] = &figure->vertices[idx_p->vertex_idx];
-    p[1] = &figure->bezier_controls[idx_p->control_idx].cq0;
+    p[1] = &figure->bezier_controls[idx_p->control_idx].c0;
+    p[2] = &figure->bezier_controls[idx_p->control_idx].c1;
     next = idx_p->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
-    p[2] = &figure->vertices[next];
+    p[3] = &figure->vertices[next];
 
     figure = &geometry->u.path.figures[idx_q->figure_idx];
     q[0] = &figure->vertices[idx_q->vertex_idx];
-    q[1] = &figure->bezier_controls[idx_q->control_idx].cq0;
+    q[1] = &figure->bezier_controls[idx_q->control_idx].c0;
+    q[2] = &figure->bezier_controls[idx_q->control_idx].c1;
     next = idx_q->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
-    q[2] = &figure->vertices[next];
+    q[3] = &figure->vertices[next];
 
-    d2d_rect_get_bezier_segment_bounds(&p_bounds, p[0], p[1], p[2], start_p, end_p);
-    d2d_rect_get_bezier_segment_bounds(&q_bounds, q[0], q[1], q[2], start_q, end_q);
+    d2d_rect_get_bezier_segment_bounds(&p_bounds, p[0], p[1], p[2], p[3], start_p, end_p);
+    d2d_rect_get_bezier_segment_bounds(&q_bounds, q[0], q[1], q[2], q[3], start_q, end_q);
 
     if (!d2d_rect_check_overlap(&p_bounds, &q_bounds))
         return TRUE;
@@ -1965,8 +2000,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
 
     if (end_p - start_p < 1e-3f)
     {
-        d2d_bezier_quad_to_cubic(p[0], p[1], p[2], &c[0], &c[1]);
-        d2d_point_calculate_bezier(&intersection, p[0], &c[0], &c[1], p[2], centre_p);
+        d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], p[3], centre_p);
         if (start_p > 0.0f && end_p < 1.0f && !d2d_geometry_intersections_add(intersections,
                 idx_p, centre_p, intersection))
             return FALSE;
-- 
2.20.1

[PATCH 04/12] d2d1: Update bezier-line intersection for cubics.

[Connor McAdams]

Update bezier-line intersection function to handle cubic bezier curves.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 172 +++++++++++++++++++++++++++++++------------
 1 file changed, 126 insertions(+), 46 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 8dad84fca3..05b1d10ed8 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -1860,12 +1860,10 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
         struct d2d_geometry_intersections *intersections, const struct d2d_segment_idx *idx_p,
         const D2D1_POINT_2F **p, const struct d2d_segment_idx *idx_q, const D2D1_POINT_2F **q, float s)
 {
-    D2D1_POINT_2F intersection, c[2];
+    D2D1_POINT_2F intersection;
     float t;
 
-
-    d2d_bezier_quad_to_cubic(p[0], p[1], p[2], &c[0], &c[1]);
-    d2d_point_calculate_bezier(&intersection, p[0], &c[0], &c[1], p[2], s);
+    d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], p[3], s);
     if (fabsf(q[1]->x - q[0]->x) > fabsf(q[1]->y - q[0]->y))
         t = (intersection.x - q[0]->x) / (q[1]->x - q[0]->x);
     else
@@ -1884,22 +1882,125 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
     return TRUE;
 }
 
+/* Cubic root finding method adapted from code at
+ * https://pomax.github.io/bezierinfo/#extremities */
+static float d2d_cubic_bezier_cuberoot(float a)
+{
+    if (a < 0)
+        return -powf(-a, 1.0f / 3.0f);
+    else
+        return powf(a, 1.0f / 3.0f);
+}
+
+static int d2d_cubic_bezier_get_roots(float p0, float p1, float p2, float p3, float root[3])
+{
+    float a, b, c, d;
+    float p, p_3, q, q2, disc, sd, tmp;
+    float mp3, r, t, cosphi, phi, crtr, t1, u1, v1;
+
+    /* First, we need to convert the bezier coefficients to 'power basis'
+     * coefficients so that we can use a generic cubic root solving equation. */
+    a = (3.0f * p0 - 6.0f * p1 + 3.0f * p2);
+    b = (-3.0f * p0 + 3.0f * p1);
+    c = p0;
+    d = (-p0 + 3.0f * p1 - 3.0f * p2 + p3);
+
+    /* Check if the curve is actually a quadratic. */
+    if (d2d_cubic_bezier_round_to_zero(d) == 0.0f)
+    {
+        /* Check if it's actually a line. */
+        if (d2d_cubic_bezier_round_to_zero(a) == 0.0f)
+        {
+            /* Check if it's just a point. If it is, no roots. */
+            if (d2d_cubic_bezier_round_to_zero(b) == 0.0f)
+                return 0;
+
+            root[0] = -c / b;
+            return 1;
+        }
+
+        tmp = sqrtf(b * b - 4.0 * a * c);
+        root[0] = (tmp - b) / (2.0 * a);
+        root[1] = (-b - tmp) / (2.0 * a);
+        return 2;
+    }
+
+    a /= d;
+    b /= d;
+    c /= d;
+
+    p = (3.0f * b - a * a) / 3.0f;
+    p_3 = p / 3.0f;
+    q = (2.0f * a * a * a - 9.0f * a * b + 27.0f * c) / 27.0f;
+    q2 = q / 2.0f;
+    disc = q2 * q2 + p_3 * p_3 * p_3;
+
+    disc = d2d_cubic_bezier_round_to_zero(disc);
+    if (disc < 0.0f)
+    {
+        /* Three real roots. */
+        mp3 = -p / 3.0f;
+        r = sqrtf(mp3 * mp3 * mp3);
+        t = -q / (2.0f * r);
+
+        if (t < -1.0f)
+            cosphi = -1.0f;
+        else if (t > 1.0f)
+            cosphi = 1.0f;
+        else
+            cosphi = t;
+
+        phi = acosf(cosphi);
+        crtr = d2d_cubic_bezier_cuberoot(r);
+        t1 = 2.0f * crtr;
+
+        root[0] = t1 * cosf(phi / 3) - a / 3.0f;
+        root[1] = t1 * cosf((phi + 2 * M_PI) / 3) - a / 3.0f;
+        root[2] = t1 * cosf((phi + 4 * M_PI) / 3) - a / 3.0f;
+        return 3;
+    }
+    else if (disc == 0.0f)
+    {
+        /* Three real roots, but two are equal. */
+        if (q2 < 0.0f)
+                tmp = d2d_cubic_bezier_cuberoot(-q2);
+        else
+                tmp = -d2d_cubic_bezier_cuberoot(q2);
+        root[0] = 2.0f * tmp - (a / 3.0f);
+        root[1] = -tmp - (a / 3.0f);
+        return 2;
+    }
+    else
+    {
+        /* One real root, and two complex roots. */
+        sd = sqrtf(disc);
+        u1 = d2d_cubic_bezier_cuberoot(sd - q2);
+        v1 = d2d_cubic_bezier_cuberoot(sd + q2);
+        root[0] = u1 - v1 - a / 3.0f;
+        return 1;
+    }
+
+    return 0;
+}
+
 static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
         struct d2d_geometry_intersections *intersections,
         const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
 {
-    const D2D1_POINT_2F *p[3], *q[2];
+    const D2D1_POINT_2F *p[4], *q[2];
     const struct d2d_figure *figure;
-    float y[3], root, theta, d, e;
+    float y[4], roots[3], theta;
+    int num_of_roots, i;
     size_t next;
 
     figure = &geometry->u.path.figures[idx_p->figure_idx];
     p[0] = &figure->vertices[idx_p->vertex_idx];
-    p[1] = &figure->bezier_controls[idx_p->control_idx].cq0;
+    p[1] = &figure->bezier_controls[idx_p->control_idx].c0;
+    p[2] = &figure->bezier_controls[idx_p->control_idx].c1;
     next = idx_p->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
-    p[2] = &figure->vertices[next];
+    p[3] = &figure->vertices[next];
 
     figure = &geometry->u.path.figures[idx_q->figure_idx];
     q[0] = &figure->vertices[idx_q->vertex_idx];
@@ -1908,54 +2009,33 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
         next = 0;
     q[1] = &figure->vertices[next];
 
+    /* If it's just a point, this isn't going to work. */
+    if (q[0]->x == q[1]->x && q[0]->y == q[1]->y)
+        return TRUE;
+
     /* Align the line with x-axis. */
     theta = -atan2f(q[1]->y - q[0]->y, q[1]->x - q[0]->x);
+    /* Rotate the Y coordinates of the cubic bezier. */
     y[0] = (p[0]->x - q[0]->x) * sinf(theta) + (p[0]->y - q[0]->y) * cosf(theta);
     y[1] = (p[1]->x - q[0]->x) * sinf(theta) + (p[1]->y - q[0]->y) * cosf(theta);
     y[2] = (p[2]->x - q[0]->x) * sinf(theta) + (p[2]->y - q[0]->y) * cosf(theta);
+    y[3] = (p[3]->x - q[0]->x) * sinf(theta) + (p[3]->y - q[0]->y) * cosf(theta);
 
-    /* Intersect the transformed curve with the x-axis.
-     *
-     * f(t) = (1 - t)²P₀ + 2(1 - t)tP₁ + t²P₂
-     *      = (P₀ - 2P₁ + P₂)t² + 2(P₁ - P₀)t + P₀
-     *
-     * a = P₀ - 2P₁ + P₂
-     * b = 2(P₁ - P₀)
-     * c = P₀
-     *
-     * f(t) = 0
-     * t = (-b ± √(b² - 4ac)) / 2a
-     *   = (-2(P₁ - P₀) ± √((2(P₁ - P₀))² - 4((P₀ - 2P₁ + P₂)P₀))) / 2(P₀ - 2P₁ + P₂)
-     *   = (2P₀ - 2P₁ ± √(4P₀² + 4P₁² - 8P₀P₁ - 4P₀² + 8P₀P₁ - 4P₀P₂)) / (2P₀ - 4P₁ + 2P₂)
-     *   = (P₀ - P₁ ± √(P₁² - P₀P₂)) / (P₀ - 2P₁ + P₂) */
+    num_of_roots = d2d_cubic_bezier_get_roots(y[0], y[1], y[2], y[3], roots);
 
-    d = y[0] - 2 * y[1] + y[2];
-    if (d == 0.0f)
+    for (i = 0; i < num_of_roots; i++)
     {
-        /* P₀ - 2P₁ + P₂ = 0
-         * f(t) = (P₀ - 2P₁ + P₂)t² + 2(P₁ - P₀)t + P₀ = 0
-         * t = -P₀ / 2(P₁ - P₀) */
-        root = -y[0] / (2.0f * (y[1] - y[0]));
-        if (root < 0.0f || root > 1.0f)
-            return TRUE;
-
-        return d2d_geometry_add_bezier_line_intersections(geometry, intersections, idx_p, p, idx_q, q, root);
+        if (roots[i] >= 0.0f && roots[i] <= 1.0f)
+        {
+            if (!d2d_geometry_add_bezier_line_intersections(geometry,
+                    intersections, idx_p, p, idx_q, q, roots[i]))
+            {
+                TRACE("d2d_geometry_add_bezier_line_intersections failed.\n");
+                return FALSE;
+            }
+        }
     }
 
-    e = y[1] * y[1] - y[0] * y[2];
-    if (e < 0.0f)
-        return TRUE;
-
-    root = (y[0] - y[1] + sqrtf(e)) / d;
-    if (root >= 0.0f && root <= 1.0f && !d2d_geometry_add_bezier_line_intersections(geometry,
-            intersections, idx_p, p, idx_q, q, root))
-        return FALSE;
-
-    root = (y[0] - y[1] - sqrtf(e)) / d;
-    if (root >= 0.0f && root <= 1.0f && !d2d_geometry_add_bezier_line_intersections(geometry,
-            intersections, idx_p, p, idx_q, q, root))
-        return FALSE;
-
     return TRUE;
 }
 
-- 
2.20.1

[PATCH 05/12] d2d1: Update apply_intersections for cubic beziers.

[Connor McAdams]

Update d2d_geometry_apply_intersections to now handle cubic beziers.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 26 ++++++++++++++------------
 1 file changed, 14 insertions(+), 12 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 05b1d10ed8..5e62ea8422 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -2112,9 +2112,10 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry,
     size_t vertex_offset, control_offset, next, i;
     struct d2d_geometry_intersection *inter;
     enum d2d_vertex_type vertex_type;
-    const D2D1_POINT_2F *p[3];
+    const D2D1_POINT_2F *p[4];
+    D2D1_POINT_2F cq0;
     struct d2d_figure *figure;
-    D2D1_POINT_2F q[2], c[2];
+    D2D1_BEZIER_SEGMENT b[2];
     float t, t_prev;
 
     for (i = 0; i < intersections->intersection_count; ++i)
@@ -2148,22 +2149,23 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry,
         }
 
         p[0] = &figure->vertices[inter->vertex_idx + vertex_offset];
-        p[1] = &figure->bezier_controls[inter->control_idx + control_offset].cq0;
+        p[1] = &figure->bezier_controls[inter->control_idx + control_offset].c0;
+        p[2] = &figure->bezier_controls[inter->control_idx + control_offset].c1;
         next = inter->vertex_idx + vertex_offset + 1;
         if (next == figure->vertex_count)
             next = 0;
-        p[2] = &figure->vertices[next];
+        p[3] = &figure->vertices[next];
 
-        d2d_point_lerp(&q[0], p[0], p[1], t);
-        d2d_point_lerp(&q[1], p[1], p[2], t);
+        d2d_cubic_bezier_split(p[0], p[1], p[2], p[3], t, &b[0], &b[1], NULL);
 
-        d2d_bezier_quad_to_cubic(p[0], &q[0], &inter->p, &c[0], &c[1]);
-        figure->bezier_controls[inter->control_idx + control_offset].cq0 = q[0];
-        figure->bezier_controls[inter->control_idx + control_offset].c0 = c[0];
-        figure->bezier_controls[inter->control_idx + control_offset].c1 = c[1];
+        d2d_bezier_cubic_to_quad(p[0], &b[0].point1, &b[0].point2, &inter->p, &cq0);
+        figure->bezier_controls[inter->control_idx + control_offset].c0 = b[0].point1;
+        figure->bezier_controls[inter->control_idx + control_offset].c1 = b[0].point2;
+        figure->bezier_controls[inter->control_idx + control_offset].cq0 = cq0;
 
-        d2d_bezier_quad_to_cubic(&inter->p, &q[1], p[2], &c[0], &c[1]);
-        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &c[0], &c[1], &q[1])))
+        d2d_bezier_cubic_to_quad(&inter->p, &b[1].point1, &b[1].point2, p[3], &cq0);
+        if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &b[1].point1,
+                        &b[1].point2, &cq0)))
             return FALSE;
         ++control_offset;
 
-- 
2.20.1

[PATCH 06/12] d2d1: Update path geometry Simplify for cubic beziers.

[Connor McAdams]

Update the Simplify method for path geometries to handle cubic bezier
curves.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 33 ++++++++++++++++++++-------------
 1 file changed, 20 insertions(+), 13 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 5e62ea8422..0e2ceb1875 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -3577,15 +3577,16 @@ static void d2d_geometry_flatten_cubic(ID2D1SimplifiedGeometrySink *sink, const
     ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_NONE);
 }
 
-static void d2d_geometry_simplify_quadratic(ID2D1SimplifiedGeometrySink *sink,
+static void d2d_geometry_simplify_bezier(ID2D1SimplifiedGeometrySink *sink,
         D2D1_GEOMETRY_SIMPLIFICATION_OPTION option, const D2D1_POINT_2F *p0,
-        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float tolerance)
+        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2,
+        const D2D1_POINT_2F *p3, float tolerance)
 {
     D2D1_BEZIER_SEGMENT b;
 
-    d2d_point_lerp(&b.point1, p0, p1, 2.0f / 3.0f);
-    d2d_point_lerp(&b.point2, p2, p1, 2.0f / 3.0f);
-    b.point3 = *p2;
+    b.point1 = *p1;
+    b.point2 = *p2;
+    b.point3 = *p3;
 
     if (option == D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES)
         d2d_geometry_flatten_cubic(sink, p0, &b, tolerance);
@@ -3601,7 +3602,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i
     enum d2d_vertex_type type = D2D_VERTEX_TYPE_NONE;
     unsigned int i, j, bezier_idx;
     D2D1_FIGURE_BEGIN begin;
-    D2D1_POINT_2F p, p1, p2;
+    D2D1_POINT_2F p, p1, p2, p3;
     D2D1_FIGURE_END end;
 
     TRACE("iface %p, option %#x, transform %p, tolerance %.8e, sink %p.\n",
@@ -3642,14 +3643,17 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i
                     break;
 
                 case D2D_VERTEX_TYPE_BEZIER:
-                    p1 = figure->original_bezier_controls[bezier_idx++].cq0;
+                    p1 = figure->original_bezier_controls[bezier_idx].c0;
                     if (transform)
                         d2d_point_transform(&p1, transform, p1.x, p1.y);
-                    p2 = figure->vertices[j];
+                    p2 = figure->original_bezier_controls[bezier_idx++].c1;
                     if (transform)
                         d2d_point_transform(&p2, transform, p2.x, p2.y);
-                    d2d_geometry_simplify_quadratic(sink, option, &p, &p1, &p2, tolerance);
-                    p = p2;
+                    p3 = figure->vertices[j];
+                    if (transform)
+                        d2d_point_transform(&p3, transform, p3.x, p3.y);
+                    d2d_geometry_simplify_bezier(sink, option, &p, &p1, &p2, &p3, tolerance);
+                    p = p3;
                     break;
 
                 default:
@@ -3666,13 +3670,16 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i
 
         if (type == D2D_VERTEX_TYPE_BEZIER)
         {
-            p1 = figure->original_bezier_controls[bezier_idx++].cq0;
+            p1 = figure->original_bezier_controls[bezier_idx].c0;
             if (transform)
                 d2d_point_transform(&p1, transform, p1.x, p1.y);
-            p2 = figure->vertices[0];
+            p2 = figure->original_bezier_controls[bezier_idx++].c1;
             if (transform)
                 d2d_point_transform(&p2, transform, p2.x, p2.y);
-            d2d_geometry_simplify_quadratic(sink, option, &p, &p1, &p2, tolerance);
+            p3 = figure->vertices[0];
+            if (transform)
+                d2d_point_transform(&p3, transform, p3.x, p3.y);
+            d2d_geometry_simplify_bezier(sink, option, &p, &p1, &p2, &p3, tolerance);
         }
 
         end = figure->flags & D2D_FIGURE_FLAG_CLOSED ? D2D1_FIGURE_END_CLOSED : D2D1_FIGURE_END_OPEN;
-- 
2.20.1

[PATCH 07/12] d2d1: Add functions for cubic bezier triangulation.

[Connor McAdams]

Add functions for the triangulation of a cubic bezier with it's control
points.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 260 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 260 insertions(+)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 0e2ceb1875..c9ea108484 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -2907,6 +2907,250 @@ static BOOL d2d_geometry_get_next_bezier_segment_idx(struct d2d_geometry *geomet
     return d2d_geometry_get_bezier_segment_idx(geometry, idx, TRUE);
 }
 
+struct d2d_cubic_triangles
+{
+    unsigned int triangles[3][3];
+    unsigned int tri_count;
+
+    D2D1_POINT_2F p[4];
+};
+
+struct d2d_cubic_triangulation
+{
+    struct d2d_cubic_triangles *cubic_tri;
+    size_t cubic_tri_count;
+    size_t cubic_tri_size;
+};
+
+static BOOL d2d_point_approximately_equal(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
+{
+    D2D1_POINT_2F length;
+
+    d2d_point_subtract(&length, a, b);
+
+    return (length.x * length.x + length.y * length.y) <
+        (D2D1_CUBIC_BEZIER_EPSILON * D2D1_CUBIC_BEZIER_EPSILON);
+}
+/*
+ * Second function found on
+ * https://blackpawn.com/texts/pointinpoly/default.html page. Uses barycentric
+ * coordinates to see whether or not the point *p is within the triangle
+ * plane defined by points a, b, and c.
+ */
+static BOOL d2d_point_within_triangle(const D2D1_POINT_2F *p, const D2D1_POINT_2F *a, const D2D1_POINT_2F *b,
+    const D2D1_POINT_2F *c)
+{
+    float dot00, dot01, dot02, dot11, dot12, u, v, inverted_denom;
+    D2D1_POINT_2F v0, v1, v2;
+
+    d2d_point_subtract(&v0, c, a);
+    d2d_point_subtract(&v1, b, a);
+    d2d_point_subtract(&v2, p, a);
+
+    dot00 = d2d_point_dot(&v0, &v0);
+    dot01 = d2d_point_dot(&v0, &v1);
+    dot02 = d2d_point_dot(&v0, &v2);
+    dot11 = d2d_point_dot(&v1, &v1);
+    dot12 = d2d_point_dot(&v1, &v2);
+
+    inverted_denom = 1.0f / (dot00 * dot11 - dot01 * dot01);
+    u = (dot11 * dot02 - dot01 * dot12) * inverted_denom;
+    v = (dot00 * dot12 - dot01 * dot02) * inverted_denom;
+
+    return (u >= 0.0f) && (v >= 0.0f) && (u + v < 1.0f);
+}
+
+/* Reusing portions of d2d_geometry_intersect_line_line */
+static BOOL d2d_line_intersect_test(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b, const D2D1_POINT_2F *c,
+    const D2D1_POINT_2F *d)
+{
+    D2D1_POINT_2F v_p, v_q, v_qp;
+    float det, s, t;
+
+    d2d_point_subtract(&v_p, b, a);
+    d2d_point_subtract(&v_q, d, c);
+    d2d_point_subtract(&v_qp, a, c);
+
+    det = v_p.x * v_q.y - v_p.y * v_q.x;
+    if (det == 0.0f)
+        return FALSE;
+
+    s = (v_q.x * v_qp.y - v_q.y * v_qp.x) / det;
+    t = (v_p.x * v_qp.y - v_p.y * v_qp.x) / det;
+
+    if (s < 0.0f || s > 1.0f || t < 0.0f || t > 1.0f)
+        return FALSE;
+
+    return TRUE;
+}
+
+static float d2d_line_length_squared(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
+{
+    return (b->x - a->x) * (b->x - a->x) + (b->y - a->y) * (b->y - a->y);
+}
+
+static void d2d_geometry_set_bezier_triangle(struct d2d_cubic_triangles *tri,
+        unsigned int tri_index, unsigned int i0, unsigned int i1, unsigned int i2)
+{
+    tri->triangles[tri_index][0] = i0;
+    tri->triangles[tri_index][1] = i1;
+    tri->triangles[tri_index][2] = i2;
+}
+
+static void d2d_geometry_triangulate_bezier(struct d2d_cubic_triangles *tri, const D2D1_POINT_2F **p)
+{
+    unsigned int i, j, k, l, tri_point[3];
+
+    for (i = 0; i < 4; i++)
+        tri->p[i] = *p[i];
+
+    /* Check to see if any of the control points are the same. If they are,
+     * we're only going to need one triangle. */
+    for (i = 0; i < 4; i++)
+    {
+        for (j = i + 1; j < 4; j++)
+        {
+            if (d2d_point_approximately_equal(p[i], p[j]))
+            {
+                for (k = 0, l = 0; k < 4; k++)
+                {
+                    if (k == j)
+                        continue;
+                    tri->triangles[0][l++] = k;
+                }
+
+                tri->tri_count = 1;
+                return;
+            }
+
+        }
+    }
+
+    /* Next, check to see if any control points are within the triangles
+     * generated by other control points. If this happens, we're going to end
+     * up needing 3 triangles. For example:
+     * /------------------\
+     * |                  |
+     * |      * p1        |
+     * |                  |
+     * |    *   *         |
+     * |   p0   p3        |
+     * |             * p2 |
+     * \------------------/
+     * p3 would be contained within the triangle generated by p0->p1->p2, so
+     * we'll need to create 3 triangles, each with p3 as a common vertex.
+     */
+    for (i = 0; i < 4; i++)
+    {
+        for (j = 0, k = 0; j < 4; j++)
+        {
+            if (i == j)
+                continue;
+            tri_point[k++] = j;
+        }
+
+        if (d2d_point_within_triangle(p[i], p[tri_point[0]], p[tri_point[1]], p[tri_point[2]]))
+        {
+            for (k = 0; k < 3; k++)
+                d2d_geometry_set_bezier_triangle(tri, k, tri_point[k % 3],
+                        tri_point[(k + 1) % 3], i);
+
+            tri->tri_count = 3;
+            return;
+        }
+    }
+
+    /* Now, with those two possibilities out of the way, we are down to the
+     * common case: Two triangles, a quad with a line splitting it down the
+     * middle. There are three possible triangles, and we check for which one
+     * to use by checking to see if the lines that split the quad intersect
+     * one another. Once we've found a suitable triangulation, we also find
+     * the shortest line to split the quad.
+     */
+    if (d2d_line_intersect_test(p[0], p[2], p[1], p[3]))
+    {
+        if (d2d_line_length_squared(p[0], p[2]) < d2d_line_length_squared(p[1], p[3]))
+        {
+            d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 2);
+            d2d_geometry_set_bezier_triangle(tri, 1, 0, 2, 3);
+        }
+        else
+        {
+            d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 3);
+            d2d_geometry_set_bezier_triangle(tri, 1, 1, 2, 3);
+        }
+    }
+    else if (d2d_line_intersect_test(p[0], p[3], p[1], p[2]))
+    {
+        if (d2d_line_length_squared(p[0], p[3]) < d2d_line_length_squared(p[1], p[2]))
+        {
+            d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 3);
+            d2d_geometry_set_bezier_triangle(tri, 1, 0, 3, 2);
+        }
+        else
+        {
+            d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 2);
+            d2d_geometry_set_bezier_triangle(tri, 1, 2, 1, 3);
+        }
+    }
+    else
+    {
+        if (d2d_line_length_squared(p[0], p[1]) < d2d_line_length_squared(p[2], p[3]))
+        {
+            d2d_geometry_set_bezier_triangle(tri, 0, 0, 2, 1);
+            d2d_geometry_set_bezier_triangle(tri, 1, 0, 1, 3);
+        }
+        else
+        {
+            d2d_geometry_set_bezier_triangle(tri, 0, 0, 2, 3);
+            d2d_geometry_set_bezier_triangle(tri, 1, 3, 2, 1);
+        }
+    }
+
+    tri->tri_count = 2;
+}
+
+static HRESULT d2d_geometry_triangulate_beziers(struct d2d_geometry *geometry,
+        struct d2d_cubic_triangulation *triangles)
+{
+    struct d2d_segment_idx idx;
+    struct d2d_figure *figure;
+    struct d2d_cubic_triangles *tri;
+    const D2D1_POINT_2F *p[4];
+    unsigned int i;
+
+    for (i = 0; i < geometry->u.path.figure_count; ++i)
+    {
+        triangles[i].cubic_tri_count = geometry->u.path.figures[i].bezier_control_count;
+        if (!(triangles[i].cubic_tri = heap_calloc(triangles[i].cubic_tri_count, sizeof(*triangles[i].cubic_tri))))
+        {
+            ERR("Failed to allocate bezier triangles array.\n");
+            return E_OUTOFMEMORY;
+        }
+    }
+
+    d2d_geometry_get_first_bezier_segment_idx(geometry, &idx);
+    for(;;)
+    {
+        tri = &triangles[idx.figure_idx].cubic_tri[idx.control_idx];
+        figure = &geometry->u.path.figures[idx.figure_idx];
+        p[0] = &figure->vertices[idx.vertex_idx];
+        p[1] = &figure->bezier_controls[idx.control_idx].c0;
+        p[2] = &figure->bezier_controls[idx.control_idx].c1;
+        if (idx.vertex_idx == figure->vertex_count - 1)
+            p[3] = &figure->vertices[0];
+        else
+            p[3] = &figure->vertices[idx.vertex_idx + 1];
+
+        d2d_geometry_triangulate_bezier(tri, p);
+
+        if (!d2d_geometry_get_next_bezier_segment_idx(geometry, &idx))
+            break;
+    }
+
+    return S_OK;
+}
+
 static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
         const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
 {
@@ -3045,15 +3289,26 @@ static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struc
 
 static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
 {
+    struct d2d_cubic_triangulation *triangles;
     struct d2d_segment_idx idx_p, idx_q;
     struct d2d_bezier_vertex *b;
     const D2D1_POINT_2F *p[3];
     struct d2d_figure *figure;
     size_t bezier_idx, i;
+    HRESULT hr;
 
     if (!d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p))
         return S_OK;
 
+    if (!(triangles = heap_calloc(geometry->u.path.figure_count, sizeof(*triangles))))
+    {
+        ERR("Failed to allocate bezier triangulation data.\n");
+        return E_OUTOFMEMORY;
+    }
+
+    if (FAILED(hr = d2d_geometry_triangulate_beziers(geometry, triangles)))
+            return hr;
+
     /* Split overlapping bezier control triangles. */
     while (d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p))
     {
@@ -3131,6 +3386,11 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
         ++bezier_idx;
     }
 
+    for (i = 0; i < geometry->u.path.figure_count; i++)
+        heap_free(triangles[i].cubic_tri);
+
+    heap_free(triangles);
+
     return S_OK;
 }
 
-- 
2.20.1

[PATCH 08/12] d2d1: Add function for getting figure orientation.

[Connor McAdams]

Add a function for getting figure orientation to find the correct fill
side of a cubic bezier.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 73 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 73 insertions(+)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index c9ea108484..a231bed986 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -2915,11 +2915,19 @@ struct d2d_cubic_triangles
     D2D1_POINT_2F p[4];
 };
 
+enum figure_orientation
+{
+    ORIENTATION_CW,  /* Clockwise. */
+    ORIENTATION_CCW, /* Counter clockwise. */
+};
+
 struct d2d_cubic_triangulation
 {
     struct d2d_cubic_triangles *cubic_tri;
     size_t cubic_tri_count;
     size_t cubic_tri_size;
+
+    unsigned int orientation;
 };
 
 static BOOL d2d_point_approximately_equal(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
@@ -3151,6 +3159,69 @@ static HRESULT d2d_geometry_triangulate_beziers(struct d2d_geometry *geometry,
     return S_OK;
 }
 
+static float d2d_geometry_point_orientation(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
+{
+    return (b->x - a->x) * (b->y + a->y);
+}
+
+static void d2d_geometry_get_figure_orientation(struct d2d_geometry *geometry,
+        struct d2d_cubic_triangulation *triangles)
+{
+    const struct d2d_figure *figure;
+    struct d2d_segment_idx idx;
+    struct d2d_cubic_triangulation *fig_tri;
+    enum d2d_vertex_type type;
+    const D2D1_POINT_2F *p[4];
+    float orientation;
+    size_t next;
+    unsigned int i;
+
+    for (idx.figure_idx = 0; idx.figure_idx < geometry->u.path.figure_count; ++idx.figure_idx)
+    {
+        figure = &geometry->u.path.figures[idx.figure_idx];
+        fig_tri = &triangles[idx.figure_idx];
+        orientation = 0.0f;
+
+        for (idx.vertex_idx = 0, idx.control_idx = 0; idx.vertex_idx < figure->vertex_count; ++idx.vertex_idx)
+        {
+            type = figure->vertex_types[idx.vertex_idx];
+            next = idx.vertex_idx + 1;
+            if (next == figure->vertex_count)
+                next = 0;
+
+            switch (type)
+            {
+                case D2D_VERTEX_TYPE_LINE:
+                    p[0] = &figure->vertices[idx.vertex_idx];
+                    p[1] = &figure->vertices[next];
+                    orientation += d2d_geometry_point_orientation(p[0], p[1]);
+                    break;
+
+                case D2D_VERTEX_TYPE_BEZIER:
+                case D2D_VERTEX_TYPE_SPLIT_BEZIER:
+                    p[0] = &figure->vertices[idx.vertex_idx];
+                    p[1] = &figure->bezier_controls[idx.control_idx].c0;
+                    p[2] = &figure->bezier_controls[idx.control_idx++].c1;
+                    p[3] = &figure->vertices[next];
+
+                    for (i = 1; i < 4; i++)
+                        orientation += d2d_geometry_point_orientation(p[i - 1], p[i]);
+                    break;
+
+                default:
+                    break;
+            }
+        }
+
+        /* Depending on orientation value, set either clockwise or
+         * counter-clockwise. */
+        if (orientation < 0.0f)
+            fig_tri->orientation = ORIENTATION_CW;
+        else
+            fig_tri->orientation = ORIENTATION_CCW;
+    }
+}
+
 static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
         const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
 {
@@ -3337,6 +3408,8 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
         }
     }
 
+    d2d_geometry_get_figure_orientation(geometry, triangles);
+
     for (i = 0; i < geometry->u.path.figure_count; ++i)
     {
         if (geometry->u.path.figures[i].flags & D2D_FIGURE_FLAG_HOLLOW)
-- 
2.20.1

[PATCH 09/12] d2d1: Add cubic bezier fill side detection.

[Connor McAdams]

Add ability to detect correct fill side for each cubic bezier.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 51 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 51 insertions(+)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index a231bed986..c78664488d 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -2913,6 +2913,7 @@ struct d2d_cubic_triangles
     unsigned int tri_count;
 
     D2D1_POINT_2F p[4];
+    unsigned int inside;
 };
 
 enum figure_orientation
@@ -3159,6 +3160,28 @@ static HRESULT d2d_geometry_triangulate_beziers(struct d2d_geometry *geometry,
     return S_OK;
 }
 
+static void d2d_geometry_bezier_normal(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
+        const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t)
+{
+    D2D1_POINT_2F derivative, probe, p1_p0, p2_p1, p3_p2;
+    float t_c = 1.0f - t;
+    float t_c_sq = t_c * t_c;
+
+    d2d_point_subtract(&p1_p0, p1, p0);
+    d2d_point_subtract(&p2_p1, p2, p1);
+    d2d_point_subtract(&p3_p2, p3, p2);
+
+    d2d_point_calculate_bezier(&probe, p0, p1, p2, p3, t);
+    derivative.x = 3.0f * t_c_sq * p1_p0.x + 6.0f * t_c * t * p2_p1.x + (3.0f * (t * t)) * p3_p2.x;
+    derivative.y = 3.0f * t_c_sq * p1_p0.y + 6.0f * t_c * t * p2_p1.y + (3.0f * (t * t)) * p3_p2.y;
+    d2d_point_normalise(&derivative);
+    /* Scale the normal down so it doesn't go too far from the curve. */
+    d2d_point_scale(&derivative, 0.01f);
+
+    out->x = -derivative.y + probe.x;
+    out->y = derivative.x + probe.y;
+}
+
 static float d2d_geometry_point_orientation(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
 {
     return (b->x - a->x) * (b->y + a->y);
@@ -3167,15 +3190,27 @@ static float d2d_geometry_point_orientation(const D2D1_POINT_2F *a, const D2D1_P
 static void d2d_geometry_get_figure_orientation(struct d2d_geometry *geometry,
         struct d2d_cubic_triangulation *triangles)
 {
+    struct d2d_geometry *geometry_flat;
+    ID2D1PathGeometry *flatten_geometry;
+    ID2D1GeometrySink *sink;
     const struct d2d_figure *figure;
     struct d2d_segment_idx idx;
     struct d2d_cubic_triangulation *fig_tri;
+    struct d2d_cubic_triangles *tri;
     enum d2d_vertex_type type;
     const D2D1_POINT_2F *p[4];
+    D2D1_POINT_2F probe;
     float orientation;
     size_t next;
     unsigned int i;
 
+    ID2D1Factory_CreatePathGeometry((ID2D1Factory *)geometry->factory, &flatten_geometry);
+    ID2D1PathGeometry_Open(flatten_geometry, &sink);
+    ID2D1PathGeometry_Simplify((ID2D1PathGeometry *)&geometry->ID2D1Geometry_iface, D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES,
+        NULL, 0.05f, (ID2D1SimplifiedGeometrySink *)sink);
+    geometry_flat = impl_from_ID2D1GeometrySink(sink);
+    ID2D1GeometrySink_Close(sink);
+
     for (idx.figure_idx = 0; idx.figure_idx < geometry->u.path.figure_count; ++idx.figure_idx)
     {
         figure = &geometry->u.path.figures[idx.figure_idx];
@@ -3184,6 +3219,7 @@ static void d2d_geometry_get_figure_orientation(struct d2d_geometry *geometry,
 
         for (idx.vertex_idx = 0, idx.control_idx = 0; idx.vertex_idx < figure->vertex_count; ++idx.vertex_idx)
         {
+            tri = &fig_tri->cubic_tri[idx.control_idx];
             type = figure->vertex_types[idx.vertex_idx];
             next = idx.vertex_idx + 1;
             if (next == figure->vertex_count)
@@ -3204,6 +3240,18 @@ static void d2d_geometry_get_figure_orientation(struct d2d_geometry *geometry,
                     p[2] = &figure->bezier_controls[idx.control_idx++].c1;
                     p[3] = &figure->vertices[next];
 
+                    /* Check the fill side for each bezier individually by
+                     * casting a normal at the center of the bezier, and
+                     * seeing if the point is within the interior of the
+                     * flattened geometry. If this isn't done, it leads to
+                     * issues with multiple overlapping figures. The geometry
+                     * needs to be flattened because otherwise interior
+                     * detection is done between the start and end vertices of
+                     * the bezier, which leads to issues where one control
+                     * point is inside and the other outside. */
+                    d2d_geometry_bezier_normal(&probe, p[0], p[1], p[2], p[3], 0.5f);
+                    tri->inside = d2d_path_geometry_point_inside(geometry_flat, &probe, FALSE);
+
                     for (i = 1; i < 4; i++)
                         orientation += d2d_geometry_point_orientation(p[i - 1], p[i]);
                     break;
@@ -3220,6 +3268,9 @@ static void d2d_geometry_get_figure_orientation(struct d2d_geometry *geometry,
         else
             fig_tri->orientation = ORIENTATION_CCW;
     }
+
+    ID2D1PathGeometry_Release(flatten_geometry);
+    ID2D1Factory_Release((ID2D1Factory *)geometry->factory);
 }
 
 static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
-- 
2.20.1

[PATCH 09/12] d2d1: Add cubic bezier fill side detection.

[Marvin]

Hi,

While running your changed tests, I think I found new failures.
Being a bot and all I'm not very good at pattern recognition, so I might be
wrong, but could you please double-check?

Full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=65746

Your paranoid android.


=== debian10 (32 bit report) ===

d2d1:
d2d1: Timeout

=== debian10 (32 bit Chinese:China report) ===

d2d1:
d2d1.c:7858: Test failed: Figure does not match.

=== debian10 (32 bit WoW report) ===

d2d1:
d2d1.c:7858: Test failed: Figure does not match.

=== debian10 (64 bit WoW report) ===

d2d1:
Unhandled exception: page fault on read access to 0x00000001 in 32-bit code (0x6c9d7006).

Report validation errors:
d2d1:d2d1 crashed (c0000005)

[PATCH 10/12] d2d1: Update bezier overlap checking for cubics.

[Connor McAdams]

Update the current bezier control triangle overlap functions to handle
cubic beziers.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 168 +++++++++++++++++++++++++++++++------------
 1 file changed, 123 insertions(+), 45 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index c78664488d..c740f232cd 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -3273,31 +3273,13 @@ static void d2d_geometry_get_figure_orientation(struct d2d_geometry *geometry,
     ID2D1Factory_Release((ID2D1Factory *)geometry->factory);
 }
 
-static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
-        const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
+static BOOL d2d_check_bezier_triangle_overlap(const D2D1_POINT_2F **a, const D2D1_POINT_2F **b)
 {
-    const D2D1_POINT_2F *a[3], *b[3], *p[2], *q;
-    const struct d2d_figure *figure;
+    const D2D1_POINT_2F *p[2], *q;
     D2D1_POINT_2F v_q[3], v_p, v_qp;
     unsigned int i, j, score;
     float det, t;
 
-    figure = &geometry->u.path.figures[idx_p->figure_idx];
-    a[0] = &figure->vertices[idx_p->vertex_idx];
-    a[1] = &figure->bezier_controls[idx_p->control_idx].cq0;
-    if (idx_p->vertex_idx == figure->vertex_count - 1)
-        a[2] = &figure->vertices[0];
-    else
-        a[2] = &figure->vertices[idx_p->vertex_idx + 1];
-
-    figure = &geometry->u.path.figures[idx_q->figure_idx];
-    b[0] = &figure->vertices[idx_q->vertex_idx];
-    b[1] = &figure->bezier_controls[idx_q->control_idx].cq0;
-    if (idx_q->vertex_idx == figure->vertex_count - 1)
-        b[2] = &figure->vertices[0];
-    else
-        b[2] = &figure->vertices[idx_q->vertex_idx + 1];
-
     if (d2d_point_ccw(a[0], a[1], a[2]) == 0.0f || d2d_point_ccw(b[0], b[1], b[2]) == 0.0f)
         return FALSE;
 
@@ -3361,48 +3343,144 @@ static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
     return score & 1;
 }
 
-static float d2d_geometry_bezier_ccw(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx)
+static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
+        const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q,
+        struct d2d_cubic_triangulation *triangles)
 {
-    const struct d2d_figure *figure = &geometry->u.path.figures[idx->figure_idx];
-    size_t next = idx->vertex_idx + 1;
+    const D2D1_POINT_2F *p[4], *q[4], *a[3], *b[3];
+    struct d2d_cubic_triangles *tri_p, *tri_q;
+    const struct d2d_figure *figure;
+    unsigned int i, j;
+    size_t next;
 
+    figure = &geometry->u.path.figures[idx_p->figure_idx];
+    p[0] = &figure->vertices[idx_p->vertex_idx];
+    p[1] = &figure->bezier_controls[idx_p->control_idx].c0;
+    p[2] = &figure->bezier_controls[idx_p->control_idx].c1;
+    next = idx_p->vertex_idx + 1;
+    if (next == figure->vertex_count)
+        next = 0;
+    p[3] = &figure->vertices[next];
+
+    figure = &geometry->u.path.figures[idx_q->figure_idx];
+    q[0] = &figure->vertices[idx_q->vertex_idx];
+    q[1] = &figure->bezier_controls[idx_q->control_idx].c0;
+    q[2] = &figure->bezier_controls[idx_q->control_idx].c1;
+    next = idx_q->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
+    q[3] = &figure->vertices[next];
+
+    /* Get the triangle structure for each. */
+    tri_p = &triangles[idx_p->figure_idx].cubic_tri[idx_p->control_idx];
+    tri_q = &triangles[idx_q->figure_idx].cubic_tri[idx_q->control_idx];
 
-    return d2d_point_ccw(&figure->vertices[idx->vertex_idx],
-            &figure->bezier_controls[idx->control_idx].cq0, &figure->vertices[next]);
+    for (i = 0; i < tri_p->tri_count; i++)
+    {
+        a[0] = p[tri_p->triangles[i][0]];
+        a[1] = p[tri_p->triangles[i][1]];
+        a[2] = p[tri_p->triangles[i][2]];
+        for (j = 0; j < tri_q->tri_count; j++)
+        {
+            b[0] = q[tri_q->triangles[j][0]];
+            b[1] = q[tri_q->triangles[j][1]];
+            b[2] = q[tri_q->triangles[j][2]];
+            if (d2d_check_bezier_triangle_overlap(a, b))
+                return TRUE;
+        }
+    }
+
+    return FALSE;
 }
 
-static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx)
+static float d2d_geometry_bezier_ccw(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx,
+    struct d2d_cubic_triangulation *triangles)
 {
-    const D2D1_POINT_2F *p[3];
-    struct d2d_figure *figure;
-    D2D1_POINT_2F q[3], c[2];
+    struct d2d_cubic_triangles *tri = &triangles[idx->figure_idx].cubic_tri[idx->control_idx];
+    const struct d2d_figure *figure;
+    const D2D1_POINT_2F *p[4];
+    float total_size;
     size_t next;
+    unsigned int i;
 
     figure = &geometry->u.path.figures[idx->figure_idx];
     p[0] = &figure->vertices[idx->vertex_idx];
-    p[1] = &figure->bezier_controls[idx->control_idx].cq0;
+    p[1] = &figure->bezier_controls[idx->control_idx].c0;
+    p[2] = &figure->bezier_controls[idx->control_idx].c1;
     next = idx->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
-    p[2] = &figure->vertices[next];
+    p[3] = &figure->vertices[next];
+
+    for (i = 0, total_size = 0.0f; i < tri->tri_count; i++)
+        total_size += fabsf(d2d_point_ccw(p[tri->triangles[i][0]], p[tri->triangles[i][1]], p[tri->triangles[i][2]]));
+
+    return total_size;
+}
+
+static BOOL d2d_geometry_insert_bezier_triangulation(struct d2d_cubic_triangulation *triangles, size_t idx,
+        struct d2d_cubic_triangles *tri)
+{
+    if (!d2d_array_reserve((void **)&triangles->cubic_tri, &triangles->cubic_tri_size,
+            triangles->cubic_tri_count + 1, sizeof(*triangles->cubic_tri)))
+    {
+        ERR("Failed to grow bezier triangles array.\n");
+        return FALSE;
+    }
 
-    d2d_point_lerp(&q[0], p[0], p[1], 0.5f);
-    d2d_point_lerp(&q[1], p[1], p[2], 0.5f);
-    d2d_point_lerp(&q[2], &q[0], &q[1], 0.5f);
+    memmove(&triangles->cubic_tri[idx + 1], &triangles->cubic_tri[idx],
+            (triangles->cubic_tri_count - idx) * sizeof(*triangles->cubic_tri));
+    triangles->cubic_tri[idx] = *tri;
+    ++triangles->cubic_tri_count;
 
-    d2d_bezier_quad_to_cubic(p[0], &q[0], &q[2], &c[0], &c[1]);
+    return TRUE;
+}
 
-    figure->bezier_controls[idx->control_idx].cq0 = q[0];
-    figure->bezier_controls[idx->control_idx].c0 = c[0];
-    figure->bezier_controls[idx->control_idx].c1 = c[1];
+static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx,
+        struct d2d_cubic_triangulation *triangles)
+{
+    const D2D1_POINT_2F *p[4], *q[4];
+    D2D1_POINT_2F cq[2];
+    struct d2d_cubic_triangulation *tri_fig = &triangles[idx->figure_idx];
+    struct d2d_cubic_triangles new_triangle;
+    struct d2d_figure *figure;
+    D2D1_BEZIER_SEGMENT b[2];
+    size_t next;
 
-    d2d_bezier_quad_to_cubic(&q[0], &q[1], p[2], &c[0], &c[1]);
+    figure = &geometry->u.path.figures[idx->figure_idx];
+    p[0] = &figure->vertices[idx->vertex_idx];
+    p[1] = &figure->bezier_controls[idx->control_idx].c0;
+    p[2] = &figure->bezier_controls[idx->control_idx].c1;
+    next = idx->vertex_idx + 1;
+    if (next == figure->vertex_count)
+        next = 0;
+    p[3] = &figure->vertices[next];
 
-    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &c[0], &c[1], &q[1])))
+    d2d_cubic_bezier_split(p[0], p[1], p[2], p[3], 0.5f, &b[0], &b[1], NULL);
+
+    q[0] = p[0];
+    q[1] = &b[0].point1;
+    q[2] = &b[0].point2;
+    q[3] = &b[0].point3;
+    d2d_bezier_cubic_to_quad(q[0], q[1], q[2], q[3], &cq[0]);
+    d2d_geometry_triangulate_bezier(&tri_fig->cubic_tri[idx->control_idx], q);
+
+    q[0] = &b[0].point3;
+    q[1] = &b[1].point1;
+    q[2] = &b[1].point2;
+    q[3] = &b[1].point3;
+    d2d_bezier_cubic_to_quad(q[0], q[1], q[2], q[3], &cq[1]);
+    d2d_geometry_triangulate_bezier(&new_triangle, q);
+    new_triangle.inside = tri_fig->cubic_tri[idx->control_idx].inside;
+
+    figure->bezier_controls[idx->control_idx].c0 = b[0].point1;
+    figure->bezier_controls[idx->control_idx].c1 = b[0].point2;
+    figure->bezier_controls[idx->control_idx].cq0 = cq[0];
+    if (!(d2d_geometry_insert_bezier_triangulation(tri_fig, idx->control_idx + 1, &new_triangle)))
+        return FALSE;
+    if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &b[1].point1, &b[1].point2, &cq[1])))
         return FALSE;
-    if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2])))
+    if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, b[0].point3)))
         return FALSE;
     figure->vertex_types[idx->vertex_idx + 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER;
 
@@ -3437,11 +3515,11 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
         d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_q);
         while (idx_q.figure_idx < idx_p.figure_idx || idx_q.vertex_idx < idx_p.vertex_idx)
         {
-            while (d2d_geometry_check_bezier_overlap(geometry, &idx_p, &idx_q))
+            while (d2d_geometry_check_bezier_overlap(geometry, &idx_p, &idx_q, triangles))
             {
-                if (fabsf(d2d_geometry_bezier_ccw(geometry, &idx_q)) > fabsf(d2d_geometry_bezier_ccw(geometry, &idx_p)))
+                if (d2d_geometry_bezier_ccw(geometry, &idx_q, triangles) > d2d_geometry_bezier_ccw(geometry, &idx_p, triangles))
                 {
-                    if (!d2d_geometry_split_bezier(geometry, &idx_q))
+                    if (!d2d_geometry_split_bezier(geometry, &idx_q, triangles))
                         return E_OUTOFMEMORY;
                     if (idx_p.figure_idx == idx_q.figure_idx)
                     {
@@ -3451,7 +3529,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
                 }
                 else
                 {
-                    if (!d2d_geometry_split_bezier(geometry, &idx_p))
+                    if (!d2d_geometry_split_bezier(geometry, &idx_p, triangles))
                         return E_OUTOFMEMORY;
                 }
             }
-- 
2.20.1

[PATCH 11/12] d2d1: Add cubic bezier texture coordinate functions.

[Connor McAdams]

Add functions for getting cubic bezier texture coordinates.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/geometry.c | 331 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 331 insertions(+)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index c740f232cd..28c62c58f0 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -2907,6 +2907,26 @@ static BOOL d2d_geometry_get_next_bezier_segment_idx(struct d2d_geometry *geomet
     return d2d_geometry_get_bezier_segment_idx(geometry, idx, TRUE);
 }
 
+enum bezier_fill_side
+{
+    FILL_LEFT,
+    FILL_RIGHT,
+};
+
+enum bezier_type
+{
+    BEZIER_TYPE_SERP,
+    BEZIER_TYPE_LOOP,
+    BEZIER_TYPE_CUSP,
+    BEZIER_TYPE_QUAD,
+    BEZIER_TYPE_LINE,
+};
+
+struct d2d_vec3
+{
+    float x, y, z;
+};
+
 struct d2d_cubic_triangles
 {
     unsigned int triangles[3][3];
@@ -2914,6 +2934,11 @@ struct d2d_cubic_triangles
 
     D2D1_POINT_2F p[4];
     unsigned int inside;
+
+    struct d2d_vec3 klm[4];
+    unsigned int type;
+    unsigned int fill_side;
+    unsigned int reverse;
 };
 
 enum figure_orientation
@@ -3487,6 +3512,304 @@ static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struc
     return TRUE;
 }
 
+static void d2d_vec3_cross_product(struct d2d_vec3 *res, struct d2d_vec3 *a, struct d2d_vec3 *b)
+{
+    res->x = (a->y * b->z) - (a->z * b->y);
+    res->y = -(a->x * b->z - a->z * b->x);
+    res->z = a->x * b->y - a->y * b->x;
+}
+
+static float d2d_vec3_dot_product(struct d2d_vec3 *a, struct d2d_vec3 *b)
+{
+    return a->x * b->x + a->y * b->y + a->z * b->z;
+}
+
+static void d2d_vec3_scale(struct d2d_vec3 *vec, float scale)
+{
+    vec->x = vec->x * scale;
+    vec->y = vec->y * scale;
+    vec->z = vec->z * scale;
+}
+
+static void d2d_vec3_normalize(struct d2d_vec3 *vec)
+{
+    float l;
+
+    if ((l = sqrt(d2d_vec3_dot_product(vec, vec))) != 0.0f)
+        d2d_vec3_scale(vec, 1.0f / l);
+}
+
+static void d2d_vec3_round_to_zero(struct d2d_vec3 *vec)
+{
+    vec->x = d2d_cubic_bezier_round_to_zero(vec->x);
+    vec->y = d2d_cubic_bezier_round_to_zero(vec->y);
+    vec->z = d2d_cubic_bezier_round_to_zero(vec->z);
+}
+
+static void d2d_point_to_vec3(struct d2d_vec3 *vec, const D2D1_POINT_2F *p)
+{
+    vec->x = p->x;
+    vec->y = p->y;
+    vec->z = 1.0f;
+}
+
+static void d2d_geometry_reverse_bezier_coords(struct d2d_cubic_triangles *tri)
+{
+    unsigned int i;
+
+    for (i = 0; i < 4; i++)
+    {
+        tri->klm[i].x = -tri->klm[i].x;
+        tri->klm[i].y = -tri->klm[i].y;
+    }
+}
+
+static void d2d_geometry_get_bezier_serp_coords(struct d2d_vec3 *d, struct d2d_cubic_triangles *tri)
+{
+    float l_s, l_t, m_s, m_t;
+
+    l_s = 3.0f * d->y - sqrtf(9.0f * d->y * d->y - 12.0f * d->x * d->z);
+    l_t = 6.0f * d->x;
+
+    m_s = 3.0f * d->y + sqrtf(9.0f * d->y * d->y - 12.0f * d->x * d->z);
+    m_t = 6.0f * d->x;
+
+    tri->klm[0].x = l_s * m_s;
+    tri->klm[0].y = l_s * l_s * l_s;
+    tri->klm[0].z = m_s * m_s * m_s;
+
+    tri->klm[1].x = (1.0f / 3.0f) * (3.0f * l_s * m_s - l_s * m_t - l_t * m_s);
+    tri->klm[1].y = l_s * l_s * (l_s - l_t);
+    tri->klm[1].z = m_s * m_s * (m_s - m_t);
+
+    tri->klm[2].x = (1.0f / 3.0f) * (l_t * (m_t - 2.0f * m_s) + l_s * (3.0f * m_s - 2.0f * m_t));
+    tri->klm[2].y = (l_t - l_s) * (l_t - l_s) * l_s;
+    tri->klm[2].z = (m_t - m_s) * (m_t - m_s) * m_s;
+
+    tri->klm[3].x = (l_t - l_s) * (m_t - m_s);
+    tri->klm[3].y = -((l_t - l_s) * (l_t - l_s) * (l_t - l_s));
+    tri->klm[3].z = -((m_t - m_s) * (m_t - m_s) * (m_t - m_s));
+
+    if (d->x < 0.0f)
+        tri->reverse = 1;
+    else
+        tri->reverse = 0;
+}
+
+static BOOL d2d_geometry_get_bezier_loop_coords(struct d2d_vec3 *d, struct d2d_cubic_triangles *tri)
+{
+    float l_s, l_t, m_s, m_t, split_check;
+
+    l_s = d->y - sqrtf(4.0f * d->x * d->z - 3.0f * d->y * d->y);
+    l_t = 2.0f * d->x;
+    split_check = l_s / l_t;
+    if (split_check > 0.0f && split_check < 1.0f)
+        return FALSE;
+
+    m_s = d->y + sqrtf(4 * d->x * d->z - 3.0f * d->y * d->y);
+    m_t = 2.0f * d->x;
+    split_check = m_s / m_t;
+    if (split_check > 0.0f && split_check < 1.0f)
+        return FALSE;
+
+    tri->klm[0].x = l_s * m_s;
+    tri->klm[0].y = l_s * l_s * m_s;
+    tri->klm[0].z = l_s * m_s * m_s;
+
+    tri->klm[1].x =  (1.0f / 3.0f) * (-l_s * m_t - l_t * m_s + 3.0f * l_s * m_s);
+    tri->klm[1].y = -(1.0f / 3.0f) * l_s * (l_s * (m_t - 3.0f * m_s) + 2.0f * l_t * m_s);
+    tri->klm[1].z = -(1.0f / 3.0f) * m_s * (l_s * (2.0f * m_t - 3.0f * m_s) + l_t * m_s);
+
+    tri->klm[2].x = (1.0f / 3.0f) * (l_t * (m_t - 2.0f * m_s) + l_s * (3.0f * m_s - 2.0f * m_t));
+    tri->klm[2].y = (1.0f / 3.0f) * (l_t - l_s) * (l_s * (2.0f * m_t - 3.0f * m_s) + l_t * m_s);
+    tri->klm[2].z = (1.0f / 3.0f) * (m_t - m_s) * (l_s * (m_t - 3.0f * m_s) + 2.0f * l_t * m_s);
+
+    tri->klm[3].x = (l_t - l_s) * (m_t - m_s);
+    tri->klm[3].y = -((l_t - l_s) * (l_t - l_s)) * (m_t - m_s);
+    tri->klm[3].z = -(l_t - l_s) * ((m_t - m_s) * (m_t - m_s));
+
+    if ((d->x > 0.0f && tri->klm[0].x < 0.0f) || (d->x < 0.0f && tri->klm[0].x > 0.0f))
+        tri->reverse = 1;
+    else
+        tri->reverse = 0;
+
+    return TRUE;
+}
+
+static void d2d_geometry_get_bezier_cusp_coords(struct d2d_vec3 *d, struct d2d_cubic_triangles *tri)
+{
+    float l_s, l_t;
+
+    l_s = d->z;
+    l_t = 3.0f * d->y;
+
+    tri->klm[0].x = l_s;
+    tri->klm[0].y = l_s * l_s * l_s;
+    tri->klm[0].z = 1.0f;
+
+    tri->klm[1].x = l_s - (1.0f / 3.0f) * l_t;
+    tri->klm[1].y = (l_s - l_t) * (l_s - l_t) * l_s;
+    tri->klm[1].z = 1.0f;
+
+    tri->klm[2].x = l_s - (2.0f / 3.0f) * l_t;
+    tri->klm[2].y = (l_s - l_t) * (l_s - l_t) * l_s;
+    tri->klm[2].z = 1.0f;
+
+    tri->klm[3].x = l_s - l_t;
+    tri->klm[3].y = (l_s - l_t) * (l_s - l_t) * (l_s - l_t);
+    tri->klm[3].z = 1.0f;
+
+    tri->reverse = 0;
+}
+
+static void d2d_geometry_get_bezier_quad_coords(struct d2d_vec3 *d, struct d2d_cubic_triangles *tri)
+{
+    tri->klm[0].x = 0.0f;
+    tri->klm[0].y = 0.0f;
+    tri->klm[0].z = 0.0f;
+
+    tri->klm[1].x = 1.0f / 3.0f;
+    tri->klm[1].y = 0.0f;
+    tri->klm[1].z = 1.0f / 3.0f;
+
+    tri->klm[2].x = 2.0f / 3.0f;
+    tri->klm[2].y = 1.0f / 3.0f;
+    tri->klm[2].z = 2.0f / 3.0f;
+
+    tri->klm[3].x = 1.0f;
+    tri->klm[3].y = 1.0f;
+    tri->klm[3].z = 1.0f;
+
+    if (d->z < 0.0f)
+        tri->reverse = 1;
+    else
+        tri->reverse = 0;
+}
+
+/* From GPU Gems 3, Chapter 25: Rendering Vector Art on the GPU. */
+static void d2d_geometry_classify_bezier(struct d2d_geometry *geometry, struct d2d_cubic_triangulation *triangles,
+    const struct d2d_segment_idx *idx)
+{
+    struct d2d_figure *figure;
+    struct d2d_cubic_triangles *tri;
+    struct d2d_vec3 p_v[4], tmp, d;
+    const D2D1_POINT_2F *p[4];
+    float a[3], discriminant, cusp_check;
+    unsigned int i;
+
+    tri = &triangles[idx->figure_idx].cubic_tri[idx->control_idx];
+    figure = &geometry->u.path.figures[idx->figure_idx];
+    p[0] = &figure->vertices[idx->vertex_idx];
+    p[1] = &figure->bezier_controls[idx->control_idx].c0;
+    p[2] = &figure->bezier_controls[idx->control_idx].c1;
+    if (idx->vertex_idx == figure->vertex_count - 1)
+        p[3] = &figure->vertices[0];
+    else
+        p[3] = &figure->vertices[idx->vertex_idx + 1];
+
+    /* Before doing any math, lets make sure that what we have isn't just a
+     * point or a line. If it is, it will be ignored. */
+    if (d2d_point_approximately_equal(p[0], p[1]) && d2d_point_approximately_equal(p[0], p[2])
+                && d2d_point_approximately_equal(p[0], p[3]))
+    {
+        tri->type = BEZIER_TYPE_LINE;
+        return;
+    }
+
+    for (i = 0; i < 4; i++)
+        d2d_point_to_vec3(&p_v[i], p[i]);
+
+    d2d_vec3_cross_product(&tmp, &p_v[3], &p_v[2]);
+    a[0] = d2d_vec3_dot_product(&p_v[0], &tmp);
+
+    d2d_vec3_cross_product(&tmp, &p_v[0], &p_v[3]);
+    a[1] = d2d_vec3_dot_product(&p_v[1], &tmp);
+
+    d2d_vec3_cross_product(&tmp, &p_v[1], &p_v[0]);
+    a[2] = d2d_vec3_dot_product(&p_v[2], &tmp);
+
+    d.x = a[0] - 2.0f * a[1] + 3.0f * a[2];
+    d.y = -a[1] + 3.0f * a[2];
+    d.z = 3.0f * a[2];
+
+    /* Not mentioned in the GPU Gems article, but the results of these
+     * computations need to be normalized, otherwise floating point overflows
+     * start to occur. */
+    d2d_vec3_normalize(&d);
+
+    /* Mentioned in 'Resolution Independent Curve Rendering using Programmable
+     * Graphics Hardware', the value cusp_check is used when getting the k, l,
+     * and m texture coordinates for the cusp case. If the cusp has an
+     * inflection point at infinity, cusp_check should be 0. */
+    cusp_check = 3.0f * d.y * d.y - 4.0f * d.x * d.z;
+    discriminant = d.x * d.x * cusp_check;
+
+    /* Need to round these values to 0, because there's issues with
+     * classification otherwise. */
+    d2d_vec3_round_to_zero(&d);
+    discriminant = d2d_cubic_bezier_round_to_zero(discriminant);
+
+    if (discriminant > 0.0f)
+    {
+        tri->type = BEZIER_TYPE_SERP;
+        d2d_geometry_get_bezier_serp_coords(&d, tri);
+    }
+    else if (discriminant < 0.0f)
+    {
+        tri->type = BEZIER_TYPE_LOOP;
+        /* Check to see if it's the type of loop that has an overlap within
+         * the t = 0 through t = 1 range. If it is, we'll need to split it
+         * into two separate beziers to avoid rendering artifacts. */
+        if (!d2d_geometry_get_bezier_loop_coords(&d, tri))
+        {
+            d2d_geometry_split_bezier(geometry, idx, triangles);
+            d2d_geometry_classify_bezier(geometry, triangles, idx);
+            return;
+        }
+    }
+    else
+    {
+        if (d.x == 0.0f && d.y == 0.0f)
+        {
+            if (d.z == 0.0f)
+            {
+                tri->type = BEZIER_TYPE_LINE;
+                return;
+            }
+            else
+            {
+                tri->type = BEZIER_TYPE_QUAD;
+                d2d_geometry_get_bezier_quad_coords(&d, tri);
+            }
+        }
+        else
+        {
+            if (d.x == 0.0f)
+            {
+                tri->type = BEZIER_TYPE_CUSP;
+                d2d_geometry_get_bezier_cusp_coords(&d, tri);
+            }
+            else if (cusp_check < 0.0f)
+            {
+                tri->type = BEZIER_TYPE_LOOP;
+                d2d_geometry_get_bezier_loop_coords(&d, tri);
+            }
+            else
+            {
+                tri->type = BEZIER_TYPE_SERP;
+                d2d_geometry_get_bezier_serp_coords(&d, tri);
+            }
+        }
+    }
+
+    tri->fill_side = triangles->orientation ^ tri->inside ? FILL_LEFT : FILL_RIGHT;
+
+    if (tri->fill_side == FILL_RIGHT)
+        tri->reverse = !tri->reverse;
+    if (tri->reverse)
+        d2d_geometry_reverse_bezier_coords(tri);
+}
+
 static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
 {
     struct d2d_cubic_triangulation *triangles;
@@ -3538,6 +3861,14 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
     }
 
     d2d_geometry_get_figure_orientation(geometry, triangles);
+    d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p);
+    for (;;)
+    {
+        d2d_geometry_classify_bezier(geometry, triangles, &idx_p);
+
+        if (!d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p))
+            break;
+    }
 
     for (i = 0; i < geometry->u.path.figure_count; ++i)
     {
-- 
2.20.1

[PATCH 12/12] d2d1: Render cubic beziers.

[Connor McAdams]

Store coordinates for rendering cubic bezier and modify pixel shader for
rendering cubic beziers.

Signed-off-by: Connor McAdams <conmanx360(a)gmail.com>
---
 dlls/d2d1/d2d1_private.h |   2 +-
 dlls/d2d1/device.c       | 350 +++++++++++++++++++--------------------
 dlls/d2d1/geometry.c     |  72 +++++---
 3 files changed, 224 insertions(+), 200 deletions(-)

diff --git a/dlls/d2d1/d2d1_private.h b/dlls/d2d1/d2d1_private.h
index 62c9d222fa..cc8a2b67d3 100644
--- a/dlls/d2d1/d2d1_private.h
+++ b/dlls/d2d1/d2d1_private.h
@@ -393,7 +393,7 @@ struct d2d_bezier_vertex
     D2D1_POINT_2F position;
     struct
     {
-        float u, v, sign;
+        float k, l, m;
     } texcoord;
 };
 
diff --git a/dlls/d2d1/device.c b/dlls/d2d1/device.c
index 0ab6e53f5f..93e9c61cfe 100644
--- a/dlls/d2d1/device.c
+++ b/dlls/d2d1/device.c
@@ -3300,20 +3300,21 @@ static HRESULT d2d_device_context_init(struct d2d_device_context *render_target,
                 /* Evaluate the implicit form of the curve in texture space.
                  * "i.b.z" determines which side of the curve is shaded. */
                 clip((i.b.x * i.b.x - i.b.y) * i.b.z);
+                clip(i.b.x * i.b.x * i.b.x - i.b.y * i.b.z);
             }
 
             return colour;
         }
 #endif
-        0x43425844, 0xf3cbb8bd, 0x5f286454, 0x139976a7, 0x6817e876, 0x00000001, 0x00001d18, 0x00000003,
+        0x43425844, 0xad9a265b, 0xacf926bb, 0xeaa1c90b, 0xf1512f75, 0x00000001, 0x00001cf0, 0x00000003,
         0x0000002c, 0x000000c4, 0x000000f8, 0x4e475349, 0x00000090, 0x00000004, 0x00000008, 0x00000068,
         0x00000000, 0x00000000, 0x00000003, 0x00000000, 0x00000303, 0x00000077, 0x00000000, 0x00000000,
         0x00000003, 0x00000001, 0x00000f0f, 0x0000007e, 0x00000000, 0x00000000, 0x00000003, 0x00000002,
         0x00000303, 0x0000007e, 0x00000001, 0x00000000, 0x00000003, 0x00000003, 0x00000303, 0x4c524f57,
         0x4f505f44, 0x49544953, 0x42004e4f, 0x45495a45, 0x54530052, 0x454b4f52, 0x4152545f, 0x4f46534e,
         0xab004d52, 0x4e47534f, 0x0000002c, 0x00000001, 0x00000008, 0x00000020, 0x00000000, 0x00000000,
-        0x00000003, 0x00000000, 0x0000000f, 0x545f5653, 0x65677261, 0xabab0074, 0x52444853, 0x00001c18,
-        0x00000040, 0x00000706, 0x04000059, 0x00208e46, 0x00000000, 0x00000009, 0x0300005a, 0x00106000,
+        0x00000003, 0x00000000, 0x0000000f, 0x545f5653, 0x65677261, 0xabab0074, 0x52444853, 0x00001bf0,
+        0x00000040, 0x000006fc, 0x04000059, 0x00208e46, 0x00000000, 0x00000009, 0x0300005a, 0x00106000,
         0x00000000, 0x0300005a, 0x00106000, 0x00000001, 0x04001858, 0x00107000, 0x00000000, 0x00005555,
         0x04001858, 0x00107000, 0x00000001, 0x00005555, 0x04000858, 0x00107000, 0x00000002, 0x00005555,
         0x04000858, 0x00107000, 0x00000003, 0x00005555, 0x03001062, 0x00101032, 0x00000000, 0x03001062,
@@ -3346,95 +3347,143 @@ static HRESULT d2d_device_context_init(struct d2d_device_context *render_target,
         0x00000002, 0x8010002a, 0x00000041, 0x00000001, 0x0010001a, 0x00000001, 0x08000000, 0x00100022,
         0x00000007, 0x8010002a, 0x00000041, 0x00000001, 0x0010000a, 0x00000007, 0x0700000e, 0x00100082,
         0x00000002, 0x0010003a, 0x00000002, 0x0010001a, 0x00000007, 0x08000000, 0x001000f2, 0x00000009,
-        0x80100e46, 0x00000041, 0x00000005, 0x00100e46, 0x00000008, 0x09000032, 0x001000f2, 0x00000009,
+        0x80100e46, 0x00000041, 0x00000005, 0x00100e46, 0x00000008, 0x09000032, 0x001000f2, 0x00000004,
         0x00100ff6, 0x00000002, 0x00100e46, 0x00000009, 0x00100e46, 0x00000005, 0x05000036, 0x001000f2,
         0x00000006, 0x00100e46, 0x00000008, 0x05000036, 0x00100022, 0x00000002, 0x00004001, 0xffffffff,
-        0x05000036, 0x001000f2, 0x00000004, 0x00100e46, 0x00000009, 0x01000002, 0x01000015, 0x05000036,
-        0x001000f2, 0x00000005, 0x00100e46, 0x00000008, 0x05000036, 0x00100042, 0x00000001, 0x0010000a,
-        0x00000007, 0x0700001e, 0x00100082, 0x00000001, 0x0010003a, 0x00000001, 0x00004001, 0x00000001,
-        0x05000036, 0x001000f2, 0x00000006, 0x00100e46, 0x00000008, 0x05000036, 0x00100022, 0x00000002,
-        0x0010002a, 0x00000002, 0x01000016, 0x09000037, 0x001000f2, 0x00000003, 0x00100556, 0x00000002,
-        0x00100e46, 0x00000004, 0x00100e46, 0x00000006, 0x01000015, 0x08000038, 0x001000f2, 0x00000000,
-        0x00100e46, 0x00000003, 0x00208556, 0x00000000, 0x00000001, 0x01000015, 0x0300001f, 0x0010000a,
-        0x00000001, 0x08000020, 0x00100012, 0x00000001, 0x0020800a, 0x00000000, 0x00000001, 0x00004001,
-        0x00000002, 0x0304001f, 0x0010000a, 0x00000001, 0x0900000f, 0x00100012, 0x00000002, 0x00208046,
-        0x00000000, 0x00000003, 0x00208046, 0x00000000, 0x00000003, 0x0900000f, 0x00100022, 0x00000002,
-        0x00208ae6, 0x00000000, 0x00000003, 0x00208ae6, 0x00000000, 0x00000003, 0x09000000, 0x00100062,
-        0x00000001, 0x00208ba6, 0x00000000, 0x00000002, 0x00208106, 0x00000000, 0x00000002, 0x08000000,
-        0x00100062, 0x00000001, 0x80100656, 0x00000041, 0x00000001, 0x00101106, 0x00000000, 0x0800000f,
-        0x00100012, 0x00000003, 0x00100596, 0x00000001, 0x00208046, 0x00000000, 0x00000003, 0x0800000f,
-        0x00100022, 0x00000003, 0x00100596, 0x00000001, 0x00208ae6, 0x00000000, 0x00000003, 0x0700000e,
-        0x00100062, 0x00000001, 0x00100106, 0x00000003, 0x00100106, 0x00000002, 0x0900000f, 0x00100012,
-        0x00000003, 0x00208ae6, 0x00000000, 0x00000002, 0x00208046, 0x00000000, 0x00000003, 0x0900000f,
-        0x00100022, 0x00000003, 0x00208ae6, 0x00000000, 0x00000002, 0x00208ae6, 0x00000000, 0x00000003,
-        0x0700000e, 0x00100032, 0x00000002, 0x00100046, 0x00000003, 0x00100046, 0x00000002, 0x0700000f,
-        0x00100082, 0x00000001, 0x00100596, 0x00000001, 0x00100596, 0x00000001, 0x0500004b, 0x00100082,
-        0x00000001, 0x0010003a, 0x00000001, 0x0700000f, 0x00100022, 0x00000001, 0x00100596, 0x00000001,
-        0x00100046, 0x00000002, 0x0700000e, 0x00100022, 0x00000001, 0x0010001a, 0x00000001, 0x0010003a,
-        0x00000001, 0x0700000f, 0x00100042, 0x00000001, 0x00100046, 0x00000002, 0x00100046, 0x00000002,
-        0x07000000, 0x00100042, 0x00000001, 0x0010002a, 0x00000001, 0x00004001, 0xbf800000, 0x0a000032,
-        0x00100042, 0x00000001, 0x0010001a, 0x00000001, 0x0010001a, 0x00000001, 0x8010002a, 0x00000041,
-        0x00000001, 0x0500004b, 0x00100042, 0x00000001, 0x0010002a, 0x00000001, 0x08000000, 0x00100022,
-        0x00000001, 0x0010002a, 0x00000001, 0x8010001a, 0x00000041, 0x00000001, 0x0700000e, 0x00100022,
-        0x00000001, 0x0010003a, 0x00000001, 0x0010001a, 0x00000001, 0x0a00002d, 0x001000f2, 0x00000002,
-        0x00004002, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00107e46, 0x00000002, 0x0a00002d,
-        0x001000f2, 0x00000003, 0x00004002, 0x00000001, 0x00000001, 0x00000001, 0x00000001, 0x00107e46,
-        0x00000002, 0x0700001d, 0x00100042, 0x00000001, 0x0010001a, 0x00000001, 0x0010000a, 0x00000002,
-        0x0304001f, 0x0010002a, 0x00000001, 0x05000036, 0x001000f2, 0x00000004, 0x00100e46, 0x00000003,
-        0x05000036, 0x001000f2, 0x00000005, 0x00100e46, 0x00000003, 0x05000036, 0x001000f2, 0x00000006,
-        0x00100e46, 0x00000003, 0x05000036, 0x00100042, 0x00000001, 0x0010000a, 0x00000002, 0x05000036,
-        0x00100082, 0x00000001, 0x00004001, 0x00000001, 0x05000036, 0x00100022, 0x00000002, 0x00004001,
-        0x00000000, 0x01000030, 0x08000050, 0x00100042, 0x00000002, 0x0010003a, 0x00000001, 0x0020800a,
-        0x00000000, 0x00000004, 0x05000036, 0x00100022, 0x00000002, 0x00004001, 0x00000000, 0x03040003,
-        0x0010002a, 0x00000002, 0x07000029, 0x00100042, 0x00000002, 0x0010003a, 0x00000001, 0x00004001,
-        0x00000001, 0x0700002d, 0x001000f2, 0x00000007, 0x00100aa6, 0x00000002, 0x00107e46, 0x00000002,
-        0x0700001e, 0x00100042, 0x00000002, 0x0010002a, 0x00000002, 0x00004001, 0x00000001, 0x0700002d,
-        0x001000f2, 0x00000008, 0x00100aa6, 0x00000002, 0x00107e46, 0x00000002, 0x0700001d, 0x00100042,
-        0x00000002, 0x0010001a, 0x00000001, 0x0010002a, 0x00000001, 0x0700001d, 0x00100082, 0x00000002,
-        0x0010000a, 0x00000007, 0x0010001a, 0x00000001, 0x07000001, 0x00100042, 0x00000002, 0x0010003a,
-        0x00000002, 0x0010002a, 0x00000002, 0x0304001f, 0x0010002a, 0x00000002, 0x08000000, 0x00100082,
-        0x00000002, 0x8010002a, 0x00000041, 0x00000001, 0x0010001a, 0x00000001, 0x08000000, 0x00100022,
-        0x00000007, 0x8010002a, 0x00000041, 0x00000001, 0x0010000a, 0x00000007, 0x0700000e, 0x00100082,
-        0x00000002, 0x0010003a, 0x00000002, 0x0010001a, 0x00000007, 0x08000000, 0x001000f2, 0x00000009,
-        0x80100e46, 0x00000041, 0x00000005, 0x00100e46, 0x00000008, 0x09000032, 0x001000f2, 0x00000009,
-        0x00100ff6, 0x00000002, 0x00100e46, 0x00000009, 0x00100e46, 0x00000005, 0x05000036, 0x001000f2,
-        0x00000006, 0x00100e46, 0x00000008, 0x05000036, 0x00100022, 0x00000002, 0x00004001, 0xffffffff,
-        0x05000036, 0x001000f2, 0x00000004, 0x00100e46, 0x00000009, 0x01000002, 0x01000015, 0x05000036,
-        0x001000f2, 0x00000005, 0x00100e46, 0x00000008, 0x05000036, 0x00100042, 0x00000001, 0x0010000a,
-        0x00000007, 0x0700001e, 0x00100082, 0x00000001, 0x0010003a, 0x00000001, 0x00004001, 0x00000001,
-        0x05000036, 0x001000f2, 0x00000006, 0x00100e46, 0x00000008, 0x05000036, 0x00100022, 0x00000002,
-        0x0010002a, 0x00000002, 0x01000016, 0x09000037, 0x001000f2, 0x00000003, 0x00100556, 0x00000002,
-        0x00100e46, 0x00000004, 0x00100e46, 0x00000006, 0x01000015, 0x08000038, 0x001000f2, 0x00000000,
-        0x00100e46, 0x00000003, 0x00208556, 0x00000000, 0x00000001, 0x01000015, 0x0300001f, 0x0010000a,
-        0x00000001, 0x08000020, 0x00100012, 0x00000001, 0x0020800a, 0x00000000, 0x00000001, 0x00004001,
-        0x00000003, 0x0304001f, 0x0010000a, 0x00000001, 0x0800000f, 0x00100022, 0x00000001, 0x00101046,
-        0x00000000, 0x00208046, 0x00000000, 0x00000002, 0x08000000, 0x00100012, 0x00000002, 0x0010001a,
-        0x00000001, 0x0020802a, 0x00000000, 0x00000002, 0x0800000f, 0x00100022, 0x00000001, 0x00101046,
-        0x00000000, 0x00208046, 0x00000000, 0x00000003, 0x08000000, 0x00100022, 0x00000002, 0x0010001a,
-        0x00000001, 0x0020802a, 0x00000000, 0x00000003, 0x09000045, 0x001000f2, 0x00000002, 0x00100046,
-        0x00000002, 0x00107e46, 0x00000000, 0x00106000, 0x00000000, 0x0a000037, 0x00100082, 0x00000002,
-        0x0020803a, 0x00000000, 0x00000003, 0x00004001, 0x3f800000, 0x0010003a, 0x00000002, 0x08000038,
-        0x001000f2, 0x00000000, 0x00100e46, 0x00000002, 0x00208556, 0x00000000, 0x00000001, 0x01000015,
-        0x05000036, 0x00100012, 0x00000002, 0x00004001, 0x00000000, 0x06000036, 0x00100082, 0x00000002,
-        0x0020801a, 0x00000000, 0x00000001, 0x09000037, 0x001000f2, 0x00000000, 0x00100006, 0x00000001,
-        0x00100e46, 0x00000000, 0x00100c06, 0x00000002, 0x01000015, 0x01000015, 0x01000015, 0x0800004f,
-        0x00100012, 0x00000001, 0x0020800a, 0x00000000, 0x00000005, 0x00004001, 0x00000004, 0x0304001f,
-        0x0010000a, 0x00000001, 0x09000038, 0x00100012, 0x00000001, 0x0020801a, 0x00000000, 0x00000005,
-        0x0020803a, 0x00000000, 0x00000006, 0x0404001f, 0x0020800a, 0x00000000, 0x00000005, 0x08000020,
-        0x00100022, 0x00000001, 0x0020800a, 0x00000000, 0x00000005, 0x00004001, 0x00000001, 0x0304001f,
-        0x0010001a, 0x00000001, 0x09000000, 0x001000c2, 0x00000001, 0x00101406, 0x00000000, 0x80208406,
-        0x00000041, 0x00000000, 0x00000006, 0x0a000000, 0x00100032, 0x00000002, 0x80208046, 0x00000041,
-        0x00000000, 0x00000006, 0x00208ae6, 0x00000000, 0x00000006, 0x0700000f, 0x00100042, 0x00000001,
-        0x00100046, 0x00000002, 0x00100ae6, 0x00000001, 0x0700000f, 0x00100082, 0x00000001, 0x00100046,
-        0x00000002, 0x00100046, 0x00000002, 0x0700000e, 0x00100042, 0x00000001, 0x0010002a, 0x00000001,
-        0x0010003a, 0x00000001, 0x0a00002d, 0x001000f2, 0x00000002, 0x00004002, 0x00000000, 0x00000000,
+        0x01000002, 0x01000015, 0x0700001e, 0x00100082, 0x00000001, 0x0010003a, 0x00000001, 0x00004001,
+        0x00000001, 0x05000036, 0x001000f2, 0x00000005, 0x00100e46, 0x00000008, 0x05000036, 0x00100042,
+        0x00000001, 0x0010000a, 0x00000007, 0x05000036, 0x001000f2, 0x00000006, 0x00100e46, 0x00000008,
+        0x05000036, 0x00100022, 0x00000002, 0x0010002a, 0x00000002, 0x01000016, 0x09000037, 0x001000f2,
+        0x00000003, 0x00100556, 0x00000002, 0x00100e46, 0x00000004, 0x00100e46, 0x00000006, 0x01000015,
+        0x08000038, 0x001000f2, 0x00000000, 0x00100e46, 0x00000003, 0x00208556, 0x00000000, 0x00000001,
+        0x01000015, 0x0300001f, 0x0010000a, 0x00000001, 0x08000020, 0x00100012, 0x00000001, 0x0020800a,
+        0x00000000, 0x00000001, 0x00004001, 0x00000002, 0x0304001f, 0x0010000a, 0x00000001, 0x0900000f,
+        0x00100012, 0x00000002, 0x00208046, 0x00000000, 0x00000003, 0x00208046, 0x00000000, 0x00000003,
+        0x0900000f, 0x00100022, 0x00000002, 0x00208ae6, 0x00000000, 0x00000003, 0x00208ae6, 0x00000000,
+        0x00000003, 0x09000000, 0x00100062, 0x00000001, 0x00208ba6, 0x00000000, 0x00000002, 0x00208106,
+        0x00000000, 0x00000002, 0x08000000, 0x00100062, 0x00000001, 0x80100656, 0x00000041, 0x00000001,
+        0x00101106, 0x00000000, 0x0800000f, 0x00100012, 0x00000003, 0x00100596, 0x00000001, 0x00208046,
+        0x00000000, 0x00000003, 0x0800000f, 0x00100022, 0x00000003, 0x00100596, 0x00000001, 0x00208ae6,
+        0x00000000, 0x00000003, 0x0700000e, 0x00100062, 0x00000001, 0x00100106, 0x00000003, 0x00100106,
+        0x00000002, 0x0900000f, 0x00100012, 0x00000003, 0x00208ae6, 0x00000000, 0x00000002, 0x00208046,
+        0x00000000, 0x00000003, 0x0900000f, 0x00100022, 0x00000003, 0x00208ae6, 0x00000000, 0x00000002,
+        0x00208ae6, 0x00000000, 0x00000003, 0x0700000e, 0x00100032, 0x00000002, 0x00100046, 0x00000003,
+        0x00100046, 0x00000002, 0x0700000f, 0x00100082, 0x00000001, 0x00100596, 0x00000001, 0x00100596,
+        0x00000001, 0x0500004b, 0x00100082, 0x00000001, 0x0010003a, 0x00000001, 0x0700000f, 0x00100022,
+        0x00000001, 0x00100596, 0x00000001, 0x00100046, 0x00000002, 0x0700000e, 0x00100022, 0x00000001,
+        0x0010001a, 0x00000001, 0x0010003a, 0x00000001, 0x0700000f, 0x00100042, 0x00000001, 0x00100046,
+        0x00000002, 0x00100046, 0x00000002, 0x07000000, 0x00100042, 0x00000001, 0x0010002a, 0x00000001,
+        0x00004001, 0xbf800000, 0x0a000032, 0x00100042, 0x00000001, 0x0010001a, 0x00000001, 0x0010001a,
+        0x00000001, 0x8010002a, 0x00000041, 0x00000001, 0x0500004b, 0x00100042, 0x00000001, 0x0010002a,
+        0x00000001, 0x08000000, 0x00100012, 0x00000002, 0x0010002a, 0x00000001, 0x8010001a, 0x00000041,
+        0x00000001, 0x0700000e, 0x00100022, 0x00000001, 0x0010003a, 0x00000001, 0x0010000a, 0x00000002,
+        0x0a00002d, 0x001000f2, 0x00000002, 0x00004002, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
+        0x00107e46, 0x00000002, 0x0a00002d, 0x001000f2, 0x00000003, 0x00004002, 0x00000001, 0x00000001,
+        0x00000001, 0x00000001, 0x00107e46, 0x00000002, 0x0700001d, 0x00100042, 0x00000001, 0x0010001a,
+        0x00000001, 0x0010000a, 0x00000002, 0x0304001f, 0x0010002a, 0x00000001, 0x05000036, 0x001000f2,
+        0x00000004, 0x00100e46, 0x00000003, 0x05000036, 0x001000f2, 0x00000005, 0x00100e46, 0x00000003,
+        0x05000036, 0x001000f2, 0x00000006, 0x00100e46, 0x00000003, 0x05000036, 0x00100042, 0x00000001,
+        0x0010000a, 0x00000002, 0x05000036, 0x00100082, 0x00000001, 0x00004001, 0x00000001, 0x05000036,
+        0x00100022, 0x00000002, 0x00004001, 0x00000000, 0x01000030, 0x08000050, 0x00100042, 0x00000002,
+        0x0010003a, 0x00000001, 0x0020800a, 0x00000000, 0x00000004, 0x05000036, 0x00100022, 0x00000002,
+        0x00004001, 0x00000000, 0x03040003, 0x0010002a, 0x00000002, 0x07000029, 0x00100042, 0x00000002,
+        0x0010003a, 0x00000001, 0x00004001, 0x00000001, 0x0700002d, 0x001000f2, 0x00000007, 0x00100aa6,
+        0x00000002, 0x00107e46, 0x00000002, 0x0700001e, 0x00100042, 0x00000002, 0x0010002a, 0x00000002,
+        0x00004001, 0x00000001, 0x0700002d, 0x001000f2, 0x00000008, 0x00100aa6, 0x00000002, 0x00107e46,
+        0x00000002, 0x0700001d, 0x00100042, 0x00000002, 0x0010001a, 0x00000001, 0x0010002a, 0x00000001,
+        0x0700001d, 0x00100082, 0x00000002, 0x0010000a, 0x00000007, 0x0010001a, 0x00000001, 0x07000001,
+        0x00100042, 0x00000002, 0x0010003a, 0x00000002, 0x0010002a, 0x00000002, 0x0304001f, 0x0010002a,
+        0x00000002, 0x08000000, 0x00100082, 0x00000002, 0x8010002a, 0x00000041, 0x00000001, 0x0010001a,
+        0x00000001, 0x08000000, 0x00100022, 0x00000007, 0x8010002a, 0x00000041, 0x00000001, 0x0010000a,
+        0x00000007, 0x0700000e, 0x00100082, 0x00000002, 0x0010003a, 0x00000002, 0x0010001a, 0x00000007,
+        0x08000000, 0x001000f2, 0x00000009, 0x80100e46, 0x00000041, 0x00000005, 0x00100e46, 0x00000008,
+        0x09000032, 0x001000f2, 0x00000004, 0x00100ff6, 0x00000002, 0x00100e46, 0x00000009, 0x00100e46,
+        0x00000005, 0x05000036, 0x001000f2, 0x00000006, 0x00100e46, 0x00000008, 0x05000036, 0x00100022,
+        0x00000002, 0x00004001, 0xffffffff, 0x01000002, 0x01000015, 0x0700001e, 0x00100082, 0x00000001,
+        0x0010003a, 0x00000001, 0x00004001, 0x00000001, 0x05000036, 0x001000f2, 0x00000005, 0x00100e46,
+        0x00000008, 0x05000036, 0x00100042, 0x00000001, 0x0010000a, 0x00000007, 0x05000036, 0x001000f2,
+        0x00000006, 0x00100e46, 0x00000008, 0x05000036, 0x00100022, 0x00000002, 0x0010002a, 0x00000002,
+        0x01000016, 0x09000037, 0x001000f2, 0x00000003, 0x00100556, 0x00000002, 0x00100e46, 0x00000004,
+        0x00100e46, 0x00000006, 0x01000015, 0x08000038, 0x001000f2, 0x00000000, 0x00100e46, 0x00000003,
+        0x00208556, 0x00000000, 0x00000001, 0x01000015, 0x0300001f, 0x0010000a, 0x00000001, 0x08000020,
+        0x00100012, 0x00000001, 0x0020800a, 0x00000000, 0x00000001, 0x00004001, 0x00000003, 0x0304001f,
+        0x0010000a, 0x00000001, 0x0800000f, 0x00100022, 0x00000001, 0x00101046, 0x00000000, 0x00208046,
+        0x00000000, 0x00000002, 0x08000000, 0x00100012, 0x00000002, 0x0010001a, 0x00000001, 0x0020802a,
+        0x00000000, 0x00000002, 0x0800000f, 0x00100022, 0x00000001, 0x00101046, 0x00000000, 0x00208046,
+        0x00000000, 0x00000003, 0x08000000, 0x00100022, 0x00000002, 0x0010001a, 0x00000001, 0x0020802a,
+        0x00000000, 0x00000003, 0x09000045, 0x001000f2, 0x00000002, 0x00100046, 0x00000002, 0x00107e46,
+        0x00000000, 0x00106000, 0x00000000, 0x0a000037, 0x00100082, 0x00000002, 0x0020803a, 0x00000000,
+        0x00000003, 0x00004001, 0x3f800000, 0x0010003a, 0x00000002, 0x08000038, 0x001000f2, 0x00000000,
+        0x00100e46, 0x00000002, 0x00208556, 0x00000000, 0x00000001, 0x01000015, 0x05000036, 0x00100012,
+        0x00000002, 0x00004001, 0x00000000, 0x06000036, 0x00100082, 0x00000002, 0x0020801a, 0x00000000,
+        0x00000001, 0x09000037, 0x001000f2, 0x00000000, 0x00100006, 0x00000001, 0x00100e46, 0x00000000,
+        0x00100c06, 0x00000002, 0x01000015, 0x01000015, 0x01000015, 0x0800004f, 0x00100012, 0x00000001,
+        0x0020800a, 0x00000000, 0x00000005, 0x00004001, 0x00000004, 0x0304001f, 0x0010000a, 0x00000001,
+        0x09000038, 0x00100012, 0x00000001, 0x0020801a, 0x00000000, 0x00000005, 0x0020803a, 0x00000000,
+        0x00000006, 0x0404001f, 0x0020800a, 0x00000000, 0x00000005, 0x08000020, 0x00100022, 0x00000001,
+        0x0020800a, 0x00000000, 0x00000005, 0x00004001, 0x00000001, 0x0304001f, 0x0010001a, 0x00000001,
+        0x09000000, 0x001000c2, 0x00000001, 0x00101406, 0x00000000, 0x80208406, 0x00000041, 0x00000000,
+        0x00000006, 0x0a000000, 0x00100032, 0x00000002, 0x80208046, 0x00000041, 0x00000000, 0x00000006,
+        0x00208ae6, 0x00000000, 0x00000006, 0x0700000f, 0x00100042, 0x00000001, 0x00100046, 0x00000002,
+        0x00100ae6, 0x00000001, 0x0700000f, 0x00100082, 0x00000001, 0x00100046, 0x00000002, 0x00100046,
+        0x00000002, 0x0700000e, 0x00100042, 0x00000001, 0x0010002a, 0x00000001, 0x0010003a, 0x00000001,
+        0x0a00002d, 0x001000f2, 0x00000002, 0x00004002, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
+        0x00107e46, 0x00000003, 0x0a00002d, 0x001000f2, 0x00000003, 0x00004002, 0x00000001, 0x00000001,
+        0x00000001, 0x00000001, 0x00107e46, 0x00000003, 0x0700001d, 0x00100082, 0x00000001, 0x0010002a,
+        0x00000001, 0x0010000a, 0x00000002, 0x0304001f, 0x0010003a, 0x00000001, 0x05000036, 0x00100082,
+        0x00000001, 0x0010003a, 0x00000003, 0x05000036, 0x00100062, 0x00000002, 0x00100ff6, 0x00000003,
+        0x05000036, 0x00100082, 0x00000002, 0x0010000a, 0x00000002, 0x08000036, 0x00100032, 0x00000003,
+        0x00004002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x01000030, 0x08000050, 0x00100042,
+        0x00000003, 0x0010000a, 0x00000003, 0x0020800a, 0x00000000, 0x00000007, 0x05000036, 0x00100022,
+        0x00000003, 0x00004001, 0x00000000, 0x03040003, 0x0010002a, 0x00000003, 0x07000029, 0x00100042,
+        0x00000003, 0x0010000a, 0x00000003, 0x00004001, 0x00000001, 0x0700002d, 0x001000f2, 0x00000004,
+        0x00100aa6, 0x00000003, 0x00107e46, 0x00000003, 0x0700001e, 0x00100042, 0x00000003, 0x0010002a,
+        0x00000003, 0x00004001, 0x00000001, 0x0700002d, 0x001000f2, 0x00000005, 0x00100aa6, 0x00000003,
+        0x00107e46, 0x00000003, 0x0700001d, 0x00100042, 0x00000003, 0x0010002a, 0x00000001, 0x0010003a,
+        0x00000002, 0x0700001d, 0x00100022, 0x00000004, 0x0010000a, 0x00000004, 0x0010002a, 0x00000001,
+        0x07000001, 0x00100042, 0x00000003, 0x0010002a, 0x00000003, 0x0010001a, 0x00000004, 0x0304001f,
+        0x0010002a, 0x00000003, 0x08000000, 0x00100022, 0x00000004, 0x0010002a, 0x00000001, 0x8010003a,
+        0x00000041, 0x00000002, 0x08000000, 0x00100042, 0x00000004, 0x8010003a, 0x00000041, 0x00000002,
+        0x0010000a, 0x00000004, 0x0700000e, 0x00100022, 0x00000004, 0x0010001a, 0x00000004, 0x0010002a,
+        0x00000004, 0x08000000, 0x00100042, 0x00000004, 0x8010001a, 0x00000041, 0x00000002, 0x0010003a,
+        0x00000005, 0x09000032, 0x00100082, 0x00000001, 0x0010001a, 0x00000004, 0x0010002a, 0x00000004,
+        0x0010001a, 0x00000002, 0x05000036, 0x00100042, 0x00000002, 0x0010003a, 0x00000005, 0x05000036,
+        0x00100022, 0x00000003, 0x00004001, 0xffffffff, 0x01000002, 0x01000015, 0x0700001e, 0x00100012,
+        0x00000003, 0x0010000a, 0x00000003, 0x00004001, 0x00000001, 0x05000036, 0x00100022, 0x00000002,
+        0x0010003a, 0x00000005, 0x05000036, 0x00100082, 0x00000002, 0x0010000a, 0x00000004, 0x05000036,
+        0x00100042, 0x00000002, 0x0010003a, 0x00000005, 0x05000036, 0x00100032, 0x00000003, 0x00100086,
+        0x00000003, 0x01000016, 0x09000037, 0x00100042, 0x00000001, 0x0010001a, 0x00000003, 0x0010003a,
+        0x00000001, 0x0010002a, 0x00000002, 0x01000012, 0x05000036, 0x00100042, 0x00000001, 0x0010003a,
+        0x00000003, 0x01000015, 0x08000038, 0x00100012, 0x00000001, 0x0010002a, 0x00000001, 0x0020801a,
+        0x00000000, 0x00000005, 0x01000015, 0x0300001f, 0x0010001a, 0x00000001, 0x08000020, 0x00100022,
+        0x00000001, 0x0020800a, 0x00000000, 0x00000005, 0x00004001, 0x00000002, 0x0304001f, 0x0010001a,
+        0x00000001, 0x0900000f, 0x00100012, 0x00000002, 0x00208046, 0x00000000, 0x00000007, 0x00208046,
+        0x00000000, 0x00000007, 0x0900000f, 0x00100022, 0x00000002, 0x00208ae6, 0x00000000, 0x00000007,
+        0x00208ae6, 0x00000000, 0x00000007, 0x09000000, 0x001000c2, 0x00000001, 0x00208ea6, 0x00000000,
+        0x00000006, 0x00208406, 0x00000000, 0x00000006, 0x08000000, 0x001000c2, 0x00000001, 0x80100ea6,
+        0x00000041, 0x00000001, 0x00101406, 0x00000000, 0x0800000f, 0x00100012, 0x00000003, 0x00100ae6,
+        0x00000001, 0x00208046, 0x00000000, 0x00000007, 0x0800000f, 0x00100022, 0x00000003, 0x00100ae6,
+        0x00000001, 0x00208ae6, 0x00000000, 0x00000007, 0x0700000e, 0x001000c2, 0x00000001, 0x00100406,
+        0x00000003, 0x00100406, 0x00000002, 0x0900000f, 0x00100012, 0x00000003, 0x00208ae6, 0x00000000,
+        0x00000006, 0x00208046, 0x00000000, 0x00000007, 0x0900000f, 0x00100022, 0x00000003, 0x00208ae6,
+        0x00000000, 0x00000006, 0x00208ae6, 0x00000000, 0x00000007, 0x0700000e, 0x00100032, 0x00000002,
+        0x00100046, 0x00000003, 0x00100046, 0x00000002, 0x0700000f, 0x00100042, 0x00000002, 0x00100ae6,
+        0x00000001, 0x00100ae6, 0x00000001, 0x0500004b, 0x00100042, 0x00000002, 0x0010002a, 0x00000002,
+        0x0700000f, 0x00100042, 0x00000001, 0x00100ae6, 0x00000001, 0x00100046, 0x00000002, 0x0700000e,
+        0x00100042, 0x00000001, 0x0010002a, 0x00000001, 0x0010002a, 0x00000002, 0x0700000f, 0x00100082,
+        0x00000001, 0x00100046, 0x00000002, 0x00100046, 0x00000002, 0x07000000, 0x00100082, 0x00000001,
+        0x0010003a, 0x00000001, 0x00004001, 0xbf800000, 0x0a000032, 0x00100082, 0x00000001, 0x0010002a,
+        0x00000001, 0x0010002a, 0x00000001, 0x8010003a, 0x00000041, 0x00000001, 0x0500004b, 0x00100082,
+        0x00000001, 0x0010003a, 0x00000001, 0x08000000, 0x00100042, 0x00000001, 0x0010003a, 0x00000001,
+        0x8010002a, 0x00000041, 0x00000001, 0x0700000e, 0x00100042, 0x00000001, 0x0010002a, 0x00000002,
+        0x0010002a, 0x00000001, 0x0a00002d, 0x001000f2, 0x00000002, 0x00004002, 0x00000000, 0x00000000,
         0x00000000, 0x00000000, 0x00107e46, 0x00000003, 0x0a00002d, 0x001000f2, 0x00000003, 0x00004002,
         0x00000001, 0x00000001, 0x00000001, 0x00000001, 0x00107e46, 0x00000003, 0x0700001d, 0x00100082,
         0x00000001, 0x0010002a, 0x00000001, 0x0010000a, 0x00000002, 0x0304001f, 0x0010003a, 0x00000001,
         0x05000036, 0x00100082, 0x00000001, 0x0010003a, 0x00000003, 0x05000036, 0x00100062, 0x00000002,
         0x00100ff6, 0x00000003, 0x05000036, 0x00100082, 0x00000002, 0x0010000a, 0x00000002, 0x08000036,
         0x00100032, 0x00000003, 0x00004002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x01000030,
-        0x08000050, 0x00100042, 0x00000003, 0x0010000a, 0x00000003, 0x0020800a, 0x00000000, 0x00000007,
+        0x08000050, 0x00100042, 0x00000003, 0x0010000a, 0x00000003, 0x0020800a, 0x00000000, 0x00000008,
         0x05000036, 0x00100022, 0x00000003, 0x00004001, 0x00000000, 0x03040003, 0x0010002a, 0x00000003,
         0x07000029, 0x00100042, 0x00000003, 0x0010000a, 0x00000003, 0x00004001, 0x00000001, 0x0700002d,
         0x001000f2, 0x00000004, 0x00100aa6, 0x00000003, 0x00107e46, 0x00000003, 0x0700001e, 0x00100042,
@@ -3446,98 +3495,49 @@ static HRESULT d2d_device_context_init(struct d2d_device_context *render_target,
         0x00000001, 0x8010003a, 0x00000041, 0x00000002, 0x08000000, 0x00100042, 0x00000004, 0x8010003a,
         0x00000041, 0x00000002, 0x0010000a, 0x00000004, 0x0700000e, 0x00100022, 0x00000004, 0x0010001a,
         0x00000004, 0x0010002a, 0x00000004, 0x08000000, 0x00100042, 0x00000004, 0x8010001a, 0x00000041,
-        0x00000002, 0x0010003a, 0x00000005, 0x09000032, 0x00100022, 0x00000004, 0x0010001a, 0x00000004,
+        0x00000002, 0x0010003a, 0x00000005, 0x09000032, 0x00100082, 0x00000001, 0x0010001a, 0x00000004,
         0x0010002a, 0x00000004, 0x0010001a, 0x00000002, 0x05000036, 0x00100042, 0x00000002, 0x0010003a,
-        0x00000005, 0x05000036, 0x00100022, 0x00000003, 0x00004001, 0xffffffff, 0x05000036, 0x00100082,
-        0x00000001, 0x0010001a, 0x00000004, 0x01000002, 0x01000015, 0x05000036, 0x00100022, 0x00000002,
-        0x0010003a, 0x00000005, 0x05000036, 0x00100082, 0x00000002, 0x0010000a, 0x00000004, 0x0700001e,
-        0x00100012, 0x00000003, 0x0010000a, 0x00000003, 0x00004001, 0x00000001, 0x05000036, 0x00100042,
-        0x00000002, 0x0010003a, 0x00000005, 0x05000036, 0x00100032, 0x00000003, 0x00100086, 0x00000003,
-        0x01000016, 0x09000037, 0x00100042, 0x00000001, 0x0010001a, 0x00000003, 0x0010003a, 0x00000001,
-        0x0010002a, 0x00000002, 0x01000012, 0x05000036, 0x00100042, 0x00000001, 0x0010003a, 0x00000003,
-        0x01000015, 0x08000038, 0x00100012, 0x00000001, 0x0010002a, 0x00000001, 0x0020801a, 0x00000000,
-        0x00000005, 0x01000015, 0x0300001f, 0x0010001a, 0x00000001, 0x08000020, 0x00100022, 0x00000001,
-        0x0020800a, 0x00000000, 0x00000005, 0x00004001, 0x00000002, 0x0304001f, 0x0010001a, 0x00000001,
-        0x0900000f, 0x00100012, 0x00000002, 0x00208046, 0x00000000, 0x00000007, 0x00208046, 0x00000000,
-        0x00000007, 0x0900000f, 0x00100022, 0x00000002, 0x00208ae6, 0x00000000, 0x00000007, 0x00208ae6,
-        0x00000000, 0x00000007, 0x09000000, 0x001000c2, 0x00000001, 0x00208ea6, 0x00000000, 0x00000006,
-        0x00208406, 0x00000000, 0x00000006, 0x08000000, 0x001000c2, 0x00000001, 0x80100ea6, 0x00000041,
-        0x00000001, 0x00101406, 0x00000000, 0x0800000f, 0x00100012, 0x00000003, 0x00100ae6, 0x00000001,
-        0x00208046, 0x00000000, 0x00000007, 0x0800000f, 0x00100022, 0x00000003, 0x00100ae6, 0x00000001,
-        0x00208ae6, 0x00000000, 0x00000007, 0x0700000e, 0x001000c2, 0x00000001, 0x00100406, 0x00000003,
-        0x00100406, 0x00000002, 0x0900000f, 0x00100012, 0x00000003, 0x00208ae6, 0x00000000, 0x00000006,
-        0x00208046, 0x00000000, 0x00000007, 0x0900000f, 0x00100022, 0x00000003, 0x00208ae6, 0x00000000,
-        0x00000006, 0x00208ae6, 0x00000000, 0x00000007, 0x0700000e, 0x00100032, 0x00000002, 0x00100046,
-        0x00000003, 0x00100046, 0x00000002, 0x0700000f, 0x00100042, 0x00000002, 0x00100ae6, 0x00000001,
-        0x00100ae6, 0x00000001, 0x0500004b, 0x00100042, 0x00000002, 0x0010002a, 0x00000002, 0x0700000f,
-        0x00100042, 0x00000001, 0x00100ae6, 0x00000001, 0x00100046, 0x00000002, 0x0700000e, 0x00100042,
-        0x00000001, 0x0010002a, 0x00000001, 0x0010002a, 0x00000002, 0x0700000f, 0x00100082, 0x00000001,
-        0x00100046, 0x00000002, 0x00100046, 0x00000002, 0x07000000, 0x00100082, 0x00000001, 0x0010003a,
-        0x00000001, 0x00004001, 0xbf800000, 0x0a000032, 0x00100082, 0x00000001, 0x0010002a, 0x00000001,
-        0x0010002a, 0x00000001, 0x8010003a, 0x00000041, 0x00000001, 0x0500004b, 0x00100082, 0x00000001,
-        0x0010003a, 0x00000001, 0x08000000, 0x00100042, 0x00000001, 0x0010003a, 0x00000001, 0x8010002a,
-        0x00000041, 0x00000001, 0x0700000e, 0x00100042, 0x00000001, 0x0010002a, 0x00000002, 0x0010002a,
-        0x00000001, 0x0a00002d, 0x001000f2, 0x00000002, 0x00004002, 0x00000000, 0x00000000, 0x00000000,
-        0x00000000, 0x00107e46, 0x00000003, 0x0a00002d, 0x001000f2, 0x00000003, 0x00004002, 0x00000001,
-        0x00000001, 0x00000001, 0x00000001, 0x00107e46, 0x00000003, 0x0700001d, 0x00100082, 0x00000001,
-        0x0010002a, 0x00000001, 0x0010000a, 0x00000002, 0x0304001f, 0x0010003a, 0x00000001, 0x05000036,
-        0x00100082, 0x00000001, 0x0010003a, 0x00000003, 0x05000036, 0x00100062, 0x00000002, 0x00100ff6,
-        0x00000003, 0x05000036, 0x00100082, 0x00000002, 0x0010000a, 0x00000002, 0x08000036, 0x00100032,
-        0x00000003, 0x00004002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x01000030, 0x08000050,
-        0x00100042, 0x00000003, 0x0010000a, 0x00000003, 0x0020800a, 0x00000000, 0x00000008, 0x05000036,
-        0x00100022, 0x00000003, 0x00004001, 0x00000000, 0x03040003, 0x0010002a, 0x00000003, 0x07000029,
-        0x00100042, 0x00000003, 0x0010000a, 0x00000003, 0x00004001, 0x00000001, 0x0700002d, 0x001000f2,
-        0x00000004, 0x00100aa6, 0x00000003, 0x00107e46, 0x00000003, 0x0700001e, 0x00100042, 0x00000003,
-        0x0010002a, 0x00000003, 0x00004001, 0x00000001, 0x0700002d, 0x001000f2, 0x00000005, 0x00100aa6,
-        0x00000003, 0x00107e46, 0x00000003, 0x0700001d, 0x00100042, 0x00000003, 0x0010002a, 0x00000001,
-        0x0010003a, 0x00000002, 0x0700001d, 0x00100022, 0x00000004, 0x0010000a, 0x00000004, 0x0010002a,
-        0x00000001, 0x07000001, 0x00100042, 0x00000003, 0x0010002a, 0x00000003, 0x0010001a, 0x00000004,
-        0x0304001f, 0x0010002a, 0x00000003, 0x08000000, 0x00100022, 0x00000004, 0x0010002a, 0x00000001,
-        0x8010003a, 0x00000041, 0x00000002, 0x08000000, 0x00100042, 0x00000004, 0x8010003a, 0x00000041,
-        0x00000002, 0x0010000a, 0x00000004, 0x0700000e, 0x00100022, 0x00000004, 0x0010001a, 0x00000004,
-        0x0010002a, 0x00000004, 0x08000000, 0x00100042, 0x00000004, 0x8010001a, 0x00000041, 0x00000002,
-        0x0010003a, 0x00000005, 0x09000032, 0x00100022, 0x00000004, 0x0010001a, 0x00000004, 0x0010002a,
-        0x00000004, 0x0010001a, 0x00000002, 0x05000036, 0x00100042, 0x00000002, 0x0010003a, 0x00000005,
-        0x05000036, 0x00100022, 0x00000003, 0x00004001, 0xffffffff, 0x05000036, 0x00100082, 0x00000001,
-        0x0010001a, 0x00000004, 0x01000002, 0x01000015, 0x05000036, 0x00100022, 0x00000002, 0x0010003a,
-        0x00000005, 0x05000036, 0x00100082, 0x00000002, 0x0010000a, 0x00000004, 0x0700001e, 0x00100012,
-        0x00000003, 0x0010000a, 0x00000003, 0x00004001, 0x00000001, 0x05000036, 0x00100042, 0x00000002,
-        0x0010003a, 0x00000005, 0x05000036, 0x00100032, 0x00000003, 0x00100086, 0x00000003, 0x01000016,
-        0x09000037, 0x00100042, 0x00000001, 0x0010001a, 0x00000003, 0x0010003a, 0x00000001, 0x0010002a,
-        0x00000002, 0x01000012, 0x05000036, 0x00100042, 0x00000001, 0x0010003a, 0x00000003, 0x01000015,
-        0x08000038, 0x00100012, 0x00000001, 0x0010002a, 0x00000001, 0x0020801a, 0x00000000, 0x00000005,
-        0x01000015, 0x0300001f, 0x0010001a, 0x00000001, 0x08000020, 0x00100022, 0x00000001, 0x0020800a,
-        0x00000000, 0x00000005, 0x00004001, 0x00000003, 0x0304001f, 0x0010001a, 0x00000001, 0x0800000f,
-        0x00100042, 0x00000001, 0x00101046, 0x00000000, 0x00208046, 0x00000000, 0x00000006, 0x08000000,
-        0x00100012, 0x00000002, 0x0010002a, 0x00000001, 0x0020802a, 0x00000000, 0x00000006, 0x0800000f,
-        0x00100042, 0x00000001, 0x00101046, 0x00000000, 0x00208046, 0x00000000, 0x00000007, 0x08000000,
-        0x00100022, 0x00000002, 0x0010002a, 0x00000001, 0x0020802a, 0x00000000, 0x00000007, 0x09000045,
-        0x001000f2, 0x00000002, 0x00100046, 0x00000002, 0x00107e46, 0x00000001, 0x00106000, 0x00000001,
-        0x0a000037, 0x00100042, 0x00000001, 0x0020803a, 0x00000000, 0x00000007, 0x00004001, 0x3f800000,
-        0x0010003a, 0x00000002, 0x08000038, 0x00100012, 0x00000001, 0x0010002a, 0x00000001, 0x0020801a,
-        0x00000000, 0x00000005, 0x01000015, 0x0a000037, 0x00100012, 0x00000001, 0x0010001a, 0x00000001,
-        0x0010000a, 0x00000001, 0x0020801a, 0x00000000, 0x00000005, 0x01000015, 0x01000015, 0x01000015,
-        0x07000038, 0x001020f2, 0x00000000, 0x00100e46, 0x00000000, 0x00100006, 0x00000001, 0x01000012,
-        0x05000036, 0x001020f2, 0x00000000, 0x00100e46, 0x00000000, 0x01000015, 0x08000027, 0x00100012,
-        0x00000000, 0x0020800a, 0x00000000, 0x00000000, 0x00004001, 0x00000000, 0x0500003b, 0x00100022,
-        0x00000000, 0x0010000a, 0x00000000, 0x0500000b, 0x00100032, 0x00000001, 0x00101046, 0x00000001,
-        0x0500000c, 0x001000c2, 0x00000001, 0x00101406, 0x00000001, 0x07000000, 0x00100042, 0x00000000,
-        0x0010100a, 0x00000001, 0x0010100a, 0x00000001, 0x0a000032, 0x001000c2, 0x00000000, 0x00100aa6,
-        0x00000000, 0x00100806, 0x00000001, 0x80100d56, 0x00000041, 0x00000001, 0x0700000f, 0x00100012,
-        0x00000001, 0x00100ae6, 0x00000000, 0x00101ae6, 0x00000001, 0x07000031, 0x00100012, 0x00000001,
-        0x0010000a, 0x00000001, 0x00004001, 0x00000000, 0x07000001, 0x00100012, 0x00000001, 0x0010000a,
-        0x00000000, 0x0010000a, 0x00000001, 0x0304000d, 0x0010000a, 0x00000001, 0x07000038, 0x00100032,
-        0x00000001, 0x00100ff6, 0x00000000, 0x00101046, 0x00000003, 0x09000032, 0x001000c2, 0x00000000,
-        0x00101406, 0x00000002, 0x00100aa6, 0x00000000, 0x00100406, 0x00000001, 0x0700000f, 0x00100042,
-        0x00000000, 0x00100ae6, 0x00000000, 0x00100ae6, 0x00000000, 0x0500004b, 0x00100042, 0x00000000,
-        0x0010002a, 0x00000000, 0x0a000032, 0x00100082, 0x00000000, 0x0010100a, 0x00000001, 0x0010100a,
-        0x00000001, 0x8010101a, 0x00000041, 0x00000001, 0x08000000, 0x00100042, 0x00000000, 0x8010003a,
-        0x000000c1, 0x00000000, 0x0010002a, 0x00000000, 0x07000031, 0x00100042, 0x00000000, 0x0010002a,
-        0x00000000, 0x00004001, 0x00000000, 0x07000001, 0x00100012, 0x00000000, 0x0010000a, 0x00000000,
-        0x0010002a, 0x00000000, 0x0304000d, 0x0010000a, 0x00000000, 0x07000038, 0x00100012, 0x00000000,
-        0x0010003a, 0x00000000, 0x0010102a, 0x00000001, 0x07000031, 0x00100012, 0x00000000, 0x0010000a,
-        0x00000000, 0x00004001, 0x00000000, 0x07000001, 0x00100012, 0x00000000, 0x0010001a, 0x00000000,
-        0x0010000a, 0x00000000, 0x0304000d, 0x0010000a, 0x00000000, 0x0100003e,
+        0x00000005, 0x05000036, 0x00100022, 0x00000003, 0x00004001, 0xffffffff, 0x01000002, 0x01000015,
+        0x0700001e, 0x00100012, 0x00000003, 0x0010000a, 0x00000003, 0x00004001, 0x00000001, 0x05000036,
+        0x00100022, 0x00000002, 0x0010003a, 0x00000005, 0x05000036, 0x00100082, 0x00000002, 0x0010000a,
+        0x00000004, 0x05000036, 0x00100042, 0x00000002, 0x0010003a, 0x00000005, 0x05000036, 0x00100032,
+        0x00000003, 0x00100086, 0x00000003, 0x01000016, 0x09000037, 0x00100042, 0x00000001, 0x0010001a,
+        0x00000003, 0x0010003a, 0x00000001, 0x0010002a, 0x00000002, 0x01000012, 0x05000036, 0x00100042,
+        0x00000001, 0x0010003a, 0x00000003, 0x01000015, 0x08000038, 0x00100012, 0x00000001, 0x0010002a,
+        0x00000001, 0x0020801a, 0x00000000, 0x00000005, 0x01000015, 0x0300001f, 0x0010001a, 0x00000001,
+        0x08000020, 0x00100022, 0x00000001, 0x0020800a, 0x00000000, 0x00000005, 0x00004001, 0x00000003,
+        0x0304001f, 0x0010001a, 0x00000001, 0x0800000f, 0x00100042, 0x00000001, 0x00101046, 0x00000000,
+        0x00208046, 0x00000000, 0x00000006, 0x08000000, 0x00100012, 0x00000002, 0x0010002a, 0x00000001,
+        0x0020802a, 0x00000000, 0x00000006, 0x0800000f, 0x00100042, 0x00000001, 0x00101046, 0x00000000,
+        0x00208046, 0x00000000, 0x00000007, 0x08000000, 0x00100022, 0x00000002, 0x0010002a, 0x00000001,
+        0x0020802a, 0x00000000, 0x00000007, 0x09000045, 0x001000f2, 0x00000002, 0x00100046, 0x00000002,
+        0x00107e46, 0x00000001, 0x00106000, 0x00000001, 0x0a000037, 0x00100042, 0x00000001, 0x0020803a,
+        0x00000000, 0x00000007, 0x00004001, 0x3f800000, 0x0010003a, 0x00000002, 0x08000038, 0x00100012,
+        0x00000001, 0x0010002a, 0x00000001, 0x0020801a, 0x00000000, 0x00000005, 0x01000015, 0x0a000037,
+        0x00100012, 0x00000001, 0x0010001a, 0x00000001, 0x0010000a, 0x00000001, 0x0020801a, 0x00000000,
+        0x00000005, 0x01000015, 0x01000015, 0x01000015, 0x07000038, 0x001020f2, 0x00000000, 0x00100e46,
+        0x00000000, 0x00100006, 0x00000001, 0x01000012, 0x05000036, 0x001020f2, 0x00000000, 0x00100e46,
+        0x00000000, 0x01000015, 0x08000027, 0x00100012, 0x00000000, 0x0020800a, 0x00000000, 0x00000000,
+        0x00004001, 0x00000000, 0x0500003b, 0x00100022, 0x00000000, 0x0010000a, 0x00000000, 0x0500000b,
+        0x00100032, 0x00000001, 0x00101046, 0x00000001, 0x0500000c, 0x001000c2, 0x00000001, 0x00101406,
+        0x00000001, 0x07000000, 0x00100042, 0x00000000, 0x0010100a, 0x00000001, 0x0010100a, 0x00000001,
+        0x0a000032, 0x001000c2, 0x00000000, 0x00100aa6, 0x00000000, 0x00100806, 0x00000001, 0x80100d56,
+        0x00000041, 0x00000001, 0x0700000f, 0x00100012, 0x00000001, 0x00100ae6, 0x00000000, 0x00101ae6,
+        0x00000001, 0x07000031, 0x00100012, 0x00000001, 0x0010000a, 0x00000001, 0x00004001, 0x00000000,
+        0x07000001, 0x00100012, 0x00000001, 0x0010000a, 0x00000000, 0x0010000a, 0x00000001, 0x0304000d,
+        0x0010000a, 0x00000001, 0x07000038, 0x00100032, 0x00000001, 0x00100ff6, 0x00000000, 0x00101046,
+        0x00000003, 0x09000032, 0x001000c2, 0x00000000, 0x00101406, 0x00000002, 0x00100aa6, 0x00000000,
+        0x00100406, 0x00000001, 0x0700000f, 0x00100042, 0x00000000, 0x00100ae6, 0x00000000, 0x00100ae6,
+        0x00000000, 0x0500004b, 0x00100042, 0x00000000, 0x0010002a, 0x00000000, 0x07000038, 0x00100032,
+        0x00000001, 0x00101086, 0x00000001, 0x00101046, 0x00000001, 0x0a000032, 0x00100082, 0x00000000,
+        0x0010100a, 0x00000001, 0x0010100a, 0x00000001, 0x8010101a, 0x00000041, 0x00000001, 0x08000000,
+        0x00100042, 0x00000000, 0x8010003a, 0x000000c1, 0x00000000, 0x0010002a, 0x00000000, 0x07000031,
+        0x00100042, 0x00000000, 0x0010002a, 0x00000000, 0x00004001, 0x00000000, 0x07000001, 0x00100012,
+        0x00000000, 0x0010000a, 0x00000000, 0x0010002a, 0x00000000, 0x0304000d, 0x0010000a, 0x00000000,
+        0x0a000032, 0x00100012, 0x00000000, 0x0010000a, 0x00000001, 0x0010100a, 0x00000001, 0x8010001a,
+        0x00000041, 0x00000001, 0x07000031, 0x00100012, 0x00000000, 0x0010000a, 0x00000000, 0x00004001,
+        0x00000000, 0x07000001, 0x00100012, 0x00000000, 0x0010001a, 0x00000000, 0x0010000a, 0x00000000,
+        0x0304000d, 0x0010000a, 0x00000000, 0x0100003e,
     };
     static const struct shape_info
     {
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 28c62c58f0..e1f1837a6e 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -136,12 +136,12 @@ struct d2d_fp_fin
 };
 
 static void d2d_bezier_vertex_set(struct d2d_bezier_vertex *b,
-        const D2D1_POINT_2F *p, float u, float v, float sign)
+        const D2D1_POINT_2F *p, float k, float l, float m)
 {
     b->position = *p;
-    b->texcoord.u = u;
-    b->texcoord.v = v;
-    b->texcoord.sign = sign;
+    b->texcoord.k = k;
+    b->texcoord.l = l;
+    b->texcoord.m = m;
 }
 
 static void d2d_face_set(struct d2d_face *f, UINT16 v0, UINT16 v1, UINT16 v2)
@@ -2956,6 +2956,20 @@ struct d2d_cubic_triangulation
     unsigned int orientation;
 };
 
+static int d2d_bezier_get_triangle_count(struct d2d_cubic_triangulation *triangles)
+{
+    int i, count;
+
+    for (i = 0, count = 0; i < triangles->cubic_tri_count; i++)
+    {
+        if (triangles->cubic_tri[i].type == BEZIER_TYPE_LINE)
+            continue;
+        count += triangles->cubic_tri[i].tri_count;
+    }
+
+    return count * 3;
+}
+
 static BOOL d2d_point_approximately_equal(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
 {
     D2D1_POINT_2F length;
@@ -3815,9 +3829,10 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
     struct d2d_cubic_triangulation *triangles;
     struct d2d_segment_idx idx_p, idx_q;
     struct d2d_bezier_vertex *b;
-    const D2D1_POINT_2F *p[3];
+    struct d2d_cubic_triangles *tri;
     struct d2d_figure *figure;
-    size_t bezier_idx, i;
+    unsigned int tri_idx[3];
+    size_t bezier_idx, i, j;
     HRESULT hr;
 
     if (!d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p))
@@ -3874,7 +3889,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
     {
         if (geometry->u.path.figures[i].flags & D2D_FIGURE_FLAG_HOLLOW)
             continue;
-        geometry->fill.bezier_vertex_count += 3 * geometry->u.path.figures[i].bezier_control_count;
+        geometry->fill.bezier_vertex_count += d2d_bezier_get_triangle_count(&triangles[i]);
     }
 
     if (!(geometry->fill.bezier_vertices = heap_calloc(geometry->fill.bezier_vertex_count,
@@ -3889,34 +3904,43 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
     d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p);
     for (;;)
     {
-        float sign = -1.0f;
-
         figure = &geometry->u.path.figures[idx_p.figure_idx];
-        p[0] = &figure->vertices[idx_p.vertex_idx];
-        p[1] = &figure->bezier_controls[idx_p.control_idx].cq0;
+        tri = &triangles[idx_p.figure_idx].cubic_tri[idx_p.control_idx];
+        if (tri->type == BEZIER_TYPE_LINE)
+        {
+            if (!d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p))
+                break;
+            else
+                continue;
+        }
 
         i = idx_p.vertex_idx + 1;
-        if (d2d_path_geometry_point_inside(geometry, p[1], FALSE))
+        if (d2d_path_geometry_point_inside(geometry, &tri->p[1], FALSE))
         {
-            sign = 1.0f;
-            d2d_figure_insert_vertex(figure, i, *p[1]);
-            /* Inserting a vertex potentially invalidates p[0]. */
-            p[0] = &figure->vertices[idx_p.vertex_idx];
+            d2d_figure_insert_vertex(figure, i, tri->p[1]);
             ++i;
         }
 
-        if (i == figure->vertex_count)
-            i = 0;
-        p[2] = &figure->vertices[i];
+        if (d2d_path_geometry_point_inside(geometry, &tri->p[2], FALSE))
+            d2d_figure_insert_vertex(figure, i, tri->p[2]);
 
-        b = &geometry->fill.bezier_vertices[bezier_idx * 3];
-        d2d_bezier_vertex_set(&b[0], p[0], 0.0f, 0.0f, sign);
-        d2d_bezier_vertex_set(&b[1], p[1], 0.5f, 0.0f, sign);
-        d2d_bezier_vertex_set(&b[2], p[2], 1.0f, 1.0f, sign);
+        for (i = 0; i < tri->tri_count; i++)
+        {
+            b = &geometry->fill.bezier_vertices[bezier_idx];
+            tri_idx[0] = tri->triangles[i][0];
+            tri_idx[1] = tri->triangles[i][1];
+            tri_idx[2] = tri->triangles[i][2];
+
+            for (j = 0; j < 3; j++)
+                d2d_bezier_vertex_set(&b[j], &tri->p[tri_idx[j]], tri->klm[tri_idx[j]].x,
+                        tri->klm[tri_idx[j]].y, tri->klm[tri_idx[j]].z);
+
+
+            bezier_idx += 3;
+        }
 
         if (!d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p))
             break;
-        ++bezier_idx;
     }
 
     for (i = 0; i < geometry->u.path.figure_count; i++)
-- 
2.20.1