[RFC PATCH 0/5] Cubic bezier helper functions.
Changed to maintain quadratic beziers alongside cubics. These are the initial helper functions before rendering, submitted for consideration. Connor McAdams (5): d2d1: Store cubic bezier control points. d2d1: Add cubic bezier bounds functions. d2d1: Add cubic bezier-bezier intersect functions. d2d1: Add cubic bezier-line intersection functions. d2d1: Update apply_intersections for cubic beziers. dlls/d2d1/geometry.c | 725 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 621 insertions(+), 104 deletions(-) -- 2.20.1
Store cubic bezier control points, instead of storing them as quadratics. Signed-off-by: Connor McAdams <conmanx360(a)gmail.com> --- dlls/d2d1/geometry.c | 197 +++++++++++++++++++++++++++++++++---------- 1 file changed, 154 insertions(+), 43 deletions(-) diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index c18b648aef..6f48980eb8 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -44,12 +44,17 @@ enum d2d_cdt_edge_next D2D_EDGE_NEXT_TOR = 3, }; +/* Flag bit for bezier vertices. */ +#define D2D_VERTEX_TYPE_SPLIT_BEZIER 0x40 +#define D2D_VERTEX_TYPE_BEZIER 0x80 enum d2d_vertex_type { - D2D_VERTEX_TYPE_NONE, - D2D_VERTEX_TYPE_LINE, - D2D_VERTEX_TYPE_BEZIER, - D2D_VERTEX_TYPE_SPLIT_BEZIER, + D2D_VERTEX_TYPE_NONE = 0, + D2D_VERTEX_TYPE_LINE = 1, + D2D_VERTEX_TYPE_QUADRATIC_BEZIER = 2 | D2D_VERTEX_TYPE_BEZIER, + D2D_VERTEX_TYPE_CUBIC_BEZIER = 3 | D2D_VERTEX_TYPE_BEZIER, + D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER = 4 | D2D_VERTEX_TYPE_SPLIT_BEZIER, + D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER = 5 | D2D_VERTEX_TYPE_SPLIT_BEZIER, }; struct d2d_segment_idx @@ -57,6 +62,7 @@ struct d2d_segment_idx size_t figure_idx; size_t vertex_idx; size_t control_idx; + size_t bezier_idx; }; struct d2d_figure @@ -70,6 +76,7 @@ struct d2d_figure D2D1_POINT_2F *bezier_controls; size_t bezier_controls_size; size_t bezier_control_count; + size_t bezier_control_points; D2D1_POINT_2F *original_bezier_controls; size_t original_bezier_control_count; @@ -409,6 +416,15 @@ 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; +} + /* 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,33 +629,35 @@ 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_quadratic_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; } memmove(&figure->bezier_controls[idx + 1], &figure->bezier_controls[idx], - (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls)); + (figure->bezier_control_points - idx) * sizeof(*figure->bezier_controls)); figure->bezier_controls[idx] = *p; + ++figure->bezier_control_points; ++figure->bezier_control_count; return TRUE; } -static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) +static BOOL d2d_figure_add_quadratic_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; } - figure->bezier_controls[figure->bezier_control_count++] = *p; + figure->bezier_controls[figure->bezier_control_points++] = *p; + ++figure->bezier_control_count; return TRUE; } @@ -1875,7 +1893,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 (!(vertex_type & D2D_VERTEX_TYPE_BEZIER) && !(vertex_type & D2D_VERTEX_TYPE_SPLIT_BEZIER)) { if (!d2d_figure_insert_vertex(&geometry->u.path.figures[inter->figure_idx], inter->vertex_idx + vertex_offset + 1, inter->p)) @@ -1908,13 +1926,13 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry, 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]))) + if (!(d2d_figure_insert_quadratic_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1]))) return FALSE; ++control_offset; 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] = D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER; ++vertex_offset; } @@ -1961,9 +1979,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 (type_q & D2D_VERTEX_TYPE_BEZIER) { - if (type_p == D2D_VERTEX_TYPE_BEZIER) + if (type_p & D2D_VERTEX_TYPE_BEZIER) { if (!d2d_geometry_intersect_bezier_bezier(geometry, &intersections, &idx_p, 0.0f, 1.0f, &idx_q, 0.0f, 1.0f)) @@ -1974,11 +1992,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 (type_p & D2D_VERTEX_TYPE_BEZIER) { if (!d2d_geometry_intersect_bezier_line(geometry, &intersections, &idx_p, &idx_q)) goto done; @@ -1991,8 +2012,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,27 +2351,30 @@ 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) - prev = &figure->bezier_controls[figure->bezier_control_count - 1]; + if (prev_type & D2D_VERTEX_TYPE_BEZIER) + prev = &figure->bezier_controls[figure->bezier_control_points - 1]; else prev = &figure->vertices[figure->vertex_count - 1]; } else { prev_type = figure->vertex_types[i - 1]; - if (prev_type == D2D_VERTEX_TYPE_BEZIER) + if (prev_type & D2D_VERTEX_TYPE_BEZIER) prev = &figure->bezier_controls[bezier_idx - 1]; else prev = &figure->vertices[i - 1]; } - if (type == D2D_VERTEX_TYPE_BEZIER) + if (type & D2D_VERTEX_TYPE_BEZIER) 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 +2398,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 (type & D2D_VERTEX_TYPE_BEZIER) { 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"); @@ -2581,12 +2615,12 @@ 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_QUADRATIC_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)) + if (!d2d_figure_add_quadratic_bezier_control(figure, &p)) { ERR("Failed to add bezier control.\n"); geometry->u.path.state = D2D_GEOMETRY_STATE_ERROR; @@ -2659,23 +2693,31 @@ 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 (type == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER || type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + ++idx->control_idx; + ++idx->vertex_idx; ++idx->control_idx; + ++idx->bezier_idx; } - for (; idx->figure_idx < geometry->u.path.figure_count; ++idx->figure_idx, idx->vertex_idx = idx->control_idx = 0) + for (; idx->figure_idx < geometry->u.path.figure_count; ++idx->figure_idx, + idx->vertex_idx = idx->control_idx = idx->bezier_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 (type & D2D_VERTEX_TYPE_BEZIER || type & D2D_VERTEX_TYPE_SPLIT_BEZIER) return TRUE; } } @@ -2815,11 +2857,11 @@ static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struc d2d_point_lerp(&q[2], &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]))) + if (!(d2d_figure_insert_quadratic_bezier_control(figure, idx->control_idx + 1, &q[1]))) return FALSE; if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2]))) return FALSE; - figure->vertex_types[idx->vertex_idx + 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER; + figure->vertex_types[idx->vertex_idx + 1] = D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER; return TRUE; } @@ -2867,7 +2909,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) { if (geometry->u.path.figures[i].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 * geometry->u.path.figures[i].bezier_control_points; } if (!(geometry->fill.bezier_vertices = heap_calloc(geometry->fill.bezier_vertex_count, @@ -2934,7 +2976,7 @@ static HRESULT STDMETHODCALLTYPE d2d_geometry_sink_Close(ID2D1GeometrySink *ifac for (i = 0; i < geometry->u.path.figure_count; ++i) { struct d2d_figure *figure = &geometry->u.path.figures[i]; - size_t size = figure->bezier_control_count * sizeof(*figure->original_bezier_controls); + size_t size = figure->bezier_control_points * sizeof(*figure->original_bezier_controls); if (!(figure->original_bezier_controls = heap_alloc(size))) goto done; memcpy(figure->original_bezier_controls, figure->bezier_controls, size); @@ -3002,8 +3044,8 @@ 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; - if (!d2d_figure_add_bezier_control(figure, &beziers[i].point1)) + figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_QUADRATIC_BEZIER; + if (!d2d_figure_add_quadratic_bezier_control(figure, &beziers[i].point1)) { ERR("Failed to add bezier.\n"); geometry->u.path.state = D2D_GEOMETRY_STATE_ERROR; @@ -3198,7 +3240,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) + || figure->vertex_types[j] & D2D_VERTEX_TYPE_SPLIT_BEZIER) continue; switch (type) @@ -3209,7 +3251,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 +3261,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 +3286,20 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry * type = figure->vertex_types[j]; } - if (type == D2D_VERTEX_TYPE_BEZIER) + if (type & D2D_VERTEX_TYPE_BEZIER) { - 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 +3432,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 +3457,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 +3485,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) + || figure->vertex_types[j] & D2D_VERTEX_TYPE_SPLIT_BEZIER) continue; switch (type) @@ -3413,7 +3497,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 +3508,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 +3534,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 +3544,19 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_Simplify(ID2D1PathGeometry *i d2d_point_transform(&p2, transform, p2.x, p2.y); d2d_geometry_simplify_quadratic(sink, option, &p, &p1, &p2, tolerance); } + else if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER) + { + p1 = figure->original_bezier_controls[bezier_idx++]; + if (transform) + d2d_point_transform(&p1, transform, p1.x, p1.y); + p2 = figure->original_bezier_controls[bezier_idx++]; + if (transform) + d2d_point_transform(&p2, transform, p2.x, p2.y); + p3 = figure->vertices[0]; + if (transform) + d2d_point_transform(&p3, transform, p3.x, p3.y); + d2d_geometry_simplify_cubic(sink, option, &p, &p1, &p2, &p3, tolerance); + } end = figure->flags & D2D_FIGURE_FLAG_CLOSED ? D2D1_FIGURE_END_CLOSED : D2D1_FIGURE_END_OPEN; ID2D1SimplifiedGeometrySink_EndFigure(sink, end); -- 2.20.1
On Sun, 15 Mar 2020 at 23:13, Connor McAdams <conmanx360(a)gmail.com> wrote:
+/* Flag bit for bezier vertices. */ +#define D2D_VERTEX_TYPE_SPLIT_BEZIER 0x40 +#define D2D_VERTEX_TYPE_BEZIER 0x80 enum d2d_vertex_type { - D2D_VERTEX_TYPE_NONE, - D2D_VERTEX_TYPE_LINE, - D2D_VERTEX_TYPE_BEZIER, - D2D_VERTEX_TYPE_SPLIT_BEZIER, + D2D_VERTEX_TYPE_NONE = 0, + D2D_VERTEX_TYPE_LINE = 1, + D2D_VERTEX_TYPE_QUADRATIC_BEZIER = 2 | D2D_VERTEX_TYPE_BEZIER, + D2D_VERTEX_TYPE_CUBIC_BEZIER = 3 | D2D_VERTEX_TYPE_BEZIER, + D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER = 4 | D2D_VERTEX_TYPE_SPLIT_BEZIER, + D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER = 5 | D2D_VERTEX_TYPE_SPLIT_BEZIER, }; That's a bit ugly. If you really need to store extra information, you could replace the "vertex_types" array with something like the following:
struct d2d_segment { uint16_t type; uint16_t flags; } *segments; Or some variant. For what you're doing here though, it seems much easier to do something like the following: 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; }
@@ -57,6 +62,7 @@ struct d2d_segment_idx size_t figure_idx; size_t vertex_idx; size_t control_idx; + size_t bezier_idx; };
struct d2d_figure @@ -70,6 +76,7 @@ struct d2d_figure D2D1_POINT_2F *bezier_controls; size_t bezier_controls_size; size_t bezier_control_count; + size_t bezier_control_points;
Are those really needed?
-static BOOL d2d_figure_insert_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) +static BOOL d2d_figure_insert_quadratic_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; }
memmove(&figure->bezier_controls[idx + 1], &figure->bezier_controls[idx], - (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls)); + (figure->bezier_control_points - idx) * sizeof(*figure->bezier_controls)); figure->bezier_controls[idx] = *p; + ++figure->bezier_control_points; ++figure->bezier_control_count;
return TRUE; }
-static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) +static BOOL d2d_figure_add_quadratic_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; }
- figure->bezier_controls[figure->bezier_control_count++] = *p; + figure->bezier_controls[figure->bezier_control_points++] = *p; + ++figure->bezier_control_count;
return TRUE; } These don't seem all that specific to quadratics.
On Tue, Mar 17, 2020 at 09:04:10PM +0330, Henri Verbeet wrote:
On Sun, 15 Mar 2020 at 23:13, Connor McAdams <conmanx360(a)gmail.com> wrote:
+/* Flag bit for bezier vertices. */ +#define D2D_VERTEX_TYPE_SPLIT_BEZIER 0x40 +#define D2D_VERTEX_TYPE_BEZIER 0x80 enum d2d_vertex_type { - D2D_VERTEX_TYPE_NONE, - D2D_VERTEX_TYPE_LINE, - D2D_VERTEX_TYPE_BEZIER, - D2D_VERTEX_TYPE_SPLIT_BEZIER, + D2D_VERTEX_TYPE_NONE = 0, + D2D_VERTEX_TYPE_LINE = 1, + D2D_VERTEX_TYPE_QUADRATIC_BEZIER = 2 | D2D_VERTEX_TYPE_BEZIER, + D2D_VERTEX_TYPE_CUBIC_BEZIER = 3 | D2D_VERTEX_TYPE_BEZIER, + D2D_VERTEX_TYPE_SPLIT_QUAD_BEZIER = 4 | D2D_VERTEX_TYPE_SPLIT_BEZIER, + D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER = 5 | D2D_VERTEX_TYPE_SPLIT_BEZIER, }; That's a bit ugly. If you really need to store extra information, you could replace the "vertex_types" array with something like the following:
struct d2d_segment { uint16_t type; uint16_t flags; } *segments;
Or some variant. For what you're doing here though, it seems much easier to do something like the following:
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; }
Okay, I can change that. That does seem to be the cleaner way to do it.
@@ -57,6 +62,7 @@ struct d2d_segment_idx size_t figure_idx; size_t vertex_idx; size_t control_idx; + size_t bezier_idx; };
struct d2d_figure @@ -70,6 +76,7 @@ struct d2d_figure D2D1_POINT_2F *bezier_controls; size_t bezier_controls_size; size_t bezier_control_count; + size_t bezier_control_points;
Are those really needed? Yes, they become more useful in later patches where there are triangulation structures per-bezier and not per-point, so knowing which bezier control we are on and not which control point we are on becomes necessary. I guess I could just introduce these changes in those patches where it becomes used specifically, but it seemed to be more related to this patch (in my opinion).
-static BOOL d2d_figure_insert_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) +static BOOL d2d_figure_insert_quadratic_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; }
memmove(&figure->bezier_controls[idx + 1], &figure->bezier_controls[idx], - (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls)); + (figure->bezier_control_points - idx) * sizeof(*figure->bezier_controls)); figure->bezier_controls[idx] = *p; + ++figure->bezier_control_points; ++figure->bezier_control_count;
return TRUE; }
-static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) +static BOOL d2d_figure_add_quadratic_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; }
- figure->bezier_controls[figure->bezier_control_count++] = *p; + figure->bezier_controls[figure->bezier_control_points++] = *p; + ++figure->bezier_control_count;
return TRUE; } These don't seem all that specific to quadratics. They are specific to quadratics in that they're only introducing one new control point. When cubics actually begin to be in use, there are d2d_figure_add_cubic_bezier_control functions along with the quadratic ones.
I guess I may be confused as to when to introduce certain things. I could introduce the add_cubic functions in this patch, but then I'd have to drop them all down to quadratics until they're actually beginning to be used. I guess this patch already does that in some areas, so maybe it'd make sense to just do them all like that. If you have any suggestions, please let me know. Thanks for the review.
On Tue, 17 Mar 2020 at 21:46, Connor McAdams <conmanx360(a)gmail.com> wrote:
On Tue, Mar 17, 2020 at 09:04:10PM +0330, Henri Verbeet wrote:
On Sun, 15 Mar 2020 at 23:13, Connor McAdams <conmanx360(a)gmail.com> wrote:
@@ -57,6 +62,7 @@ struct d2d_segment_idx size_t figure_idx; size_t vertex_idx; size_t control_idx; + size_t bezier_idx; };
struct d2d_figure @@ -70,6 +76,7 @@ struct d2d_figure D2D1_POINT_2F *bezier_controls; size_t bezier_controls_size; size_t bezier_control_count; + size_t bezier_control_points;
Are those really needed? Yes, they become more useful in later patches where there are triangulation structures per-bezier and not per-point, so knowing which bezier control we are on and not which control point we are on becomes necessary. I guess I could just introduce these changes in those patches where it becomes used specifically, but it seemed to be more related to this patch (in my opinion).
It's hard to say much without having seen the code that uses these, but for what it's worth: - What does "bezier_control_points" signify? Based on the name I'd expect it to be an array of bezier control points; i.e., the same as "bezier_controls". In practice it seems to mostly be a variant of "bezier_control_count", but without looking much closer at the patches it's not clear it stores any information that couldn't be reconstructed from the vertex type information. - That is again without having seen the code using it, but the d2d_segment_idx structure is used for indexing segments. E.g. suppose you have the index {1, 2, 3}, that refers to the segment starting at figures[1]->vertices[2], of type figures[1]->vertex_types[2]. If that type were to be a cubic bezier, it would have control points figures[1]->bezier_controls[3] and figures[1]->bezier_controls[4]. Unless this was the last segment in the figure, the next segment would then have index {1, 3, 5}.
-static BOOL d2d_figure_insert_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) +static BOOL d2d_figure_insert_quadratic_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; }
memmove(&figure->bezier_controls[idx + 1], &figure->bezier_controls[idx], - (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls)); + (figure->bezier_control_points - idx) * sizeof(*figure->bezier_controls)); figure->bezier_controls[idx] = *p; + ++figure->bezier_control_points; ++figure->bezier_control_count;
return TRUE; }
-static BOOL d2d_figure_add_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) +static BOOL d2d_figure_add_quadratic_bezier_control(struct d2d_figure *figure, const D2D1_POINT_2F *p) { if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, - figure->bezier_control_count + 1, sizeof(*figure->bezier_controls))) + figure->bezier_control_points + 1, sizeof(*figure->bezier_controls))) { ERR("Failed to grow bezier controls array.\n"); return FALSE; }
- figure->bezier_controls[figure->bezier_control_count++] = *p; + figure->bezier_controls[figure->bezier_control_points++] = *p; + ++figure->bezier_control_count;
return TRUE; } These don't seem all that specific to quadratics. They are specific to quadratics in that they're only introducing one new control point. When cubics actually begin to be in use, there are d2d_figure_add_cubic_bezier_control functions along with the quadratic ones.
Well, sure. But you could also handle that by either simply calling d2d_figure_add_bezier_control()/d2d_figure_insert_bezier_control() twice for cubics, or by introducing d2d_figure_add_bezier_controls()/d2d_figure_insert_bezier_controls() which would add/insert an array of points instead of a single one.
Add functions for calculating the bounds of a cubic bezier. Signed-off-by: Connor McAdams <conmanx360(a)gmail.com> --- dlls/d2d1/geometry.c | 181 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 151 insertions(+), 30 deletions(-) diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 6f48980eb8..33d55c6451 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -399,7 +399,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; @@ -408,6 +408,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; @@ -522,7 +536,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; @@ -544,18 +558,124 @@ 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, a, b, c; + float root, sq_root; + + 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.x = v1.x - 2.0f * v2.x + v3.x; + a.y = v1.y - 2.0f * v2.y + v3.y; + b.x = 2.0f * (v2.x - v1.x); + b.y = 2.0f * (v2.y - v1.y); + c.x = v1.x; + c.y = v1.y; + + /* If the square root in the equation is negative, there are no roots. */ + if ((sq_root = sqrtf(b.x * b.x - 4.0f * a.x * c.x)) >= 0.0f) + { + root = (-b.x + sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + + root = (-b.x - sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + } + + if ((sq_root = sqrtf(b.y * b.y - 4.0f * a.y * c.y)) >= 0.0f) + { + root = (-b.y + sq_root) / (2.0f * a.y); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + + root = (-b.y - sq_root) / (2.0f * a.y); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + } +} + + static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float start, float end) { @@ -570,7 +690,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) @@ -1715,7 +1835,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 @@ -1848,7 +1968,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; @@ -2617,8 +2737,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_QUADRATIC_BEZIER; - d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1], - &p, &beziers[i].point3); + d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1], + &beziers[i].point1, &beziers[i].point2, &beziers[i].point3); if (!d2d_figure_add_quadratic_bezier_control(figure, &p)) { @@ -3041,7 +3161,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; @@ -3211,7 +3331,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) @@ -3256,23 +3376,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: @@ -3290,20 +3408,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); } } -- 2.20.1
On Sun, 15 Mar 2020 at 23:20, Connor McAdams <conmanx360(a)gmail.com> wrote:
+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, a, b, c; + float root, sq_root; + + 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; + } Is that test worth it?
+ /* + * 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 + */ ... + /* If the square root in the equation is negative, there are no roots. */ + if ((sq_root = sqrtf(b.x * b.x - 4.0f * a.x * c.x)) >= 0.0f) + { + root = (-b.x + sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + + root = (-b.x - sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + } Passing a negative value to sqrtf() won't return a negative result. (And it shouldn't, of course.) It'll return NaN.
When the value of √(b² - 4ac) is close to b (i.e., if b² is much larger than 4ac), -b + √(b² - 4ac) will have a relatively large error. Fortunately, this particular formula has another well-known variant: 2c / (-b ∓ √(b² - 4ac)) It has the same issue, but in the opposite case, so you can use one calculation or the other depending on the sign of b.
On Tue, Mar 17, 2020 at 09:04:18PM +0330, Henri Verbeet wrote:
On Sun, 15 Mar 2020 at 23:20, Connor McAdams <conmanx360(a)gmail.com> wrote:
+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, a, b, c; + float root, sq_root; + + 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; + } Is that test worth it?
Yes, because trying to get the roots of a quadratic that's been upped to a cubic with the cubic root functions won't get the correct values. You need to get the derivative of a quadratic for a quadratic, even if it's been upped to a cubic.
+ /* + * 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 + */ ... + /* If the square root in the equation is negative, there are no roots. */ + if ((sq_root = sqrtf(b.x * b.x - 4.0f * a.x * c.x)) >= 0.0f) + { + root = (-b.x + sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + + root = (-b.x - sq_root) / (2.0f * a.x); + if (root < 1.0f && root > 0.0f) + { + d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root); + d2d_rect_expand(bounds, &p); + } + } Passing a negative value to sqrtf() won't return a negative result. (And it shouldn't, of course.) It'll return NaN.
When the value of √(b² - 4ac) is close to b (i.e., if b² is much larger than 4ac), -b + √(b² - 4ac) will have a relatively large error. Fortunately, this particular formula has another well-known variant:
2c / (-b ∓ √(b² - 4ac))
It has the same issue, but in the opposite case, so you can use one calculation or the other depending on the sign of b. Okay, I will change this. Thanks for the insight.
Update bezier-bezier intersection function to handle both cubic and quadratic beziers. Signed-off-by: Connor McAdams <conmanx360(a)gmail.com> --- dlls/d2d1/geometry.c | 83 +++++++++++++++++++++++++++++++++++++++----- 1 file changed, 75 insertions(+), 8 deletions(-) diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 33d55c6451..0fb46a9c87 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -439,6 +439,38 @@ static void d2d_bezier_cubic_to_quad(const D2D1_POINT_2F *p0, const D2D1_POINT_2 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; + } +} + /* 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. */ @@ -676,8 +708,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]; @@ -693,6 +726,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, @@ -1934,31 +1982,46 @@ 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; + enum d2d_vertex_type type_p, type_q; D2D_RECT_F p_bounds, q_bounds; D2D1_POINT_2F intersection; 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]; + 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]; + 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]; + q[3] = &figure->vertices[next]; + + 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 + d2d_rect_get_quadratic_bezier_segment_bounds(&p_bounds, p[0], p[1], p[3], start_p, end_p); + + 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); - 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 (!d2d_rect_check_overlap(&p_bounds, &q_bounds)) return TRUE; @@ -1968,7 +2031,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; -- 2.20.1
Update bezier-line intersection function to handle both cubic and quadratic beziers. Signed-off-by: Connor McAdams <conmanx360(a)gmail.com> --- dlls/d2d1/geometry.c | 216 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 193 insertions(+), 23 deletions(-) diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index 0fb46a9c87..dd6f50bbec 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -1880,10 +1880,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 @@ -1902,35 +1910,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; - size_t next; - - figure = &geometry->u.path.figures[idx_p->figure_idx]; - p[0] = &figure->vertices[idx_p->vertex_idx]; - p[1] = &figure->bezier_controls[idx_p->control_idx]; - next = idx_p->vertex_idx + 1; - if (next == figure->vertex_count) - next = 0; - p[2] = &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]; /* 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. * @@ -1947,7 +1938,7 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry, * = (2P₀ - 2P₁ ± √(4P₀² + 4P₁² - 8P₀P₁ - 4P₀² + 8P₀P₁ - 4P₀P₂)) / (2P₀ - 4P₁ + 2P₂) * = (P₀ - P₁ ± √(P₁² - P₀P₂)) / (P₀ - 2P₁ + P₂) */ - d = y[0] - 2 * y[1] + y[2]; + d = y[0] - 2.0f * y[1] + y[2]; if (d == 0.0f) { /* P₀ - 2P₁ + P₂ = 0 @@ -1975,6 +1966,185 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry, return FALSE; 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 float d2d_bezier_round_to_zero(float a) +{ + if ((a < 0.0005f && a > -0.0005f)) + return 0.0f; + else + return a; +} + +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; + float a, b, c, d; + + /* 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 (d2d_bezier_round_to_zero(d) == 0.0f) + { + /* Check if it's actually a line. */ + if (d2d_bezier_round_to_zero(a) == 0.0f) + { + /* Check if it's just a point. If it is, no roots. */ + if (d2d_bezier_round_to_zero(b) == 0.0f) + return 0; + + roots[0] = -c / b; + return 1; + } + + tmp = sqrtf(b * b - 4.0 * a * c); + roots[0] = (tmp - b) / (2.0 * a); + roots[1] = (-b - tmp) / (2.0 * a); + return 2; + } + + 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; + + disc = d2d_bezier_round_to_zero(disc); + 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) - a / 3.0f; + roots[1] = t1 * cosf((phi + 2 * M_PI) / 3) - a / 3.0f; + roots[2] = t1 * cosf((phi + 4 * M_PI) / 3) - a / 3.0f; + + return 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); + + return 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; + + return 1; + } + + return 0; +} + +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); + + return TRUE; } static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry, -- 2.20.1
Signed-off-by: Connor McAdams <conmanx360(a)gmail.com> --- dlls/d2d1/geometry.c | 84 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 66 insertions(+), 18 deletions(-) diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index dd6f50bbec..154741a364 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -830,6 +830,26 @@ static BOOL d2d_figure_add_quadratic_bezier_control(struct d2d_figure *figure, c return TRUE; } +static BOOL d2d_figure_insert_cubic_bezier_control(struct d2d_figure *figure, size_t idx, const D2D1_POINT_2F *c0, + const D2D1_POINT_2F *c1) +{ + if (!d2d_array_reserve((void **)&figure->bezier_controls, &figure->bezier_controls_size, + figure->bezier_control_points + 2, sizeof(*figure->bezier_controls))) + { + ERR("Failed to grow bezier controls array.\n"); + return FALSE; + } + + memmove(&figure->bezier_controls[idx + 2], &figure->bezier_controls[idx], + (figure->bezier_control_count - idx) * sizeof(*figure->bezier_controls)); + figure->bezier_controls[idx] = *c0; + figure->bezier_controls[idx + 1] = *c1; + figure->bezier_control_points += 2; + ++figure->bezier_control_count; + + return TRUE; +} + static void d2d_cdt_edge_rot(struct d2d_cdt_edge_ref *dst, const struct d2d_cdt_edge_ref *src) { dst->idx = src->idx; @@ -2237,8 +2257,9 @@ 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]; + const D2D1_POINT_2F *p[4]; struct d2d_figure *figure; + D2D1_BEZIER_SEGMENT left, right; D2D1_POINT_2F q[2]; float t, t_prev; @@ -2272,25 +2293,52 @@ static BOOL d2d_geometry_apply_intersections(struct d2d_geometry *geometry, t = (t - t_prev) / (1.0f - t_prev); } - p[0] = &figure->vertices[inter->vertex_idx + vertex_offset]; - p[1] = &figure->bezier_controls[inter->control_idx + control_offset]; - 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 (vertex_type == D2D_VERTEX_TYPE_CUBIC_BEZIER || vertex_type == D2D_VERTEX_TYPE_SPLIT_CUBIC_BEZIER) + { + p[0] = &figure->vertices[inter->vertex_idx + vertex_offset]; + p[1] = &figure->bezier_controls[inter->control_idx + control_offset]; + p[2] = &figure->bezier_controls[inter->control_idx + control_offset + 1]; + next = inter->vertex_idx + vertex_offset + 1; + if (next == figure->vertex_count) + next = 0; + p[3] = &figure->vertices[next]; + + d2d_bezier_split_cubic(p[0], p[1], p[2], p[3], t, &left, &right, NULL); + + figure->bezier_controls[inter->control_idx + control_offset] = left.point1; + figure->bezier_controls[inter->control_idx + control_offset + 1] = left.point2; + if (!(d2d_figure_insert_cubic_bezier_control(figure, inter->control_idx + control_offset + 1, &right.point1, + &right.point2))) + return FALSE; + control_offset += 2; - figure->bezier_controls[inter->control_idx + control_offset] = q[0]; - if (!(d2d_figure_insert_quadratic_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1]))) - return FALSE; - ++control_offset; + 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_CUBIC_BEZIER; + ++vertex_offset; + } + else + { + p[0] = &figure->vertices[inter->vertex_idx + vertex_offset]; + p[1] = &figure->bezier_controls[inter->control_idx + control_offset]; + 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); + + figure->bezier_controls[inter->control_idx + control_offset] = q[0]; + if (!(d2d_figure_insert_quadratic_bezier_control(figure, inter->control_idx + control_offset + 1, &q[1]))) + return FALSE; + ++control_offset; - 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_QUAD_BEZIER; - ++vertex_offset; + 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_QUAD_BEZIER; + ++vertex_offset; + } } return TRUE; -- 2.20.1
participants (2)
-
Connor McAdams -
Henri Verbeet