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@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@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@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@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@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@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)
>> > >>
>> > >>
>> >