[PATCH 2/2] gdiplus: Revise closeness check for bezier curve flattening.

[Robert Feuerbach]

My apologies, the equation of the flatness check is consistent with:
dist_m = | cross(pt_st - pt, mp[2] - pt) | / | pt_st - pt |  < 0.5 *
flatness



On Fri, Feb 4, 2022 at 2:50 PM Robert Feuerbach <rjfeuerbach at gmail.com>
wrote:

> The flatness check is consistent with deriving from:
> dist_m = | dot(pt_st - mp[2], cross(pt_st, pt)) | / | pt_st - pt |
>
> The simplified closeness check also just compares the same points on the
> curve: pt, pt_st, and mp[2].
>
> It is possible, for example an S-shaped curve, for mp[2], pt, and pt_st to
> be collinear but for the true curve to vary more than the flatness.
> A more pathological case would be for all the control points [pt, pt_st,
> (x2,y2), (x3, y3)] to be colinear with (x2, y2) and (x3, y3) outside of the
> pt --> pt_st segment.
>
> Taking these into account are deeper possible fixes than I was aiming for
> here, which was simply to improve the handling to prevent a crash in an
> application.
>
>
> On Fri, Feb 4, 2022 at 2:12 PM Nikolay Sivov <nsivov at codeweavers.com>
> wrote:
>
>>
>>
>> On 2/4/22 20:33, Esme Povirk (she/they) wrote:
>> > I'm not convinced by this approach. There might be a situation where
>> > the midpoint between the endpoints happens to be close to the midpoint
>> > between the control points, but the control points are further than
>> > the flatness, leaving a possibility that we stop while our
>> > approximation has more error than the flatness.
>> >
>> > I feel like we should be testing the distance between the control
>> > points and the line segment (or the distance between the control
>> > points and an endpoint, which should be no less than the distance from
>> > the line segment).
>> >
>> > I don't really understand the existing "half of distance between
>> > middle point and a linearized path" test either. Nikolay, can you
>> > explain this?
>>
>> It's be a while. The idea is to check a distance from mp[2] point to
>> {pt, pt_st} segment (dist_m), and stop recursion if it's small enough.
>>
>> I haven't verified right now, but expression I believe was meant to get
>> that distance as:
>>
>> sqr(dot(mp - pt, pt_st - pt)) + sqr(dist_m) = sqr(dist(pt_st, pt));
>>
>> >
>> > On Fri, Feb 4, 2022 at 9:59 AM Robert Feuerbach <rjfeuerbach at gmail.com>
>> wrote:
>> >> The float equality and flatness calculation in flatten_bezier
>> >> can fail due to the limited precision of the float math.
>> >> The equality test was replaced with a simple check against
>> >> the given flatness tolerance.
>> >>
>> >> Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=52492
>> >> Signed-off-by: Robert Feuerbach <rjfeuerbach at gmail.com>
>> >> ---
>> >>   dlls/gdiplus/graphicspath.c | 11 ++++++-----
>> >>   1 file changed, 6 insertions(+), 5 deletions(-)
>> >>
>> >> diff --git a/dlls/gdiplus/graphicspath.c b/dlls/gdiplus/graphicspath.c
>> >> index ce2666eedab..c1bdf226e52 100644
>> >> --- a/dlls/gdiplus/graphicspath.c
>> >> +++ b/dlls/gdiplus/graphicspath.c
>> >> @@ -109,7 +109,7 @@ static INT path_list_count(path_list_node_t *node)
>> >>    *  - (x2, y2): first control point;
>> >>    *  - (x3, y3): second control point;
>> >>    *  - end     : pointer to end point node
>> >> - *  - flatness: admissible error of linear approximation.
>> >> + *  - flatness: admissible error of linear approximation in
>> coordinate units.
>> >>    *
>> >>    * Return value:
>> >>    *  TRUE : success
>> >> @@ -142,12 +142,13 @@ static BOOL flatten_bezier(path_list_node_t
>> *start, REAL x2, REAL y2, REAL x3, R
>> >>       mp[2].X = (mp[1].X + mp[3].X) / 2.0;
>> >>       mp[2].Y = (mp[1].Y + mp[3].Y) / 2.0;
>> >>
>> >> -    if ((x2 == mp[0].X && y2 == mp[0].Y && x3 == mp[1].X && y3 ==
>> mp[1].Y) ||
>> >> -        (x2 == mp[3].X && y2 == mp[3].Y && x3 == mp[4].X && y3 ==
>> mp[4].Y))
>> >> -        return TRUE;
>> >> -
>> >>       pt = end->pt;
>> >>       pt_st = start->pt;
>> >> +    /* test for closely spaced points to avoid limited-precision
>> errors in flatness check */
>> >> +    if((fabs(pt.X - mp[2].X) + fabs(pt.Y - mp[2].Y) +
>> >> +        fabs(pt_st.X - mp[2].X) + fabs(pt_st.Y - mp[2].Y) ) <=
>> flatness)
>> >> +        return TRUE;
>> >> +
>> >>       /* check flatness as a half of distance between middle point and
>> a linearized path */
>> >>       if(fabs(((pt.Y - pt_st.Y)*mp[2].X + (pt_st.X - pt.X)*mp[2].Y +
>> >>           (pt_st.Y*pt.X - pt_st.X*pt.Y))) <=
>> >> --
>> >> 2.32.0 (Apple Git-132)
>> >>
>> >>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20220204/5eb49044/attachment.htm>