Does better polynomial calculations for avoid objects.

Does better polynomial calculations for avoid objects.

[MikeSol, 2011-08-10 12:58:10]

Hey all,

My summer of Lily plugs along with a fix for Issue 1328.  It also generally
cleans up a lot of little collisions in the regtests between slurs and
articulations.

Passes regtests.

Cheers,
MS

[pkx166h, 2011-08-10 21:01:20]

Passes Make and there are some reg test differences - see

http://code.google.com/p/lilypond/issues/detail?id=1328#c2

[joeneeman, 2011-08-18 21:36:45]

http://codereview.appspot.com/4860042/diff/1/flower/polynomial.cc
File flower/polynomial.cc (right):

http://codereview.appspot.com/4860042/diff/1/flower/polynomial.cc#newcode65
flower/polynomial.cc:65: Polynomial::minmax (Real l, Real r, bool dir) const
Perhaps "bool max" instead of "bool dir"?

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc
File lily/bezier.cc (right):

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode87
lily/bezier.cc:87: Axis other = Axis ((a + 1) % NO_AXES);
Use the other_axis function.

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode217
lily/bezier.cc:217: Bezier::minmax (Axis ax, Real l, Real r, Direction d) const
What is this function supposed to do?

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode219
lily/bezier.cc:219: Axis other = Axis ((ax + 1) % NO_AXES);
other_axis

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode239
lily/bezier.cc:239: return p.minmax (sol[LEFT][0], sol[RIGHT][0], d != LEFT);
If there are multiple intersections with (say) r, then Polynomial::solve doesn't
seem to return them in any useful order. So sol[RIGHT][0] is really just an
arbitrary solution, isn't it?

[MikeSol, 2011-08-19 07:03:50]

Thanks Joe!
New patchset uploaded.

Cheers,
MS

http://codereview.appspot.com/4860042/diff/1/flower/polynomial.cc
File flower/polynomial.cc (right):

http://codereview.appspot.com/4860042/diff/1/flower/polynomial.cc#newcode65
flower/polynomial.cc:65: Polynomial::minmax (Real l, Real r, bool dir) const
On 2011/08/18 21:36:45, joeneeman wrote:
> Perhaps "bool max" instead of "bool dir"?

Done.

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc
File lily/bezier.cc (right):

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode87
lily/bezier.cc:87: Axis other = Axis ((a + 1) % NO_AXES);
On 2011/08/18 21:36:45, joeneeman wrote:
> Use the other_axis function.

Done.

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode217
lily/bezier.cc:217: Bezier::minmax (Axis ax, Real l, Real r, Direction d) const
On 2011/08/18 21:36:45, joeneeman wrote:
> What is this function supposed to do?

This is like other_coordinate insofar as it is a fancy wrapper around a
polynomial function that.  It finds the max or min along the bezier between l
and r.

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode239
lily/bezier.cc:239: return p.minmax (sol[LEFT][0], sol[RIGHT][0], d != LEFT);
On 2011/08/18 21:36:45, joeneeman wrote:
> If there are multiple intersections with (say) r, then Polynomial::solve
doesn't
> seem to return them in any useful order. So sol[RIGHT][0] is really just an
> arbitrary solution, isn't it?

True, but this seems no worse than line 81 where ts[0] is returned.  Not that
this is a good excuse...
I'll overload the function such that 0 is a default.

[hanwenn, 2011-08-23 04:21:37]

http://codereview.appspot.com/4860042/diff/8001/flower/polynomial.cc
File flower/polynomial.cc (right):

http://codereview.appspot.com/4860042/diff/8001/flower/polynomial.cc#newcode80
flower/polynomial.cc:80: return ret_max ? sols.back () : sols[0];
you could return an interval instead; 

Polynomial::range() ?

http://codereview.appspot.com/4860042/diff/8001/lily/bezier.cc
File lily/bezier.cc (right):

http://codereview.appspot.com/4860042/diff/8001/lily/bezier.cc#newcode223
lily/bezier.cc:223: Bezier::minmax (Axis ax, Real l, Real r, Direction d, vsize
lres, vsize rres) const
you could be less stingy with letters.  "axis". 

what do lres and vres mean?

http://codereview.appspot.com/4860042/diff/8001/lily/bezier.cc#newcode258
lily/bezier.cc:258: return p.minmax (sol[LEFT][res[LEFT]],
sol[RIGHT][res[RIGHT]], d != LEFT);
could return an interval here too? Bezier::extent ?

[joeneeman, 2011-08-23 04:55:57]

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc
File lily/bezier.cc (right):

http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode239
lily/bezier.cc:239: return p.minmax (sol[LEFT][0], sol[RIGHT][0], d != LEFT);
On 2011/08/19 07:03:50, MikeSol wrote:
> On 2011/08/18 21:36:45, joeneeman wrote:
> > If there are multiple intersections with (say) r, then Polynomial::solve
> doesn't
> > seem to return them in any useful order. So sol[RIGHT][0] is really just an
> > arbitrary solution, isn't it?
> 
> True, but this seems no worse than line 81 where ts[0] is returned.  Not that
> this is a good excuse...

Right, but what really bothers me is that you're then using sol[RIGHT][0] as
though it means something. So what this function seems to do (suppose ax=X_AXIS)
is to take an arbitrary point where the curve intersects x=r and an arbitrary
point where the curve intersects x=l and then finds the maximum y value of the
curve between those two points. But there's no guarantee that that maximum is
what you're after. For example, if the curve intersects x=r before it intersects
x=l then it seems to me that Polynomial::minmax will return something weird. And
if there are multiple intersections with either line, there are a lot of
different answers that could come out.

[mikesol_ufl.edu, 2011-08-23 07:35:49]

On Aug 23, 2011, at 6:21 AM, hanwenn@gmail.com wrote:

> 
> http://codereview.appspot.com/4860042/diff/8001/flower/polynomial.cc
> File flower/polynomial.cc (right):
> 
> http://codereview.appspot.com/4860042/diff/8001/flower/polynomial.cc#newcode80
> flower/polynomial.cc:80: return ret_max ? sols.back () : sols[0];
> you could return an interval instead;
> 
> Polynomial::range() ?

I'm hesitant to incorporate native Lilypond types into polynomial.cc - I'd like
to keep the included files as "polynomial.hh" and "warn.hh" so that it could
work stand-alone with minimal modifications.
Een beter milieu begint bij uzelf. Hergebruik!

> 
> http://codereview.appspot.com/4860042/diff/8001/lily/bezier.cc
> File lily/bezier.cc (right):
> 
> http://codereview.appspot.com/4860042/diff/8001/lily/bezier.cc#newcode223
> lily/bezier.cc:223: Bezier::minmax (Axis ax, Real l, Real r, Direction
> d, vsize lres, vsize rres) const
> you could be less stingy with letters.  "axis".
> 
> what do lres and vres mean?
> 

I've expanded these out.

> http://codereview.appspot.com/4860042/diff/8001/lily/bezier.cc#newcode258
> lily/bezier.cc:258: return p.minmax (sol[LEFT][res[LEFT]],
> sol[RIGHT][res[RIGHT]], d != LEFT);
> could return an interval here too? Bezier::extent ?
> 

It's up to you.  It is more an architecture/style question than anything else. 
If you're OK including interval.hh in polynomial.cc, then I can do this.

New patchset up.

Cheers,
MS

[mikesol_ufl.edu, 2011-08-23 07:36:37]

On Aug 23, 2011, at 6:55 AM, joeneeman@gmail.com wrote:

> 
> http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc
> File lily/bezier.cc (right):
> 
> http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode239
> lily/bezier.cc:239: return p.minmax (sol[LEFT][0], sol[RIGHT][0], d !=
> LEFT);
> On 2011/08/19 07:03:50, MikeSol wrote:
>> On 2011/08/18 21:36:45, joeneeman wrote:
>> > If there are multiple intersections with (say) r, then
> Polynomial::solve
>> doesn't
>> > seem to return them in any useful order. So sol[RIGHT][0] is really
> just an
>> > arbitrary solution, isn't it?
> 
>> True, but this seems no worse than line 81 where ts[0] is returned.
> Not that
>> this is a good excuse...
> 
> Right, but what really bothers me is that you're then using
> sol[RIGHT][0] as though it means something. So what this function seems
> to do (suppose ax=X_AXIS) is to take an arbitrary point where the curve
> intersects x=r and an arbitrary point where the curve intersects x=l and
> then finds the maximum y value of the curve between those two points.

True.
A well-formed slur should never retrograde along the X-axis, and thus, the size
of sol[LEFT] and sol[RIGHT] should be 1 after filtering out all values less than
0 and greater than 1.
I think that the programming errors in the current patch should do the trick.

> But there's no guarantee that that maximum is what you're after.

I'm pretty sure that, in the case of a well-formed slur, the Y maximum or
minimum is what I'm after.

> For example, if the curve intersects x=r before it intersects x=l then it
> seems to me that Polynomial::minmax will return something weird.

This is true - I've put a programming error in polynomial.cc for this case.

> And if there are multiple intersections with either line, there are a lot of
> different answers that could come out.

True.  In the case of slurs, this should not happen.  The patch passes the
regtests without ever triggering this warning (it'd be difficult to trigger it,
as you'd have to make the slur run backwards).

Cheers,
MS

[MikeSol, 2011-08-25 07:40:28]

Pushed as 29d1121d260318ed07f152c346a1a69e5dadb69d.

Many thanks to Joe and Han-Wen for your comments.

Han-Wen: I didn't hear back from you regarding the intervals for minmax, so I
went ahead and kept them returning Real values.  Lemme know if you still want
them to return intervals and I'll upload that as a separate patch.

Cheers,
MS

[hanwenn, 2011-08-25 13:18:39]

On Thu, Aug 25, 2011 at 4:40 AM,  <mtsolo@gmail.com> wrote:
> Pushed as 29d1121d260318ed07f152c346a1a69e5dadb69d.
>
> Many thanks to Joe and Han-Wen for your comments.
>
> Han-Wen: I didn't hear back from you regarding the intervals for minmax,
> so I went ahead and kept them returning Real values.  Lemme know if you
> still want them to return intervals and I'll upload that as a separate
> patch.

IIRC, you were already calculating all the values needed to return
intervals. If that is so, please use them. It makes the caller code
easier to follow.

-- 
Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

[joeneeman, 2011-08-25 16:03:09]

On Tue, Aug 23, 2011 at 12:36 AM, Mike Solomon <mikesol@ufl.edu> wrote:
> On Aug 23, 2011, at 6:55 AM, joeneeman@gmail.com wrote:
>
>>
>> http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc
>> File lily/bezier.cc (right):
>>
>> http://codereview.appspot.com/4860042/diff/1/lily/bezier.cc#newcode239
>> lily/bezier.cc:239: return p.minmax (sol[LEFT][0], sol[RIGHT][0], d !=
>> LEFT);
>> On 2011/08/19 07:03:50, MikeSol wrote:
>>> On 2011/08/18 21:36:45, joeneeman wrote:
>>> > If there are multiple intersections with (say) r, then
>> Polynomial::solve
>>> doesn't
>>> > seem to return them in any useful order. So sol[RIGHT][0] is really
>> just an
>>> > arbitrary solution, isn't it?
>>
>>> True, but this seems no worse than line 81 where ts[0] is returned.
>> Not that
>>> this is a good excuse...
>>
>> Right, but what really bothers me is that you're then using
>> sol[RIGHT][0] as though it means something. So what this function seems
>> to do (suppose ax=X_AXIS) is to take an arbitrary point where the curve
>> intersects x=r and an arbitrary point where the curve intersects x=l and
>> then finds the maximum y value of the curve between those two points.
>
> True.
> A well-formed slur should never retrograde along the X-axis, and thus, the
size of sol[LEFT] and sol[RIGHT] should be 1 after filtering out all values less
than 0 and greater than 1.
> I think that the programming errors in the current patch should do the trick.

Is it so difficult to just make the solution general? Assuming axis is
Y_AXIS and d is UP, the maximum must appear either at a critical point
of the y-axis polynomial or when the x-axis polynomial is equal to
either l or r. You can filter the critical points to make sure the x
coordinate is within the correct interval, and then filter everything
to make sure that the parameter is between 0 and 1. You'll have no
more than 8 points left and you take the one with the largest Y
coordinate.

I realize that it's unlikely to trigger, at least in the way that
Lilypond currently uses this code, but I do feel that code in a file
called bezier.cc should work for bezier curves in general.

Cheers,
Joe