Add functions for calculating the bounds of a cubic bezier.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 187 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 157 insertions(+), 30 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 001f142fe5..951d28f85e 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -401,7 +401,7 @@ static void d2d_point_lerp(D2D1_POINT_2F *out, out->y = a->y * (1.0f - t) + b->y * t; }
-static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0, +static void d2d_point_calculate_quadratic_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float t) { float t_c = 1.0f - t; @@ -410,6 +410,20 @@ static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F * out->y = t_c * (t_c * p0->y + t * p1->y) + t * (t_c * p1->y + t * p2->y); }
+static void d2d_point_calculate_cubic_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0, + const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t) +{ + D2D1_POINT_2F q[5]; + + 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(&q[3], &q[0], &q[1], t); + d2d_point_lerp(&q[4], &q[1], &q[2], t); + d2d_point_lerp(out, &q[3], &q[4], t); +} + static void d2d_point_normalise(D2D1_POINT_2F *p) { float l; @@ -566,6 +580,37 @@ static float d2d_point_ccw(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b, const return det_d[det_d_len - 1]; }
+static unsigned int d2d_solve_quadratic_roots(float a, float b, float c, float *roots) +{ + float sq_root, root, tmp; + unsigned int root_count = 0; + + tmp = b * b - 4.0f * a * c; + + if (tmp >= 0.0f) + { + sq_root = sqrtf(tmp); + + if (b >= 0.0f) + root = (-b - sq_root) / (2.0f * a); + else + root = (2.0f * c) / (-b + sq_root); + + if (root > 0.0f && root < 1.0f) + roots[root_count++] = root; + + if (b >= 0.0f) + root = (2.0f * c) / (-b - sq_root); + else + root = (-b + sq_root) / (2.0f * a); + + if (root > 0.0f && root < 1.0f) + roots[root_count++] = root; + } + + return root_count; +} + static void d2d_rect_union(D2D1_RECT_F *l, const D2D1_RECT_F *r) { l->left = min(l->left, r->left); @@ -579,7 +624,7 @@ static BOOL d2d_rect_check_overlap(const D2D_RECT_F *p, const D2D_RECT_F *q) return p->left < q->right && p->top < q->bottom && p->right > q->left && p->bottom > q->top; }
-static void d2d_rect_get_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0, +static void d2d_rect_get_quadratic_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2) { D2D1_POINT_2F p; @@ -601,18 +646,101 @@ static void d2d_rect_get_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F * root = (p0->x - p1->x) / (p2->x - 2.0f * p1->x + p0->x); if (root > 0.0f && root < 1.0f) { - d2d_point_calculate_bezier(&p, p0, p1, p2, root); + d2d_point_calculate_quadratic_bezier(&p, p0, p1, p2, root); d2d_rect_expand(bounds, &p); }
root = (p0->y - p1->y) / (p2->y - 2.0f * p1->y + p0->y); if (root > 0.0f && root < 1.0f) { - d2d_point_calculate_bezier(&p, p0, p1, p2, root); + d2d_point_calculate_quadratic_bezier(&p, p0, p1, p2, root); d2d_rect_expand(bounds, &p); } }
+static BOOL d2d_check_if_cubic_is_quad(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1, + const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3) +{ + D2D1_POINT_2F tmp; + + tmp.x = -p0->x + 3.0f * p1->x - 3.0f * p2->x + p3->x; + tmp.y = -p0->y + 3.0f * p1->y - 3.0f * p2->y + p3->y; + + if ((tmp.x < 0.0005f && tmp.x > -0.0005f) && (tmp.y < 0.0005f && tmp.y > -0.0005f)) + return TRUE; + else + return FALSE; +} + +static void d2d_rect_get_cubic_bezier_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) +{ + D2D1_POINT_2F p, v1, v2, v3; + float roots[2], a[2], b[2], c[2]; + unsigned int i, y, root_count; + + if (d2d_check_if_cubic_is_quad(p0, p1, p2, p3)) + { + d2d_bezier_cubic_to_quad(p0, p1, p2, p3, &p); + d2d_rect_get_quadratic_bezier_bounds(bounds, p0, &p, p3); + return; + } + + bounds->left = p0->x; + bounds->top = p0->y; + bounds->right = p0->x; + bounds->bottom = p0->y; + + d2d_rect_expand(bounds, p3); + + /* + * f(t) = (1 - t)³P₀ + 3(1 - t)²tP₁ + 3(1 - t)t²P₂ + t³P₃ + * f'(t) = 3(1 - t)²(P₁ - P₀) + 6(1 - t)t(P₂ - P₁) + 3t²(P₃ - P₂) + * + * Or, from https://pomax.github.io/bezierinfo/#extremities + * V₁ = 3(P₁ - P₀) + * V₂ = 3(P₂ - P₁) + * V₃ = 3(P₃ - P₂) + * f'(t) = V₁(1 - t)² + 2V₂(1 - t)t + V₃t² + * = (V₁ - 2V₂ + V₃)t² + 2(V₂ - V₁)t + V₁ + * + * And new quadratic coefficients a, b, and c are: + * a = V₁ - 2V₂ + V₃ + * b = 2(V₂ - V₁) + * c = V₁ + * + * f'(t) = 0 + * t = (-b ± √(b² - 4ac)) / 2a + */ + d2d_point_subtract(&v1, p1, p0); + d2d_point_scale(&v1, 3.0f); + + d2d_point_subtract(&v2, p2, p1); + d2d_point_scale(&v2, 3.0f); + + d2d_point_subtract(&v3, p3, p2); + d2d_point_scale(&v3, 3.0f); + + a[0] = v1.x - 2.0f * v2.x + v3.x; + a[1] = v1.y - 2.0f * v2.y + v3.y; + + b[0] = 2.0f * (v2.x - v1.x); + b[1] = 2.0f * (v2.y - v1.y); + + c[0] = v1.x; + c[1] = v1.y; + + for (i = 0; i < 2; ++i) + { + root_count = d2d_solve_quadratic_roots(a[i], b[i], c[i], roots); + for (y = 0; y < root_count; ++y) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, roots[y]); + d2d_rect_expand(bounds, &p); + } + } +} + 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) { @@ -627,7 +755,7 @@ static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_PO d2d_point_lerp(&r[0], &r[1], p2, end); d2d_point_lerp(&q[2], &q[1], &r[0], end);
- d2d_rect_get_bezier_bounds(bounds, &q[0], &q[1], &q[2]); + d2d_rect_get_quadratic_bezier_bounds(bounds, &q[0], &q[1], &q[2]); }
static BOOL d2d_figure_insert_vertex(struct d2d_figure *figure, size_t idx, D2D1_POINT_2F vertex) @@ -1804,7 +1932,7 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom D2D1_POINT_2F intersection; float t;
- d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], s); + d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], 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 @@ -1964,7 +2092,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
if (end_p - start_p < 1e-3f) { - d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], centre_p); + d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], centre_p); if (start_p > 0.0f && end_p < 1.0f && !d2d_geometry_intersections_add(intersections, idx_p, centre_p, intersection)) return FALSE; @@ -2754,8 +2882,8 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if &beziers[i].point2, &beziers[i].point3, &p); figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_CUBIC_BEZIER;
- d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1], - &p, &beziers[i].point3); + d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1], + &beziers[i].point1, &beziers[i].point2, &beziers[i].point3);
if (!d2d_figure_add_bezier_controls(figure, 2, (D2D1_POINT_2F *)&beziers[i])) { @@ -3256,7 +3384,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr { D2D1_RECT_F bezier_bounds;
- d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1], + d2d_rect_get_quadratic_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1], &beziers[i].point1, &beziers[i].point2);
figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_QUADRATIC_BEZIER; @@ -3426,7 +3554,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * const struct d2d_figure *figure = &geometry->u.path.figures[i]; enum d2d_vertex_type type = D2D_VERTEX_TYPE_NONE; D2D1_RECT_F bezier_bounds; - D2D1_POINT_2F p, p1, p2; + D2D1_POINT_2F p, p1, p2, p3; size_t j, bezier_idx;
if (figure->flags & D2D_FIGURE_FLAG_HOLLOW) @@ -3471,23 +3599,21 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * d2d_point_transform(&p1, transform, p1.x, p1.y); p2 = figure->vertices[j]; d2d_point_transform(&p2, transform, p2.x, p2.y); - d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2); + d2d_rect_get_quadratic_bezier_bounds(&bezier_bounds, &p, &p1, &p2); d2d_rect_union(bounds, &bezier_bounds); p = p2; break;
case D2D_VERTEX_TYPE_CUBIC_BEZIER: - d2d_bezier_cubic_to_quad(&figure->vertices[j - 1], - &figure->original_bezier_controls[bezier_idx], - &figure->original_bezier_controls[bezier_idx + 1], - &figure->vertices[j], &p1); - bezier_idx += 2; + p1 = figure->original_bezier_controls[bezier_idx++]; d2d_point_transform(&p1, transform, p1.x, p1.y); - p2 = figure->vertices[j]; + p2 = figure->original_bezier_controls[bezier_idx++]; d2d_point_transform(&p2, transform, p2.x, p2.y); - d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2); + p3 = figure->vertices[j]; + d2d_point_transform(&p3, transform, p3.x, p3.y); + d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3); d2d_rect_union(bounds, &bezier_bounds); - p = p2; + p = p3; break;
default: @@ -3504,19 +3630,20 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * if (d2d_vertex_type_is_bezier(type)) { p1 = figure->original_bezier_controls[bezier_idx++]; + d2d_point_transform(&p1, transform, p1.x, p1.y); + p3 = figure->vertices[0]; + d2d_point_transform(&p3, transform, p3.x, p3.y); if (d2d_vertex_type_is_cubic_bezier(type)) { - d2d_bezier_cubic_to_quad(&figure->vertices[j - 1], - &figure->original_bezier_controls[bezier_idx - 1], - &figure->original_bezier_controls[bezier_idx], - &figure->vertices[0], &p1); - - ++bezier_idx; + p2 = figure->original_bezier_controls[bezier_idx++]; + d2d_point_transform(&p2, transform, p2.x, p2.y); + d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3); } - d2d_point_transform(&p1, transform, p1.x, p1.y); - p2 = figure->vertices[0]; - d2d_point_transform(&p2, transform, p2.x, p2.y); - d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2); + else + { + d2d_rect_get_quadratic_bezier_bounds(&bezier_bounds, &p, &p1, &p2); + } + d2d_rect_union(bounds, &bezier_bounds); } }