Re: Another fix candidate for issue 1613. (issue4426072)

[Han-Wen Nienhuys]

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,  <address@hidden> 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
> address@hidden
> https://lists.gnu.org/mailman/listinfo/lilypond-devel
>



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