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