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 <set>
  25 #include <algorithm>
  26 using namespace std;
  27
  28 #include "align-interface.hh"
  29 #include "beam.hh"
  30 #include "direction.hh"
  31 #include "directional-element-interface.hh"
  32 #include "grob.hh"
  33 #include "international.hh"
  34 #include "main.hh"
  35 #include "output-def.hh"
  36 #include "pointer-group-interface.hh"
  37 #include "staff-symbol-referencer.hh"
  38 #include "stencil.hh"
  39 #include "stem.hh"
  40 #include "warn.hh"
  41
  42 Real
  43 get_detail (SCM alist, SCM sym, Real def)
  44 {
  45   SCM entry = scm_assq (sym, alist);
  46
  47   if (scm_is_pair (entry))
  48     return robust_scm2double (scm_cdr (entry), def);
  49   return def;
  50 }
  51
  52 void
  53 Beam_quant_parameters::fill (Grob *him)
  54 {
  55   SCM details = him->get_property ("details");
  56
  57   // General
  58   BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
  59   REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
  60
  61   // forbidden quants
  62   SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
  63   STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
  64   HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
  65
  66   STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
  67   DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
  68   HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
  69   MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
  70   IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
  71   ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
  72
  73   // Collisions
  74   COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
  75   COLLISION_DISTANCE = get_detail (details, ly_symbol2scm ("collision-distance"), 0.5);
  76   STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
  77 }
  78
  79 // Add x if x is positive, add |x|*fac if x is negative.
  80 static Real
  81 shrink_extra_weight (Real x, Real fac)
  82 {
  83   return fabs (x) * ((x < 0) ? fac : 1.0);
  84 }
  85
  86 /****************************************************************/
  87
  88 Beam_configuration::Beam_configuration ()
  89 {
  90   y = Interval (0.0, 0.0);
  91   demerits = 0.0;
  92   next_scorer_todo = ORIGINAL_DISTANCE;
  93 }
  94
  95 bool Beam_configuration::done () const
  96 {
  97   return next_scorer_todo >= NUM_SCORERS;
  98 }
  99
 100 void Beam_configuration::add (Real demerit, const string &reason)
 101 {
 102   demerits += demerit;
 103
 104 #if DEBUG_BEAM_SCORING
 105   if (demerit)
 106     score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
 107 #endif
 108 }
 109
 110 Beam_configuration* Beam_configuration::new_config (Interval start,
 111                                                     Interval offset)
 112 {
 113   Beam_configuration* qs = new Beam_configuration;
 114   qs->y = Interval (int (start[LEFT]) + offset[LEFT],
 115                     int (start[RIGHT]) + offset[RIGHT]);
 116
 117   // This orders the sequence so we try combinations closest to the
 118   // the ideal offset first.
 119   Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
 120   qs->demerits = start_score / 1000.0;
 121   qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
 122
 123   return qs;
 124 }
 125
 126 Real
 127 Beam_scoring_problem::y_at (Real x, Beam_configuration const* p) const {
 128   return p->y[LEFT] + (x - x_span[LEFT]) * p->y.delta() / x_span.delta();
 129 }
 130
 131 /****************************************************************/
 132
 133 /*
 134   TODO:
 135
 136   - Make all demerits customisable
 137
 138   - Add demerits for quants per se, as to forbid a specific quant
 139   entirely
 140 */
 141
 142 // This is a temporary hack to see how much we can gain by using a
 143 // priority queue on the beams to score.
 144 static int score_count = 0;
 145 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
 146            (),
 147            "count number of beam scores.") {
 148   return scm_from_int (score_count);
 149 }
 150
 151 void Beam_scoring_problem::add_collision (Real x, Interval y,
 152                                           Real score_factor)
 153 {
 154   if (edge_dirs[LEFT] == edge_dirs[RIGHT]) {
 155     Direction d = edge_dirs[LEFT];
 156
 157     Real quant_range_y = quant_range[LEFT][-d] +
 158       (x - x_span[LEFT]) * (quant_range[RIGHT][-d] - quant_range[LEFT][-d]) / x_span.delta();
 159
 160     if (d*(quant_range_y - minmax(d, y[UP], y[DOWN])) > 0) {
 161       return;
 162     }
 163   }
 164
 165   Beam_collision c;
 166   c.beam_y_.set_empty ();
 167
 168   for (vsize j = 0; j < segments_.size (); j++)
 169     {
 170       if (segments_[j].horizontal_.contains(x))
 171         c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation);
 172       if (segments_[j].horizontal_[LEFT] > x)
 173         break;
 174     }
 175   c.beam_y_.widen (0.5 * beam_thickness);
 176
 177   c.x_ = x;
 178   c.y_ = y;
 179   c.base_penalty_ = score_factor;
 180   collisions_.push_back (c);
 181 }
 182
 183 void Beam_scoring_problem::init_collisions (vector<Grob*> grobs)
 184 {
 185   Grob* common_x = NULL;
 186   segments_ = Beam::get_beam_segments (beam, &common_x);
 187   vector_sort (segments_, beam_segment_less);
 188   if (common[X_AXIS] != common_x)
 189     {
 190       programming_error ("Disagree on common x. Skipping collisions in beam scoring.");
 191       return;
 192     }
 193
 194   set<Grob*> stems;
 195   for (vsize i = 0; i < grobs.size (); i++) {
 196     Box b;
 197
 198     for (Axis a = X_AXIS; a < NO_AXES; incr (a))
 199       b[a] = grobs[i]->extent(common[a], a);
 200
 201     Real width = b[X_AXIS].length();
 202
 203     Real width_factor = sqrt(width / staff_space);
 204
 205     Direction d = LEFT;
 206     do
 207       add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
 208     while (flip (&d) != LEFT);
 209
 210     Grob* stem = unsmob_grob (grobs[i]->get_object ("stem"));
 211     if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
 212       {
 213         stems.insert (stem);
 214       }
 215   }
 216
 217   for (set<Grob*>::const_iterator it(stems.begin ()); it != stems.end (); it++)
 218     {
 219       Grob *s = *it;
 220       Real x = s->extent (common[X_AXIS], X_AXIS).center();
 221
 222       Direction stem_dir = get_grob_direction (*it);
 223       Interval y;
 224       y.set_full ();
 225       y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
 226         - beam->relative_coordinate (common[Y_AXIS], Y_AXIS);
 227
 228       Real factor = parameters.STEM_COLLISION_FACTOR;
 229       if (!unsmob_grob (s->get_object ("beam"))
 230           && !Stem::flag (s).is_empty ())
 231         factor = 1.0;
 232       add_collision (x, y, factor);
 233     }
 234 }
 235
 236 void Beam_scoring_problem::init_stems ()
 237 {
 238   extract_grob_set (beam, "covered-grobs", collisions);
 239   extract_grob_set (beam, "stems", stems);
 240   for (int a = 2; a--;)
 241     {
 242       common[a] = common_refpoint_of_array (stems, beam, Axis (a));
 243       common[a] = common_refpoint_of_array (collisions, common[a], Axis (a));
 244     }
 245
 246   Drul_array<Grob *> edge_stems(Beam::first_normal_stem (beam),
 247                                 Beam::last_normal_stem (beam));
 248   Direction d = LEFT;
 249   do
 250     x_span[d] = edge_stems[d] ? edge_stems[d]->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 251   while (flip (&d) != LEFT);
 252
 253   Drul_array<bool> dirs_found (0, 0);
 254   for (vsize i = 0; i < stems.size (); i++)
 255     {
 256       Grob *s = stems[i];
 257       if (!Stem::is_normal_stem (s))
 258         continue;
 259
 260       Stem_info si (Stem::get_stem_info (s));
 261       si.scale (1 / staff_space);
 262       stem_infos.push_back (si);
 263       dirs_found[si.dir_] = true;
 264
 265       bool f = to_boolean (s->get_property ("french-beaming"))
 266         && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
 267
 268       Real y = Beam::calc_stem_y (beam, s, common, x_span[LEFT], x_span[RIGHT], CENTER,
 269                                   Interval (0, 0), f);
 270       base_lengths.push_back (y / staff_space);
 271       stem_xpositions.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
 272     }
 273
 274   edge_dirs = Drul_array<Direction> (CENTER, CENTER);
 275   if (stem_infos.size ())
 276     {
 277       edge_dirs = Drul_array<Direction> (stem_infos[0].dir_,
 278                                          stem_infos.back().dir_);
 279     }
 280
 281   is_xstaff = Align_interface::has_interface (common[Y_AXIS]);
 282   is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
 283
 284   staff_radius = Staff_symbol_referencer::staff_radius (beam);
 285   edge_beam_counts =  Drul_array<int>
 286     (Stem::beam_multiplicity (stems[0]).length () + 1,
 287      Stem::beam_multiplicity (stems.back ()).length () + 1);
 288
 289   // TODO - why are we dividing by staff_space?
 290   beam_translation = Beam::get_beam_translation (beam) / staff_space;
 291
 292   d = LEFT;
 293   do
 294     {
 295       quant_range[d].set_full ();
 296       if (!edge_stems[d])
 297         continue;
 298
 299       Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
 300         - beam->relative_coordinate (common[Y_AXIS], Y_AXIS);
 301       Interval heads = Stem::head_positions(edge_stems[d]) * 0.5 * staff_space;
 302
 303       Direction ed = edge_dirs[d];
 304       heads.widen(0.5 * staff_space
 305                   + (edge_beam_counts[d] - 1) * beam_translation + beam_thickness * .5);
 306       quant_range[d][-ed] = heads[ed] + stem_offset;
 307     }
 308   while (flip (&d) != LEFT);
 309
 310   init_collisions (collisions);
 311 }
 312
 313 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys)
 314 {
 315   beam = me;
 316   unquanted_y = ys;
 317
 318   /*
 319     Calculations are relative to a unit-scaled staff, i.e. the quants are
 320     divided by the current staff_space.
 321   */
 322   staff_space = Staff_symbol_referencer::staff_space (me);
 323   beam_thickness = Beam::get_beam_thickness (me) / staff_space;
 324   line_thickness = Staff_symbol_referencer::line_thickness (me) / staff_space;
 325
 326   // This is the least-squares DY, corrected for concave beams.
 327   musical_dy = robust_scm2double (me->get_property ("least-squares-dy"), 0);
 328
 329   parameters.fill (me);
 330   init_stems ();
 331 }
 332
 333 void
 334 Beam_scoring_problem::generate_quants (vector<Beam_configuration*> *scores) const
 335 {
 336   int region_size = (int) parameters.REGION_SIZE;
 337
 338   // Knees and collisions are harder, lets try some more possibilities
 339   if (is_knee)
 340     region_size += 2;
 341   if (collisions_.size ())
 342     region_size += 2;
 343
 344   Real straddle = 0.0;
 345   Real sit = (beam_thickness - line_thickness) / 2;
 346   Real inter = 0.5;
 347   Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
 348   Real base_quants [] = {straddle, sit, inter, hang};
 349   int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
 350
 351   /*
 352     Asymetry ? should run to <= region_size ?
 353   */
 354   vector<Real> unshifted_quants;
 355   for (int i = -region_size; i < region_size; i++)
 356     for (int j = 0; j < num_base_quants; j++)
 357       {
 358         unshifted_quants.push_back (i + base_quants[j]);
 359       }
 360
 361   for (vsize i = 0; i < unshifted_quants.size (); i++)
 362     for (vsize j = 0; j < unshifted_quants.size (); j++)
 363       {
 364         Beam_configuration *c =
 365           Beam_configuration::new_config (unquanted_y,
 366                                           Interval (unshifted_quants[i],
 367                                                     unshifted_quants[j]));
 368
 369         Direction d = LEFT;
 370         do
 371           {
 372             if (!quant_range[d].contains (c->y[d]))
 373               {
 374                 delete c;
 375                 c = NULL;
 376                 break;
 377               }
 378           }
 379         while (flip (&d) != LEFT);
 380         if (c)
 381           scores->push_back (c);
 382       }
 383
 384 }
 385
 386
 387 void Beam_scoring_problem::one_scorer (Beam_configuration* config) const
 388 {
 389   score_count ++;
 390   switch (config->next_scorer_todo) {
 391   case SLOPE_IDEAL:
 392     score_slope_ideal (config);
 393     break;
 394   case SLOPE_DIRECTION:
 395     score_slope_direction (config);
 396     break;
 397   case SLOPE_MUSICAL:
 398     score_slope_musical (config);
 399     break;
 400   case FORBIDDEN:
 401     score_forbidden_quants (config);
 402     break;
 403   case STEM_LENGTHS:
 404     score_stem_lengths (config);
 405     break;
 406   case COLLISIONS:
 407     score_collisions (config);
 408     break;
 409   case HORIZONTAL_INTER:
 410     score_horizontal_inter_quants (config);
 411     break;
 412
 413   case NUM_SCORERS:
 414   case ORIGINAL_DISTANCE:
 415   default:
 416     assert (false);
 417   }
 418   config->next_scorer_todo++;
 419 }
 420
 421
 422 Beam_configuration *
 423 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration*> &configs) const
 424 {
 425   Drul_array<Real> ins = ly_scm2interval (inspect_quants);
 426   Real mindist = 1e6;
 427   Beam_configuration *best = NULL;
 428   for (vsize i = 0; i < configs.size (); i++)
 429     {
 430       Real d = fabs (configs[i]->y[LEFT]- ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
 431       if (d < mindist)
 432         {
 433           best = configs[i];
 434           mindist = d;
 435         }
 436     }
 437   if (mindist > 1e5)
 438     programming_error ("cannot find quant");
 439
 440   while (!best->done ())
 441     one_scorer (best);
 442
 443   return best;
 444 }
 445
 446 Drul_array<Real>
 447 Beam_scoring_problem::solve () const {
 448   vector<Beam_configuration*> configs;
 449   generate_quants (&configs);
 450
 451   Beam_configuration *best = NULL;
 452
 453   bool debug =
 454     to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
 455   SCM inspect_quants = beam->get_property ("inspect-quants");
 456   if (to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))
 457       && scm_is_pair (inspect_quants))
 458     {
 459       debug = true;
 460       best = force_score (inspect_quants, configs);
 461     }
 462   else
 463     {
 464       std::priority_queue<Beam_configuration*, std::vector<Beam_configuration*>,
 465                           Beam_configuration_less> queue;
 466       for (vsize i = 0; i < configs.size(); i++)
 467         queue.push(configs[i]);
 468
 469       /*
 470         TODO
 471
 472         It would be neat if we generated new configurations on the
 473         fly, depending on the best complete score so far, eg.
 474
 475         if (best->done()) {
 476           if (best->demerits < sqrt(queue.size())
 477             break;
 478           while (best->demerits > sqrt(queue.size()) {
 479             generate and insert new configuration
 480           }
 481         }
 482
 483         that would allow us to do away with region_size altogether.
 484       */
 485       while (true) {
 486         best = queue.top ();
 487         if (best->done ())
 488           break;
 489
 490         queue.pop ();
 491         one_scorer (best);
 492         queue.push (best);
 493       }
 494     }
 495
 496   Interval final_positions = best->y;
 497
 498 #if DEBUG_BEAM_SCORING
 499   if (debug)
 500     {
 501       // debug quanting
 502       int completed = 0;
 503       for (vsize i = 0; i < configs.size (); i++)
 504         {
 505           if (configs[i]->done ())
 506             completed++;
 507         }
 508
 509       string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size());
 510       beam->set_property ("annotation", ly_string2scm (card));
 511     }
 512 #endif
 513
 514   junk_pointers (configs);
 515   return final_positions;
 516 }
 517
 518 void
 519 Beam_scoring_problem::score_stem_lengths (Beam_configuration* config) const
 520 {
 521   Real limit_penalty = parameters.STEM_LENGTH_LIMIT_PENALTY;
 522   Drul_array<Real> score (0, 0);
 523   Drul_array<int> count (0, 0);
 524
 525   for (vsize i = 0; i < stem_xpositions.size (); i++)
 526     {
 527       Real x = stem_xpositions[i];
 528       Real dx = x_span.delta ();
 529       Real beam_y = dx
 530         ? config->y[RIGHT] * (x - x_span[LEFT]) / dx + config->y[LEFT] * (x_span[RIGHT] - x) / dx
 531         : (config->y[RIGHT] + config->y[LEFT]) / 2;
 532       Real current_y = beam_y + base_lengths[i];
 533       Real length_pen = parameters.STEM_LENGTH_DEMERIT_FACTOR;
 534
 535       Stem_info info = stem_infos[i];
 536       Direction d = info.dir_;
 537
 538       score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
 539
 540       Real ideal_diff = d * (current_y - info.ideal_y_);
 541       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
 542
 543       /* We introduce a power, to make the scoring strictly
 544          convex. Otherwise a symmetric knee beam (up/down/up/down)
 545          does not have an optimum in the middle. */
 546       if (is_knee)
 547         ideal_score = pow (ideal_score, 1.1);
 548
 549       score[d] += length_pen * ideal_score;
 550       count[d]++;
 551     }
 552
 553   /* Divide by number of stems, to make the measure scale-free. */
 554   Direction d = DOWN;
 555   do
 556     score[d] /= max (count[d], 1);
 557   while (flip (&d) != DOWN);
 558
 559   config->add (score[LEFT] + score[RIGHT], "L");
 560 }
 561
 562 void
 563 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
 564 {
 565   Real dy = config->y.delta ();
 566   Real damped_dy = unquanted_y.delta();
 567   Real dem = 0.0;
 568   /*
 569     DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
 570     complex beaming patterns, horizontal is often a good choice.
 571
 572     TODO: find a way to incorporate the complexity of the beam in this
 573     penalty.
 574   */
 575   if (sign (damped_dy) != sign (dy))
 576     {
 577       if (!dy)
 578         {
 579           if (fabs (damped_dy / x_span.delta ()) > parameters.ROUND_TO_ZERO_SLOPE)
 580             dem += parameters.DAMPING_DIRECTION_PENALTY;
 581           else
 582             dem += parameters.HINT_DIRECTION_PENALTY;
 583         }
 584       else
 585         dem += parameters.DAMPING_DIRECTION_PENALTY;
 586     }
 587
 588   config->add (dem, "Sd");
 589 }
 590
 591 // Score for going against the direction of the musical pattern
 592 void
 593 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
 594 {
 595   Real dy = config->y.delta ();
 596   Real dem = parameters.MUSICAL_DIRECTION_FACTOR
 597     * max (0.0, (fabs (dy) - fabs (musical_dy)));
 598   config->add (dem, "Sm");
 599 }
 600
 601 // Score deviation from calculated ideal slope.
 602 void
 603 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
 604 {
 605   Real dy = config->y.delta ();
 606   Real damped_dy = unquanted_y.delta();
 607   Real dem = 0.0;
 608
 609   Real slope_penalty = parameters.IDEAL_SLOPE_FACTOR;
 610
 611   /* Xstaff beams tend to use extreme slopes to get short stems. We
 612      put in a penalty here. */
 613   if (is_xstaff)
 614     slope_penalty *= 10;
 615
 616   /* Huh, why would a too steep beam be better than a too flat one ? */
 617   dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
 618     * slope_penalty;
 619
 620   config->add (dem, "Si");
 621 }
 622
 623 static Real
 624 my_modf (Real x)
 625 {
 626   return x - floor (x);
 627 }
 628
 629 // TODO - there is some overlap with forbidden quants, but for
 630 // horizontal beams, it is much more serious to have stafflines
 631 // appearing in the wrong place, so we have a separate scorer.
 632 void
 633 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
 634 {
 635   if (config->y.delta() == 0.0 && abs (config->y[LEFT]) < staff_radius * staff_space)
 636     {
 637       Real yshift = config->y[LEFT] - 0.5 * staff_space;
 638       if (abs (round(yshift) - yshift) < 0.01 * staff_space)
 639         config->add (parameters.HORIZONTAL_INTER_QUANT_PENALTY, "H");
 640     }
 641 }
 642
 643 /*
 644   TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
 645   because for 32nd and 64th beams the forbidden quants are relatively
 646   more important than stem lengths.
 647 */
 648 void
 649 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
 650 {
 651   Real dy = config->y.delta ();
 652
 653   Real extra_demerit = parameters.SECONDARY_BEAM_DEMERIT /
 654     max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]);
 655
 656   Direction d = LEFT;
 657   Real dem = 0.0;
 658   Real eps = parameters.BEAM_EPS;
 659
 660   do
 661     {
 662       for (int j = 1; j <= edge_beam_counts[d]; j++)
 663         {
 664           Direction stem_dir = edge_dirs[d];
 665
 666           /*
 667             The 2.2 factor is to provide a little leniency for
 668             borderline cases. If we do 2.0, then the upper outer line
 669             will be in the gap of the (2, sit) quant, leading to a
 670             false demerit.
 671           */
 672           Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation + beam_thickness / 2 - line_thickness / 2.2);
 673           Real gap2 = config->y[d] - stem_dir * (j * beam_translation - beam_thickness / 2 + line_thickness / 2.2);
 674
 675           Interval gap;
 676           gap.add_point (gap1);
 677           gap.add_point (gap2);
 678
 679           for (Real k = -staff_radius;
 680                k <= staff_radius + eps; k += 1.0)
 681             if (gap.contains (k))
 682               {
 683                 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
 684
 685                 /*
 686                   this parameter is tuned to grace-stem-length.ly
 687                 */
 688                 Real fixed_demerit = 0.4;
 689
 690                 dem += extra_demerit
 691                   * (fixed_demerit
 692                      + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
 693               }
 694         }
 695     }
 696   while ((flip (&d)) != LEFT);
 697
 698   if (max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]) >= 2)
 699     {
 700       Real straddle = 0.0;
 701       Real sit = (beam_thickness - line_thickness) / 2;
 702       Real inter = 0.5;
 703       Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
 704
 705       Direction d = LEFT;
 706       do
 707         {
 708           if (edge_beam_counts[d] >= 2
 709               && fabs (config->y[d] - edge_dirs[d] * beam_translation) < staff_radius + inter)
 710             {
 711               // TODO up/down symmetry.
 712               if (edge_dirs[d] == UP && dy <= eps
 713                   && fabs (my_modf (config->y[d]) - sit) < eps)
 714                 dem += extra_demerit;
 715
 716               if (edge_dirs[d] == DOWN && dy >= eps
 717                   && fabs (my_modf (config->y[d]) - hang) < eps)
 718                 dem += extra_demerit;
 719             }
 720
 721           if (edge_beam_counts[d] >= 3
 722               && fabs (config->y[d] - 2 * edge_dirs[d] * beam_translation) < staff_radius + inter)
 723             {
 724               // TODO up/down symmetry.
 725               if (edge_dirs[d] == UP && dy <= eps
 726                   && fabs (my_modf (config->y[d]) - straddle) < eps)
 727                 dem += extra_demerit;
 728
 729               if (edge_dirs[d] == DOWN && dy >= eps
 730                   && fabs (my_modf (config->y[d]) - straddle) < eps)
 731                 dem += extra_demerit;
 732             }
 733         }
 734       while (flip (&d) != LEFT);
 735     }
 736
 737   config->add (dem, "F");
 738 }
 739
 740 void
 741 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
 742 {
 743   Real demerits = 0.0;
 744   for (vsize i = 0; i < collisions_.size (); i++)
 745     {
 746       Interval collision_y = collisions_[i].y_;
 747       Real x = collisions_[i].x_;
 748
 749       Real center_beam_y = y_at (x, config);
 750       Interval beam_y = center_beam_y + collisions_[i].beam_y_;
 751
 752       Real dist = infinity_f;
 753       if (!intersection (beam_y, collision_y).is_empty ())
 754         dist = 0.0;
 755       else
 756         dist = min (beam_y.distance (collision_y[DOWN]),
 757                     beam_y.distance (collision_y[UP]));
 758
 759       Real scale_free =
 760         max (parameters.COLLISION_DISTANCE - dist, 0.0)/
 761         parameters.COLLISION_DISTANCE;
 762       demerits +=
 763         collisions_[i].base_penalty_ *
 764         pow (scale_free, 3) * parameters.COLLISION_PENALTY;
 765     }
 766
 767   config->add (demerits, "C");
 768 }