Update functions for handling bezier-bezier intersection to now handle cubic bezier curves.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 74 ++++++++++++++++++++++++++++++++------------ 1 file changed, 54 insertions(+), 20 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 4ec0f16d07..8dad84fca3 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -448,6 +448,38 @@ static float d2d_cubic_bezier_round_to_zero(float a) return a; }
+static void d2d_cubic_bezier_split(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1, + const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t, D2D1_BEZIER_SEGMENT *left, + D2D1_BEZIER_SEGMENT *right, D2D1_POINT_2F *center) +{ + D2D1_POINT_2F q[4], r[3], mid; + + 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(&r[0], &q[0], &q[1], t); + d2d_point_lerp(&r[1], &q[1], &q[2], t); + d2d_point_lerp(&mid, &r[0], &r[1], t); + + if (center) + *center = mid; + + if (left) + { + left->point1 = q[0]; + left->point2 = r[0]; + left->point3 = mid; + } + + if (right) + { + right->point1 = r[1]; + right->point2 = q[2]; + right->point3 = *p3; + } +} + /* 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. */ @@ -667,21 +699,22 @@ static void d2d_rect_get_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F * }
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) + const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, + float start, float end) { - D2D1_POINT_2F q[3], r[2], c[2]; + D2D1_BEZIER_SEGMENT left, right; + D2D1_POINT_2F mid;
- d2d_point_lerp(&r[0], p0, p1, start); - d2d_point_lerp(&r[1], p1, p2, start); - d2d_point_lerp(&q[0], &r[0], &r[1], start); + /* First part: Create a new cubic bezier with control points on the right + * side of the start t-value split. */ + d2d_cubic_bezier_split(p0, p1, p2, p3, start, NULL, &right, &mid);
+ /* Now, create another cubic bezier from the previous one, this time on + * the left side of the end value t-split. */ end = (end - start) / (1.0f - start); - d2d_point_lerp(&q[1], &q[0], &r[1], end); - d2d_point_lerp(&r[0], &r[1], p2, end); - d2d_point_lerp(&q[2], &q[1], &r[0], end); + d2d_cubic_bezier_split(&mid, &right.point1, &right.point2, p3, end, &left, NULL, NULL);
- 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]); + d2d_rect_get_bezier_bounds(bounds, &mid, &left.point1, &left.point2, &left.point3); }
static BOOL d2d_figure_insert_vertex(struct d2d_figure *figure, size_t idx, D2D1_POINT_2F vertex) @@ -1931,31 +1964,33 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx_p, float start_p, float end_p, const struct d2d_segment_idx *idx_q, float start_q, float end_q) { - const D2D1_POINT_2F *p[3], *q[3]; + const D2D1_POINT_2F *p[4], *q[4]; const struct d2d_figure *figure; D2D_RECT_F p_bounds, q_bounds; - D2D1_POINT_2F intersection, c[2]; + D2D1_POINT_2F intersection; float centre_p, centre_q; 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]; - q[1] = &figure->bezier_controls[idx_q->control_idx].cq0; + q[1] = &figure->bezier_controls[idx_q->control_idx].c0; + q[2] = &figure->bezier_controls[idx_q->control_idx].c1; next = idx_q->vertex_idx + 1; if (next == figure->vertex_count) next = 0; - q[2] = &figure->vertices[next]; + q[3] = &figure->vertices[next];
- d2d_rect_get_bezier_segment_bounds(&p_bounds, p[0], p[1], p[2], start_p, end_p); - d2d_rect_get_bezier_segment_bounds(&q_bounds, q[0], q[1], q[2], start_q, end_q); + d2d_rect_get_bezier_segment_bounds(&p_bounds, p[0], p[1], p[2], p[3], start_p, end_p); + d2d_rect_get_bezier_segment_bounds(&q_bounds, q[0], q[1], q[2], q[3], start_q, end_q);
if (!d2d_rect_check_overlap(&p_bounds, &q_bounds)) return TRUE; @@ -1965,8 +2000,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
if (end_p - start_p < 1e-3f) { - 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); + d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], p[3], centre_p); if (start_p > 0.0f && end_p < 1.0f && !d2d_geometry_intersections_add(intersections, idx_p, centre_p, intersection)) return FALSE;