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

[Robert Feuerbach]

A different way to perform the flatten is with a direct approach, instead
of recursive, which eliminates the stack overflow risk and also is rather
straightforward.  The open access reference, "Computer Aided Geometric
Design" by Sederberg (
https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1000&context=facpub#section.10.6)
has a description that is easily implemented, and I can make a v2 patch
with it instead.

I'm also not familiar with the etiquette of this mailing list -- should
this type of discussion be emailed about off the list?


On Fri, Feb 4, 2022 at 2:28 PM Esme Povirk (she/they) <esme at codeweavers.com>
wrote:

> Couldn't that point be closer to the line segment than the actual
> curve, if the control points are on opposite sides of the line?
>
> On Fri, Feb 4, 2022 at 1: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/20220207/286f7879/attachment.htm>