[RFC PATCH 5/8] d2d1: Implement cubic bezier-line intersection.

Connor McAdams conmanx360 at gmail.com
Mon May 4 14:44:51 CDT 2020


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

diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 49fb517636..3f57cc1852 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -1943,10 +1943,18 @@ 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)
 {
+    const struct d2d_figure *figure;
+    enum d2d_vertex_type type;
     D2D1_POINT_2F intersection;
     float t;
 
-    d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], s);
+    figure = &geometry->u.path.figures[idx_p->figure_idx];
+    type = figure->vertex_types[idx_p->vertex_idx];
+    if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+        d2d_point_calculate_cubic_bezier(&intersection, p[0], p[1], p[2], p[3], s);
+    else
+        d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], 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
@@ -1965,48 +1973,18 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
     return TRUE;
 }
 
-static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
+static BOOL d2d_geometry_get_quadratic_bezier_roots(struct d2d_geometry *geometry,
         struct d2d_geometry_intersections *intersections,
-        const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
+        const struct d2d_segment_idx *idx_p, const D2D1_POINT_2F **p,
+        const struct d2d_segment_idx *idx_q, const D2D1_POINT_2F **q)
 {
-    const D2D1_POINT_2F *p[3], *q[2];
-    const struct d2d_figure *figure;
     float y[3], root, theta, d, e;
-    enum d2d_vertex_type type;
-    D2D1_POINT_2F tmp;
-    size_t next;
-
-    figure = &geometry->u.path.figures[idx_p->figure_idx];
-    type = figure->vertex_types[idx_p->vertex_idx];
-    p[0] = &figure->vertices[idx_p->vertex_idx];
-    next = idx_p->vertex_idx + 1;
-    if (next == figure->vertex_count)
-        next = 0;
-    p[2] = &figure->vertices[next];
-    if (d2d_vertex_type_is_cubic_bezier(type))
-    {
-        d2d_bezier_cubic_to_quad(p[0],
-            &figure->bezier_controls[idx_p->control_idx],
-            &figure->bezier_controls[idx_p->control_idx + 1],
-            p[2], &tmp);
-
-        p[1] = &tmp;
-    }
-    else
-        p[1] = &figure->bezier_controls[idx_p->control_idx];
-
-    figure = &geometry->u.path.figures[idx_q->figure_idx];
-    q[0] = &figure->vertices[idx_q->vertex_idx];
-    next = idx_q->vertex_idx + 1;
-    if (next == figure->vertex_count)
-        next = 0;
-    q[1] = &figure->vertices[next];
 
     /* Align the line with x-axis. */
     theta = -atan2f(q[1]->y - q[0]->y, q[1]->x - q[0]->x);
     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[2] = (p[3]->x - q[0]->x) * sinf(theta) + (p[3]->y - q[0]->y) * cosf(theta);
 
     /* Intersect the transformed curve with the x-axis.
      *
@@ -2053,6 +2031,174 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
     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.0f)
+        return -powf(-a, 1.0f / 3.0f);
+    else
+        return powf(a, 1.0f / 3.0f);
+}
+
+static int d2d_cubic_bezier_get_roots(float *y, float *roots)
+{
+    float mp3, r, t, cosphi, phi, crtr, t1, u1, v1;
+    float p, p_3, q, q2, disc, sd, tmp, a, b, c, d;
+    unsigned int root_count;
+
+    /* 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 * y[0] - 6.0f * y[1] + 3.0f * y[2]);
+    b = (-3.0f * y[0] + 3.0f * y[1]);
+    c = y[0];
+    d = (-y[0] + 3.0f * y[1] - 3.0f * y[2] + y[3]);
+
+    /* Check if the curve is actually a quadratic. */
+    if ((d < 0.0005f && d > -0.0005f))
+    {
+        /* Check if it's actually a line. */
+        if ((a < 0.0005f && a > -0.0005f))
+        {
+            /* Check if it's just a point. If it is, no roots. */
+            if ((b < 0.0005f && b > -0.0005f))
+                return 0;
+
+            roots[0] = -c / b;
+            return 1;
+        }
+
+        return d2d_solve_quadratic_roots(a, b, c, roots);
+    }
+
+    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;
+
+    if ((disc < 0.00005f && disc > -0.00005f))
+        disc = 0.0f;
+
+    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;
+
+        roots[0] = t1 * cosf(phi / 3.0f) - a / 3.0f;
+        roots[1] = t1 * cosf((phi + 2.0f * M_PI) / 3.0f) - a / 3.0f;
+        roots[2] = t1 * cosf((phi + 4.0f * M_PI) / 3.0f) - a / 3.0f;
+
+        root_count = 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);
+
+        roots[0] = 2.0f * tmp - (a / 3.0f);
+        roots[1] = -tmp - (a / 3.0f);
+
+        root_count = 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);
+        roots[0] = u1 - v1 - a / 3.0f;
+
+        root_count = 1;
+    }
+
+    return root_count;
+}
+
+static BOOL d2d_geometry_get_cubic_bezier_roots(struct d2d_geometry *geometry,
+        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 y[4], roots[3], theta;
+    unsigned int num_roots, i;
+
+    /* 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);
+
+    num_roots = d2d_cubic_bezier_get_roots(y, roots);
+
+    for (i = 0; i < num_roots; ++i)
+    {
+        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]))
+                return FALSE;
+        }
+    }
+
+    return TRUE;
+}
+
+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[4], *q[2];
+    const struct d2d_figure *figure;
+    enum d2d_vertex_type type;
+    size_t next;
+
+    figure = &geometry->u.path.figures[idx_p->figure_idx];
+    type = 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 == 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[3] = &figure->vertices[next];
+
+    figure = &geometry->u.path.figures[idx_q->figure_idx];
+    q[0] = &figure->vertices[idx_q->vertex_idx];
+    next = idx_q->vertex_idx + 1;
+    if (next == figure->vertex_count)
+        next = 0;
+    q[1] = &figure->vertices[next];
+
+    if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+        return d2d_geometry_get_cubic_bezier_roots(geometry, intersections, idx_p, p, idx_q, q);
+    else
+        return d2d_geometry_get_quadratic_bezier_roots(geometry, intersections, idx_p, p, idx_q, q);
+}
+
 static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
         struct d2d_geometry_intersections *intersections,
         const struct d2d_segment_idx *idx_p, float start_p, float end_p,
-- 
2.20.1




More information about the wine-devel mailing list