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--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7   Jan Nieuwenhuizen <janneke@gnu.org>
   8 */
   9
  10 #include "beam.hh"
  11
  12 #include <algorithm>
  13 using namespace std;
  14
  15 #include "warn.hh"
  16 #include "staff-symbol-referencer.hh"
  17 #include "stem.hh"
  18 #include "output-def.hh"
  19 #include "pointer-group-interface.hh"
  20 #include "align-interface.hh"
  21
  22 Real
  23 get_detail (SCM alist, SCM sym, Real def)
  24 {
  25   SCM entry = scm_assq (sym, alist);
  26
  27   if (scm_is_pair (entry))
  28     return robust_scm2double (scm_cdr (entry), def);
  29   return def;
  30 }
  31
  32 void
  33 Beam_quant_parameters::fill (Grob *him)
  34 {
  35   SCM details = him->get_property ("details");
  36
  37   INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("inter-quant-penalty"), 1000.0);
  38   SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
  39   STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
  40   REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
  41   BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
  42
  43   // possibly ridiculous, but too short stems just won't do
  44   STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
  45   DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
  46   MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
  47   IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
  48   ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
  49 }
  50
  51 static Real
  52 shrink_extra_weight (Real x, Real fac)
  53 {
  54   return fabs (x) * ((x < 0) ? fac : 1.0);
  55 }
  56
  57 struct Quant_score
  58 {
  59   Real yl;
  60   Real yr;
  61   Real demerits;
  62
  63 #if DEBUG_QUANTING
  64   String score_card_;
  65 #endif
  66 };
  67
  68 /*
  69   TODO:
  70
  71   - Make all demerits customisable
  72
  73   - One sensible check per demerit (what's this --hwn)
  74
  75   - Add demerits for quants per se, as to forbid a specific quant
  76   entirely
  77 */
  78
  79 int
  80 best_quant_score_idx (Array<Quant_score> const &qscores)
  81 {
  82   Real best = 1e6;
  83   int best_idx = -1;
  84   for (int i = qscores.size (); i--;)
  85     {
  86       if (qscores[i].demerits < best)
  87         {
  88           best = qscores [i].demerits;
  89           best_idx = i;
  90         }
  91     }
  92
  93   return best_idx;
  94 }
  95
  96 MAKE_SCHEME_CALLBACK (Beam, quanting, 2);
  97 SCM
  98 Beam::quanting (SCM smob, SCM posns)
  99 {
 100   Grob *me = unsmob_grob (smob);
 101
 102   Beam_quant_parameters parameters;
 103   parameters.fill (me);
 104
 105   Real yl = scm_to_double (scm_car (posns));
 106   Real yr = scm_to_double (scm_cdr (posns));
 107
 108   /*
 109     Calculations are relative to a unit-scaled staff, i.e. the quants are
 110     divided by the current staff_space.
 111
 112   */
 113   Real ss = Staff_symbol_referencer::staff_space (me);
 114   Real thickness = Beam::get_thickness (me) / ss;
 115   Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
 116
 117   Real dy_mus = robust_scm2double (me->get_property ("least-squares-dy"), 0);
 118   Real straddle = 0.0;
 119   Real sit = (thickness - slt) / 2;
 120   Real inter = 0.5;
 121   Real hang = 1.0 - (thickness - slt) / 2;
 122   Real quants [] = {straddle, sit, inter, hang };
 123
 124   int num_quants = int (sizeof (quants) / sizeof (Real));
 125   Array<Real> quantsl;
 126   Array<Real> quantsr;
 127
 128   /*
 129     going to REGION_SIZE == 2, yields another 0.6 second with
 130     wtk1-fugue2.
 131
 132
 133     (result indexes between 70 and 575)  ? --hwn.
 134
 135   */
 136
 137   /*
 138     Do stem computations.  These depend on YL and YR linearly, so we can
 139     precompute for every stem 2 factors.
 140   */
 141   Link_array<Grob> stems
 142     = extract_grob_array (me, "stems");
 143   Array<Stem_info> stem_infos;
 144   Array<Real> base_lengths;
 145   Array<Real> stem_xposns;
 146
 147   Drul_array<bool> dirs_found (0, 0);
 148   Grob *common[2];
 149   for (int a = 2; a--;)
 150     common[a] = common_refpoint_of_array (stems, me, Axis (a));
 151
 152   Grob *fvs = first_visible_stem (me);
 153   Grob *lvs = last_visible_stem (me);
 154   Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 155   Real xr = fvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 156
 157   /*
 158     We store some info to quickly interpolate.
 159
 160     Sometimes my head is screwed on backwards.  The stemlength are
 161     AFFINE linear in YL and YR. If YL == YR == 0, then we might have
 162     stem_y != 0.0, when we're cross staff.
 163
 164   */
 165   for (int i = 0; i < stems.size (); i++)
 166     {
 167       Grob *s = stems[i];
 168
 169       Stem_info si (Stem::get_stem_info (s));
 170       si.scale (1 / ss);
 171       stem_infos.push (si);
 172       dirs_found[stem_infos.top ().dir_] = true;
 173
 174       bool f = to_boolean (s->get_property ("french-beaming"))
 175         && s != lvs && s != fvs;
 176
 177       base_lengths.push (calc_stem_y (me, s, common, xl, xr,
 178                                       Interval (0, 0), f) / ss);
 179       stem_xposns.push (s->relative_coordinate (common[X_AXIS], X_AXIS));
 180     }
 181
 182   bool xstaff = false;
 183   if (lvs && fvs)
 184     {
 185       Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
 186       xstaff = Align_interface::has_interface (commony);
 187     }
 188
 189   Direction ldir = Direction (stem_infos[0].dir_);
 190   Direction rdir = Direction (stem_infos.top ().dir_);
 191   bool is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
 192
 193   int region_size = (int) parameters.REGION_SIZE;
 194
 195   /*
 196     Knees are harder, lets try some more possibilities for knees.
 197   */
 198   if (is_knee)
 199     region_size += 2;
 200
 201   /*
 202     Asymetry ? should run to <= region_size ?
 203   */
 204   for (int i = -region_size; i < region_size; i++)
 205     for (int j = 0; j < num_quants; j++)
 206       {
 207         quantsl.push (i + quants[j] + int (yl));
 208         quantsr.push (i + quants[j] + int (yr));
 209       }
 210
 211   Array<Quant_score> qscores;
 212
 213   for (int l = 0; l < quantsl.size (); l++)
 214     for (int r = 0; r < quantsr.size (); r++)
 215       {
 216         Quant_score qs;
 217         qs.yl = quantsl[l];
 218         qs.yr = quantsr[r];
 219         qs.demerits = 0.0;
 220
 221         qscores.push (qs);
 222       }
 223
 224   /* This is a longish function, but we don't separate this out into
 225      neat modular separate subfunctions, as the subfunctions would be
 226      called for many values of YL, YR. By precomputing various
 227      parameters outside of the loop, we can save a lot of time. */
 228   for (int i = qscores.size (); i--;)
 229     {
 230       Real d = score_slopes_dy (qscores[i].yl, qscores[i].yr,
 231                                 dy_mus, yr- yl,
 232                                 xr - xl,
 233                                 xstaff, &parameters);
 234       qscores[i].demerits += d;
 235
 236 #if DEBUG_QUANTING
 237       qscores[i].score_card_ += to_string ("S%.2f", d);
 238 #endif
 239     }
 240
 241   Real rad = Staff_symbol_referencer::staff_radius (me);
 242   Drul_array<int> edge_beam_counts
 243     (Stem::beam_multiplicity (stems[0]).length () + 1,
 244      Stem::beam_multiplicity (stems.top ()).length () + 1);
 245
 246   Real beam_translation = get_beam_translation (me) / ss;
 247
 248   Real reasonable_score = (is_knee) ? 200000 : 100;
 249   for (int i = qscores.size (); i--;)
 250     if (qscores[i].demerits < reasonable_score)
 251       {
 252         Real d = score_forbidden_quants (qscores[i].yl, qscores[i].yr,
 253                                          rad, slt, thickness, beam_translation,
 254                                          edge_beam_counts, ldir, rdir, &parameters);
 255         qscores[i].demerits += d;
 256
 257 #if DEBUG_QUANTING
 258         qscores[i].score_card_ += to_string (" F %.2f", d);
 259 #endif
 260       }
 261
 262   for (int i = qscores.size (); i--;)
 263     if (qscores[i].demerits < reasonable_score)
 264       {
 265         Real d = score_stem_lengths (stems, stem_infos,
 266                                      base_lengths, stem_xposns,
 267                                      xl, xr,
 268                                      is_knee,
 269                                      qscores[i].yl, qscores[i].yr, &parameters);
 270         qscores[i].demerits += d;
 271
 272 #if DEBUG_QUANTING
 273         qscores[i].score_card_ += to_string (" L %.2f", d);
 274 #endif
 275       }
 276
 277   int best_idx = best_quant_score_idx (qscores);
 278
 279 #if DEBUG_QUANTING
 280   SCM inspect_quants = me->get_property ("inspect-quants");
 281   if (to_boolean (me->get_layout ()->lookup_variable (ly_symbol2scm ("debug-beam-quanting")))
 282       && scm_is_pair (inspect_quants))
 283     {
 284       Drul_array<Real> ins = ly_scm2interval (inspect_quants);
 285
 286       int i = 0;
 287
 288       Real mindist = 1e6;
 289       for (; 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_QUANTING
 316   if (best_idx >= 0
 317       && to_boolean (me->get_layout ()->lookup_variable (ly_symbol2scm ("debug-beam-quanting"))))
 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_.to_str0 ()));
 324     }
 325 #endif
 326
 327   return ly_interval2scm (final_positions);
 328 }
 329
 330 Real
 331 Beam::score_stem_lengths (Link_array<Grob> const &stems,
 332                           Array<Stem_info> const &stem_infos,
 333                           Array<Real> const &base_stem_ys,
 334                           Array<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 (int 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