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

[Robert Feuerbach]

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/db4923d2/attachment.htm>