Add functions for calculating the bounds of a cubic bezier.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 185 +++++++++++++++++++++++++++++++++++-------- 1 file changed, 152 insertions(+), 33 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index a8e6a3f2b7..4ec0f16d07 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -399,12 +399,14 @@ static void d2d_point_lerp(D2D1_POINT_2F *out, }
static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0, - const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float t) + const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t) { float t_c = 1.0f - t; + float t_c_cube = t_c * t_c * t_c, t_cube = t * t * t; + float t_c_sq = t_c * t_c, t_sq = t * t;
- out->x = t_c * (t_c * p0->x + t * p1->x) + t * (t_c * p1->x + t * p2->x); - out->y = t_c * (t_c * p0->y + t * p1->y) + t * (t_c * p1->y + t * p2->y); + out->x = t_c_cube * p0->x + 3.0f * t_c_sq * t * p1->x + 3.0f * t_c * t_sq * p2->x + t_cube * p3->x; + out->y = t_c_cube * p0->y + 3.0f * t_c_sq * t * p1->y + 3.0f * t_c * t_sq * p2->y + t_cube * p3->y; }
static void d2d_point_normalise(D2D1_POINT_2F *p) @@ -424,6 +426,28 @@ static void d2d_bezier_quad_to_cubic(const D2D1_POINT_2F *p0, const D2D1_POINT_2 c1->y = p2->y * (1.0f / 3.0f) + (2.0f / 3.0f) * p1->y; }
+static void d2d_bezier_cubic_to_quad(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1, + const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, D2D1_POINT_2F *c0) +{ + c0->x = (p1->x + p2->x) * 0.75f; + c0->y = (p1->y + p2->y) * 0.75f; + c0->x -= (p0->x + p3->x) * 0.25f; + c0->y -= (p0->y + p3->y) * 0.25f; +} + +/* + * This value is useful for many different cubic bezier operations, including + * root finding, derivative checking, and texture coordinate calculations. + */ +#define D2D1_CUBIC_BEZIER_EPSILON 0.00005f +static float d2d_cubic_bezier_round_to_zero(float a) +{ + if (a < 0.00005f && a > -0.00005f) + return 0.0f; + + return a; +} + /* This implementation is based on the paper "Adaptive Precision * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and * associated (Public Domain) code by Jonathan Richard Shewchuk. */ @@ -521,44 +545,131 @@ 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, - const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2) +static void d2d_rect_get_quad_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; + D2D1_POINT_2F p, c; float root;
- bounds->left = p0->x; - bounds->top = p0->y; - bounds->right = p0->x; - bounds->bottom = p0->y; - - d2d_rect_expand(bounds, p2); + d2d_bezier_cubic_to_quad(p0, p1, p2, p3, &c);
/* f(t) = (1 - t)²P₀ + 2(1 - t)tP₁ + t²P₂ * f'(t) = 2(1 - t)(P₁ - P₀) + 2t(P₂ - P₁) * = 2(P₂ - 2P₁ + P₀)t + 2(P₁ - P₀) * * f'(t) = 0 - * t = (P₀ - P₁) / (P₂ - 2P₁ + P₀) */ - root = (p0->x - p1->x) / (p2->x - 2.0f * p1->x + p0->x); + * t = (P₀ - P₁) / (P₂ - 2P₁ + P₀) + */ + root = (p0->x - c.x) / (p3->x - 2.0f * c.x + p0->x); if (root > 0.0f && root < 1.0f) { - d2d_point_calculate_bezier(&p, p0, p1, p2, root); + d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root); d2d_rect_expand(bounds, &p); }
- root = (p0->y - p1->y) / (p2->y - 2.0f * p1->y + p0->y); + root = (p0->y - c.y) / (p3->y - 2.0f * c.y + p0->y); if (root > 0.0f && root < 1.0f) { - d2d_point_calculate_bezier(&p, p0, p1, p2, root); + d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root); d2d_rect_expand(bounds, &p); } }
+static void d2d_rect_get_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, a, b, c; + float root, sq_root; + + 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 + */ + v1.x = 3.0f * (p1->x - p0->x); + v1.y = 3.0f * (p1->y - p0->y); + + v2.x = 3.0f * (p2->x - p1->x); + v2.y = 3.0f * (p2->y - p1->y); + + v3.x = 3.0f * (p3->x - p2->x); + v3.y = 3.0f * (p3->y - p2->y); + + /* This will check if the cubic bezier is actually a quadratic, in which + * case we need the second derivative to get the extremities. */ + a.x = v1.x - 2.0f * v2.x + v3.x; + a.y = v1.y - 2.0f * v2.y + v3.y; + if ((d2d_cubic_bezier_round_to_zero(a.x) == 0.0f) && (d2d_cubic_bezier_round_to_zero(a.y) == 0.0f)) + { + d2d_rect_get_quad_bezier_bounds(bounds, p0, p1, p2, p3); + return; + } + b.x = 2.0f * (v2.x - v1.x); + b.y = 2.0f * (v2.y - v1.y); + c.x = v1.x; + c.y = v1.y; + + /* If the square root in the equation is negative, there are no roots. */ + if ((sq_root = sqrtf(b.x * b.x - 4.0f * a.x * c.x)) >= 0.0f) + { + root = (-b.x + sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + + root = (-b.x - sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + } + + if ((sq_root = sqrtf(b.y * b.y - 4.0f * a.y * c.y)) >= 0.0f) + { + root = (-b.y + sq_root) / (2.0f * a.y); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + + root = (-b.y - sq_root) / (2.0f * a.y); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root); + 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) { - D2D1_POINT_2F q[3], r[2]; + D2D1_POINT_2F q[3], r[2], c[2];
d2d_point_lerp(&r[0], p0, p1, start); d2d_point_lerp(&r[1], p1, p2, start); @@ -569,7 +680,8 @@ 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_bezier_quad_to_cubic(&q[0], &q[1], &q[2], &c[0], &c[1]); + d2d_rect_get_bezier_bounds(bounds, &q[0], &c[0], &c[1], &q[2]); }
static BOOL d2d_figure_insert_vertex(struct d2d_figure *figure, size_t idx, D2D1_POINT_2F vertex) @@ -1715,10 +1827,12 @@ 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; + D2D1_POINT_2F intersection, c[2]; float t;
- d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], s); + + 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); 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 @@ -1820,7 +1934,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry, const D2D1_POINT_2F *p[3], *q[3]; const struct d2d_figure *figure; D2D_RECT_F p_bounds, q_bounds; - D2D1_POINT_2F intersection; + D2D1_POINT_2F intersection, c[2]; float centre_p, centre_q; size_t next;
@@ -1851,7 +1965,8 @@ 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_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], centre_p); if (start_p > 0.0f && end_p < 1.0f && !d2d_geometry_intersections_add(intersections, idx_p, centre_p, intersection)) return FALSE; @@ -2565,7 +2680,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER;
d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1], - &p, &beziers[i].point3); + &beziers[i].point1, &beziers[i].point2, &beziers[i].point3);
if (!d2d_figure_add_bezier_control(figure, &beziers[i].point1, &beziers[i].point2, &p)) { @@ -2993,7 +3108,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr p2 = beziers[i].point2; d2d_bezier_quad_to_cubic(&p0, &p1, &p2, &c[0], &c[1]);
- d2d_rect_get_bezier_bounds(&bezier_bounds, &p0, &p1, &p2); + d2d_rect_get_bezier_bounds(&bezier_bounds, &p0, &c[0], &c[1], &p2);
figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER; if (!d2d_figure_add_bezier_control(figure, &c[0], &c[1], &p1)) @@ -3162,7 +3277,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) @@ -3203,13 +3318,15 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * break;
case D2D_VERTEX_TYPE_BEZIER: - p1 = figure->original_bezier_controls[bezier_idx++].cq0; + p1 = figure->original_bezier_controls[bezier_idx].c0; d2d_point_transform(&p1, transform, p1.x, p1.y); - p2 = figure->vertices[j]; + p2 = figure->original_bezier_controls[bezier_idx++].c1; 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_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3); d2d_rect_union(bounds, &bezier_bounds); - p = p2; + p = p3; break;
default: @@ -3225,11 +3342,13 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
if (type == D2D_VERTEX_TYPE_BEZIER) { - p1 = figure->original_bezier_controls[bezier_idx++].cq0; + p1 = figure->original_bezier_controls[bezier_idx].c0; d2d_point_transform(&p1, transform, p1.x, p1.y); - p2 = figure->vertices[0]; + p2 = figure->original_bezier_controls[bezier_idx++].c1; d2d_point_transform(&p2, transform, p2.x, p2.y); - d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2); + p3 = figure->vertices[0]; + d2d_point_transform(&p3, transform, p3.x, p3.y); + d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3); d2d_rect_union(bounds, &bezier_bounds); } }