Update bezier-line intersection function to handle cubic bezier curves.
Signed-off-by: Connor McAdams conmanx360@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; }