Signed-off-by: Connor McAdams conmanx360@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,