[PATCH 4/4] d2d1: Implement path_geometry_StrokeContainsPoint() for Bézier segments.
From: David White <dwhite(a)codeweavers.com> Signed-off-by: Henri Verbeet <hverbeet(a)codeweavers.com> --- dlls/d2d1/geometry.c | 198 +++++++++++++++++++++++++++++++++++++++-- dlls/d2d1/tests/d2d1.c | 93 +++++++++++++++++++ 2 files changed, 285 insertions(+), 6 deletions(-) diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index d5a430e1f74..a7074899fda 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -586,6 +586,172 @@ static BOOL d2d_point_on_line_segment(const D2D1_POINT_2F *q, const D2D1_POINT_2 return fabsf(d2d_point_dot(&v_q, &v_n)) < tolerance; } +/* Approximate the Bézier segment with a (wide) line segment. If the point + * lies outside the approximation, we're done. If the width of the + * approximation is less than the tolerance and the point lies inside, we're + * also done. If neither of those is the case, we subdivide the Bézier segment + * and try again. */ +static BOOL d2d_point_on_bezier_segment(const D2D1_POINT_2F *q, const D2D1_POINT_2F *p0, + const D2D1_BEZIER_SEGMENT *b, const D2D1_MATRIX_3X2_F *transform, float stroke_width, float tolerance) +{ + float d1, d2, d3, d4, d, l, m, w, w2; + D2D1_POINT_2F t[7], start, end, v_p; + D2D1_BEZIER_SEGMENT b0, b1; + + m = 1.0f; + w = stroke_width * 0.5f; + + d2d_point_subtract(&v_p, &b->point3, p0); + /* If the endpoints coincide, use the line through the control points as + * the direction vector. That choice is somewhat arbitrary; other choices + * with tighter error bounds exist. */ + if ((l = d2d_point_dot(&v_p, &v_p)) == 0.0f) + { + d2d_point_subtract(&v_p, &b->point2, &b->point1); + /* If the control points also coincide, the curve is in fact a line. */ + if ((l = d2d_point_dot(&v_p, &v_p)) == 0.0f) + { + d2d_point_subtract(&v_p, &b->point1, p0); + end.x = p0->x + 0.75f * v_p.x; + end.y = p0->y + 0.75f * v_p.y; + + return d2d_point_on_line_segment(q, p0, &end, transform, w, tolerance); + } + m = 0.0f; + } + l = sqrtf(l); + d2d_point_scale(&v_p, 1.0f / l); + m *= l; + + /* Calculate the width w2 of the approximation. */ + + end.x = p0->x + v_p.x; + end.y = p0->y + v_p.y; + /* Here, d1 and d2 are the maximum (signed) distance of the control points + * from the line through the start and end points. */ + d1 = d2d_point_ccw(p0, &end, &b->point1); + d2 = d2d_point_ccw(p0, &end, &b->point2); + /* It can be shown that if the control points of a cubic Bézier curve lie + * on the same side of the line through the endpoints, the distance of the + * curve itself to that line will be within 3/4 of the distance of the + * control points to that line; if the control points lie on opposite + * sides, that distance will be within 4/9 of the distance of the + * corresponding control point. We're taking that as a given here. */ + if (d1 * d2 > 0.0f) + { + d1 *= 0.75f; + d2 *= 0.75f; + } + else + { + d1 = (d1 * 4.0f) / 9.0f; + d2 = (d2 * 4.0f) / 9.0f; + } + w2 = max(fabsf(d1), fabsf(d2)); + + /* Project the control points onto the line through the endpoints of the + * curve. We will use these to calculate the endpoints of the + * approximation. */ + d2d_point_subtract(&t[1], &b->point1, p0); + d1 = d2d_point_dot(&v_p, &t[1]); + d2d_point_subtract(&t[2], &b->point2, p0); + d2 = d2d_point_dot(&v_p, &t[2]); + + /* Calculate the start point of the approximation. Like further above, the + * actual curve is somewhat closer to the endpoints than the control + * points are. */ + d = min(min(d1, d2), 0); + if (d1 * d2 > 0.0f) + d *= 0.75f; + else + d = (d * 4.0f) / 9.0f; + /* Account for the stroke width and tolerance around the endpoints by + * adjusting the endpoints here. This matters because there are no joins + * in the original geometry for the places where we subdivide the original + * curve. We do this here because it's easy; alternatively we could + * explicitly test for this when subdividing the curve further below. */ + d -= min(w + tolerance, w2); + start.x = p0->x + d * v_p.x; + start.y = p0->y + d * v_p.y; + + /* Calculate the end point of the approximation. */ + d1 -= m; + d2 -= m; + d = max(max(d1, d2), 0); + if (d1 * d2 > 0.0f) + d = m + d * 0.75f; + else + d = m + (d * 4.0f) / 9.0f; + d += min(w2, w + tolerance); + end.x = p0->x + d * v_p.x; + end.y = p0->y + d * v_p.y; + + /* Calculate the error bounds of the approximation. We do this in + * transformed space because we need these to be relative to the given + * tolerance. */ + + d2d_point_transform(&t[0], transform, p0->x, p0->y); + d2d_point_transform(&t[1], transform, b->point1.x, b->point1.y); + d2d_point_transform(&t[2], transform, b->point2.x, b->point2.y); + d2d_point_transform(&t[3], transform, b->point3.x, b->point3.y); + d2d_point_transform(&t[4], transform, start.x, start.y); + d2d_point_transform(&t[5], transform, end.x, end.y); + + d2d_point_subtract(&t[6], &t[5], &t[4]); + l = d2d_point_length(&t[6]); + /* Here, d1 and d2 are the maximum (signed) distance of the control points + * from the line through the start and end points. */ + d1 = d2d_point_ccw(&t[4], &t[5], &t[1]) / l; + d2 = d2d_point_ccw(&t[4], &t[5], &t[2]) / l; + if (d1 * d2 > 0.0f) + { + d1 *= 0.75f; + d2 *= 0.75f; + } + else + { + d1 = (d1 * 4.0f) / 9.0f; + d2 = (d2 * 4.0f) / 9.0f; + } + l = max(max(d1, d2), 0) - min(min(d1, d2), 0); + + /* d3 and d4 are the (unsigned) distance of the endpoints of the + * approximation from the original endpoints. */ + d2d_point_subtract(&t[6], &t[4], &t[0]); + d3 = d2d_point_length(&t[6]); + d2d_point_subtract(&t[6], &t[5], &t[3]); + d4 = d2d_point_length(&t[6]); + l = max(max(d3, d4), l); + + /* If the error of the approximation is less than the tolerance, and Q + * lies on the approximation, the distance of Q to the stroked curve is + * definitely within the tolerance. */ + if (l <= tolerance && d2d_point_on_line_segment(q, &start, &end, transform, w, tolerance - l)) + return TRUE; + /* On the other hand, if the distance of Q to the stroked curve is more + * than the sum of the tolerance and d, the distance of Q to the stroked + * curve can't possibly be within the tolerance. */ + if (!d2d_point_on_line_segment(q, &start, &end, transform, w + w2, tolerance)) + return FALSE; + + /* Subdivide the curve. Note that simply splitting the segment in half + * here works and is easy, but may not be optimal. We could potentially + * reduce the number of iterations we need to do by splitting based on + * curvature or segment length. */ + d2d_point_lerp(&t[0], &b->point1, &b->point2, 0.5f); + + b1.point3 = b->point3; + d2d_point_lerp(&b1.point2, &b->point3, &b->point2, 0.5f); + d2d_point_lerp(&b1.point1, &t[0], &b1.point2, 0.5f); + + d2d_point_lerp(&b0.point1, p0, &b->point1, 0.5f); + d2d_point_lerp(&b0.point2, &t[0], &b0.point1, 0.5f); + d2d_point_lerp(&b0.point3, &b0.point2, &b1.point1, 0.5f); + + return d2d_point_on_bezier_segment(q, p0, &b0, transform, stroke_width, tolerance) + || d2d_point_on_bezier_segment(q, &b0.point3, &b1, transform, stroke_width, tolerance); +} + static void d2d_rect_union(D2D1_RECT_F *l, const D2D1_RECT_F *r) { l->left = min(l->left, r->left); @@ -3411,8 +3577,9 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_StrokeContainsPoint(ID2D1Path { struct d2d_geometry *geometry = impl_from_ID2D1PathGeometry(iface); enum d2d_vertex_type type = D2D_VERTEX_TYPE_NONE; + unsigned int i, j, bezier_idx; + D2D1_BEZIER_SEGMENT b; D2D1_POINT_2F p, p1; - unsigned int i, j; TRACE("iface %p, point %s, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, contains %p.\n", iface, debug_d2d_point_2f(&point), stroke_width, stroke_style, transform, tolerance, contains); @@ -3441,7 +3608,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_StrokeContainsPoint(ID2D1Path break; } - for (++j; j < figure->vertex_count; ++j) + for (bezier_idx = 0, ++j; j < figure->vertex_count; ++j) { if (figure->vertex_types[j] == D2D_VERTEX_TYPE_NONE || d2d_vertex_type_is_split_bezier(figure->vertex_types[j])) @@ -3455,6 +3622,14 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_StrokeContainsPoint(ID2D1Path p = p1; break; + case D2D_VERTEX_TYPE_BEZIER: + b.point1 = figure->original_bezier_controls[bezier_idx++]; + b.point2 = figure->original_bezier_controls[bezier_idx++]; + b.point3 = figure->vertices[j]; + *contains = d2d_point_on_bezier_segment(&point, &p, &b, transform, stroke_width, tolerance); + p = b.point3; + break; + default: FIXME("Unhandled vertex type %#x.\n", type); p = figure->vertices[j]; @@ -3465,11 +3640,22 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_StrokeContainsPoint(ID2D1Path type = figure->vertex_types[j]; } - if (figure->flags & D2D_FIGURE_FLAG_CLOSED && (!*contains) && type == D2D_VERTEX_TYPE_LINE) + if (figure->flags & D2D_FIGURE_FLAG_CLOSED && (!*contains)) { - p1 = figure->vertices[0]; - *contains = d2d_point_on_line_segment(&point, &p, &p1, transform, stroke_width * 0.5f, tolerance); - p = p1; + if (type == D2D_VERTEX_TYPE_LINE) + { + p1 = figure->vertices[0]; + *contains = d2d_point_on_line_segment(&point, &p, &p1, transform, stroke_width * 0.5f, tolerance); + p = p1; + } + else if (d2d_vertex_type_is_bezier(type)) + { + b.point1 = figure->original_bezier_controls[bezier_idx++]; + b.point2 = figure->original_bezier_controls[bezier_idx++]; + b.point3 = figure->vertices[0]; + *contains = d2d_point_on_bezier_segment(&point, &p, &b, transform, stroke_width, tolerance); + p = b.point3; + } } if (*contains) diff --git a/dlls/d2d1/tests/d2d1.c b/dlls/d2d1/tests/d2d1.c index 15088d679df..70c47795b4e 100644 --- a/dlls/d2d1/tests/d2d1.c +++ b/dlls/d2d1/tests/d2d1.c @@ -10244,6 +10244,67 @@ static void test_stroke_contains_point(BOOL d3d11) {{{{0.0f}}}, {239.41f, 600.0f}, 0.1f, 1.0f, FALSE, TRUE}, {{{{0.0f}}}, {240.59f, 600.0f}, 0.1f, 1.0f, FALSE, TRUE}, {{{{0.0f}}}, {240.61f, 600.0f}, 0.1f, 1.0f, FALSE, FALSE}, + + /* 13. Curves. */ + {{{{1.0f, 0.0f, 0.0f, 1.0f, 10.0f, 10.0f}}}, {170.0f, 418.6f}, 0.0f, 1.0f, TRUE, TRUE}, + {{{{1.0f, 0.0f, 0.0f, 1.0f, 10.0f, 10.0f}}}, {170.0f, 420.1f}, 0.0f, 1.0f, TRUE, FALSE}, + {{{{1.0f, 0.0f, 0.0f, 1.0f, 10.0f, 10.0f}}}, {170.0f, 417.7f}, 0.0f, 1.0f, TRUE, FALSE}, + {{{{1.0f, 0.0f, 0.0f, 1.0f, 10.0f, 10.0f}}}, { 89.5f, 485.3f}, 0.1f, 1.0f, TRUE, TRUE}, + {{{{1.0f, 0.0f, 0.0f, 1.0f, 10.0f, 10.0f}}}, { 90.5f, 485.3f}, 0.1f, 1.0f, TRUE, TRUE}, + {{{{1.0f, 0.0f, 0.0f, 1.0f, 10.0f, 10.0f}}}, { 91.5f, 485.3f}, 0.1f, 1.0f, TRUE, FALSE}, + {{{{1.0f, 0.0f, 0.0f, 1.0f, 10.0f, 10.0f}}}, { 89.0f, 485.3f}, 0.1f, 1.0f, TRUE, FALSE}, + + /* 20. A curve where the control points project beyond the endpoints + * onto the line through the endpoints. */ + {{{{0.0f}}}, {306.97f, 791.67f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {307.27f, 791.67f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {308.47f, 791.67f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {308.77f, 791.67f}, 0.0f, 1.0f, FALSE, FALSE}, + + {{{{0.0f}}}, {350.00f, 824.10f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {350.00f, 824.40f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {350.00f, 825.60f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {350.00f, 825.90f}, 0.0f, 1.0f, FALSE, FALSE}, + + {{{{0.0f}}}, {391.23f, 791.67f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {391.53f, 791.67f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {392.73f, 791.67f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {393.03f, 791.67f}, 0.0f, 1.0f, FALSE, FALSE}, + + /* 32. A curve where the endpoints coincide. */ + {{{{0.0f}}}, {570.23f, 799.77f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {570.53f, 799.77f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {571.73f, 799.77f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {572.03f, 799.77f}, 0.0f, 1.0f, FALSE, FALSE}, + + {{{{0.0f}}}, {600.00f, 824.10f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {600.00f, 824.40f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {600.00f, 825.60f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {600.00f, 825.90f}, 0.0f, 1.0f, FALSE, FALSE}, + + {{{{0.0f}}}, {627.97f, 799.77f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {628.27f, 799.77f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {629.47f, 799.77f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {629.77f, 799.77f}, 0.0f, 1.0f, FALSE, FALSE}, + + /* 44. A curve with coinciding endpoints, as well as coinciding + * control points. */ + {{{{0.0f}}}, {825.00f, 800.00f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {861.00f, 824.00f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {861.00f, 826.00f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {862.50f, 825.00f}, 0.0f, 1.0f, FALSE, TRUE}, + {{{{0.0f}}}, {864.00f, 824.00f}, 0.0f, 1.0f, FALSE, FALSE}, + {{{{0.0f}}}, {864.00f, 826.00f}, 0.0f, 1.0f, FALSE, FALSE}, + + /* 50. Shear transforms. */ + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, { 837.2f, 600.0f}, 0.1f, 5.0f, TRUE, FALSE}, + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, { 837.5f, 600.0f}, 0.1f, 5.0f, TRUE, TRUE}, + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, {1186.3f, 791.7f}, 0.1f, 5.0f, TRUE, TRUE}, + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, {1186.6f, 791.7f}, 0.1f, 5.0f, TRUE, FALSE}, + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, {1425.0f, 827.3f}, 0.1f, 5.0f, TRUE, TRUE}, + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, {1425.0f, 827.6f}, 0.1f, 5.0f, TRUE, FALSE}, + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, {1620.1f, 800.0f}, 0.1f, 5.0f, TRUE, FALSE}, + {{{{1.0f, 0.0f, 1.0f, 1.0f}}}, {1620.4f, 800.0f}, 0.1f, 5.0f, TRUE, TRUE}, }; hr = D2D1CreateFactory(D2D1_FACTORY_TYPE_SINGLE_THREADED, &IID_ID2D1Factory, NULL, (void **)&factory); @@ -10273,6 +10334,19 @@ static void test_stroke_contains_point(BOOL d3d11) hr = ID2D1PathGeometry_Open(path, &sink); ok(hr == S_OK, "Got unexpected hr %#x.\n", hr); + /* A limaçon. */ + set_point(&point, 160.0f, 720.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + cubic_to(sink, 119.0f, 720.0f, 83.0f, 600.0f, 80.0f, 474.0f); + cubic_to(sink, 78.0f, 349.0f, 108.0f, 245.0f, 135.0f, 240.0f); + cubic_to(sink, 163.0f, 235.0f, 180.0f, 318.0f, 176.0f, 370.0f); + cubic_to(sink, 171.0f, 422.0f, 149.0f, 422.0f, 144.0f, 370.0f); + cubic_to(sink, 140.0f, 318.0f, 157.0f, 235.0f, 185.0f, 240.0f); + cubic_to(sink, 212.0f, 245.0f, 242.0f, 349.0f, 240.0f, 474.0f); + cubic_to(sink, 238.0f, 600.0f, 201.0f, 720.0f, 160.0f, 720.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_CLOSED); + + /* Some straight lines. */ set_point(&point, 160.0f, 240.0f); ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); line_to(sink, 240.0f, 240.0f); @@ -10280,6 +10354,25 @@ static void test_stroke_contains_point(BOOL d3d11) line_to(sink, 160.0f, 720.0f); ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_OPEN); + /* Projected control points extending beyond the line segment through the + * endpoints. */ + set_point(&point, 325.0f, 750.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + cubic_to(sink, 250.0f, 850.0f, 450.0f, 850.0f, 375.0f, 750.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_OPEN); + + /* Coinciding endpoints. */ + set_point(&point, 600.0f, 750.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + cubic_to(sink, 500.0f, 850.0f, 700.0f, 850.0f, 600.0f, 750.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_OPEN); + + /* Coinciding endpoints, as well as coinciding control points. */ + set_point(&point, 750.0f, 750.0f); + ID2D1GeometrySink_BeginFigure(sink, point, D2D1_FIGURE_BEGIN_FILLED); + cubic_to(sink, 900.0f, 850.0f, 900.0f, 850.0f, 750.0f, 750.0f); + ID2D1GeometrySink_EndFigure(sink, D2D1_FIGURE_END_OPEN); + hr = ID2D1GeometrySink_Close(sink); ok(hr == S_OK, "Got unexpected hr %#x.\n", hr); ID2D1GeometrySink_Release(sink); -- 2.30.2
participants (1)
-
Henri Verbeet