lily/beam-quanting.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1997--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5   Jan Nieuwenhuizen <janneke@gnu.org>
   6
   7   LilyPond is free software: you can redistribute it and/or modify
   8   it under the terms of the GNU General Public License as published by
   9   the Free Software Foundation, either version 3 of the License, or
  10   (at your option) any later version.
  11
  12   LilyPond is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15   GNU General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 #include "beam-scoring-problem.hh"
  22
  23 #include <queue>
  24 #include <algorithm>
  25 using namespace std;
  26
  27 #include "align-interface.hh"
  28 #include "beam.hh"
  29 #include "grob.hh"
  30 #include "international.hh"
  31 #include "main.hh"
  32 #include "output-def.hh"
  33 #include "pointer-group-interface.hh"
  34 #include "staff-symbol-referencer.hh"
  35 #include "stem.hh"
  36 #include "warn.hh"
  37
  38 Real
  39 get_detail (SCM alist, SCM sym, Real def)
  40 {
  41   SCM entry = scm_assq (sym, alist);
  42
  43   if (scm_is_pair (entry))
  44     return robust_scm2double (scm_cdr (entry), def);
  45   return def;
  46 }
  47
  48 void
  49 Beam_quant_parameters::fill (Grob *him)
  50 {
  51   SCM details = him->get_property ("details");
  52
  53   SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
  54   STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
  55   REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
  56   BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
  57   STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
  58   DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
  59   HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
  60   MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
  61   IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
  62   ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
  63 }
  64
  65 static Real
  66 shrink_extra_weight (Real x, Real fac)
  67 {
  68   return fabs (x) * ((x < 0) ? fac : 1.0);
  69 }
  70
  71 /****************************************************************/
  72
  73 Beam_configuration::Beam_configuration ()
  74 {
  75   y = Interval (0.0, 0.0);
  76   demerits = 0.0;
  77   next_scorer_todo = ORIGINAL_DISTANCE;
  78 }
  79
  80 bool Beam_configuration::done () const
  81 {
  82   return next_scorer_todo >= NUM_SCORERS;
  83 }
  84
  85 void Beam_configuration::add (Real demerit, const string &reason)
  86 {
  87   demerits += demerit;
  88
  89 #if DEBUG_BEAM_SCORING
  90   if (demerit)
  91     score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
  92 #endif
  93 }
  94
  95 Beam_configuration* Beam_configuration::new_config (Interval start,
  96                                                     Interval offset)
  97 {
  98   Beam_configuration* qs = new Beam_configuration;
  99   qs->y = Interval (int (start[LEFT]) + offset[LEFT],
 100                     int (start[RIGHT]) + offset[RIGHT]);
 101
 102   // This orders the sequence so we try combinations closest to the
 103   // the ideal offset first.
 104   Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
 105   qs->demerits = start_score / 1000.0;
 106   qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
 107
 108   return qs;
 109 }
 110
 111 /****************************************************************/
 112
 113 /*
 114   TODO:
 115
 116   - Make all demerits customisable
 117
 118   - One sensible check per demerit (what's this --hwn)
 119
 120   - Add demerits for quants per se, as to forbid a specific quant
 121   entirely
 122 */
 123 int
 124 best_quant_score_idx (vector<Beam_configuration*> const &configs)
 125 {
 126   Real best = 1e6;
 127   int best_idx = -1;
 128   for (vsize i = configs.size (); i--;)
 129     {
 130       if (configs[i]->demerits < best)
 131         {
 132           best = configs [i]->demerits;
 133           best_idx = i;
 134         }
 135     }
 136
 137   return best_idx;
 138 }
 139
 140 // This is a temporary hack to see how much we can gain by using a
 141 // priority queue on the beams to score.
 142 static int score_count = 0;
 143 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
 144            (),
 145            "count number of beam scores.") {
 146   return scm_from_int (score_count);
 147 }
 148
 149 void Beam_scoring_problem::init_stems ()
 150 {
 151   extract_grob_set (beam, "stems", stems);
 152   for (int a = 2; a--;)
 153     common[a] = common_refpoint_of_array (stems, beam, Axis (a));
 154
 155   Drul_array<Grob *> edge_stems(Beam::first_normal_stem (beam),
 156                                 Beam::last_normal_stem (beam));
 157   Direction d = LEFT;
 158   do
 159     x_span[d] = edge_stems[d] ? edge_stems[d]->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 160   while (flip (&d) != LEFT);
 161
 162   Drul_array<bool> dirs_found (0, 0);
 163   for (vsize i = 0; i < stems.size (); i++)
 164     {
 165       Grob *s = stems[i];
 166       if (!Stem::is_normal_stem (s))
 167         continue;
 168
 169       Stem_info si (Stem::get_stem_info (s));
 170       si.scale (1 / staff_space);
 171       stem_infos.push_back (si);
 172       dirs_found[si.dir_] = true;
 173
 174       bool f = to_boolean (s->get_property ("french-beaming"))
 175         && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
 176
 177       Real y = Beam::calc_stem_y (beam, s, common, x_span[LEFT], x_span[RIGHT], CENTER,
 178                                   Interval (0, 0), f);
 179       base_lengths.push_back (y / staff_space);
 180       stem_xpositions.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
 181     }
 182
 183   edge_dirs = Drul_array<Direction> (CENTER, CENTER);
 184   if (stem_infos.size ())
 185     {
 186       edge_dirs = Drul_array<Direction> (stem_infos[0].dir_,
 187                                          stem_infos.back().dir_);
 188     }
 189
 190   is_xstaff = Align_interface::has_interface (common[Y_AXIS]);
 191   is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
 192
 193   staff_radius = Staff_symbol_referencer::staff_radius (beam);
 194   edge_beam_counts =  Drul_array<int>
 195     (Stem::beam_multiplicity (stems[0]).length () + 1,
 196      Stem::beam_multiplicity (stems.back ()).length () + 1);
 197
 198   // TODO - why are we dividing by staff_space?
 199   beam_translation = Beam::get_beam_translation (beam) / staff_space;
 200
 201   d = LEFT;
 202   do
 203     {
 204       quant_range[d].set_full ();
 205       if (!edge_stems[d])
 206         continue;
 207
 208       Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
 209         - beam->relative_coordinate (common[Y_AXIS], Y_AXIS);
 210       Interval heads = Stem::head_positions(edge_stems[d]) * 0.5 * staff_space;
 211
 212       Direction ed = edge_dirs[d];
 213       heads.widen(0.5 * staff_space
 214                   + (edge_beam_counts[d] - 1) * beam_translation + beam_thickness * .5);
 215       quant_range[d][-ed] = heads[ed] + stem_offset;
 216     }
 217   while (flip (&d) != LEFT);
 218 }
 219
 220 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys)
 221 {
 222   beam = me;
 223   unquanted_y = ys;
 224
 225   /*
 226     Calculations are relative to a unit-scaled staff, i.e. the quants are
 227     divided by the current staff_space.
 228   */
 229   staff_space = Staff_symbol_referencer::staff_space (me);
 230   beam_thickness = Beam::get_beam_thickness (me) / staff_space;
 231   line_thickness = Staff_symbol_referencer::line_thickness (me) / staff_space;
 232
 233   // This is the least-squares DY, corrected for concave beams.
 234   musical_dy = robust_scm2double (me->get_property ("least-squares-dy"), 0);
 235
 236   parameters.fill (me);
 237   init_stems ();
 238 }
 239
 240 void
 241 Beam_scoring_problem::generate_quants (vector<Beam_configuration*> *scores) const
 242 {
 243   int region_size = (int) parameters.REGION_SIZE;
 244
 245   /*
 246     Knees are harder, lets try some more possibilities for knees.
 247   */
 248   if (is_knee)
 249     region_size += 2;
 250
 251   Real straddle = 0.0;
 252   Real sit = (beam_thickness - line_thickness) / 2;
 253   Real inter = 0.5;
 254   Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
 255   Real base_quants [] = {straddle, sit, inter, hang};
 256   int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
 257
 258   /*
 259     Asymetry ? should run to <= region_size ?
 260   */
 261   vector<Real> unshifted_quants;
 262   for (int i = -region_size; i < region_size; i++)
 263     for (int j = 0; j < num_base_quants; j++)
 264       {
 265         unshifted_quants.push_back (i + base_quants[j]);
 266       }
 267
 268   for (vsize i = 0; i < unshifted_quants.size (); i++)
 269     for (vsize j = 0; j < unshifted_quants.size (); j++)
 270       {
 271         Beam_configuration *c =
 272           Beam_configuration::new_config (unquanted_y,
 273                                           Interval (unshifted_quants[i],
 274                                                     unshifted_quants[j]));
 275
 276         Direction d = LEFT;
 277         do
 278           {
 279             if (!quant_range[d].contains (c->y[d]))
 280               {
 281                 delete c;
 282                 c = NULL;
 283                 break;
 284               }
 285           }
 286         while (flip (&d) != LEFT);
 287         if (c)
 288           scores->push_back (c);
 289       }
 290
 291 }
 292
 293
 294 void Beam_scoring_problem::one_scorer (Beam_configuration* config) const
 295 {
 296   score_count ++;
 297   switch (config->next_scorer_todo) {
 298   case SLOPES:
 299     score_slopes_dy (config);
 300     break;
 301   case FORBIDDEN:
 302     score_forbidden_quants (config);
 303     break;
 304   case STEM_LENGTHS:
 305     score_stem_lengths (config);
 306     break;
 307
 308   case NUM_SCORERS:
 309   case ORIGINAL_DISTANCE:
 310   default:
 311     assert (false);
 312   }
 313   config->next_scorer_todo++;
 314 }
 315
 316
 317 Beam_configuration *
 318 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration*> &configs) const
 319 {
 320   Drul_array<Real> ins = ly_scm2interval (inspect_quants);
 321   Real mindist = 1e6;
 322   Beam_configuration *best = NULL;
 323   for (vsize i = 0; i < configs.size (); i++)
 324     {
 325       Real d = fabs (configs[i]->y[LEFT]- ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
 326       if (d < mindist)
 327         {
 328           best = configs[i];
 329           mindist = d;
 330         }
 331     }
 332   if (mindist > 1e5)
 333     programming_error ("cannot find quant");
 334
 335   return best;
 336 }
 337
 338 Drul_array<Real>
 339 Beam_scoring_problem::solve () const {
 340   vector<Beam_configuration*> configs;
 341   generate_quants (&configs);
 342
 343   Beam_configuration *best = NULL;
 344
 345   SCM inspect_quants = beam->get_property ("inspect-quants");
 346   if (to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))
 347       && scm_is_pair (inspect_quants))
 348     {
 349       best = force_score (inspect_quants, configs);
 350     }
 351   else
 352     {
 353       std::priority_queue<Beam_configuration*, std::vector<Beam_configuration*>,
 354                           Beam_configuration_less> queue;
 355       for (vsize i = 0; i < configs.size(); i++)
 356         queue.push(configs[i]);
 357
 358
 359       /*
 360         TODO
 361
 362         It would be neat if we generated new configurations on the
 363         fly, depending on the best complete score so far, eg.
 364
 365         if (best->done()) {
 366           if (best->demerits < sqrt(queue.size())
 367             break;
 368           while (best->demerits > sqrt(queue.size()) {
 369             generate and insert new configuration
 370           }
 371         }
 372
 373         that would allow us to do away with region_size altogether.
 374       */
 375       while (true) {
 376         best = queue.top ();
 377         if (best->done ())
 378           break;
 379
 380         queue.pop ();
 381         one_scorer (best);
 382         queue.push (best);
 383       }
 384     }
 385
 386   Interval final_positions = best->y;
 387
 388 #if DEBUG_BEAM_SCORING
 389   if (to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring"))))
 390     {
 391       // debug quanting
 392       int completed = 0;
 393       for (vsize i = 0; i < configs.size (); i++)
 394         {
 395           if (configs[i]->done ())
 396             completed++;
 397         }
 398
 399       string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size());
 400       beam->set_property ("quant-score", ly_string2scm (card));
 401     }
 402 #endif
 403
 404   junk_pointers (configs);
 405   return final_positions;
 406 }
 407
 408 void
 409 Beam_scoring_problem::score_stem_lengths (Beam_configuration* config) const
 410 {
 411   Real limit_penalty = parameters.STEM_LENGTH_LIMIT_PENALTY;
 412   Drul_array<Real> score (0, 0);
 413   Drul_array<int> count (0, 0);
 414
 415   for (vsize i = 0; i < stem_xpositions.size (); i++)
 416     {
 417       Real x = stem_xpositions[i];
 418       Real dx = x_span.delta ();
 419       Real beam_y = dx
 420         ? config->y[RIGHT] * (x - x_span[LEFT]) / dx + config->y[LEFT] * (x_span[RIGHT] - x) / dx
 421         : (config->y[RIGHT] + config->y[LEFT]) / 2;
 422       Real current_y = beam_y + base_lengths[i];
 423       Real length_pen = parameters.STEM_LENGTH_DEMERIT_FACTOR;
 424
 425       Stem_info info = stem_infos[i];
 426       Direction d = info.dir_;
 427
 428       score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
 429
 430       Real ideal_diff = d * (current_y - info.ideal_y_);
 431       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
 432
 433       /* We introduce a power, to make the scoring strictly
 434          convex. Otherwise a symmetric knee beam (up/down/up/down)
 435          does not have an optimum in the middle. */
 436       if (is_knee)
 437         ideal_score = pow (ideal_score, 1.1);
 438
 439       score[d] += length_pen * ideal_score;
 440       count[d]++;
 441     }
 442
 443   /* Divide by number of stems, to make the measure scale-free. */
 444   Direction d = DOWN;
 445   do
 446     score[d] /= max (count[d], 1);
 447   while (flip (&d) != DOWN);
 448
 449   config->add (score[LEFT] + score[RIGHT], "L");
 450 }
 451
 452 void
 453 Beam_scoring_problem::score_slopes_dy (Beam_configuration *config) const
 454 {
 455   Real dy = config->y.delta ();
 456   Real damped_dy = unquanted_y.delta();
 457   Real dem = 0.0;
 458
 459   /*
 460     DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
 461     complex beaming patterns, horizontal is often a good choice.
 462
 463     TODO: find a way to incorporate the complexity of the beam in this
 464     penalty.
 465   */
 466   if (sign (damped_dy) != sign (dy))
 467     {
 468       if (!dy)
 469         {
 470           if (fabs (damped_dy / x_span.delta ()) > parameters.ROUND_TO_ZERO_SLOPE)
 471             dem += parameters.DAMPING_DIRECTION_PENALTY;
 472           else
 473             dem += parameters.HINT_DIRECTION_PENALTY;
 474         }
 475       else
 476         dem += parameters.DAMPING_DIRECTION_PENALTY;
 477     }
 478
 479   dem += parameters.MUSICAL_DIRECTION_FACTOR
 480     * max (0.0, (fabs (dy) - fabs (musical_dy)));
 481
 482   Real slope_penalty = parameters.IDEAL_SLOPE_FACTOR;
 483
 484   /* Xstaff beams tend to use extreme slopes to get short stems. We
 485      put in a penalty here. */
 486   if (is_xstaff)
 487     slope_penalty *= 10;
 488
 489   /* Huh, why would a too steep beam be better than a too flat one ? */
 490   dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
 491     * slope_penalty;
 492
 493   config->add (dem, "S");
 494 }
 495
 496 static Real
 497 my_modf (Real x)
 498 {
 499   return x - floor (x);
 500 }
 501
 502 /*
 503   TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
 504   because for 32nd and 64th beams the forbidden quants are relatively
 505   more important than stem lengths.
 506 */
 507 void
 508 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
 509 {
 510   Real dy = config->y.delta ();
 511
 512   Real extra_demerit = parameters.SECONDARY_BEAM_DEMERIT /
 513     max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]);
 514
 515   Direction d = LEFT;
 516   Real dem = 0.0;
 517   Real eps = parameters.BEAM_EPS;
 518
 519   do
 520     {
 521       for (int j = 1; j <= edge_beam_counts[d]; j++)
 522         {
 523           Direction stem_dir = edge_dirs[d];
 524
 525           /*
 526             The 2.2 factor is to provide a little leniency for
 527             borderline cases. If we do 2.0, then the upper outer line
 528             will be in the gap of the (2, sit) quant, leading to a
 529             false demerit.
 530           */
 531           Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation + beam_thickness / 2 - line_thickness / 2.2);
 532           Real gap2 = config->y[d] - stem_dir * (j * beam_translation - beam_thickness / 2 + line_thickness / 2.2);
 533
 534           Interval gap;
 535           gap.add_point (gap1);
 536           gap.add_point (gap2);
 537
 538           for (Real k = -staff_radius;
 539                k <= staff_radius + eps; k += 1.0)
 540             if (gap.contains (k))
 541               {
 542                 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
 543
 544                 /*
 545                   this parameter is tuned to grace-stem-length.ly
 546                 */
 547                 Real fixed_demerit = 0.4;
 548
 549                 dem += extra_demerit
 550                   * (fixed_demerit
 551                      + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
 552               }
 553         }
 554     }
 555   while ((flip (&d)) != LEFT);
 556
 557   if (max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]) >= 2)
 558     {
 559       Real straddle = 0.0;
 560       Real sit = (beam_thickness - line_thickness) / 2;
 561       Real inter = 0.5;
 562       Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
 563
 564       Direction d = LEFT;
 565       do
 566         {
 567           if (edge_beam_counts[d] >= 2
 568               && fabs (config->y[d] - edge_dirs[d] * beam_translation) < staff_radius + inter)
 569             {
 570               // TODO up/down symmetry.
 571               if (edge_dirs[d] == UP && dy <= eps
 572                   && fabs (my_modf (config->y[d]) - sit) < eps)
 573                 dem += extra_demerit;
 574
 575               if (edge_dirs[d] == DOWN && dy >= eps
 576                   && fabs (my_modf (config->y[d]) - hang) < eps)
 577                 dem += extra_demerit;
 578             }
 579
 580           if (edge_beam_counts[d] >= 3
 581               && fabs (config->y[d] - 2 * edge_dirs[d] * beam_translation) < staff_radius + inter)
 582             {
 583               // TODO up/down symmetry.
 584               if (edge_dirs[d] == UP && dy <= eps
 585                   && fabs (my_modf (config->y[d]) - straddle) < eps)
 586                 dem += extra_demerit;
 587
 588               if (edge_dirs[d] == DOWN && dy >= eps
 589                   && fabs (my_modf (config->y[d]) - straddle) < eps)
 590                 dem += extra_demerit;
 591             }
 592         }
 593       while (flip (&d) != LEFT);
 594     }
 595
 596   config->add (dem, "F");
 597 }
 598