[PATCH] d2d1: Partially implement StrokeContainsPoint() for rectangles

[Nikolay Sivov]

On 08.09.2017 20:22, Henri Verbeet wrote:
> On 8 September 2017 at 16:11, Nikolay Sivov <nsivov at 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.