Re: [PATCH] d2d1: Partially implement StrokeContainsPoint() for rectangles
On 8 September 2017 at 16:11, Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
+static BOOL d2d_point_on_segment(const D2D1_POINT_2F *q, const D2D1_POINT_2F *p0, + const D2D1_POINT_2F *p1, float tolerance) +{ + float dot, edge_length, distance; + D2D1_POINT_2F v_p, v_q, n; + + d2d_point_subtract(&v_p, p1, p0); + if ((edge_length = d2d_point_length(&v_p)) == 0.0f) + return FALSE; + + /* Edge distance. */ + d2d_point_subtract(&v_q, q, p0); + + n.x = -v_p.y; + n.y = v_p.x; Unfortunately it's not that easy when "transform" is a world transformation instead of a geometry transformation. I.e., when you have for example a shear transformation, the "normal" is no longer necessarily perpendicular to the line segment. Put a different way, you're potentially testing against a parallelogram instead of a rectangle. In a sense you account for that with stroke_widths[], but see below.
+ distance = fabsf(d2d_point_dot(&v_q, &n)) / edge_length; + if (distance >= tolerance) + return FALSE; + + /* Test if normal and edge intersect. */ + dot = d2d_point_dot(&v_q, &v_p); + return dot >= 0.0f && dot <= edge_length * edge_length; +} Likewise, this doesn't do the right thing under all transformations.
+ d2d_point_transform(&v_s[0], transform, stroke_width, 0.0f); + d2d_point_transform(&v_s[1], transform, stroke_width, 0.0f); + d2d_point_transform(&origin, transform, 0.0f, 0.0f); + + d2d_point_subtract(&v_s[0], &v_s[0], &origin); + d2d_point_subtract(&v_s[1], &v_s[1], &origin); + + stroke_widths[0] = d2d_point_length(&v_s[0]); + stroke_widths[1] = d2d_point_length(&v_s[1]); This ends up with the same value for stroke_widths[0] and stroke_widths[1].
+ d2d_point_subtract(&v, &point, &vertices[i]); + + if (d2d_point_dot(&v, &v) < tolerance * tolerance) + { + *contains = TRUE; + break; + } This tests around the corner of the joins, but note that there's potentially a space between that corner and the start of the line segment that this would miss.
+ else + { + D2D1_POINT_2F d, s; + + s.x = rect->right - rect->left; + s.y = rect->bottom - rect->top; + d.x = fabsf((rect->right + rect->left) * 0.5f - point.x); + d.y = fabsf((rect->bottom + rect->top) * 0.5f - point.y); + + /* Inside test. */ + if (d.x <= (s.x - stroke_width) * 0.5f - tolerance && d.y <= (s.y - stroke_width) * 0.5f - tolerance) + { + *contains = FALSE; + return S_OK; + } + + if (tolerance == 0.0f) + { + *contains = d.x < (s.x + stroke_width) * 0.5f && d.y < (s.y + stroke_width) * 0.5f; + } + else + { + d.x = max(d.x - (s.x + stroke_width) * 0.5f, 0.0f); + d.y = max(d.y - (s.y + stroke_width) * 0.5f, 0.0f); + + *contains = d2d_point_dot(&d, &d) < tolerance * tolerance; + } + } Ultimately it's not that important, but I think there's something to be said for handling the "!transform" case first as a special case. I.e.,
if (!transform) { ... return S_OK; } /* General case. */
diff --git a/dlls/d2d1/tests/d2d1.c b/dlls/d2d1/tests/d2d1.c index f6261295b6..95a010b13e 100644 --- a/dlls/d2d1/tests/d2d1.c +++ b/dlls/d2d1/tests/d2d1.c @@ -76,6 +76,15 @@ struct expected_geometry_figure const struct geometry_segment *segments; };
+struct contains_point_test +{ + D2D1_MATRIX_3X2_F transform; + D2D1_POINT_2F point; + float tolerance; + float stroke_width; + BOOL contains; +}; Unless these are reused between tests, we tend to keep them local to the function.
+ static const struct contains_point_test stroke_contains[] = + { + {{0.0f, 0.0f, 0.0f, 1.0f}, {0.1f, 10.0f}, 0.0f, 1.0f, FALSE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {5.0f, 10.0f}, 5.0f, 1.0f, FALSE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {4.9f, 10.0f}, 5.0f, 1.0f, TRUE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {5.0f, 10.0f}, -5.0f, 1.0f, FALSE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {4.9f, 10.0f}, -5.0f, 1.0f, TRUE}, + + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.0f, 10.0f}, 0.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.1f, 10.0f}, 0.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.5f, 10.0f}, 0.0f, 1.0f, FALSE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.0f, 10.0f}, 1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.59f, 10.0f}, 1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {-0.59f, 10.0f}, 1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.59f, 10.0f}, -1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {-0.59f, 10.0f}, -1.0f, 1.0f, TRUE}, + }; Rotations and shears are interesting.
@@ -2766,6 +2793,108 @@ static void test_rectangle_geometry(void) ok(SUCCEEDED(hr), "FillContainsPoint() failed, hr %#x.\n", hr); ok(!!contains, "Got wrong hit test result %d.\n", contains);
+ /* Stroked area hittesting. Edge. */ + contains = FALSE; + set_point(&point, 0.4f, 10.0f); + hr = ID2D1RectangleGeometry_StrokeContainsPoint(geometry, point, 1.0f, NULL, NULL, 0.0f, &contains); + ok(SUCCEEDED(hr), "StrokeContainsPoint() failed, hr %#x.\n", hr); + ok(!!contains, "Got wrong hit test result %d.\n", contains); We tend to use %#x for BOOLs. And well, you might as well make these array based as well.
On 08.09.2017 20:22, Henri Verbeet wrote:
On 8 September 2017 at 16:11, Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
+static BOOL d2d_point_on_segment(const D2D1_POINT_2F *q, const D2D1_POINT_2F *p0, + const D2D1_POINT_2F *p1, float tolerance) +{ + float dot, edge_length, distance; + D2D1_POINT_2F v_p, v_q, n; + + d2d_point_subtract(&v_p, p1, p0); + if ((edge_length = d2d_point_length(&v_p)) == 0.0f) + return FALSE; + + /* Edge distance. */ + d2d_point_subtract(&v_q, q, p0); + + n.x = -v_p.y; + n.y = v_p.x; Unfortunately it's not that easy when "transform" is a world transformation instead of a geometry transformation. I.e., when you have for example a shear transformation, the "normal" is no longer necessarily perpendicular to the line segment. Put a different way, you're potentially testing against a parallelogram instead of a rectangle. In a sense you account for that with stroke_widths[], but see below.
I'm missing something here. if this function is called on transformed coordinates, so v_p is transformed vector, why isn't 'n' perpendicular to it? Width to test against sure will change.
+ distance = fabsf(d2d_point_dot(&v_q, &n)) / edge_length; + if (distance >= tolerance) + return FALSE; + + /* Test if normal and edge intersect. */ + dot = d2d_point_dot(&v_q, &v_p); + return dot >= 0.0f && dot <= edge_length * edge_length; +} Likewise, this doesn't do the right thing under all transformations.
+ d2d_point_transform(&v_s[0], transform, stroke_width, 0.0f); + d2d_point_transform(&v_s[1], transform, stroke_width, 0.0f); + d2d_point_transform(&origin, transform, 0.0f, 0.0f); + + d2d_point_subtract(&v_s[0], &v_s[0], &origin); + d2d_point_subtract(&v_s[1], &v_s[1], &origin); + + stroke_widths[0] = d2d_point_length(&v_s[0]); + stroke_widths[1] = d2d_point_length(&v_s[1]); This ends up with the same value for stroke_widths[0] and stroke_widths[1].
Right.
+ d2d_point_subtract(&v, &point, &vertices[i]); + + if (d2d_point_dot(&v, &v) < tolerance * tolerance) + { + *contains = TRUE; + break; + } This tests around the corner of the joins, but note that there's potentially a space between that corner and the start of the line segment that this would miss.
'vertices' here isn't transformed rectangle vertices, but adjusted by widths. It's inaccurate not because of missed space, but because it ignores style, assuming strokes meet at 90 degrees.
+ else + { + D2D1_POINT_2F d, s; + + s.x = rect->right - rect->left; + s.y = rect->bottom - rect->top; + d.x = fabsf((rect->right + rect->left) * 0.5f - point.x); + d.y = fabsf((rect->bottom + rect->top) * 0.5f - point.y); + + /* Inside test. */ + if (d.x <= (s.x - stroke_width) * 0.5f - tolerance && d.y <= (s.y - stroke_width) * 0.5f - tolerance) + { + *contains = FALSE; + return S_OK; + } + + if (tolerance == 0.0f) + { + *contains = d.x < (s.x + stroke_width) * 0.5f && d.y < (s.y + stroke_width) * 0.5f; + } + else + { + d.x = max(d.x - (s.x + stroke_width) * 0.5f, 0.0f); + d.y = max(d.y - (s.y + stroke_width) * 0.5f, 0.0f); + + *contains = d2d_point_dot(&d, &d) < tolerance * tolerance; + } + } Ultimately it's not that important, but I think there's something to be said for handling the "!transform" case first as a special case. I.e.,
if (!transform) { ... return S_OK; }
/* General case. */
I don't mind that of course, I think it makes sense to handle diagonal matrices with uniform scaling, and shifts with that simplified approach.
diff --git a/dlls/d2d1/tests/d2d1.c b/dlls/d2d1/tests/d2d1.c index f6261295b6..95a010b13e 100644 --- a/dlls/d2d1/tests/d2d1.c +++ b/dlls/d2d1/tests/d2d1.c @@ -76,6 +76,15 @@ struct expected_geometry_figure const struct geometry_segment *segments; };
+struct contains_point_test +{ + D2D1_MATRIX_3X2_F transform; + D2D1_POINT_2F point; + float tolerance; + float stroke_width; + BOOL contains; +}; Unless these are reused between tests, we tend to keep them local to the function.
I was thinking about using this for FillContainsPoint too later, but I can move it when that happens.
+ static const struct contains_point_test stroke_contains[] = + { + {{0.0f, 0.0f, 0.0f, 1.0f}, {0.1f, 10.0f}, 0.0f, 1.0f, FALSE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {5.0f, 10.0f}, 5.0f, 1.0f, FALSE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {4.9f, 10.0f}, 5.0f, 1.0f, TRUE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {5.0f, 10.0f}, -5.0f, 1.0f, FALSE}, + {{0.0f, 0.0f, 0.0f, 1.0f}, {4.9f, 10.0f}, -5.0f, 1.0f, TRUE}, + + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.0f, 10.0f}, 0.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.1f, 10.0f}, 0.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.5f, 10.0f}, 0.0f, 1.0f, FALSE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.0f, 10.0f}, 1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.59f, 10.0f}, 1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {-0.59f, 10.0f}, 1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {0.59f, 10.0f}, -1.0f, 1.0f, TRUE}, + {{1.0f, 0.0f, 0.0f, 1.0f}, {-0.59f, 10.0f}, -1.0f, 1.0f, TRUE}, + }; Rotations and shears are interesting.
@@ -2766,6 +2793,108 @@ static void test_rectangle_geometry(void) ok(SUCCEEDED(hr), "FillContainsPoint() failed, hr %#x.\n", hr); ok(!!contains, "Got wrong hit test result %d.\n", contains);
+ /* Stroked area hittesting. Edge. */ + contains = FALSE; + set_point(&point, 0.4f, 10.0f); + hr = ID2D1RectangleGeometry_StrokeContainsPoint(geometry, point, 1.0f, NULL, NULL, 0.0f, &contains); + ok(SUCCEEDED(hr), "StrokeContainsPoint() failed, hr %#x.\n", hr); + ok(!!contains, "Got wrong hit test result %d.\n", contains); We tend to use %#x for BOOLs. And well, you might as well make these array based as well.
That was an easy way to test NULL matrix as opposed to identity one in arrays so we test both our paths.
On 8 September 2017 at 20:07, Nikolay Sivov <bunglehead(a)gmail.com> wrote:
On 08.09.2017 20:22, Henri Verbeet wrote:
On 8 September 2017 at 16:11, Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
+ /* Stroked area hittesting. Edge. */ + contains = FALSE; + set_point(&point, 0.4f, 10.0f); + hr = ID2D1RectangleGeometry_StrokeContainsPoint(geometry, point, 1.0f, NULL, NULL, 0.0f, &contains); + ok(SUCCEEDED(hr), "StrokeContainsPoint() failed, hr %#x.\n", hr); + ok(!!contains, "Got wrong hit test result %d.\n", contains); We tend to use %#x for BOOLs. And well, you might as well make these array based as well.
That was an easy way to test NULL matrix as opposed to identity one in arrays so we test both our paths.
Sure, I don't mean in the same stroke_contains[] array with an identity transformation, but either as a separate array of tests or with some flag to indicate passing a NULL transformation.
participants (2)
-
Henri Verbeet -
Nikolay Sivov