From: Connor McAdams Subject: [PATCH 1/4] d2d1: Store cubic bezier control points. Message-Id: <20200331201103.15219-1-conmanx360@gmail.com> Date: Tue, 31 Mar 2020 16:11:00 -0400 Store cubic bezier control points, instead of storing them as quadratics. Signed-off-by: Connor McAdams --- dlls/d2d1/geometry.c | 474 +++++++++++++++++++++++++++++++++++++------ 1 file changed, 407 insertions(+), 67 deletions(-) diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index c18b648aef..cd21ef21c5 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -48,8 +48,10 @@ enum d2d_vertex_type { D2D_VERTEX_TYPE_NONE, D2D_VERTEX_TYPE_LINE, - D2D_VERTEX_TYPE_BEZIER, - D2D_VERTEX_TYPE_SPLIT_BEZIER, + D2D_VERTEX_TYPE_QUADRATIC_BEZIER, + D2D_VERTEX_TYPE_CUBIC_BEZIER, + D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER, + D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER, }; struct d2d_segment_idx @@ -409,6 +411,68 @@ static void d2d_point_normalise(D2D1_POINT_2F *p) d2d_point_scale(p, 1.0f / l); } +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; +} + +static void d2d_bezier_split_cubic(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; + } +} + +static BOOL d2d_vertex_type_is_bezier(enum d2d_vertex_type t) +{ + return (t == D2D_VERTEX_TYPE_QUADRATIC_BEZIER || t == D2D_VERTEX_TYPE_CUBIC_BEZIER || + t == D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER || t == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER); +} + +static BOOL d2d_vertex_type_is_cubic_bezier(enum d2d_vertex_type t) +{ + return (t == D2D_VERTEX_TYPE_CUBIC_BEZIER || t == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER); +} + +static BOOL d2d_vertex_type_is_split_bezier(enum d2d_vertex_type t) +{ + return (t == D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER || t == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER); +} + +static BOOL d2d_vertex_type_is_unsplit_bezier(enum d2d_vertex_type t) +{ + return (t == D2D_VERTEX_TYPE_QUADRATIC_BEZIER || t == D2D_VERTEX_TYPE_CUBIC_BEZIER); +} + /* 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. */ @@ -613,37 +677,71 @@ static BOOL d2d_figure_add_vertex(struct d2d_figure *figure, D2D1_POINT_2F verte return TRUE; } -static BOOL d2d_figure_insert_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) +static BOOL d2d_figure_insert_bezier_controls(struct d2d_figure *figure, size_t idx, size_t count, + const D2D1_POINT_2F **p) { + unsigned int i; + if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_count + count, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; } - memmove(&figure->bezier_controls[idx + 1], &figure->bezier_controls[idx], + memmove(&figure->bezier_controls[idx + count], &figure->bezier_controls[idx], (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls)); - figure->bezier_controls[idx] = *p; - ++figure->bezier_control_count; + + for (i = 0; i < count; ++i) + figure->bezier_controls[idx + i] = *p[i]; + + figure->bezier_control_count += count; return TRUE; } -static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) +static BOOL d2d_figure_add_bezier_controls(struct d2d_figure *figure, size_t count, const D2D1_POINT_2F **p) { + unsigned int i; + if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_count + count, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; } - figure->bezier_controls[figure->bezier_control_count++] = *p; + for (i = 0; i < count; ++i) + figure->bezier_controls[figure->bezier_control_count + i] = *p[i]; + + figure->bezier_control_count += count; return TRUE; } +static BOOL d2d_figure_insert_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) +{ + return d2d_figure_insert_bezier_controls(figure, idx, 1, &p); +} + +static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) +{ + return d2d_figure_add_bezier_controls(figure, 1, &p); +} + +static unsigned int d2d_figure_get_bezier_control_count(struct d2d_figure *figure) +{ + unsigned int i, control_count; + + for (i = control_count = 0; i < figure->vertex_count; ++i) + { + if (d2d_vertex_type_is_bezier(figure->vertex_types[i])) + ++control_count; + } + + return control_count; +} + static void d2d_cdt_edge_rot(struct d2d_cdt_edge_ref *dst, const struct d2d_cdt_edge_ref *src) { dst->idx = src->idx; @@ -1723,15 +1821,28 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry, const D2D1_POINT_2F *p[3], *q[2]; const struct d2d_figure *figure; float y[3], root, theta, d, e; + enum d2d_vertex_type type; + D2D1_POINT_2F tmp; 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]; next = idx_p->vertex_idx + 1; if (next == figure->vertex_count) next = 0; p[2] = &figure->vertices[next]; + if (d2d_vertex_type_is_cubic_bezier(type)) + { + d2d_bezier_cubic_to_quad(p[0], + &figure->bezier_controls[idx_p->control_idx], + &figure->bezier_controls[idx_p->control_idx + 1], + p[2], &tmp); + + p[1] = &tmp; + } + else + p[1] = &figure->bezier_controls[idx_p->control_idx]; figure = &geometry->u.path.figures[idx_q->figure_idx]; q[0] = &figure->vertices[idx_q->vertex_idx]; @@ -1799,25 +1910,48 @@ 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, tmp_p, tmp_q; + enum d2d_vertex_type type_p, type_q; float centre_p, centre_q; size_t next; figure = &geometry->u.path.figures[idx_p->figure_idx]; + type_p = figure->vertex_types[idx_p->vertex_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]; + if (d2d_vertex_type_is_cubic_bezier(type_p)) + { + d2d_bezier_cubic_to_quad(p[0], + &figure->bezier_controls[idx_p->control_idx], + &figure->bezier_controls[idx_p->control_idx + 1], + p[2], &tmp_p); + + p[1] = &tmp_p; + } + else + p[1] = &figure->bezier_controls[idx_p->control_idx]; figure = &geometry->u.path.figures[idx_q->figure_idx]; + type_q = figure->vertex_types[idx_q->vertex_idx]; q[0] = &figure->vertices[idx_q->vertex_idx]; - q[1] = &figure->bezier_controls[idx_q->control_idx]; next = idx_q->vertex_idx + 1; if (next == figure->vertex_count) next = 0; q[2] = &figure->vertices[next]; + if (d2d_vertex_type_is_cubic_bezier(type_q)) + { + d2d_bezier_cubic_to_quad(q[0], + &figure->bezier_controls[idx_q->control_idx], + &figure->bezier_controls[idx_q->control_idx + 1], + q[2], &tmp_q); + + q[1] = &tmp_q; + } + else + q[1] = &figure->bezier_controls[idx_q->control_idx]; 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); @@ -1861,9 +1995,10 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry, { size_t vertex_offset, control_offset, next, i; struct d2d_geometry_intersection *inter; - enum d2d_vertex_type vertex_type; - const D2D1_POINT_2F *p[3]; + enum d2d_vertex_type vertex_type, split_type; + const D2D1_POINT_2F *p[4], *c[2]; struct d2d_figure *figure; + D2D1_BEZIER_SEGMENT b[2]; D2D1_POINT_2F q[2]; float t, t_prev; @@ -1875,7 +2010,7 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry, figure = &geometry->u.path.figures[inter->figure_idx]; vertex_type = figure->vertex_types[inter->vertex_idx + vertex_offset]; - if (vertex_type != D2D_VERTEX_TYPE_BEZIER && vertex_type != D2D_VERTEX_TYPE_SPLIT_BEZIER) + if (!d2d_vertex_type_is_bezier(vertex_type)) { if (!d2d_figure_insert_vertex(&geometry->u.path.figures[inter->figure_idx], inter->vertex_idx + vertex_offset + 1, inter->p)) @@ -1902,19 +2037,43 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry, next = inter->vertex_idx + vertex_offset + 1; if (next == figure->vertex_count) next = 0; - p[2] = &figure->vertices[next]; - d2d_point_lerp(&q[0], p[0], p[1], t); - d2d_point_lerp(&q[1], p[1], p[2], t); + if (d2d_vertex_type_is_cubic_bezier(vertex_type)) + { + p[2] = &figure->bezier_controls[inter->control_idx + control_offset + 1]; + p[3] = &figure->vertices[next]; + + d2d_bezier_split_cubic(p[0], p[1], p[2], p[3], t, &b[0], &b[1], NULL); - figure->bezier_controls[inter->control_idx + control_offset] = q[0]; - if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1]))) - return FALSE; - ++control_offset; + figure->bezier_controls[inter->control_idx + control_offset] = b[0].point1; + figure->bezier_controls[inter->control_idx + control_offset + 1] = b[0].point2; + c[0] = &b[1].point1; + c[1] = &b[1].point2; + + if (!(d2d_figure_insert_bezier_controls(figure, inter->control_idx + control_offset + 2, 2, c))) + return FALSE; + control_offset += 2; + + split_type = D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER; + } + else + { + p[2] = &figure->vertices[next]; + + d2d_point_lerp(&q[0], p[0], p[1], t); + d2d_point_lerp(&q[1], p[1], p[2], t); + + figure->bezier_controls[inter->control_idx + control_offset] = q[0]; + if (!(d2d_figure_insert_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1]))) + return FALSE; + ++control_offset; + + split_type = D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER; + } if (!(d2d_figure_insert_vertex(figure, inter->vertex_idx + vertex_offset + 1, inter->p))) return FALSE; - figure->vertex_types[inter->vertex_idx + vertex_offset + 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER; + figure->vertex_types[inter->vertex_idx + vertex_offset + 1] = split_type; ++vertex_offset; } @@ -1961,9 +2120,9 @@ static BOOL d2d_geometry_intersect_self(struct d2d_geometry *geometry) for (idx_q.vertex_idx = 0; idx_q.vertex_idx < max_q; ++idx_q.vertex_idx) { type_q = figure_q->vertex_types[idx_q.vertex_idx]; - if (type_q == D2D_VERTEX_TYPE_BEZIER) + if (d2d_vertex_type_is_unsplit_bezier(type_q)) { - if (type_p == D2D_VERTEX_TYPE_BEZIER) + if (d2d_vertex_type_is_unsplit_bezier(type_p)) { if (!d2d_geometry_intersect_bezier_bezier(geometry, &intersections, &idx_p, 0.0f, 1.0f, &idx_q, 0.0f, 1.0f)) @@ -1974,11 +2133,14 @@ static BOOL d2d_geometry_intersect_self(struct d2d_geometry *geometry) if (!d2d_geometry_intersect_bezier_line(geometry, &intersections, &idx_q, &idx_p)) goto done; } - ++idx_q.control_idx; + if (type_q == D2D_VERTEX_TYPE_QUADRATIC_BEZIER) + ++idx_q.control_idx; + else if (type_q == D2D_VERTEX_TYPE_CUBIC_BEZIER) + idx_q.control_idx += 2; } else { - if (type_p == D2D_VERTEX_TYPE_BEZIER) + if (d2d_vertex_type_is_unsplit_bezier(type_p)) { if (!d2d_geometry_intersect_bezier_line(geometry, &intersections, &idx_p, &idx_q)) goto done; @@ -1991,8 +2153,10 @@ static BOOL d2d_geometry_intersect_self(struct d2d_geometry *geometry) } } } - if (type_p == D2D_VERTEX_TYPE_BEZIER) + if (type_p == D2D_VERTEX_TYPE_QUADRATIC_BEZIER) ++idx_p.control_idx; + else if (type_p == D2D_VERTEX_TYPE_CUBIC_BEZIER) + idx_p.control_idx += 2; } } @@ -2328,7 +2492,7 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry, if (!i) { prev_type = figure->vertex_types[figure->vertex_count - 1]; - if (prev_type == D2D_VERTEX_TYPE_BEZIER) + if (d2d_vertex_type_is_unsplit_bezier(prev_type)) prev = &figure->bezier_controls[figure->bezier_control_count - 1]; else prev = &figure->vertices[figure->vertex_count - 1]; @@ -2336,19 +2500,22 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry, else { prev_type = figure->vertex_types[i - 1]; - if (prev_type == D2D_VERTEX_TYPE_BEZIER) + if (d2d_vertex_type_is_unsplit_bezier(prev_type)) prev = &figure->bezier_controls[bezier_idx - 1]; else prev = &figure->vertices[i - 1]; } - if (type == D2D_VERTEX_TYPE_BEZIER) + if (d2d_vertex_type_is_unsplit_bezier(type)) next = &figure->bezier_controls[bezier_idx++]; else if (i == figure->vertex_count - 1) next = &figure->vertices[0]; else next = &figure->vertices[i + 1]; + if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + bezier_idx++; + if (figure_end == D2D1_FIGURE_END_CLOSED || (i && i < figure->vertex_count - 1)) { D2D1_POINT_2F q_next, q_prev; @@ -2372,15 +2539,23 @@ static BOOL d2d_geometry_add_figure_outline(struct d2d_geometry *geometry, ERR("Failed to add line segment.\n"); return FALSE; } - else if (type == D2D_VERTEX_TYPE_BEZIER) + else if (d2d_vertex_type_is_unsplit_bezier(type)) { const D2D1_POINT_2F *p2; + D2D1_POINT_2F tmp; if (i == figure->vertex_count - 1) p2 = &figure->vertices[0]; else p2 = &figure->vertices[i + 1]; + if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + { + d2d_bezier_cubic_to_quad(p0, &figure->bezier_controls[bezier_idx - 2], + &figure->bezier_controls[bezier_idx - 1], p2, &tmp); + next = &tmp; + } + if (!d2d_geometry_outline_add_bezier_segment(geometry, p0, next, p2)) { ERR("Failed to add bezier segment.\n"); @@ -2561,6 +2736,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if { struct d2d_geometry *geometry = impl_from_ID2D1GeometrySink(iface); struct d2d_figure *figure = &geometry->u.path.figures[geometry->u.path.figure_count - 1]; + const D2D1_POINT_2F *c[2]; D2D1_POINT_2F p; unsigned int i; @@ -2581,12 +2757,15 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if p.y = (beziers[i].point1.y + beziers[i].point2.y) * 0.75f; p.x -= (figure->vertices[figure->vertex_count - 1].x + beziers[i].point3.x) * 0.25f; p.y -= (figure->vertices[figure->vertex_count - 1].y + beziers[i].point3.y) * 0.25f; - figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER; + 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); - if (!d2d_figure_add_bezier_control(figure, &p)) + c[0] = &beziers[i].point1; + c[1] = &beziers[i].point2; + + if (!d2d_figure_add_bezier_controls(figure, 2, c)) { ERR("Failed to add bezier control.\n"); geometry->u.path.state = D2D_GEOMETRY_STATE_ERROR; @@ -2659,23 +2838,29 @@ static void d2d_path_geometry_free_figures(struct d2d_geometry *geometry) static BOOL d2d_geometry_get_bezier_segment_idx(struct d2d_geometry *geometry, struct d2d_segment_idx *idx, BOOL next) { + struct d2d_figure *figure = &geometry->u.path.figures[idx->figure_idx]; + enum d2d_vertex_type type = figure->vertex_types[idx->vertex_idx]; + if (next) { + if (d2d_vertex_type_is_cubic_bezier(type)) + ++idx->control_idx; + ++idx->vertex_idx; ++idx->control_idx; } for (; idx->figure_idx < geometry->u.path.figure_count; ++idx->figure_idx, idx->vertex_idx = idx->control_idx = 0) { - struct d2d_figure *figure = &geometry->u.path.figures[idx->figure_idx]; + figure = &geometry->u.path.figures[idx->figure_idx]; if (!figure->bezier_control_count || figure->flags & D2D_FIGURE_FLAG_HOLLOW) continue; for (; idx->vertex_idx < figure->vertex_count; ++idx->vertex_idx) { - if (figure->vertex_types[idx->vertex_idx] == D2D_VERTEX_TYPE_BEZIER - || figure->vertex_types[idx->vertex_idx] == D2D_VERTEX_TYPE_SPLIT_BEZIER) + type = figure->vertex_types[idx->vertex_idx]; + if (d2d_vertex_type_is_bezier(type)) return TRUE; } } @@ -2700,25 +2885,48 @@ static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry, { const D2D1_POINT_2F *a[3], *b[3], *p[2], *q; const struct d2d_figure *figure; - D2D1_POINT_2F v_q[3], v_p, v_qp; + D2D1_POINT_2F v_q[3], v_p, v_qp, tmp_p, tmp_q; + enum d2d_vertex_type type; unsigned int i, j, score; float det, t; figure = &geometry->u.path.figures[idx_p->figure_idx]; + type = figure->vertex_types[idx_p->vertex_idx]; a[0] = &figure->vertices[idx_p->vertex_idx]; - a[1] = &figure->bezier_controls[idx_p->control_idx]; if (idx_p->vertex_idx == figure->vertex_count - 1) a[2] = &figure->vertices[0]; else a[2] = &figure->vertices[idx_p->vertex_idx + 1]; + if (d2d_vertex_type_is_cubic_bezier(type)) + { + d2d_bezier_cubic_to_quad(a[0], + &figure->bezier_controls[idx_p->control_idx], + &figure->bezier_controls[idx_p->control_idx + 1], + a[2], &tmp_p); + + a[1] = &tmp_p; + } + else + a[1] = &figure->bezier_controls[idx_p->control_idx]; figure = &geometry->u.path.figures[idx_q->figure_idx]; + type = figure->vertex_types[idx_q->vertex_idx]; b[0] = &figure->vertices[idx_q->vertex_idx]; - b[1] = &figure->bezier_controls[idx_q->control_idx]; if (idx_q->vertex_idx == figure->vertex_count - 1) b[2] = &figure->vertices[0]; else b[2] = &figure->vertices[idx_q->vertex_idx + 1]; + if (d2d_vertex_type_is_cubic_bezier(type)) + { + d2d_bezier_cubic_to_quad(b[0], + &figure->bezier_controls[idx_q->control_idx], + &figure->bezier_controls[idx_q->control_idx + 1], + b[2], &tmp_q); + + b[1] = &tmp_q; + } + else + b[1] = &figure->bezier_controls[idx_q->control_idx]; if (d2d_point_ccw(a[0], a[1], a[2]) == 0.0f || d2d_point_ccw(b[0], b[1], b[2]) == 0.0f) return FALSE; @@ -2786,40 +2994,81 @@ static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry, static float d2d_geometry_bezier_ccw(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx) { const struct d2d_figure *figure = &geometry->u.path.figures[idx->figure_idx]; + enum d2d_vertex_type type = figure->vertex_types[idx->vertex_idx]; size_t next = idx->vertex_idx + 1; + const D2D1_POINT_2F *p; + D2D1_POINT_2F tmp; if (next == figure->vertex_count) next = 0; - return d2d_point_ccw(&figure->vertices[idx->vertex_idx], - &figure->bezier_controls[idx->control_idx], &figure->vertices[next]); + if (d2d_vertex_type_is_cubic_bezier(type)) + { + d2d_bezier_cubic_to_quad(&figure->vertices[idx->vertex_idx], + &figure->bezier_controls[idx->control_idx], + &figure->bezier_controls[idx->control_idx + 1], + &figure->vertices[next], &tmp); + + p = &tmp; + } + else + p = &figure->bezier_controls[idx->control_idx]; + + return d2d_point_ccw(&figure->vertices[idx->vertex_idx], p, &figure->vertices[next]); } static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx) { - const D2D1_POINT_2F *p[3]; + const D2D1_POINT_2F *p[4], *c[2]; struct d2d_figure *figure; - D2D1_POINT_2F q[3]; + enum d2d_vertex_type type; + D2D1_BEZIER_SEGMENT b[2]; + D2D1_POINT_2F q[2], mid; size_t next; figure = &geometry->u.path.figures[idx->figure_idx]; + type = figure->vertex_types[idx->vertex_idx]; p[0] = &figure->vertices[idx->vertex_idx]; p[1] = &figure->bezier_controls[idx->control_idx]; next = idx->vertex_idx + 1; if (next == figure->vertex_count) next = 0; - p[2] = &figure->vertices[next]; - d2d_point_lerp(&q[0], p[0], p[1], 0.5f); - d2d_point_lerp(&q[1], p[1], p[2], 0.5f); - d2d_point_lerp(&q[2], &q[0], &q[1], 0.5f); + if (d2d_vertex_type_is_cubic_bezier(type)) + { + p[2] = &figure->bezier_controls[idx->control_idx + 1]; + p[3] = &figure->vertices[next]; - figure->bezier_controls[idx->control_idx] = q[0]; - if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &q[1]))) - return FALSE; - if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2]))) + d2d_bezier_split_cubic(p[0], p[1], p[2], p[3], 0.5f, &b[0], &b[1], &mid); + + figure->bezier_controls[idx->control_idx] = b[0].point1; + figure->bezier_controls[idx->control_idx + 1] = b[0].point2; + c[0] = &b[1].point1; + c[1] = &b[1].point2; + + if (!(d2d_figure_insert_bezier_controls(figure, idx->control_idx + 2, 2, c))) + return FALSE; + + type = D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER; + } + else + { + p[2] = &figure->vertices[next]; + + d2d_point_lerp(&q[0], p[0], p[1], 0.5f); + d2d_point_lerp(&q[1], p[1], p[2], 0.5f); + d2d_point_lerp(&mid, &q[0], &q[1], 0.5f); + + figure->bezier_controls[idx->control_idx] = q[0]; + if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &q[1]))) + return FALSE; + + type = D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER; + } + + if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, mid))) return FALSE; - figure->vertex_types[idx->vertex_idx + 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER; + figure->vertex_types[idx->vertex_idx + 1] = type; return TRUE; } @@ -2831,6 +3080,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) const D2D1_POINT_2F *p[3]; struct d2d_figure *figure; size_t bezier_idx, i; + D2D1_POINT_2F tmp; if (!d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p)) return S_OK; @@ -2838,6 +3088,8 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) /* Split overlapping bezier control triangles. */ while (d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p)) { + figure = &geometry->u.path.figures[idx_p.figure_idx]; + d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_q); while (idx_q.figure_idx < idx_p.figure_idx || idx_q.vertex_idx < idx_p.vertex_idx) { @@ -2849,6 +3101,9 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) return E_OUTOFMEMORY; if (idx_p.figure_idx == idx_q.figure_idx) { + if (d2d_vertex_type_is_cubic_bezier(figure->vertex_types[idx_p.vertex_idx])) + ++idx_p.control_idx; + ++idx_p.vertex_idx; ++idx_p.control_idx; } @@ -2865,9 +3120,11 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) for (i = 0; i < geometry->u.path.figure_count; ++i) { - if (geometry->u.path.figures[i].flags & D2D_FIGURE_FLAG_HOLLOW) + figure = &geometry->u.path.figures[i]; + if (figure->flags & D2D_FIGURE_FLAG_HOLLOW) continue; - geometry->fill.bezier_vertex_count += 3 * geometry->u.path.figures[i].bezier_control_count; + + geometry->fill.bezier_vertex_count += 3 * d2d_figure_get_bezier_control_count(figure); } if (!(geometry->fill.bezier_vertices = heap_calloc(geometry->fill.bezier_vertex_count, @@ -2886,9 +3143,23 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) 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]; i = idx_p.vertex_idx + 1; + if (d2d_vertex_type_is_cubic_bezier(figure->vertex_types[idx_p.vertex_idx])) + { + if (i == figure->vertex_count) + p[2] = &figure->vertices[0]; + else + p[2] = &figure->vertices[i]; + + d2d_bezier_cubic_to_quad(p[0], &figure->bezier_controls[idx_p.control_idx], + &figure->bezier_controls[idx_p.control_idx + 1], p[2], &tmp); + + p[1] = &tmp; + } + else + p[1] = &figure->bezier_controls[idx_p.control_idx]; + if (d2d_path_geometry_point_inside(geometry, p[1], FALSE)) { sign = 1.0f; @@ -3002,7 +3273,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr d2d_rect_get_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_BEZIER; + figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_QUADRATIC_BEZIER; if (!d2d_figure_add_bezier_control(figure, &beziers[i].point1)) { ERR("Failed to add bezier.\n"); @@ -3198,7 +3469,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * for (bezier_idx = 0, ++j; j < figure->vertex_count; ++j) { if (figure->vertex_types[j] == D2D_VERTEX_TYPE_NONE - || figure->vertex_types[j] == D2D_VERTEX_TYPE_SPLIT_BEZIER) + || d2d_vertex_type_is_split_bezier(figure->vertex_types[j])) continue; switch (type) @@ -3209,7 +3480,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * d2d_rect_expand(bounds, &p); break; - case D2D_VERTEX_TYPE_BEZIER: + case D2D_VERTEX_TYPE_QUADRATIC_BEZIER: p1 = figure->original_bezier_controls[bezier_idx++]; d2d_point_transform(&p1, transform, p1.x, p1.y); p2 = figure->vertices[j]; @@ -3219,6 +3490,20 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * 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; + 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_union(bounds, &bezier_bounds); + p = p2; + break; + default: FIXME("Unhandled vertex type %#x.\n", type); p = figure->vertices[j]; @@ -3230,9 +3515,20 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * type = figure->vertex_types[j]; } - if (type == D2D_VERTEX_TYPE_BEZIER) + if (d2d_vertex_type_is_unsplit_bezier(type)) { - p1 = figure->original_bezier_controls[bezier_idx++]; + if (type == 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[0], &p1); + + bezier_idx += 2; + } + else + p1 = figure->original_bezier_controls[bezier_idx++]; + d2d_point_transform(&p1, transform, p1.x, p1.y); p2 = figure->vertices[0]; d2d_point_transform(&p2, transform, p2.x, p2.y); @@ -3365,6 +3661,23 @@ static void d2d_geometry_simplify_quadratic(ID2D1SimplifiedGeometrySink *sink, ID2D1SimplifiedGeometrySink_AddBeziers(sink, &b, 1); } +static void d2d_geometry_simplify_cubic(ID2D1SimplifiedGeometrySink *sink, + D2D1_GEOMETRY_SIMPLIFICATION_OPTION option, const D2D1_POINT_2F *p0, + const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, + float tolerance) +{ + D2D1_BEZIER_SEGMENT b; + + b.point1 = *p1; + b.point2 = *p2; + b.point3 = *p3; + + if (option == D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES) + d2d_geometry_flatten_cubic(sink, p0, &b, tolerance); + else + ID2D1SimplifiedGeometrySink_AddBeziers(sink, &b, 1); +} + static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *iface, D2D1_GEOMETRY_SIMPLIFICATION_OPTION option, const D2D1_MATRIX_3X2_F *transform, float tolerance, ID2D1SimplifiedGeometrySink *sink) @@ -3373,7 +3686,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i enum d2d_vertex_type type = D2D_VERTEX_TYPE_NONE; unsigned int i, j, bezier_idx; D2D1_FIGURE_BEGIN begin; - D2D1_POINT_2F p, p1, p2; + D2D1_POINT_2F p, p1, p2, p3; D2D1_FIGURE_END end; TRACE("iface %p, option %#x, transform %p, tolerance %.8e, sink %p.\n", @@ -3401,7 +3714,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i for (bezier_idx = 0, ++j; j < figure->vertex_count; ++j) { if (figure->vertex_types[j] == D2D_VERTEX_TYPE_NONE - || figure->vertex_types[j] == D2D_VERTEX_TYPE_SPLIT_BEZIER) + || d2d_vertex_type_is_split_bezier(figure->vertex_types[j])) continue; switch (type) @@ -3413,7 +3726,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i ID2D1SimplifiedGeometrySink_AddLines(sink, &p, 1); break; - case D2D_VERTEX_TYPE_BEZIER: + case D2D_VERTEX_TYPE_QUADRATIC_BEZIER: p1 = figure->original_bezier_controls[bezier_idx++]; if (transform) d2d_point_transform(&p1, transform, p1.x, p1.y); @@ -3424,6 +3737,20 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i p = p2; break; + case D2D_VERTEX_TYPE_CUBIC_BEZIER: + p1 = figure->original_bezier_controls[bezier_idx++]; + if (transform) + d2d_point_transform(&p1, transform, p1.x, p1.y); + p2 = figure->original_bezier_controls[bezier_idx++]; + if (transform) + d2d_point_transform(&p2, transform, p2.x, p2.y); + p3 = figure->vertices[j]; + if (transform) + d2d_point_transform(&p3, transform, p3.x, p3.y); + d2d_geometry_simplify_cubic(sink, option, &p, &p1, &p2, &p3, tolerance); + p = p3; + break; + default: FIXME("Unhandled vertex type %#x.\n", type); p = figure->vertices[j]; @@ -3436,7 +3763,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i type = figure->vertex_types[j]; } - if (type == D2D_VERTEX_TYPE_BEZIER) + if (type == D2D_VERTEX_TYPE_QUADRATIC_BEZIER) { p1 = figure->original_bezier_controls[bezier_idx++]; if (transform) @@ -3446,6 +3773,19 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i d2d_point_transform(&p2, transform, p2.x, p2.y); d2d_geometry_simplify_quadratic(sink, option, &p, &p1, &p2, tolerance); } + else if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + { + p1 = figure->original_bezier_controls[bezier_idx++]; + if (transform) + d2d_point_transform(&p1, transform, p1.x, p1.y); + p2 = figure->original_bezier_controls[bezier_idx++]; + if (transform) + d2d_point_transform(&p2, transform, p2.x, p2.y); + p3 = figure->vertices[0]; + if (transform) + d2d_point_transform(&p3, transform, p3.x, p3.y); + d2d_geometry_simplify_cubic(sink, option, &p, &p1, &p2, &p3, tolerance); + } end = figure->flags & D2D_FIGURE_FLAG_CLOSED ? D2D1_FIGURE_END_CLOSED : D2D1_FIGURE_END_OPEN; ID2D1SimplifiedGeometrySink_EndFigure(sink, end); -- 2.20.1