[PATCH 2/2] gdiplus: Revise closeness check for bezier curve flattening.
Robert Feuerbach
rjfeuerbach at gmail.com
Tue Feb 15 14:50:45 CST 2022
I tested the direct approach, and it was as you suspected: it was difficult
to pass the GdipFlattenPath tests. The spacing of the points could not be
easily made to match or improve upon the tests.
Keeping with the recursion approach, by changing the scaling term in the
flatness test from 0.5 to 0.577, we are able to pass all the
GdipFlattenPath tests and remove the TODOs. This is approximately
1/sqrt(3), which might be motivated by the polynomial terms, but I do not
have that math worked out yet. It also is probably not needed in the quest
to simply match the native behavior.
I have made updates to dlls/gdiplus/graphicspath.c and
dlls/gdiplus/tests/graphicspath.c to capture these results. Should I
submit them as an updated, single patch to address both files? If I do
them separately, the test metrics will fail since the todo's will succeed
when they are expected to fail.
Thanks.
On Mon, Feb 7, 2022 at 5:03 PM Esme Povirk (she/they) <esme at codeweavers.com>
wrote:
> Unless there's a specific reason to discuss it in private, we should
> do it on the mailing list where everyone can participate.
>
> I consider myself weak in this kind of math, so I'd appreciate having
> others chime in who may have a better understanding of it.
>
> So if I understand the concept correctly, this would give us a way to
> calculate the number of line segments we need to approximate the
> Bezier curve with a specific upper bound on the error, and calculate
> the approximation without splitting it into more Bezier curves.
>
> This would also enable an alternative approach where we use this
> method to determine the error of 1 single line segment, and split the
> curve similar to how we do it now if the error is too large. I don't
> think we technically needed recursion to begin with because we can
> insert additional points on the path we're working on. But if the
> number of points we need can be easily calculated, I don't think
> there's a clear advantage to this approach.
>
> A possible obstacle is that we have tests for GdipFlattenPath which
> look for specific points and point counts. One of them still has some
> todo's meaning we don't quite match native. But, there's a risk that
> you would do this work and find out that your approach cannot pass our
> existing tests. If the approach is still bisecting, that probably
> won't make the situation any worse. (Then again, for all I know,
> native might do a direct approximation.)
>
> If you think you can make the direct approach work while still passing
> the tests, I would appreciate that. Regardless, I think it'd be
> acceptable to keep the recursive approach, but fix the flatness test.
>
> On Mon, Feb 7, 2022 at 12:36 PM Robert Feuerbach <rjfeuerbach at gmail.com>
> wrote:
> >
> > 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/20220215/803b7d4d/attachment.htm>
More information about the wine-devel
mailing list