[PATCH 4/4] d2d1: Implement path_geometry_StrokeContainsPoint() for Bézier segments.
Henri Verbeet
hverbeet at codeweavers.com
Wed Dec 8 13:14:22 CST 2021
From: David White <dwhite at codeweavers.com>
Signed-off-by: Henri Verbeet <hverbeet at 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
More information about the wine-devel
mailing list