lily/beam-quanting.cc

   1 /*
   2   beam-quanting.cc -- implement Beam quanting functions
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1997--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7   Jan Nieuwenhuizen <janneke@gnu.org>
   8 */
   9
  10 #include "beam.hh"
  11
  12 #include <algorithm>
  13 using namespace std;
  14
  15 #include "grob.hh"
  16 #include "align-interface.hh"
  17 #include "international.hh"
  18 #include "output-def.hh"
  19 #include "pointer-group-interface.hh"
  20 #include "staff-symbol-referencer.hh"
  21 #include "stem.hh"
  22 #include "warn.hh"
  23 #include "main.hh"
  24
  25 Real
  26 get_detail (SCM alist, SCM sym, Real def)
  27 {
  28   SCM entry = scm_assq (sym, alist);
  29
  30   if (scm_is_pair (entry))
  31     return robust_scm2double (scm_cdr (entry), def);
  32   return def;
  33 }
  34
  35 void
  36 Beam_quant_parameters::fill (Grob *him)
  37 {
  38   SCM details = him->get_property ("details");
  39
  40   /*
  41     TODO: put in define-grobs.scm
  42    */
  43   INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("inter-quant-penalty"), 1000.0);
  44   SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
  45   STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
  46   REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
  47   BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
  48   STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
  49   DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
  50   HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
  51   MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
  52   IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
  53   ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
  54 }
  55
  56 static Real
  57 shrink_extra_weight (Real x, Real fac)
  58 {
  59   return fabs (x) * ((x < 0) ? fac : 1.0);
  60 }
  61
  62 struct Quant_score
  63 {
  64   Real yl;
  65   Real yr;
  66   Real demerits;
  67
  68 #if DEBUG_BEAM_SCORING
  69   string score_card_;
  70 #endif
  71 };
  72
  73 /*
  74   TODO:
  75
  76   - Make all demerits customisable
  77
  78   - One sensible check per demerit (what's this --hwn)
  79
  80   - Add demerits for quants per se, as to forbid a specific quant
  81   entirely
  82 */
  83
  84 int
  85 best_quant_score_idx (vector<Quant_score> const &qscores)
  86 {
  87   Real best = 1e6;
  88   int best_idx = -1;
  89   for (vsize i = qscores.size (); i--;)
  90     {
  91       if (qscores[i].demerits < best)
  92         {
  93           best = qscores [i].demerits;
  94           best_idx = i;
  95         }
  96     }
  97
  98   return best_idx;
  99 }
 100
 101 MAKE_SCHEME_CALLBACK (Beam, quanting, 2);
 102 SCM
 103 Beam::quanting (SCM smob, SCM posns)
 104 {
 105   Grob *me = unsmob_grob (smob);
 106
 107   Beam_quant_parameters parameters;
 108   parameters.fill (me);
 109
 110   Real yl = scm_to_double (scm_car (posns));
 111   Real yr = scm_to_double (scm_cdr (posns));
 112
 113   /*
 114     Calculations are relative to a unit-scaled staff, i.e. the quants are
 115     divided by the current staff_space.
 116
 117   */
 118   Real ss = Staff_symbol_referencer::staff_space (me);
 119   Real thickness = Beam::get_thickness (me) / ss;
 120   Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
 121
 122   Real dy_mus = robust_scm2double (me->get_property ("least-squares-dy"), 0);
 123   Real straddle = 0.0;
 124   Real sit = (thickness - slt) / 2;
 125   Real inter = 0.5;
 126   Real hang = 1.0 - (thickness - slt) / 2;
 127   Real quants [] = {straddle, sit, inter, hang };
 128
 129   int num_quants = int (sizeof (quants) / sizeof (Real));
 130   vector<Real> quantsl;
 131   vector<Real> quantsr;
 132
 133   /*
 134     going to REGION_SIZE == 2, yields another 0.6 second with
 135     wtk1-fugue2.
 136
 137
 138     (result indexes between 70 and 575)  ? --hwn.
 139
 140   */
 141
 142   /*
 143     Do stem computations.  These depend on YL and YR linearly, so we can
 144     precompute for every stem 2 factors.
 145   */
 146   vector<Grob*> stems
 147     = extract_grob_array (me, "stems");
 148   vector<Stem_info> stem_infos;
 149   vector<Real> base_lengths;
 150   vector<Real> stem_xposns;
 151
 152   Drul_array<bool> dirs_found (0, 0);
 153   Grob *common[2];
 154   for (int a = 2; a--;)
 155     common[a] = common_refpoint_of_array (stems, me, Axis (a));
 156
 157   Grob *fvs = first_normal_stem (me);
 158   Grob *lvs = last_normal_stem (me);
 159   Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 160   Real xr = fvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 161
 162   /*
 163     We store some info to quickly interpolate.  The stemlength are
 164     affine linear in YL and YR. If YL == YR == 0, then we might have
 165     stem_y != 0.0, when we're cross staff.
 166
 167   */
 168   for (vsize i = 0; i < stems.size (); i++)
 169     {
 170       Grob *s = stems[i];
 171
 172       Stem_info si (Stem::get_stem_info (s));
 173       si.scale (1 / ss);
 174       stem_infos.push_back (si);
 175       dirs_found[stem_infos.back ().dir_] = true;
 176
 177       bool f = to_boolean (s->get_property ("french-beaming"))
 178         && s != lvs && s != fvs;
 179
 180       if (Stem::is_normal_stem (s))
 181         {
 182           base_lengths.push_back (calc_stem_y (me, s, common, xl, xr,
 183                                                Interval (0, 0), f) / ss);
 184         }
 185       else
 186         {
 187           base_lengths.push_back (0);
 188         }
 189
 190       stem_xposns.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
 191     }
 192   bool xstaff = false;
 193   if (lvs && fvs)
 194     {
 195       Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
 196       xstaff = Align_interface::has_interface (commony);
 197     }
 198
 199   Direction ldir = Direction (stem_infos[0].dir_);
 200   Direction rdir = Direction (stem_infos.back ().dir_);
 201   bool is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
 202
 203   int region_size = (int) parameters.REGION_SIZE;
 204
 205   /*
 206     Knees are harder, lets try some more possibilities for knees.
 207   */
 208   if (is_knee)
 209     region_size += 2;
 210
 211   /*
 212     Asymetry ? should run to <= region_size ?
 213   */
 214   for (int i = -region_size; i < region_size; i++)
 215     for (int j = 0; j < num_quants; j++)
 216       {
 217         quantsl.push_back (i + quants[j] + int (yl));
 218         quantsr.push_back (i + quants[j] + int (yr));
 219       }
 220
 221   vector<Quant_score> qscores;
 222
 223   for (vsize l = 0; l < quantsl.size (); l++)
 224     for (vsize r = 0; r < quantsr.size (); r++)
 225       {
 226         Quant_score qs;
 227         qs.yl = quantsl[l];
 228         qs.yr = quantsr[r];
 229         qs.demerits = 0.0;
 230
 231         qscores.push_back (qs);
 232       }
 233
 234   /* This is a longish function, but we don't separate this out into
 235      neat modular separate subfunctions, as the subfunctions would be
 236      called for many values of YL, YR. By precomputing various
 237      parameters outside of the loop, we can save a lot of time. */
 238   for (vsize i = qscores.size (); i--;)
 239     {
 240       Real d = score_slopes_dy (qscores[i].yl, qscores[i].yr,
 241                                 dy_mus, yr- yl,
 242                                 xr - xl,
 243                                 xstaff, &parameters);
 244       qscores[i].demerits += d;
 245
 246 #if DEBUG_BEAM_SCORING
 247       qscores[i].score_card_ += to_string ("S%.2f", d);
 248 #endif
 249     }
 250
 251   Real rad = Staff_symbol_referencer::staff_radius (me);
 252   Drul_array<int> edge_beam_counts
 253     (Stem::beam_multiplicity (stems[0]).length () + 1,
 254      Stem::beam_multiplicity (stems.back ()).length () + 1);
 255
 256   Real beam_translation = get_beam_translation (me) / ss;
 257
 258   Real reasonable_score = (is_knee) ? 200000 : 100;
 259   for (vsize i = qscores.size (); i--;)
 260     if (qscores[i].demerits < reasonable_score)
 261       {
 262         Real d = score_forbidden_quants (qscores[i].yl, qscores[i].yr,
 263                                          rad, slt, thickness, beam_translation,
 264                                          edge_beam_counts, ldir, rdir, &parameters);
 265         qscores[i].demerits += d;
 266
 267 #if DEBUG_BEAM_SCORING
 268         qscores[i].score_card_ += to_string (" F %.2f", d);
 269 #endif
 270       }
 271
 272   for (vsize i = qscores.size (); i--;)
 273     if (qscores[i].demerits < reasonable_score)
 274       {
 275         Real d = score_stem_lengths (stems, stem_infos,
 276                                      base_lengths, stem_xposns,
 277                                      xl, xr,
 278                                      is_knee,
 279                                      qscores[i].yl, qscores[i].yr, &parameters);
 280         qscores[i].demerits += d;
 281
 282 #if DEBUG_BEAM_SCORING
 283         qscores[i].score_card_ += to_string (" L %.2f", d);
 284 #endif
 285       }
 286
 287   int best_idx = best_quant_score_idx (qscores);
 288
 289 #if DEBUG_BEAM_SCORING
 290   SCM inspect_quants = me->get_property ("inspect-quants");
 291   if (to_boolean (me->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))
 292       && scm_is_pair (inspect_quants))
 293     {
 294       Drul_array<Real> ins = ly_scm2interval (inspect_quants);
 295
 296       Real mindist = 1e6;
 297       for (vsize i = 0; i < qscores.size (); i++)
 298         {
 299           Real d = fabs (qscores[i].yl- ins[LEFT]) + fabs (qscores[i].yr - ins[RIGHT]);
 300           if (d < mindist)
 301             {
 302               best_idx = i;
 303               mindist = d;
 304             }
 305         }
 306       if (mindist > 1e5)
 307         programming_error ("cannot find quant");
 308     }
 309 #endif
 310
 311   Interval final_positions;
 312   if (best_idx < 0)
 313     {
 314       warning (_ ("no feasible beam position"));
 315       final_positions = Interval (0, 0);
 316     }
 317   else
 318     {
 319       final_positions = Drul_array<Real> (qscores[best_idx].yl,
 320                                           qscores[best_idx].yr);
 321     }
 322
 323 #if DEBUG_BEAM_SCORING
 324   if (best_idx >= 0
 325       && to_boolean (me->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring"))))
 326     {
 327       qscores[best_idx].score_card_ += to_string ("i%d", best_idx);
 328
 329       // debug quanting
 330       me->set_property ("quant-score",
 331                         ly_string2scm (qscores[best_idx].score_card_));
 332     }
 333 #endif
 334
 335   return ly_interval2scm (final_positions);
 336 }
 337
 338 Real
 339 Beam::score_stem_lengths (vector<Grob*> const &stems,
 340                           vector<Stem_info> const &stem_infos,
 341                           vector<Real> const &base_stem_ys,
 342                           vector<Real> const &stem_xs,
 343                           Real xl, Real xr,
 344                           bool knee,
 345                           Real yl, Real yr,
 346
 347                           Beam_quant_parameters const *parameters)
 348 {
 349   Real limit_penalty = parameters->STEM_LENGTH_LIMIT_PENALTY;
 350   Drul_array<Real> score (0, 0);
 351   Drul_array<int> count (0, 0);
 352
 353   for (vsize i = 0; i < stems.size (); i++)
 354     {
 355       Grob *s = stems[i];
 356       if (!Stem::is_normal_stem (s))
 357         continue;
 358
 359       Real x = stem_xs[i];
 360       Real dx = xr - xl;
 361       Real beam_y = dx ? yr * (x - xl) / dx + yl * (xr - x) / dx : (yr + yl) / 2;
 362       Real current_y = beam_y + base_stem_ys[i];
 363       Real length_pen = parameters->STEM_LENGTH_DEMERIT_FACTOR;
 364
 365       Stem_info info = stem_infos[i];
 366       Direction d = info.dir_;
 367
 368       score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
 369
 370       Real ideal_diff = d * (current_y - info.ideal_y_);
 371       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
 372
 373       /* We introduce a power, to make the scoring strictly
 374          convex. Otherwise a symmetric knee beam (up/down/up/down)
 375          does not have an optimum in the middle. */
 376       if (knee)
 377         ideal_score = pow (ideal_score, 1.1);
 378
 379       score[d] += length_pen * ideal_score;
 380
 381       count[d]++;
 382     }
 383
 384   Direction d = DOWN;
 385   do
 386     score[d] /= max (count[d], 1);
 387   while (flip (&d) != DOWN)
 388     ;
 389
 390   return score[LEFT] + score[RIGHT];
 391 }
 392
 393 Real
 394 Beam::score_slopes_dy (Real yl, Real yr,
 395                        Real dy_mus, Real dy_damp,
 396                        Real dx,
 397                        bool xstaff,
 398
 399                        Beam_quant_parameters const *parameters)
 400 {
 401   Real dy = yr - yl;
 402   Real dem = 0.0;
 403
 404   /*
 405     DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
 406     complex beaming patterns, horizontal is often a good choice.
 407
 408     TODO: find a way to incorporate the complexity of the beam in this
 409     penalty.
 410   */
 411   if (sign (dy_damp) != sign (dy))
 412     {
 413       if (!dy)
 414         {
 415           if (fabs (dy_damp / dx) > parameters->ROUND_TO_ZERO_SLOPE)
 416             dem += parameters->DAMPING_DIRECTION_PENALTY;
 417           else
 418             dem += parameters->HINT_DIRECTION_PENALTY;
 419         }
 420       else
 421         dem += parameters->DAMPING_DIRECTION_PENALTY;
 422     }
 423
 424   dem += parameters->MUSICAL_DIRECTION_FACTOR
 425     * max (0.0, (fabs (dy) - fabs (dy_mus)));
 426
 427   Real slope_penalty = parameters->IDEAL_SLOPE_FACTOR;
 428
 429   /* Xstaff beams tend to use extreme slopes to get short stems. We
 430      put in a penalty here. */
 431   if (xstaff)
 432     slope_penalty *= 10;
 433
 434   /* Huh, why would a too steep beam be better than a too flat one ? */
 435   dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
 436     * slope_penalty;
 437
 438   return dem;
 439 }
 440
 441 static Real
 442 my_modf (Real x)
 443 {
 444   return x - floor (x);
 445 }
 446
 447 /*
 448   TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
 449   because for 32nd and 64th beams the forbidden quants are relatively
 450   more important than stem lengths.
 451 */
 452 Real
 453 Beam::score_forbidden_quants (Real yl, Real yr,
 454                               Real radius,
 455                               Real slt,
 456                               Real thickness, Real beam_translation,
 457                               Drul_array<int> beam_counts,
 458                               Direction ldir, Direction rdir,
 459
 460                               Beam_quant_parameters const *parameters)
 461 {
 462   Real dy = yr - yl;
 463   Drul_array<Real> y (yl, yr);
 464   Drul_array<Direction> dirs (ldir, rdir);
 465
 466   Real extra_demerit = parameters->SECONDARY_BEAM_DEMERIT / (max (beam_counts[LEFT], beam_counts[RIGHT]));
 467
 468   Direction d = LEFT;
 469   Real dem = 0.0;
 470   Real eps = parameters->BEAM_EPS;
 471
 472   do
 473     {
 474       for (int j = 1; j <= beam_counts[d]; j++)
 475         {
 476           Direction stem_dir = dirs[d];
 477
 478           /*
 479             The 2.2 factor is to provide a little leniency for
 480             borderline cases. If we do 2.0, then the upper outer line
 481             will be in the gap of the (2, sit) quant, leading to a
 482             false demerit.
 483           */
 484           Real gap1 = y[d] - stem_dir * ((j - 1) * beam_translation + thickness / 2 - slt / 2.2);
 485           Real gap2 = y[d] - stem_dir * (j * beam_translation - thickness / 2 + slt / 2.2);
 486
 487           Interval gap;
 488           gap.add_point (gap1);
 489           gap.add_point (gap2);
 490
 491           for (Real k = -radius;
 492                k <= radius + eps; k += 1.0)
 493             if (gap.contains (k))
 494               {
 495                 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
 496
 497                 /*
 498                   this parameter is tuned to grace-stem-length.ly
 499                 */
 500                 Real fixed_demerit = 0.4;
 501
 502                 dem += extra_demerit
 503                   * (fixed_demerit
 504                      + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
 505               }
 506         }
 507     }
 508   while ((flip (&d)) != LEFT);
 509
 510   if (max (beam_counts[LEFT], beam_counts[RIGHT]) >= 2)
 511     {
 512       Real straddle = 0.0;
 513       Real sit = (thickness - slt) / 2;
 514       Real inter = 0.5;
 515       Real hang = 1.0 - (thickness - slt) / 2;
 516
 517       Direction d = LEFT;
 518       do
 519         {
 520           if (beam_counts[d] >= 2
 521               && fabs (y[d] - dirs[d] * beam_translation) < radius + inter)
 522             {
 523               if (dirs[d] == UP && dy <= eps
 524                   && fabs (my_modf (y[d]) - sit) < eps)
 525                 dem += extra_demerit;
 526
 527               if (dirs[d] == DOWN && dy >= eps
 528                   && fabs (my_modf (y[d]) - hang) < eps)
 529                 dem += extra_demerit;
 530             }
 531
 532           if (beam_counts[d] >= 3
 533               && fabs (y[d] - 2 * dirs[d] * beam_translation) < radius + inter)
 534             {
 535               if (dirs[d] == UP && dy <= eps
 536                   && fabs (my_modf (y[d]) - straddle) < eps)
 537                 dem += extra_demerit;
 538
 539               if (dirs[d] == DOWN && dy >= eps
 540                   && fabs (my_modf (y[d]) - straddle) < eps)
 541                 dem += extra_demerit;
 542             }
 543         }
 544       while (flip (&d) != LEFT);
 545     }
 546
 547   return dem;
 548 }
 549