Looking for feedback on my current methods of storing the control points of cubic beziers, and the new bezier flattening method. Also, any suggestions on more tests to write would be helpful.
Thanks.
Connor McAdams (8): d2d1: Store cubic bezier control points. d2d1: Implement new bezier flattening method. d2d1: Add cubic bezier bounds functions. d2d1: Implement cubic bezier-bezier intersection. d2d1: Implement cubic bezier-line intersection. d2d1: Add cubic bezier overlap splitting limit. d2d1: Add tests for cubic-bezier path geometry. d2d1: Cubic bezier-line intersection tests.
dlls/d2d1/geometry.c | 1094 ++++++++++++++++++++++++++++++++++------ dlls/d2d1/tests/d2d1.c | 429 ++++++++++++++++ 2 files changed, 1381 insertions(+), 142 deletions(-)
Store cubic bezier control points, instead of storing them as quadratics.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 472 +++++++++++++++++++++++++++++++++++++------ 1 file changed, 405 insertions(+), 67 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index c18b648aef..299e997ea1 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,79 @@ 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]; + p[3] = &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];
- 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 + { + d2d_point_lerp(&q[0], p[0], p[1], 0.5f); + d2d_point_lerp(&q[1], p[1], p[3], 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 +3078,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 +3086,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 +3099,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 +3118,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 +3141,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 +3271,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 +3467,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 +3478,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 +3488,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 +3513,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 +3659,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 +3684,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 +3712,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 +3724,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 +3735,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 +3761,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 +3771,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);
On Tue, 5 May 2020 at 00:23, Connor McAdams conmanx360@gmail.com wrote:
@@ -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,
};
If I read the patch correctly, you don't actually need D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER in this patch, and introducing it in a later patch may simplify this one somewhat.
+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);
+}
Some of these helpers could probably be introduced on their own, before this patch, again simplifying this one a little.
I don't think you need d2d_vertex_type_is_unsplit_bezier(), all of the places that use it should work just as well with d2d_vertex_type_is_bezier(). (E.g., in d2d_geometry_intersect_self(), there's no reason the D2D_VERTEX_TYPE_BEZIER paths wouldn't apply to split beziers; we just don't have any at that point.)
-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)))
- 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)))
- 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;
}
The array of pointers probably isn't worth it. On 64-bit in particular pointers are the same size as the D2D1_POINT_2F structure, so any benefit seems questionable. If copying the points was a concern you could take advantage of the fact that the D2D1_BEZIER_SEGMENT structure is effectively an array of points, but I don't think it is.
+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;
+}
This returns the number of Bézier curves in the figure, not the number of control points. Those are of course equivalent if all curves are of the same order, but once you can have both quadratics and cubics that's no longer true.
@@ -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))
As mentioned above, this should work fine with d2d_vertex_type_is_bezier().
@@ -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");
Like d2d_geometry_intersect_self(), this would work the same with split curves; we just don't have any here.
@@ -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;
d2d_bezier_cubic_to_quad(&figure->vertices[figure->vertex_count - 1], &beziers[i].point1, &beziers[i].point2, &beziers[i].point3, &p);
@@ -3198,7 +3467,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 +3478,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 +3488,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 +3513,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;}elsep1 = figure->original_bezier_controls[bezier_idx++];
We skipped all the split types above, so if "type" is a Bézier type, it's not split. You could also consider simply handling D2D_VERTEX_TYPE_QUADRATIC_BEZIER and D2D_VERTEX_TYPE_CUBIC_BEZIER individually, as you do inside the preceding loop, and in d2d_path_geometry_Simplify() below.
Add new flattening methods for cubic beziers and quadratic beziers.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- Note: The documentation here is mainly because of RFC, probably isn't as well written as most math oriented people would like. I can try to explain it further if need be, and these will probably not need to be included in the actual patch series. dlls/d2d1/geometry.c | 249 +++++++++++++++++++++++++++++++++++++------ 1 file changed, 215 insertions(+), 34 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 299e997ea1..f6608a19b4 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -374,6 +374,13 @@ static void d2d_fp_scale_expansion_zeroelim(float *out, size_t *out_len, const f *out_len = out_idx; }
+static void d2d_point_add(D2D1_POINT_2F *out, + const D2D1_POINT_2F *a, const D2D1_POINT_2F *b) +{ + out->x = a->x + b->x; + out->y = a->y + b->y; +} + static void d2d_point_subtract(D2D1_POINT_2F *out, const D2D1_POINT_2F *a, const D2D1_POINT_2F *b) { @@ -3598,48 +3605,222 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_CompareWithGeometry(ID2D1Path return E_NOTIMPL; }
+/* + * Cubic flattening method derived from now expired US Patent 5,367,617, + * titled "System and Method of Hybrid Forward Differencing To Render Bezier + * Splines". This is the same method used in WPF, which through testing + * appears to be the same method used in D2D. + * + * This method uses the same principles as Adaptive Foward Differencing, + * except instead of adaptively creating points along the curve depending on + * the flattening tolerance threshold, we always split at fixed points, so + * that the results line up with recursive subdivision. + * + * Applying AFD to cubic/quadratic beziers basically comes down to this: + * p[0] is always p[0]. + * p[1] is always the difference between the end point and the start point. + * p[2] is the second derivative at p[0] for cubics, and just the individual + * second derivative for quadratics. + * p[3] is the second derivative at p[3] for cubics, and unused for + * quadratics, because the second derivative for a quadratic is non-linear. + */ +static BOOL d2d_cubic_flattener_half_step_check(D2D1_POINT_2F *p2, D2D1_POINT_2F *p3, float step_size, + float flat_tol) +{ + /* Step size should never go below half of this amount, which is the + * minimum possible tolerance of this method, 0.000001f. */ + if (step_size < 0.001f) + return FALSE; + + /* Check if either derivative is greater than the flattening tolerance, if + * one of them is, there is more halving to be done. */ + if (p2) + { + if ((max(fabsf(p2->x), fabsf(p2->y))) > flat_tol) + return TRUE; + } + + if (p3) + { + if ((max(fabsf(p3->x), fabsf(p3->y))) > flat_tol) + return TRUE; + } + + return FALSE; +} + +/* + * Try to take a double-step forward if doing so would be within tolerance and + * also wouldn't break up splitting at halves. + */ +static BOOL d2d_cubic_flattener_try_double_step(D2D1_POINT_2F *p, int *steps, float *step_size, float q_tol) +{ + BOOL doubled = (0 == (*steps & 1)); + D2D1_POINT_2F tmp; + + if (doubled) + { + tmp = p[2]; + d2d_point_scale(&tmp, 2.0f); + d2d_point_subtract(&tmp, &tmp, &p[3]); + + if (((max(fabsf(p[3].x), fabsf(p[3].y))) <= q_tol) && ((max(fabsf(tmp.x), fabsf(tmp.y))) <= q_tol)) + { + d2d_point_scale(&p[1], 2.0f); + + p[1].x += p[2].x; + p[1].y += p[2].y; + + d2d_point_scale(&p[3], 4.0f); + + p[2] = tmp; + d2d_point_scale(&p[2], 4.0f); + + *steps /= 2; // Halve the number of steps left + *step_size *= 2.0f; + } + else + doubled = FALSE; + } + + return doubled; +} + +/* + * Take a half step backwards on the cubic bezier, splitting the cubic bezier + * in half. + */ +static void d2d_cubic_flattener_half_step(D2D1_POINT_2F *p, int *steps, float *step_size) +{ + d2d_point_add(&p[2], &p[2], &p[3]); + d2d_point_scale(&p[2], 0.125f); + + d2d_point_subtract(&p[1], &p[1], &p[2]); + d2d_point_scale(&p[1], 0.50f); + + d2d_point_scale(&p[3], 0.25f); + + *steps *= 2; + *step_size *= 0.5f; +} + +static void d2d_quadratic_flattener_half_step(D2D1_POINT_2F *p, int *steps, float *step_size) +{ + d2d_point_scale(&p[1], 0.5f); + p[1].x += p[2].x * -0.125f; + p[1].y += p[2].y * -0.125f; + + d2d_point_scale(&p[2], 0.25f); + + *steps *= 2; + *step_size *= 0.5f; +} + +/* + * Go forward a step from a previously halved cubic bezier. + */ +static void d2d_cubic_flattener_forward_step(ID2D1SimplifiedGeometrySink *sink, D2D1_POINT_2F *p, + int *steps, float *step_size) +{ + D2D1_POINT_2F tmp = p[2]; + + d2d_point_add(&p[0], &p[0], &p[1]); + d2d_point_add(&p[1], &p[1], &tmp); + d2d_point_add(&p[2], &p[2], &tmp); + d2d_point_subtract(&p[2], &p[2], &p[3]); + + p[3] = tmp; + + ID2D1SimplifiedGeometrySink_AddLines(sink, &p[0], 1); + + *steps -= 1; +} + +static void d2d_quadratic_flattener_forward_step(ID2D1SimplifiedGeometrySink *sink, D2D1_POINT_2F *p, + int *steps, float *step_size) +{ + p[0].x += p[1].x; + p[0].y += p[1].y; + + p[1].x += p[2].x; + p[1].y += p[2].y; + + ID2D1SimplifiedGeometrySink_AddLines(sink, &p[0], 1); + + *steps -= 1; +} + static void d2d_geometry_flatten_cubic(ID2D1SimplifiedGeometrySink *sink, const D2D1_POINT_2F *p0, const D2D1_BEZIER_SEGMENT *b, float tolerance) { - D2D1_BEZIER_SEGMENT b0, b1; - D2D1_POINT_2F q; - float d; + float flat_tol, q_flat_tol; + float step_size = 1.0f; + int step_count = 1; + D2D1_POINT_2F q[4];
- /* It's certainly possible to calculate the maximum deviation of the - * approximation from the curve, but it's a little involved. Instead, note - * that if the control points were evenly spaced and collinear, p1 would - * be exactly between p0 and p2, and p2 would be exactly between p1 and - * p3. The deviation is a decent enough approximation, and much easier to - * calculate. - * - * p1' = (p0 + p2) / 2 - * p2' = (p1 + p3) / 2 - * d = ‖p1 - p1'‖₁ + ‖p2 - p2'‖₁ */ - d2d_point_lerp(&q, p0, &b->point2, 0.5f); - d2d_point_subtract(&q, &b->point1, &q); - d = fabsf(q.x) + fabsf(q.y); - d2d_point_lerp(&q, &b->point1, &b->point3, 0.5f); - d2d_point_subtract(&q, &b->point2, &q); - d += fabsf(q.x) + fabsf(q.y); - if (d < tolerance) - { - ID2D1SimplifiedGeometrySink_AddLines(sink, &b->point3, 1); - return; + + q[0] = *p0; + d2d_point_subtract(&q[1], &b->point3, p0); + q[2].x = (b->point1.x - b->point2.x * 2.0f + b->point3.x) * 6.0f; + q[2].y = (b->point1.y - b->point2.y * 2.0f + b->point3.y) * 6.0f; + q[3].x = (p0->x - b->point1.x * 2.0f + b->point2.x) * 6.0f; + q[3].y = (p0->y - b->point1.y * 2.0f + b->point2.y) * 6.0f; + + flat_tol = tolerance >= 0.0f ? tolerance : 0.0f; + flat_tol *= 6.0f; + q_flat_tol = flat_tol * 0.25f; + + while (d2d_cubic_flattener_half_step_check(&q[2], &q[3], step_size, flat_tol)) + d2d_cubic_flattener_half_step(q, &step_count, &step_size); + + while(step_count > 1) + { + d2d_cubic_flattener_forward_step(sink, q, &step_count, &step_size); + + if (d2d_cubic_flattener_half_step_check(&q[2], NULL, step_size, flat_tol)) + d2d_cubic_flattener_half_step(q, &step_count, &step_size); + else + { + while (d2d_cubic_flattener_try_double_step(q, &step_count, &step_size, q_flat_tol)) + continue; + } + + ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN); }
- d2d_point_lerp(&q, &b->point1, &b->point2, 0.5f); + /* Add final point. */ + ID2D1SimplifiedGeometrySink_AddLines(sink, &b->point3, 1); + ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_NONE); +} + +static void d2d_geometry_flatten_quadratic(ID2D1SimplifiedGeometrySink *sink, const D2D1_POINT_2F *p0, + const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float tolerance) +{ + float step_size = 1.0f; + D2D1_POINT_2F q[3]; + int step_count = 1; + float flat_tol; + + q[0] = *p0; + d2d_point_subtract(&q[1], p2, p0); + q[2].x = 2.0f * (p2->x - (2.0f * p1->x) + p0->x); + q[2].y = 2.0f * (p2->y - (2.0f * p1->y) + p0->y);
- b1.point3 = b->point3; - d2d_point_lerp(&b1.point2, &b1.point3, &b->point2, 0.5f); - d2d_point_lerp(&b1.point1, &b1.point2, &q, 0.5f); + flat_tol = tolerance >= 0.0f ? tolerance : 0.0f; + flat_tol *= 6.0f;
- d2d_point_lerp(&b0.point1, p0, &b->point1, 0.5f); - d2d_point_lerp(&b0.point2, &b0.point1, &q, 0.5f); - d2d_point_lerp(&b0.point3, &b0.point2, &b1.point1, 0.5f); + while (d2d_cubic_flattener_half_step_check(&q[2], NULL, step_size, flat_tol)) + d2d_quadratic_flattener_half_step(q, &step_count, &step_size);
- d2d_geometry_flatten_cubic(sink, p0, &b0, tolerance); - ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN); - d2d_geometry_flatten_cubic(sink, &b0.point3, &b1, tolerance); + while (step_count > 1) + { + d2d_quadratic_flattener_forward_step(sink, q, &step_count, &step_size); + + ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN); + } + + /* Add final point. */ + ID2D1SimplifiedGeometrySink_AddLines(sink, p2, 1); ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_NONE); }
@@ -3654,7 +3835,7 @@ static void d2d_geometry_simplify_quadratic(ID2D1SimplifiedGeometrySink *sink, b.point3 = *p2;
if (option == D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES) - d2d_geometry_flatten_cubic(sink, p0, &b, tolerance); + d2d_geometry_flatten_quadratic(sink, p0, p1, p2, tolerance); else ID2D1SimplifiedGeometrySink_AddBeziers(sink, &b, 1); }
Add functions for calculating the bounds of a cubic bezier.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 189 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 159 insertions(+), 30 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index f6608a19b4..ba7f51cccd 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; @@ -564,6 +578,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); @@ -577,7 +622,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; @@ -599,18 +644,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) { @@ -625,7 +753,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) @@ -1802,7 +1930,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 @@ -1971,7 +2099,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; @@ -2766,8 +2894,8 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if 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_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);
c[0] = &beziers[i].point1; c[1] = &beziers[i].point2; @@ -3275,7 +3403,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; @@ -3445,7 +3573,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) @@ -3490,23 +3618,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: @@ -3524,20 +3650,23 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * { 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; + p1 = figure->original_bezier_controls[bezier_idx++]; + d2d_point_transform(&p1, transform, p1.x, p1.y); + p2 = figure->original_bezier_controls[bezier_idx++]; + d2d_point_transform(&p2, transform, p2.x, p2.y); + p3 = figure->vertices[0]; + d2d_point_transform(&p3, transform, p3.x, p3.y); + d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3); } 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); + d2d_rect_get_quadratic_bezier_bounds(&bezier_bounds, &p, &p1, &p2); + }
- 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); d2d_rect_union(bounds, &bezier_bounds); } }
Hi,
While running your changed tests, I think I found new failures. Being a bot and all I'm not very good at pattern recognition, so I might be wrong, but could you please double-check?
Full results can be found at: https://testbot.winehq.org/JobDetails.pl?Key=71119
Your paranoid android.
=== debiant (32 bit report) ===
Report validation errors: d2d1:d2d1 has no test summary line (early exit of the main process?) d2d1:d2d1 has unaccounted for todo messages
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 69 +++++++++++++++++++++++++------------------- 1 file changed, 40 insertions(+), 29 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index ba7f51cccd..49fb517636 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -739,8 +739,9 @@ static void d2d_rect_get_cubic_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POIN } }
-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) +static void d2d_rect_get_quadratic_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];
@@ -756,6 +757,21 @@ static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_PO d2d_rect_get_quadratic_bezier_bounds(bounds, &q[0], &q[1], &q[2]); }
+static void d2d_rect_get_cubic_bezier_segment_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, float start, float end) +{ + D2D1_BEZIER_SEGMENT left, right; + D2D1_POINT_2F mid; + + d2d_bezier_split_cubic(p0, p1, p2, p3, start, NULL, &right, &mid); + + end = (end - start) / (1.0f - start); + d2d_bezier_split_cubic(&mid, &right.point1, &right.point2, p3, end, &left, NULL, NULL); + + d2d_rect_get_cubic_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) { if (!d2d_array_reserve((void **)&figure->vertices, &figure->vertices_size, @@ -2042,10 +2058,10 @@ 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, tmp_p, tmp_q; + D2D1_POINT_2F intersection; enum d2d_vertex_type type_p, type_q; float centre_p, centre_q; size_t next; @@ -2053,43 +2069,34 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry, 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]; + if (type_p == D2D_VERTEX_TYPE_CUBIC_BEZIER) + p[2] = &figure->bezier_controls[idx_p->control_idx + 1]; 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]; + p[3] = &figure->vertices[next];
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]; + if (type_q == D2D_VERTEX_TYPE_CUBIC_BEZIER) + q[2] = &figure->bezier_controls[idx_q->control_idx + 1]; 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[3] = &figure->vertices[next];
- q[1] = &tmp_q; - } + if (type_p == D2D_VERTEX_TYPE_CUBIC_BEZIER) + d2d_rect_get_cubic_bezier_segment_bounds(&p_bounds, p[0], p[1], p[2], p[3], start_p, end_p); else - q[1] = &figure->bezier_controls[idx_q->control_idx]; + d2d_rect_get_quadratic_bezier_segment_bounds(&p_bounds, p[0], p[1], p[3], start_p, end_p);
- 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); + if (type_q == D2D_VERTEX_TYPE_CUBIC_BEZIER) + d2d_rect_get_cubic_bezier_segment_bounds(&q_bounds, q[0], q[1], q[2], q[3], start_q, end_q); + else + d2d_rect_get_quadratic_bezier_segment_bounds(&q_bounds, q[0], q[1], q[3], start_q, end_q);
if (!d2d_rect_check_overlap(&p_bounds, &q_bounds)) return TRUE; @@ -2099,7 +2106,11 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
if (end_p - start_p < 1e-3f) { - d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], centre_p); + if (type_p == D2D_VERTEX_TYPE_CUBIC_BEZIER) + d2d_point_calculate_cubic_bezier(&intersection, p[0], p[1], p[2], p[3], centre_p); + else + d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], 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;
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 216 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 181 insertions(+), 35 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 49fb517636..3f57cc1852 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -1943,10 +1943,18 @@ 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) { + const struct d2d_figure *figure; + enum d2d_vertex_type type; D2D1_POINT_2F intersection; float t;
- d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], s); + figure = &geometry->u.path.figures[idx_p->figure_idx]; + type = figure->vertex_types[idx_p->vertex_idx]; + if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + d2d_point_calculate_cubic_bezier(&intersection, p[0], p[1], p[2], p[3], s); + else + d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], 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 @@ -1965,48 +1973,18 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom return TRUE; }
-static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry, +static BOOL d2d_geometry_get_quadratic_bezier_roots(struct d2d_geometry *geometry, struct d2d_geometry_intersections *intersections, - const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q) + const struct d2d_segment_idx *idx_p, const D2D1_POINT_2F **p, + const struct d2d_segment_idx *idx_q, const D2D1_POINT_2F **q) { - 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]; - 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]; - next = idx_q->vertex_idx + 1; - if (next == figure->vertex_count) - next = 0; - q[1] = &figure->vertices[next];
/* Align the line with x-axis. */ theta = -atan2f(q[1]->y - q[0]->y, q[1]->x - q[0]->x); 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[2] = (p[3]->x - q[0]->x) * sinf(theta) + (p[3]->y - q[0]->y) * cosf(theta);
/* Intersect the transformed curve with the x-axis. * @@ -2053,6 +2031,174 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry, 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.0f) + return -powf(-a, 1.0f / 3.0f); + else + return powf(a, 1.0f / 3.0f); +} + +static int d2d_cubic_bezier_get_roots(float *y, float *roots) +{ + float mp3, r, t, cosphi, phi, crtr, t1, u1, v1; + float p, p_3, q, q2, disc, sd, tmp, a, b, c, d; + unsigned int root_count; + + /* 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 * y[0] - 6.0f * y[1] + 3.0f * y[2]); + b = (-3.0f * y[0] + 3.0f * y[1]); + c = y[0]; + d = (-y[0] + 3.0f * y[1] - 3.0f * y[2] + y[3]); + + /* Check if the curve is actually a quadratic. */ + if ((d < 0.0005f && d > -0.0005f)) + { + /* Check if it's actually a line. */ + if ((a < 0.0005f && a > -0.0005f)) + { + /* Check if it's just a point. If it is, no roots. */ + if ((b < 0.0005f && b > -0.0005f)) + return 0; + + roots[0] = -c / b; + return 1; + } + + return d2d_solve_quadratic_roots(a, b, c, roots); + } + + 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; + + if ((disc < 0.00005f && disc > -0.00005f)) + disc = 0.0f; + + 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; + + roots[0] = t1 * cosf(phi / 3.0f) - a / 3.0f; + roots[1] = t1 * cosf((phi + 2.0f * M_PI) / 3.0f) - a / 3.0f; + roots[2] = t1 * cosf((phi + 4.0f * M_PI) / 3.0f) - a / 3.0f; + + root_count = 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); + + roots[0] = 2.0f * tmp - (a / 3.0f); + roots[1] = -tmp - (a / 3.0f); + + root_count = 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); + roots[0] = u1 - v1 - a / 3.0f; + + root_count = 1; + } + + return root_count; +} + +static BOOL d2d_geometry_get_cubic_bezier_roots(struct d2d_geometry *geometry, + 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 y[4], roots[3], theta; + unsigned int num_roots, i; + + /* 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); + + num_roots = d2d_cubic_bezier_get_roots(y, roots); + + for (i = 0; i < num_roots; ++i) + { + 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])) + return FALSE; + } + } + + return TRUE; +} + +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[4], *q[2]; + const struct d2d_figure *figure; + enum d2d_vertex_type type; + 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]; + if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + p[2] = &figure->bezier_controls[idx_p->control_idx + 1]; + next = idx_p->vertex_idx + 1; + if (next == figure->vertex_count) + next = 0; + p[3] = &figure->vertices[next]; + + figure = &geometry->u.path.figures[idx_q->figure_idx]; + q[0] = &figure->vertices[idx_q->vertex_idx]; + next = idx_q->vertex_idx + 1; + if (next == figure->vertex_count) + next = 0; + q[1] = &figure->vertices[next]; + + if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + return d2d_geometry_get_cubic_bezier_roots(geometry, intersections, idx_p, p, idx_q, q); + else + return d2d_geometry_get_quadratic_bezier_roots(geometry, intersections, idx_p, p, idx_q, q); +} + static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry, struct d2d_geometry_intersections *intersections, const struct d2d_segment_idx *idx_p, float start_p, float end_p,
Add a splitting limit for cubic bezier overlap splitting, otherwise certain cubic beziers will indefinitely continue splitting.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 3f57cc1852..7296aee8bf 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -3369,7 +3369,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) struct d2d_curve_vertex *b; const D2D1_POINT_2F *p[3]; struct d2d_figure *figure; - size_t bezier_idx, i; + size_t bezier_idx, i, split_count; D2D1_POINT_2F tmp;
if (!d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p)) @@ -3383,7 +3383,8 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) 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) { - while (d2d_geometry_check_bezier_overlap(geometry, &idx_p, &idx_q)) + split_count = 0; + while (d2d_geometry_check_bezier_overlap(geometry, &idx_p, &idx_q) && split_count < 2) { if (fabsf(d2d_geometry_bezier_ccw(geometry, &idx_q)) > fabsf(d2d_geometry_bezier_ccw(geometry, &idx_p))) { @@ -3397,11 +3398,15 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) ++idx_p.vertex_idx; ++idx_p.control_idx; } + if (d2d_vertex_type_is_cubic_bezier(figure->vertex_types[idx_q.vertex_idx])) + split_count++; } else { if (!d2d_geometry_split_bezier(geometry, &idx_p)) return E_OUTOFMEMORY; + if (d2d_vertex_type_is_cubic_bezier(figure->vertex_types[idx_p.vertex_idx])) + split_count++; } } d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_q);
On Tue, 5 May 2020 at 00:20, Connor McAdams conmanx360@gmail.com wrote:
Add a splitting limit for cubic bezier overlap splitting, otherwise certain cubic beziers will indefinitely continue splitting.
Could you provide some more details about how and why that happens? If this is a consequence of D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER, you'll probably need to fold it into 1/8 in order to avoid regressions. On the other hand, in that case not introducing split cubics in 1/8 would also avoid the issue. As you're probably already aware, in order to actually render cubics, you'll need to eliminate self-intersections/double points in d2d_geometry_resolve_beziers(), which also affects the overlap check here.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/tests/d2d1.c | 357 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 357 insertions(+)
diff --git a/dlls/d2d1/tests/d2d1.c b/dlls/d2d1/tests/d2d1.c index 7c0ee91099..a3fe5f10a8 100644 --- a/dlls/d2d1/tests/d2d1.c +++ b/dlls/d2d1/tests/d2d1.c @@ -2494,6 +2494,45 @@ static void fill_geometry_sink_bezier(ID2D1GeometrySink *sink, unsigned int holl ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); }
+static void fill_geometry_sink_cubic_bezier(ID2D1GeometrySink *sink, unsigned int hollow_count) +{ + D2D1_FIGURE_BEGIN begin; + unsigned int idx = 0; + D2D1_POINT_2F point; + + set_point(&point, 25.0f, 220.0f); + begin = idx++ < hollow_count ? D2D1_FIGURE_BEGIN_HOLLOW : D2D1_FIGURE_BEGIN_FILLED; + ID2D1GeometrySink_BeginFigure(sink, point, begin); + cubic_to(sink, 37.5f, 170.0f, 12.5f, 120.0f, 25.0f, 70.0f); + cubic_to(sink, 37.5f, 120.0f, 50.0f, 20.0f, 62.5f, 70.0f); + cubic_to(sink, 50.0f, 120.0f, 75.0f, 170.0f, 62.5f, 220.0f); + cubic_to(sink, 50.0f, 170.0f, 37.5f, 270.0f, 25.0f, 220.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + set_point(&point, 20.0f, 145.0f); + begin = idx++ < hollow_count ? D2D1_FIGURE_BEGIN_HOLLOW : D2D1_FIGURE_BEGIN_FILLED; + ID2D1GeometrySink_BeginFigure(sink, point, begin); + cubic_to(sink, 55.0f, 0.0f, 35.0f, 0.0f, 70.0f, 145.0f); + cubic_to(sink, 35.0f, 290.0f, 55.0f, 290.0f, 20.0f, 145.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + set_point(&point, 25.0f, 672.0f); + begin = idx++ < hollow_count ? D2D1_FIGURE_BEGIN_HOLLOW : D2D1_FIGURE_BEGIN_FILLED; + ID2D1GeometrySink_BeginFigure(sink, point, begin); + cubic_to(sink, 37.5f, 622.0f, 12.5f, 572.0f, 25.0f, 522.0f); + cubic_to(sink, 37.5f, 572.0f, 50.0f, 472.0f, 62.5f, 522.0f); + cubic_to(sink, 50.0f, 572.0f, 75.0f, 622.0f, 62.5f, 672.0f); + cubic_to(sink, 50.0f, 622.0f, 37.5f, 722.0f, 25.0f, 672.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + set_point(&point, 20.0f, 597.0f); + begin = idx++ < hollow_count ? D2D1_FIGURE_BEGIN_HOLLOW : D2D1_FIGURE_BEGIN_FILLED; + ID2D1GeometrySink_BeginFigure(sink, point, begin); + cubic_to(sink, 55.0f, 452.0f, 35.0f, 452.0f, 70.0f, 597.0f); + cubic_to(sink, 35.0f, 742.0f, 55.0f, 742.0f, 20.0f, 597.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); +} + static void test_path_geometry(void) { ID2D1TransformedGeometry *transformed_geometry; @@ -2786,6 +2825,154 @@ static void test_path_geometry(void) /* Figure 28. */ {SEGMENT_LINE, {{{ 75.0f, 300.0f}}}}, {SEGMENT_LINE, {{{ 5.0f, 300.0f}}}}, + /* Figure 29. */ + {SEGMENT_BEZIER, {{{3.75000000e+01f, 1.70000000e+02f}, + {1.25000000e+01f, 1.20000000e+02f}, + {2.50000000e+01f, 7.00000000e+01f}}}}, + {SEGMENT_BEZIER, {{{3.75000000e+01f, 1.20000000e+02f}, + {5.00000000e+01f, 2.00000000e+01f}, + {6.25000000e+01f, 7.00000000e+01f}}}}, + {SEGMENT_BEZIER, {{{5.00000000e+01f, 1.20000000e+02f}, + {7.50000000e+01f, 1.70000000e+02f}, + {6.25000000e+01f, 2.20000000e+02f}}}}, + {SEGMENT_BEZIER, {{{5.00000000e+01f, 1.70000000e+02f}, + {3.75000000e+01f, 2.70000000e+02f}, + {2.50000000e+01f, 2.20000000e+02f}}}}, + /* Figure 30. */ + {SEGMENT_BEZIER, {{{5.50000000e+01f, 0.00000000e+00f}, + {3.50000000e+01f, 0.00000000e+00f}, + {7.00000000e+01f, 1.45000000e+02f}}}}, + {SEGMENT_BEZIER, {{{3.50000000e+01f, 2.90000000e+02f}, + {5.50000000e+01f, 2.90000000e+02f}, + {2.00000000e+01f, 1.45000000e+02f}}}}, + /* Figure 31. */ + {SEGMENT_BEZIER, {{{3.75000000e+01f, 6.22000000e+02f}, + {1.25000000e+01f, 5.72000000e+02f}, + {2.50000000e+01f, 5.22000000e+02f}}}}, + {SEGMENT_BEZIER, {{{3.75000000e+01f, 5.72000000e+02f}, + {5.00000000e+01f, 4.72000000e+02f}, + {6.25000000e+01f, 5.22000000e+02f}}}}, + {SEGMENT_BEZIER, {{{5.00000000e+01f, 5.72000000e+02f}, + {7.50000000e+01f, 6.22000000e+02f}, + {6.25000000e+01f, 6.72000000e+02f}}}}, + {SEGMENT_BEZIER, {{{5.00000000e+01f, 6.22000000e+02f}, + {3.75000000e+01f, 7.22000000e+02f}, + {2.50000000e+01f, 6.72000000e+02f}}}}, + /* Figure 32. */ + {SEGMENT_BEZIER, {{{5.50000000e+01f, 4.52000000e+02f}, + {3.50000000e+01f, 4.52000000e+02f}, + {7.00000000e+01f, 5.97000000e+02f}}}}, + {SEGMENT_BEZIER, {{{3.50000000e+01f, 7.42000000e+02f}, + {5.50000000e+01f, 7.42000000e+02f}, + {2.00000000e+01f, 5.97000000e+02f}}}}, + /* Figure 33. */ + {SEGMENT_LINE, {{{2.50000000e+01f, 7.00000000e+01f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 7.00000000e+01f}}}}, + {SEGMENT_LINE, {{{6.25000000e+01f, 7.00000000e+01f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{6.25000000e+01f, 2.20000000e+02f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 2.20000000e+02f}}}}, + {SEGMENT_LINE, {{{2.50000000e+01f, 2.20000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 34. */ + {SEGMENT_LINE, {{{4.50000000e+01f, 3.62500000e+01f}}}}, + {SEGMENT_LINE, {{{7.00000000e+01f, 1.45000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{4.50000000e+01f, 2.53750000e+02f}}}}, + {SEGMENT_LINE, {{{2.00000000e+01f, 1.45000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 35. */ + {SEGMENT_LINE, {{{2.50000000e+01f, 5.22000000e+02f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 5.22000000e+02f}}}}, + {SEGMENT_LINE, {{{6.25000000e+01f, 5.22000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{6.25000000e+01f, 6.72000000e+02f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 6.72000000e+02f}}}}, + {SEGMENT_LINE, {{{2.50000000e+01f, 6.72000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 36. */ + {SEGMENT_LINE, {{{4.50000000e+01f, 4.88250000e+02f}}}}, + {SEGMENT_LINE, {{{7.00000000e+01f, 5.97000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{4.50000000e+01f, 7.05750000e+02f}}}}, + {SEGMENT_LINE, {{{2.00000000e+01f, 5.97000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 37. */ + {SEGMENT_LINE, {{{2.50000000e+01f, 1.45000000e+02f}}}}, + {SEGMENT_LINE, {{{2.50000000e+01f, 7.00000000e+01f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{3.43750000e+01f, 8.40625000e+01f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 7.00000000e+01f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.31250000e+01f, 5.59375000e+01f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{6.25000000e+01f, 7.00000000e+01f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{6.25000000e+01f, 1.45000000e+02f}}}}, + {SEGMENT_LINE, {{{6.25000000e+01f, 2.20000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.31250000e+01f, 2.05937500e+02f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 2.20000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{3.43750000e+01f, 2.34062500e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{2.50000000e+01f, 2.20000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 38. */ + {SEGMENT_LINE, {{{3.76562500e+01f, 6.34375000e+01f}}}}, + {SEGMENT_LINE, {{{4.50000000e+01f, 3.62500000e+01f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.23437500e+01f, 6.34375000e+01f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{7.00000000e+01f, 1.45000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.23437500e+01f, 2.26562500e+02f}}}}, + {SEGMENT_LINE, {{{4.50000000e+01f, 2.53750000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{3.76562500e+01f, 2.26562500e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{2.00000000e+01f, 1.45000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 39. */ + {SEGMENT_LINE, {{{2.50000000e+01f, 5.97000000e+02f}}}}, + {SEGMENT_LINE, {{{2.50000000e+01f, 5.22000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{3.43750000e+01f, 5.36062500e+02f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 5.22000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.31250000e+01f, 5.07937500e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{6.25000000e+01f, 5.22000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{6.25000000e+01f, 5.97000000e+02f}}}}, + {SEGMENT_LINE, {{{6.25000000e+01f, 6.72000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.31250000e+01f, 6.57937500e+02f}}}}, + {SEGMENT_LINE, {{{4.37500000e+01f, 6.72000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{3.43750000e+01f, 6.86062500e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{2.50000000e+01f, 6.72000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 40. */ + {SEGMENT_LINE, {{{3.76562500e+01f, 5.15437500e+02f}}}}, + {SEGMENT_LINE, {{{4.50000000e+01f, 4.88250000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.23437500e+01f, 5.15437500e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{7.00000000e+01f, 5.97000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{5.23437500e+01f, 6.78562500e+02f}}}}, + {SEGMENT_LINE, {{{4.50000000e+01f, 7.05750000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{3.76562500e+01f, 6.78562500e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + {SEGMENT_LINE, {{{2.00000000e+01f, 5.97000000e+02f}}}, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN}, + /* Figure 41. */ + {SEGMENT_BEZIER, {{{1.96464462e+02f, 1.60274170e+02f}, + {1.87625626e+02f, 5.42081528e+01f}, + {2.05303299e+02f, 5.42081528e+01f}}}}, + {SEGMENT_BEZIER, {{{2.05303299e+02f, 1.24918823e+02f}, + {2.31819809e+02f, 8.95634918e+01f}, + {2.31819809e+02f, 1.60274170e+02f}}}}, + {SEGMENT_BEZIER, {{{2.14142136e+02f, 1.60274170e+02f}, + {2.22980972e+02f, 2.66340179e+02f}, + {2.05303299e+02f, 2.66340179e+02f}}}}, + {SEGMENT_BEZIER, {{{2.05303299e+02f, 1.95629517e+02f}, + {1.78786804e+02f, 2.30984833e+02f}, + {1.78786804e+02f, 1.60274170e+02f}}}}, + /* Figure 42. */ + {SEGMENT_BEZIER, {{{2.38890869e+02f, 8.95634918e+01f}, + {2.24748734e+02f, 3.29949493e+01f}, + {2.23864853e+02f, 2.34520386e+02f}}}}, + {SEGMENT_BEZIER, {{{1.73483490e+02f, 2.38055908e+02f}, + {1.87625641e+02f, 2.94624451e+02f}, + {1.88509521e+02f, 9.30990295e+01f}}}}, + /* Figure 43. */ + {SEGMENT_BEZIER, {{{1.16561401e+02f, 4.79886414e+02f}, + {1.07722572e+02f, 3.73820404e+02f}, + {1.25400238e+02f, 3.73820435e+02f}}}}, + {SEGMENT_BEZIER, {{{1.25400238e+02f, 4.44531067e+02f}, + {1.51916748e+02f, 4.09175751e+02f}, + {1.51916733e+02f, 4.79886414e+02f}}}}, + {SEGMENT_BEZIER, {{{1.34239075e+02f, 4.79886414e+02f}, + {1.43077911e+02f, 5.85952454e+02f}, + {1.25400238e+02f, 5.85952454e+02f}}}}, + {SEGMENT_BEZIER, {{{1.25400238e+02f, 5.15241760e+02f}, + {9.88837280e+01f, 5.50597107e+02f}, + {9.88837280e+01f, 4.79886414e+02f}}}}, + /* Figure 44. */ + {SEGMENT_BEZIER, {{{1.58987808e+02f, 4.09175781e+02f}, + {1.44845673e+02f, 3.52607239e+02f}, + {1.43961792e+02f, 5.54132629e+02f}}}}, + {SEGMENT_BEZIER, {{{9.35804291e+01f, 5.57668152e+02f}, + {1.07722565e+02f, 6.14236694e+02f}, + {1.08606453e+02f, 4.12711273e+02f}}}}, }; static const struct expected_geometry_figure expected_figures[] = { @@ -2829,6 +3016,30 @@ static void test_path_geometry(void) {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 20.0f, 612.0f}, 8, &expected_segments[164]}, /* 28 */ {D2D1_FIGURE_BEGIN_HOLLOW, D2D1_FIGURE_END_OPEN, { 40.0f, 20.0f}, 2, &expected_segments[172]}, + /* 29 */ + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 25.0f, 220.0f}, 4, &expected_segments[174]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 20.0f, 145.0f}, 2, &expected_segments[178]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 25.0f, 672.0f}, 4, &expected_segments[180]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 20.0f, 597.0f}, 2, &expected_segments[184]}, + /* 33 */ + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 25.0f, 220.0f}, 6, &expected_segments[186]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 20.0f, 145.0f}, 4, &expected_segments[192]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 25.0f, 672.0f}, 6, &expected_segments[196]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 20.0f, 597.0f}, 4, &expected_segments[202]}, + /* 37 */ + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 25.0f, 220.0f}, 12, &expected_segments[206]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 20.0f, 145.0f}, 8, &expected_segments[218]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 25.0f, 672.0f}, 12, &expected_segments[226]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, { 20.0f, 597.0f}, 8, &expected_segments[238]}, + /* 41 */ + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, + {1.78786804e+02f, 1.60274170e+02f}, 4, &expected_segments[246]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, + {1.88509521e+02f, 9.30990295e+01f}, 2, &expected_segments[250]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, + {9.88837280e+01f, 4.79886414e+02f}, 4, &expected_segments[252]}, + {D2D1_FIGURE_BEGIN_FILLED, D2D1_FIGURE_END_CLOSED, + {1.08606453e+02f, 4.12711273e+02f}, 2, &expected_segments[256]}, };
if (!(device = create_device())) @@ -3070,6 +3281,8 @@ static void test_path_geometry(void)
ID2D1PathGeometry_Release(geometry);
+ + /* GetBounds() with bezier segments. */ hr = ID2D1Factory_CreatePathGeometry(factory, &geometry); ok(SUCCEEDED(hr), "Failed to create path geometry, hr %#x.\n", hr); @@ -3087,6 +3300,12 @@ static void test_path_geometry(void) ok(match, "Got unexpected rectangle {%.8e, %.8e, %.8e, %.8e}.\n", rect.left, rect.top, rect.right, rect.bottom);
+ ID2D1RenderTarget_BeginDraw(rt); + set_color(&color, 0.396f, 0.180f, 0.537f, 1.0f); + ID2D1RenderTarget_Clear(rt, &color); + ID2D1RenderTarget_FillGeometry(rt, (ID2D1Geometry *)geometry, (ID2D1Brush *)brush, NULL); + hr = ID2D1RenderTarget_EndDraw(rt, NULL, NULL); + set_matrix_identity(&matrix); translate_matrix(&matrix, 80.0f, 640.0f); scale_matrix(&matrix, 2.0f, 0.5f); @@ -3556,7 +3775,145 @@ static void test_path_geometry(void) ok(SUCCEEDED(hr), "Failed to simplify geometry, hr %#x.\n", hr); geometry_sink_check(&simplify_sink, D2D1_FILL_MODE_ALTERNATE, 1, &expected_figures[28], 1); geometry_sink_cleanup(&simplify_sink); + ID2D1PathGeometry_Release(geometry); + + /* GetBounds() with cubic bezier segments. */ + hr = ID2D1Factory_CreatePathGeometry(factory, &geometry); + ok(SUCCEEDED(hr), "Failed to create path geometry, hr %#x.\n", hr); + hr = ID2D1PathGeometry_Open(geometry, &sink); + ok(SUCCEEDED(hr), "Failed to open geometry sink, hr %#x.\n", hr); + fill_geometry_sink_cubic_bezier(sink, 0); + hr = ID2D1GeometrySink_Close(sink); + ok(SUCCEEDED(hr), "Failed to close geometry sink, hr %#x.\n", hr); + ID2D1GeometrySink_Release(sink); + + set_rect(&rect, 0.0f, 0.0f, 0.0f, 0.0f); + hr = ID2D1PathGeometry_GetBounds(geometry, NULL, &rect); + ok(SUCCEEDED(hr), "Failed to get geometry bounds, hr %#x.\n", hr); + match = compare_rect(&rect, 20.0f, 36.25f, 70.0f, 705.75f, 0); + ok(match, "Got unexpected rectangle {%.8e, %.8e, %.8e, %.8e}.\n", + rect.left, rect.top, rect.right, rect.bottom); + + set_matrix_identity(&matrix); + translate_matrix(&matrix, 80.0f, 640.0f); + scale_matrix(&matrix, 2.0f, 0.5f); + set_rect(&rect, 0.0f, 0.0f, 0.0f, 0.0f); + hr = ID2D1PathGeometry_GetBounds(geometry, &matrix, &rect); + ok(SUCCEEDED(hr), "Failed to get geometry bounds, hr %#x.\n", hr); + match = compare_rect(&rect, 120.0f, 658.125f, 220.0f, 992.875f, 0); + ok(match, "Got unexpected rectangle {%.8e, %.8e, %.8e, %.8e}.\n", + rect.left, rect.top, rect.right, rect.bottom); + + ID2D1PathGeometry_Release(geometry); + + /* GetBounds() with cubic bezier segments and some hollow components. */ + hr = ID2D1Factory_CreatePathGeometry(factory, &geometry); + ok(SUCCEEDED(hr), "Failed to create path geometry, hr %#x.\n", hr); + hr = ID2D1PathGeometry_Open(geometry, &sink); + ok(SUCCEEDED(hr), "Failed to open geometry sink, hr %#x.\n", hr); + fill_geometry_sink_cubic_bezier(sink, 2); + hr = ID2D1GeometrySink_Close(sink); + ok(SUCCEEDED(hr), "Failed to close geometry sink, hr %#x.\n", hr); + ID2D1GeometrySink_Release(sink); + + set_rect(&rect, 0.0f, 0.0f, 0.0f, 0.0f); + hr = ID2D1PathGeometry_GetBounds(geometry, NULL, &rect); + ok(SUCCEEDED(hr), "Failed to get geometry bounds, hr %#x.\n", hr); + match = compare_rect(&rect, 20.0f, 488.25f, 70.0f, 705.75f, 0); + ok(match, "Got unexpected rectangle {%.8e, %.8e, %.8e, %.8e}.\n", + rect.left, rect.top, rect.right, rect.bottom); + + set_matrix_identity(&matrix); + translate_matrix(&matrix, 80.0f, 640.0f); + scale_matrix(&matrix, 2.0f, 0.5f); + set_rect(&rect, 0.0f, 0.0f, 0.0f, 0.0f); + hr = ID2D1PathGeometry_GetBounds(geometry, &matrix, &rect); + ok(SUCCEEDED(hr), "Failed to get geometry bounds, hr %#x.\n", hr); + match = compare_rect(&rect, 120.0f, 884.125f, 220.0f, 992.875f, 0); + ok(match, "Got unexpected rectangle {%.8e, %.8e, %.8e, %.8e}.\n", + rect.left, rect.top, rect.right, rect.bottom); + + ID2D1PathGeometry_Release(geometry); + + /* GetBounds() with bezier segments and all hollow components. */ + hr = ID2D1Factory_CreatePathGeometry(factory, &geometry); + ok(SUCCEEDED(hr), "Failed to create path geometry, hr %#x.\n", hr); + hr = ID2D1PathGeometry_Open(geometry, &sink); + ok(SUCCEEDED(hr), "Failed to open geometry sink, hr %#x.\n", hr); + fill_geometry_sink_cubic_bezier(sink, 4); + hr = ID2D1GeometrySink_Close(sink); + ok(SUCCEEDED(hr), "Failed to close geometry sink, hr %#x.\n", hr); + ID2D1GeometrySink_Release(sink); + + set_rect(&rect, 0.0f, 0.0f, 0.0f, 0.0f); + hr = ID2D1PathGeometry_GetBounds(geometry, NULL, &rect); + ok(SUCCEEDED(hr), "Failed to get geometry bounds, hr %#x.\n", hr); + match = compare_rect(&rect, INFINITY, INFINITY, FLT_MAX, FLT_MAX, 0); + ok(match, "Got unexpected rectangle {%.8e, %.8e, %.8e, %.8e}.\n", + rect.left, rect.top, rect.right, rect.bottom); + + set_matrix_identity(&matrix); + translate_matrix(&matrix, 80.0f, 640.0f); + scale_matrix(&matrix, 2.0f, 0.5f); + set_rect(&rect, 0.0f, 0.0f, 0.0f, 0.0f); + hr = ID2D1PathGeometry_GetBounds(geometry, &matrix, &rect); + ok(SUCCEEDED(hr), "Failed to get geometry bounds, hr %#x.\n", hr); + match = compare_rect(&rect, INFINITY, INFINITY, FLT_MAX, FLT_MAX, 0); + ok(match, "Got unexpected rectangle {%.8e, %.8e, %.8e, %.8e}.\n", + rect.left, rect.top, rect.right, rect.bottom); + + ID2D1PathGeometry_Release(geometry); + + /* Cubic bezier simplify tests. */ + hr = ID2D1Factory_CreatePathGeometry(factory, &geometry); + ok(SUCCEEDED(hr), "Failed to create path geometry, hr %#x.\n", hr); + hr = ID2D1PathGeometry_Open(geometry, &sink); + ok(SUCCEEDED(hr), "Failed to open geometry sink, hr %#x.\n", hr); + fill_geometry_sink_cubic_bezier(sink, 0); + hr = ID2D1GeometrySink_Close(sink); + ok(SUCCEEDED(hr), "Failed to close geometry sink, hr %#x.\n", hr); + hr = ID2D1PathGeometry_GetFigureCount(geometry, &count); + ok(SUCCEEDED(hr), "Failed to get figure count, hr %#x.\n", hr); + ok(count == 4, "Got unexpected figure count %u.\n", count); + hr = ID2D1PathGeometry_GetSegmentCount(geometry, &count); + ok(SUCCEEDED(hr), "Failed to get segment count, hr %#x.\n", hr); + ok(count == 16, "Got unexpected segment count %u.\n", count); + ID2D1GeometrySink_Release(sink); + + geometry_sink_init(&simplify_sink); + hr = ID2D1PathGeometry_Simplify(geometry, D2D1_GEOMETRY_SIMPLIFICATION_OPTION_CUBICS_AND_LINES, + NULL, 0.0f, &simplify_sink.ID2D1SimplifiedGeometrySink_iface); + ok(SUCCEEDED(hr), "Failed to simplify geometry, hr %#x.\n", hr); + geometry_sink_check(&simplify_sink, D2D1_FILL_MODE_ALTERNATE, 4, &expected_figures[29], 1); + geometry_sink_cleanup(&simplify_sink); + geometry_sink_init(&simplify_sink); + hr = ID2D1PathGeometry_Simplify(geometry, D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES, + NULL, 100.0f, &simplify_sink.ID2D1SimplifiedGeometrySink_iface); + ok(SUCCEEDED(hr), "Failed to simplify geometry, hr %#x.\n", hr); + geometry_sink_check(&simplify_sink, D2D1_FILL_MODE_ALTERNATE, 4, &expected_figures[33], 1); + geometry_sink_cleanup(&simplify_sink); + geometry_sink_init(&simplify_sink); + hr = ID2D1PathGeometry_Simplify(geometry, D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES, + NULL, 10.0f, &simplify_sink.ID2D1SimplifiedGeometrySink_iface); + ok(SUCCEEDED(hr), "Failed to simplify geometry, hr %#x.\n", hr); + geometry_sink_check(&simplify_sink, D2D1_FILL_MODE_ALTERNATE, 4, &expected_figures[37], 1); + geometry_sink_cleanup(&simplify_sink);
+ set_matrix_identity(&matrix); + scale_matrix(&matrix, 0.5f, 2.0f); + translate_matrix(&matrix, 400.0f, -33.0f); + rotate_matrix(&matrix, M_PI / 4.0f); + scale_matrix(&matrix, 2.0f, 0.5f); + hr = ID2D1Factory_CreateTransformedGeometry(factory, (ID2D1Geometry *)geometry, &matrix, &transformed_geometry); + ok(SUCCEEDED(hr), "Failed to create transformed geometry, hr %#x.\n", hr); + + geometry_sink_init(&simplify_sink); + hr = ID2D1TransformedGeometry_Simplify(transformed_geometry, D2D1_GEOMETRY_SIMPLIFICATION_OPTION_CUBICS_AND_LINES, + NULL, 0.0f, &simplify_sink.ID2D1SimplifiedGeometrySink_iface); + ok(SUCCEEDED(hr), "Failed to simplify geometry, hr %#x.\n", hr); + geometry_sink_check(&simplify_sink, D2D1_FILL_MODE_ALTERNATE, 4, &expected_figures[41], 4); + geometry_sink_cleanup(&simplify_sink); + ID2D1TransformedGeometry_Release(transformed_geometry); ID2D1PathGeometry_Release(geometry);
ID2D1SolidColorBrush_Release(brush);
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/tests/d2d1.c | 72 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+)
diff --git a/dlls/d2d1/tests/d2d1.c b/dlls/d2d1/tests/d2d1.c index a3fe5f10a8..7426a793c0 100644 --- a/dlls/d2d1/tests/d2d1.c +++ b/dlls/d2d1/tests/d2d1.c @@ -8256,6 +8256,78 @@ static void test_bezier_intersect(void) "c9EBcdQBb9YBbNkBatsBaN0BZeEBYuQBX+gBW+0BVvEBUvUBTvwBR4QCQIoCOZgCK6oCGQIA"); ok(match, "Figure does not match.\n");
+ /* Cubic bezier figure with a single line-bezier intersection and multiple + * double line-bezier intersections. */ + hr = ID2D1Factory_CreatePathGeometry(factory, &geometry); + ok(SUCCEEDED(hr), "Failed to create path geometry, hr %#x.\n", hr); + hr = ID2D1PathGeometry_Open(geometry, &sink); + ok(SUCCEEDED(hr), "Failed to open geometry sink, hr %#x.\n", hr); + + set_point(&point, 50.0f, 120.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + cubic_to(sink, 100.0f, 20.0f, 150.0f, 220.0f, 200.0f, 120.0f); + cubic_to(sink, 150.0f, 320.0f, 250.0f, 520.0f, 200.0f, 720.0f); + cubic_to(sink, 150.0f, 620.0f, 100.0f, 820.0f, 50.0f, 720.0f); + cubic_to(sink, 0.0f, 520.0f, 100.0f, 320.0f, 50.0f, 120.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + set_point(&point, 40.0f, 80.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + line_to(sink, 180.0f, 80.0f); + line_to(sink, 180.0f, 720.0f); + line_to(sink, 40.0f, 720.0f); + + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + hr = ID2D1GeometrySink_Close(sink); + ok(SUCCEEDED(hr), "Failed to close geometry sink, hr %#x.\n", hr); + ID2D1GeometrySink_Release(sink); + + ID2D1RenderTarget_BeginDraw(rt); + set_color(&color, 1.0f, 1.0f, 1.0f, 1.0f); + set_color(&color, 0.396f, 0.180f, 0.537f, 1.0f); + ID2D1RenderTarget_Clear(rt, &color); + ID2D1RenderTarget_FillGeometry(rt, (ID2D1Geometry *)geometry, (ID2D1Brush *)brush, NULL); + hr = ID2D1RenderTarget_EndDraw(rt, NULL, NULL); + ok(SUCCEEDED(hr), "Failed to end draw, hr %#x.\n", hr); + ID2D1PathGeometry_Release(geometry); + + /* Cubic bezier figure with a line-bezier intersection of 3 points within + * one line and one bezier segment. */ + hr = ID2D1Factory_CreatePathGeometry(factory, &geometry); + ok(SUCCEEDED(hr), "Failed to create path geometry, hr %#x.\n", hr); + hr = ID2D1PathGeometry_Open(geometry, &sink); + ok(SUCCEEDED(hr), "Failed to open geometry sink, hr %#x.\n", hr); + + set_point(&point, 50.0f, 120.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + cubic_to(sink, 100.0f, 20.0f, 150.0f, 220.0f, 200.0f, 120.0f); + cubic_to(sink, 150.0f, 320.0f, 250.0f, 520.0f, 200.0f, 720.0f); + cubic_to(sink, 150.0f, 620.0f, 100.0f, 820.0f, 50.0f, 720.0f); + cubic_to(sink, 0.0f, 520.0f, 100.0f, 320.0f, 50.0f, 120.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + set_point(&point, 20.0f, 20.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + line_to(sink, 180.0f, 80.0f); + line_to(sink, 220.0f, 900.0f); + line_to(sink, 20.0f, 900.0f); + + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + hr = ID2D1GeometrySink_Close(sink); + ok(SUCCEEDED(hr), "Failed to close geometry sink, hr %#x.\n", hr); + ID2D1GeometrySink_Release(sink); + + ID2D1RenderTarget_BeginDraw(rt); + set_color(&color, 1.0f, 1.0f, 1.0f, 1.0f); + set_color(&color, 0.396f, 0.180f, 0.537f, 1.0f); + ID2D1RenderTarget_Clear(rt, &color); + ID2D1RenderTarget_FillGeometry(rt, (ID2D1Geometry *)geometry, (ID2D1Brush *)brush, NULL); + hr = ID2D1RenderTarget_EndDraw(rt, NULL, NULL); + ok(SUCCEEDED(hr), "Failed to end draw, hr %#x.\n", hr); + ID2D1PathGeometry_Release(geometry); + ID2D1SolidColorBrush_Release(brush); ID2D1RenderTarget_Release(rt); refcount = ID2D1Factory_Release(factory);
On Tue, 5 May 2020 at 00:15, Connor McAdams conmanx360@gmail.com wrote:
Looking for feedback on my current methods of storing the control points of cubic beziers, and the new bezier flattening method. Also, any suggestions on more tests to write would be helpful.
The way cubics are stored largely makes sense to me. I have some more specific comments in reply to the patch itself. I didn't look at the flattening code; it seems best to worry about one thing at a time for the moment.
-
Connor McAdams -
Henri Verbeet -
Marvin