Another fix candidate for issue 1613.

Another fix candidate for issue 1613.

[MikeSol, 2011-05-01 00:49:25]

This is a significant rewrite of one chunk of of beam.cc that fixes issue 1613.

I won't have the time to run the regtests today to think if it breaks anything,
but I have run it on several test files and it seems to yield good results. 
Please look it over and let me know what you think!

Cheers,
MS

[Carl, 2011-05-01 00:56:38]

Looks good to me -- just a comment on a variable name.

http://codereview.appspot.com/4426072/diff/1001/lily/beam.cc
File lily/beam.cc (right):

http://codereview.appspot.com/4426072/diff/1001/lily/beam.cc#newcode1272
lily/beam.cc:1272: Interval vorboten;
We shouldn't use german words for variable names, I think.  English is the
standard code language for lilypond.

And if we do, we should spell it properly -- I'm pretty sure the spelling is
verboten.

Perhaps "disallowed"?

[MikeSol, 2011-05-01 01:36:42]

Sorry about that...back to German 101!

http://codereview.appspot.com/4426072/diff/1001/lily/beam.cc
File lily/beam.cc (right):

http://codereview.appspot.com/4426072/diff/1001/lily/beam.cc#newcode1272
lily/beam.cc:1272: Interval vorboten;
On 2011/05/01 00:56:39, Carl wrote:
> We shouldn't use german words for variable names, I think.  English is the
> standard code language for lilypond.
> 
> And if we do, we should spell it properly -- I'm pretty sure the spelling is
> verboten.
> 
> Perhaps "disallowed"?

Changed and a new patchset uploaded.

[hanwenn, 2011-05-01 02:44:31]

Can you document what this is doing?

My idea was to have a datatype

class RealSubset {
  // Starts out as full interval
  Real_subset();

  // Remove an interval
  remove(Interval v);

  // Return sorted, non-overlapping list of allowed intervals
  vector<Interval> allowed() const;

  // implement with list or tree of non-overlapping intervals
}


You create such an object, remove the extents of all collisions (duly
transformed to be corresponding to left beam edge).  Finally, pick the
center of the most sensible interval from allowed(), one which is not
too small and as close as possible to the original left Y.


On Sat, Apr 30, 2011 at 9:49 PM,  <mtsolo@gmail.com> wrote:
> Reviewers: ,
>
> Message:
> This is a significant rewrite of one chunk of of beam.cc that fixes
> issue 1613.
>
> I won't have the time to run the regtests today to think if it breaks
> anything, but I have run it on several test files and it seems to yield
> good results.  Please look it over and let me know what you think!
>
> Cheers,
> MS
>
> Description:
> Another fix candidate for issue 1613.
>
> Please review this at http://codereview.appspot.com/4426072/
>
> Affected files:
>  M lily/beam.cc
>
>
> Index: lily/beam.cc
> diff --git a/lily/beam.cc b/lily/beam.cc
> index
>
938567984ecc81f2b96889bec0c0432c0f99e09c..31f6cc9339ae90466d8aeb7a69e97e4f26224b3a
> 100644
> --- a/lily/beam.cc
> +++ b/lily/beam.cc
> @@ -1182,13 +1182,6 @@ Beam::shift_region_to_valid (SCM grob, SCM posns)
>       feasible_left_point.intersect (flp);
>     }
>
> -  /*
> -    We have two intervals here, one for the up variant (beams goes
> -    over the collision) one for the down.
> -  */
> -  Drul_array<Interval> collision_free (feasible_left_point,
> -                                       feasible_left_point);
> -
>   vector<Grob*> filtered;
>   /*
>     We only update these for objects that are too large for quanting
> @@ -1201,6 +1194,10 @@ Beam::shift_region_to_valid (SCM grob, SCM posns)
>     take care of computing the impact those exactly.
>   */
>   Real min_y_size = 2.0;
> +
> +  // A list of intervals into which beams may not fall
> +  vector<Interval> forbidden_intervals;
> +
>   for (vsize i = 0; i < covered.size(); i++)
>     {
>       if (!covered[i]->is_live())
> @@ -1272,28 +1269,21 @@ Beam::shift_region_to_valid (SCM grob, SCM posns)
>           Real dy = slope * x;
>
>           Direction yd = DOWN;
> +          Interval vorboten;
>           do
>             {
>               Real left_y = b[Y_AXIS][yd];
>
> -              if (left_y == yd * infinity_f)
> -                {
> -                  collision_free[yd].set_empty ();
> -                  continue;
> -                }
> -
>               left_y -= dy;
>
>               // Translate back to beam as ref point.
>               left_y -= me->relative_coordinate (common[Y_AXIS], Y_AXIS);
> -
> -              Interval allowed;
> -              allowed.set_full ();
>
> -              allowed[-yd] = left_y;
> -              collision_free[yd].intersect (allowed);
> +              vorboten[yd] = left_y;
>             }
>           while (flip (&yd) != DOWN);
> +
> +          forbidden_intervals.push_back (vorboten);
>         }
>       while (flip (&d) != LEFT);
>     }
> @@ -1303,45 +1293,58 @@ Beam::shift_region_to_valid (SCM grob, SCM posns)
>                                              ly_symbol2scm
> ("covered-grobs"));
>   arr->set_array (filtered);
>
> -  if (collision_free[DOWN].contains (beam_left_y)
> -      || collision_free[UP].contains (beam_left_y))
> +  vector_sort (forbidden_intervals, Interval::left_less);
> +  Real epsilon = 1.0e-10;
> +  Interval feasible_beam_placements (beam_left_y, beam_left_y);
> +
> +  bool dirty = false;
> +  do
>     {
> -      // We're good to go. Do nothing.
> +      dirty = false;
> +      for (vsize i = 0; i < forbidden_intervals.size (); i++)
> +        {
> +          Direction d = DOWN;
> +          do
> +            {
> +              if (!(forbidden_intervals[i][d] == d*infinity_f) &&
> forbidden_intervals[i].contains (feasible_beam_placements[d]))
> +                {
> +                  feasible_beam_placements[d] = d * epsilon +
> forbidden_intervals[i][d];
> +                  dirty = true;
> +                }
> +            }
> +          while (flip (&d) != DOWN);
> +        }
>     }
> -  else if (collision_free[DOWN].is_empty() !=
> collision_free[UP].is_empty())
> -    {
> -      // Only one of them offers is feasible solution. Pick that one.
> -      Interval v =
> -        (!collision_free[DOWN].is_empty()) ?
> -        collision_free[DOWN] :
> -        collision_free[UP];
> +  while (dirty);
>
> -      beam_left_y = point_in_interval (v, 2.0);
> -    }
> -  else if (!collision_free[DOWN].is_empty ()
> -           && !collision_free[UP].is_empty ())
> +  Direction d = DOWN;
> +  do
>     {
> -      // Above and below are candidates, take the one closest to the
> -      // starting solution.
> -      Interval best =
> -        (collision_free[DOWN].distance (beam_left_y)
> -         < collision_free[UP].distance (beam_left_y)) ?
> -        collision_free[DOWN] : collision_free[UP];
> -
> -      beam_left_y = point_in_interval (best, 2.0);
> +      if (!feasible_left_point.contains (feasible_beam_placements[d]))
> +        feasible_beam_placements[d] = d*infinity_f;
>     }
> -  else if (!feasible_left_point.is_empty ())
> +  while (flip (&d) != DOWN);
> +
> +  if ((feasible_beam_placements[UP] == infinity_f &&
> feasible_beam_placements[DOWN] == -infinity_f) &&
> !feasible_left_point.is_empty ())
>     {
>       // We are somewhat screwed: we have a collision, but at least
>       // there is a way to satisfy stem length constraints.
>       beam_left_y = point_in_interval (feasible_left_point, 2.0);
>     }
> +  else if (!feasible_left_point.is_empty ())
> +    {
> +      // Only one of them offers is feasible solution. Pick that one.
> +      if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs
> (beam_left_y - feasible_beam_placements[UP]))
> +        beam_left_y = feasible_beam_placements[UP];
> +      else
> +        beam_left_y = feasible_beam_placements[DOWN];
> +    }
>   else
>     {
>       // We are completely screwed.
>       me->warning (_ ("no viable initial configuration found: may not find
> good beam slope"));
>     }
> -
> +
>   pos = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
>   scale_drul (&pos, 1 / Staff_symbol_referencer::staff_space (me));
>
>
>
>
> _______________________________________________
> lilypond-devel mailing list
> lilypond-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/lilypond-devel
>



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

[MikeSol, 2011-05-01 04:29:00]

On 2011/05/01 02:44:31, hanwenn wrote:
> Can you document what this is doing?
> 
> My idea was to have a datatype
> 
> class RealSubset {
>   // Starts out as full interval
>   Real_subset();
> 
>   // Remove an interval
>   remove(Interval v);
> 
>   // Return sorted, non-overlapping list of allowed intervals
>   vector<Interval> allowed() const;
> 
>   // implement with list or tree of non-overlapping intervals
> }
> 
> 
> You create such an object, remove the extents of all collisions (duly
> transformed to be corresponding to left beam edge).  Finally, pick the
> center of the most sensible interval from allowed(), one which is not
> too small and as close as possible to the original left Y.
> 
> 

Hey Han-Wen,

I put some more comments in a new patch in hopes that it is enough to help you
make an implementation of the type of thing you're talking about.  Conversely,
if you think that the patch in its current state is admissible, let me know.

Cheers,
MS

[hanwenn, 2011-05-01 12:24:16]

http://codereview.appspot.com/4426072/diff/4002/lily/beam.cc
File lily/beam.cc (right):

http://codereview.appspot.com/4426072/diff/4002/lily/beam.cc#newcode1329
lily/beam.cc:1329: while (dirty);
this looks fishy; what guarantees that the loop will terminate?

  forbidden is 

    [ (-inf, 2), (1, inf) ]

this will loop forever?

[mike_apollinemike.com, 2011-05-01 13:47:07]

On May 1, 2011, at 5:24 AM, hanwenn@gmail.com wrote:

> 
> http://codereview.appspot.com/4426072/diff/4002/lily/beam.cc
> File lily/beam.cc (right):
> 
> http://codereview.appspot.com/4426072/diff/4002/lily/beam.cc#newcode1329
> lily/beam.cc:1329: while (dirty);
> this looks fishy; what guarantees that the loop will terminate?
> 
>  forbidden is
> 
>    [ (-inf, 2), (1, inf) ]
> 
> this will loop forever?
> 

I think that line 1320 prohibits that:

              if (!(forbidden_intervals[i][d] == d*infinity_f) &&
forbidden_intervals[i].contains (feasible_beam_placements[d]))

So long as the sign on the infinity is negative if DOWN and positive if UP
(which I can't imagine it not being given the way the code above works), these
should be screened out.

Cheers,
MS

[MikeSol, 2011-05-01 17:47:24]

Ran the regtests - had to make one change, but they are now squeaky clean. 
Confirmations would be appreciated!

Cheers,
Mike

[mike_apollinemike.com, 2011-05-04 14:57:01]

On May 1, 2011, at 10:47 AM, mtsolo@gmail.com wrote:

> Ran the regtests - had to make one change, but they are now squeaky
> clean.  Confirmations would be appreciated!
> 
> Cheers,
> Mike
> 
> http://codereview.appspot.com/4426072/

After chatting a bit w/ Han-Wen, I'm pushing this for now.  In the future, he
may implement a class to take care of this.  For now, my solution works and does
not break any regtests.  I have some ideas for how to optimize one of the loops
(at the expense of slightly more memory used), but I want to get this version up
and running to see if it is as functional as I think it is.

beam-collision-large-object.ly can be modified via the addition of an accidental
to check for this behavior.  Let me know if you want me to do this.

Pushed as e0679ba2d5af0f480a67e6108760ef3ee9bcdb80

Cheers,
MS

[c_sorensen, 2011-05-04 16:30:47]

On 5/4/11 8:56 AM, "mike@apollinemike.com" <mike@apollinemike.com> wrote:

> On May 1, 2011, at 10:47 AM, mtsolo@gmail.com wrote:
> 
>> Ran the regtests - had to make one change, but they are now squeaky
>> clean.  Confirmations would be appreciated!
>> 
>> Cheers,
>> Mike
>> 
>> http://codereview.appspot.com/4426072/
> 
> After chatting a bit w/ Han-Wen, I'm pushing this for now.  In the future, he
> may implement a class to take care of this.  For now, my solution works and
> does not break any regtests.  I have some ideas for how to optimize one of the
> loops (at the expense of slightly more memory used), but I want to get this
> version up and running to see if it is as functional as I think it is.
> 
> beam-collision-large-object.ly can be modified via the addition of an
> accidental to check for this behavior.  Let me know if you want me to do this.

Yes, please do.  WE always want to keep regtests updated to check for fixed
bugs.

Thanks,

Carl