Update bezier-line intersection function to handle both cubic and quadratic beziers.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 216 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 193 insertions(+), 23 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 0fb46a9c87..dd6f50bbec 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -1880,10 +1880,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 @@ -1902,35 +1910,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; - 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]; - next = idx_p->vertex_idx + 1; - if (next == figure->vertex_count) - next = 0; - p[2] = &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];
/* 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. * @@ -1947,7 +1938,7 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry, * = (2P₀ - 2P₁ ± √(4P₀² + 4P₁² - 8P₀P₁ - 4P₀² + 8P₀P₁ - 4P₀P₂)) / (2P₀ - 4P₁ + 2P₂) * = (P₀ - P₁ ± √(P₁² - P₀P₂)) / (P₀ - 2P₁ + P₂) */
- d = y[0] - 2 * y[1] + y[2]; + d = y[0] - 2.0f * y[1] + y[2]; if (d == 0.0f) { /* P₀ - 2P₁ + P₂ = 0 @@ -1975,6 +1966,185 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry, return FALSE;
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 float d2d_bezier_round_to_zero(float a) +{ + if ((a < 0.0005f && a > -0.0005f)) + return 0.0f; + else + return a; +} + +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; + float a, b, c, d; + + /* 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 (d2d_bezier_round_to_zero(d) == 0.0f) + { + /* Check if it's actually a line. */ + if (d2d_bezier_round_to_zero(a) == 0.0f) + { + /* Check if it's just a point. If it is, no roots. */ + if (d2d_bezier_round_to_zero(b) == 0.0f) + return 0; + + roots[0] = -c / b; + return 1; + } + + tmp = sqrtf(b * b - 4.0 * a * c); + roots[0] = (tmp - b) / (2.0 * a); + roots[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_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; + + roots[0] = t1 * cosf(phi / 3) - a / 3.0f; + roots[1] = t1 * cosf((phi + 2 * M_PI) / 3) - a / 3.0f; + roots[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); + roots[0] = 2.0f * tmp - (a / 3.0f); + roots[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); + roots[0] = u1 - v1 - a / 3.0f; + + return 1; + } + + return 0; +} + +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); + + return TRUE; }
static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,