[RFC PATCH 3/5] d2d1: Add cubic bezier-bezier intersect functions.

[Connor McAdams]

Update bezier-bezier intersection function to handle both cubic and
quadratic beziers.

Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
 dlls/d2d1/geometry.c | 83 +++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 75 insertions(+), 8 deletions(-)

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 33d55c6451..0fb46a9c87 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -439,6 +439,38 @@ static void d2d_bezier_cubic_to_quad(const D2D1_POINT_2F *p0, const D2D1_POINT_2
     c0->y -= (p0->y + p3->y) * 0.25f;
 }
 
+static void d2d_bezier_split_cubic(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1,
+        const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t, D2D1_BEZIER_SEGMENT *left,
+        D2D1_BEZIER_SEGMENT *right, D2D1_POINT_2F *center)
+{
+    D2D1_POINT_2F q[4], r[3], mid;
+
+    d2d_point_lerp(&q[0], p0, p1, t);
+    d2d_point_lerp(&q[1], p1, p2, t);
+    d2d_point_lerp(&q[2], p2, p3, t);
+
+    d2d_point_lerp(&r[0], &q[0], &q[1], t);
+    d2d_point_lerp(&r[1], &q[1], &q[2], t);
+    d2d_point_lerp(&mid, &r[0], &r[1], t);
+
+    if (center)
+        *center = mid;
+
+    if (left)
+    {
+        left->point1 = q[0];
+        left->point2 = r[0];
+        left->point3 = mid;
+    }
+
+    if (right)
+    {
+        right->point1 = r[1];
+        right->point2 = q[2];
+        right->point3 = *p3;
+    }
+}
+
 /* 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. */
@@ -676,8 +708,9 @@ static void d2d_rect_get_cubic_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POIN
 }
 
 
-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)
+static void d2d_rect_get_quadratic_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];
 
@@ -693,6 +726,21 @@ static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_PO
     d2d_rect_get_quadratic_bezier_bounds(bounds, &q[0], &q[1], &q[2]);
 }
 
+static void d2d_rect_get_cubic_bezier_segment_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, float start, float end)
+{
+    D2D1_BEZIER_SEGMENT left, right;
+    D2D1_POINT_2F mid;
+
+    d2d_bezier_split_cubic(p0, p1, p2, p3, start, NULL, &right, &mid);
+
+    end = (end - start) / (1.0f - start);
+    d2d_bezier_split_cubic(&mid, &right.point1, &right.point2, p3, end, &left, NULL, NULL);
+
+    d2d_rect_get_cubic_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)
 {
     if (!d2d_array_reserve((void **)&figure->vertices, &figure->vertices_size,
@@ -1934,31 +1982,46 @@ 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;
+    enum d2d_vertex_type type_p, type_q;
     D2D_RECT_F p_bounds, q_bounds;
     D2D1_POINT_2F intersection;
     float centre_p, centre_q;
     size_t next;
 
     figure = &geometry->u.path.figures[idx_p->figure_idx];
+    type_p = figure->vertex_types[idx_p->vertex_idx];
     p[0] = &figure->vertices[idx_p->vertex_idx];
     p[1] = &figure->bezier_controls[idx_p->control_idx];
+    if (type_p == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+        p[2] = &figure->bezier_controls[idx_p->control_idx + 1];
     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];
+    type_q = figure->vertex_types[idx_q->vertex_idx];
     q[0] = &figure->vertices[idx_q->vertex_idx];
     q[1] = &figure->bezier_controls[idx_q->control_idx];
+    if (type_q == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+        q[2] = &figure->bezier_controls[idx_q->control_idx + 1];
     next = idx_q->vertex_idx + 1;
     if (next == figure->vertex_count)
         next = 0;
-    q[2] = &figure->vertices[next];
+    q[3] = &figure->vertices[next];
+
+    if (type_p == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+        d2d_rect_get_cubic_bezier_segment_bounds(&p_bounds, p[0], p[1], p[2], p[3], start_p, end_p);
+    else
+        d2d_rect_get_quadratic_bezier_segment_bounds(&p_bounds, p[0], p[1], p[3], start_p, end_p);
+
+    if (type_q == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+        d2d_rect_get_cubic_bezier_segment_bounds(&q_bounds, q[0], q[1], q[2], q[3], start_q, end_q);
+    else
+        d2d_rect_get_quadratic_bezier_segment_bounds(&q_bounds, q[0], q[1], q[3], start_q, end_q);
 
-    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);
 
     if (!d2d_rect_check_overlap(&p_bounds, &q_bounds))
         return TRUE;
@@ -1968,7 +2031,11 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
 
     if (end_p - start_p < 1e-3f)
     {
-        d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], centre_p);
+        if (type_p == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+            d2d_point_calculate_cubic_bezier(&intersection, p[0], p[1], p[2], p[3], centre_p);
+        else
+            d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], 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