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