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--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7   Jan Nieuwenhuizen <janneke@gnu.org>
   8
   9
  10
  11 */
  12
  13
  14
  15 #include <math.h>
  16
  17 #include "warn.hh"
  18 #include "grob.hh"
  19 #include "staff-symbol-referencer.hh"
  20 #include "beam.hh"
  21 #include "stem.hh"
  22 #include "output-def.hh"
  23 #include "group-interface.hh"
  24 #include "align-interface.hh"
  25
  26 const int INTER_QUANT_PENALTY = 1000;
  27 const Real SECONDARY_BEAM_DEMERIT  = 10.0;
  28 const int STEM_LENGTH_DEMERIT_FACTOR = 5;
  29
  30 /*
  31   threshold to combat rounding errors.
  32  */
  33 const Real BEAM_EPS = 1e-3;
  34
  35 // possibly ridiculous, but too short stems just won't do
  36 const int STEM_LENGTH_LIMIT_PENALTY = 5000;
  37 const int DAMPING_DIRECTION_PENALTY = 800;
  38 const int MUSICAL_DIRECTION_FACTOR = 400;
  39 const int IDEAL_SLOPE_FACTOR = 10;
  40 const Real ROUND_TO_ZERO_SLOPE = 0.02;
  41 const int ROUND_TO_ZERO_POINTS = 4;
  42
  43 extern bool debug_beam_quanting_flag;
  44
  45 static Real
  46 shrink_extra_weight (Real x, Real fac)
  47 {
  48   return fabs (x) * ((x < 0) ? fac : 1.0);
  49 }
  50
  51
  52 struct Quant_score
  53 {
  54   Real yl;
  55   Real yr;
  56   Real demerits;
  57
  58 #if DEBUG_QUANTING
  59   String score_card_;
  60 #endif
  61 };
  62
  63
  64 /*
  65   TODO:
  66
  67    - Make all demerits customisable
  68
  69    - One sensible check per demerit (what's this --hwn)
  70
  71    - Add demerits for quants per se, as to forbid a specific quant
  72      entirely
  73
  74 */
  75
  76 int best_quant_score_idx (Array<Quant_score>  const & qscores)
  77 {
  78   Real best = 1e6;
  79   int best_idx = -1;
  80   for (int i = qscores.size (); i--;)
  81     {
  82       if (qscores[i].demerits < best)
  83         {
  84           best = qscores [i].demerits ;
  85           best_idx = i;
  86         }
  87     }
  88
  89   return best_idx;
  90 }
  91
  92 MAKE_SCHEME_CALLBACK (Beam, quanting, 1);
  93 SCM
  94 Beam::quanting (SCM smob)
  95 {
  96   Grob *me = unsmob_grob (smob);
  97
  98   SCM s = me->get_property ("positions");
  99   Real yl = ly_scm2double (ly_car (s));
 100   Real yr = ly_scm2double (ly_cdr (s));
 101
 102
 103   /*
 104     Calculations are relative to a unit-scaled staff, i.e. the quants are
 105     divided by the current staff_space.
 106
 107    */
 108   Real ss = Staff_symbol_referencer::staff_space (me);
 109   Real thickness = Beam::get_thickness (me) / ss ;
 110   Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
 111
 112   SCM sdy = me->get_property ("least-squares-dy");
 113   Real dy_mus = ly_c_number_p (sdy) ? ly_scm2double (sdy) : 0.0;
 114
 115   Real straddle = 0.0;
 116   Real sit = (thickness - slt) / 2;
 117   Real inter = 0.5;
 118   Real hang = 1.0 - (thickness - slt) / 2;
 119   Real quants [] = {straddle, sit, inter, hang };
 120
 121   int num_quants = int (sizeof (quants)/sizeof (Real));
 122   Array<Real> quantsl;
 123   Array<Real> quantsr;
 124
 125   /*
 126     going to REGION_SIZE == 2, yields another 0.6 second with
 127     wtk1-fugue2.
 128
 129
 130     (result indexes between 70 and 575)  ? --hwn.
 131
 132   */
 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   Link_array<Grob> stems=
 141     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
 142   Array<Stem_info> stem_infos;
 143   Array<Real> base_lengths;
 144   Array<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_visible_stem (me);
 152   Grob *lvs = last_visible_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.
 158
 159     Sometimes my head is screwed on backwards.  The stemlength are
 160     AFFINE linear in YL and YR. If YL == YR == 0, then we might have
 161     stem_y != 0.0, when we're cross staff.
 162
 163    */
 164   for (int i= 0; i < stems.size (); i++)
 165     {
 166       Grob*s = stems[i];
 167
 168       Stem_info si (Stem::get_stem_info (s));
 169       si.scale (1 / ss);
 170       stem_infos.push (si);
 171       dirs_found[stem_infos.top ().dir_] = true;
 172
 173       bool f = to_boolean (s->get_property ("french-beaming"))
 174          && s != lvs && s != fvs;
 175
 176       base_lengths.push (calc_stem_y (me, s, common, xl, xr,
 177                                       Interval (0,0), f) / ss);
 178       stem_xposns.push (s->relative_coordinate (common[X_AXIS], X_AXIS));
 179     }
 180
 181   bool xstaff= false;
 182   if (lvs && fvs)
 183     {
 184       Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
 185       xstaff = Align_interface::has_interface (commony);
 186     }
 187
 188   Direction ldir = Direction (stem_infos[0].dir_);
 189   Direction rdir = Direction (stem_infos.top ().dir_);
 190   bool is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
 191
 192
 193   int region_size = REGION_SIZE;
 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 (i + quants[j] + int (yl));
 207         quantsr.push (i + quants[j] + int (yr));
 208       }
 209
 210   Array<Quant_score> qscores;
 211
 212   for (int l =0; l < quantsl.size (); l++)
 213     for (int 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 (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 (int 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);
 233       qscores[i].demerits += d;
 234
 235 #if DEBUG_QUANTING
 236       qscores[i].score_card_ += to_string ("S%.2f",d);
 237 #endif
 238     }
 239
 240   Real rad = Staff_symbol_referencer::staff_radius (me);
 241
 242
 243
 244   Drul_array<int> edge_beam_counts
 245     (Stem::beam_multiplicity (stems[0]).length  () + 1,
 246      Stem::beam_multiplicity (stems.top ()).length  () + 1);
 247
 248   Real beam_translation = get_beam_translation (me) / ss;
 249
 250   Real reasonable_score = (is_knee) ? 200000 : 100;
 251   for (int 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);
 257         qscores[i].demerits += d;
 258
 259 #if DEBUG_QUANTING
 260         qscores[i].score_card_ += to_string (" F %.2f", d);
 261 #endif
 262       }
 263
 264   for (int 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);
 272         qscores[i].demerits +=  d;
 273
 274 #if DEBUG_QUANTING
 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
 282 #if DEBUG_QUANTING
 283   SCM inspect_quants = me->get_property ("inspect-quants");
 284   if (debug_beam_quanting_flag
 285       && ly_c_pair_p (inspect_quants))
 286     {
 287       Drul_array<Real> ins = ly_scm2interval (inspect_quants);
 288
 289       int i = 0;
 290
 291       Real mindist = 1e6;
 292       for (; i < qscores.size (); i ++)
 293         {
 294           Real d =fabs (qscores[i].yl- ins[LEFT]) + fabs (qscores[i].yr - ins[RIGHT]);
 295           if (d < mindist)
 296             {
 297               best_idx = i;
 298               mindist= d;
 299             }
 300         }
 301       if (mindist > 1e5)
 302         programming_error ("Could not find quant.");
 303     }
 304 #endif
 305
 306   me->set_property ("positions",
 307                     ly_interval2scm (Drul_array<Real> (qscores[best_idx].yl,
 308                                                        qscores[best_idx].yr)));
 309 #if DEBUG_QUANTING
 310   if (debug_beam_quanting_flag)
 311     {
 312       qscores[best_idx].score_card_ += to_string ("i%d", best_idx);
 313
 314       // debug quanting
 315       me->set_property ("quant-score",
 316                              scm_makfrom0str (qscores[best_idx].score_card_.to_str0 ()));
 317     }
 318 #endif
 319
 320   return SCM_UNSPECIFIED;
 321 }
 322
 323 Real
 324 Beam::score_stem_lengths (Link_array<Grob> const &stems,
 325                           Array<Stem_info> const &stem_infos,
 326                           Array<Real> const &base_stem_ys,
 327                           Array<Real> const &stem_xs,
 328                           Real xl, Real xr,
 329                           bool knee,
 330                           Real yl, Real yr)
 331 {
 332   Real limit_penalty = STEM_LENGTH_LIMIT_PENALTY;
 333   Drul_array<Real> score (0, 0);
 334   Drul_array<int> count (0, 0);
 335
 336   for (int i=0; i < stems.size (); i++)
 337     {
 338       Grob* s = stems[i];
 339       if (Stem::is_invisible (s))
 340         continue;
 341
 342       Real x = stem_xs[i];
 343       Real dx = xr-xl;
 344       Real beam_y = dx ? yr *(x - xl)/dx + yl * ( xr - x)/dx : (yr + yl)/2;
 345       Real current_y = beam_y + base_stem_ys[i];
 346       Real length_pen = STEM_LENGTH_DEMERIT_FACTOR;
 347
 348       Stem_info info = stem_infos[i];
 349       Direction d = info.dir_;
 350
 351       score[d] += limit_penalty * (0 >? (d * (info.shortest_y_ - current_y)));
 352
 353       Real ideal_diff = d * (current_y - info.ideal_y_);
 354       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
 355
 356       /* We introduce a power, to make the scoring strictly
 357          convex. Otherwise a symmetric knee beam (up/down/up/down)
 358          does not have an optimum in the middle. */
 359       if (knee)
 360         ideal_score = pow (ideal_score, 1.1);
 361
 362       score[d] += length_pen * ideal_score;
 363
 364       count[d] ++;
 365     }
 366
 367   Direction d = DOWN;
 368   do
 369     {
 370       score[d] /= (count[d] >? 1);
 371     }
 372   while (flip (&d) != DOWN);
 373
 374   return score[LEFT]+score[RIGHT];
 375 }
 376
 377 Real
 378 Beam::score_slopes_dy (Real yl, Real yr,
 379                        Real dy_mus, Real dy_damp,
 380                        Real dx,
 381                        bool xstaff)
 382 {
 383   Real dy = yr - yl;
 384   Real dem = 0.0;
 385
 386   /*
 387     DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
 388     complex beaming patterns, horizontal is often a good choice.
 389
 390     TODO: find a way to incorporate the complexity of the beam in this
 391     penalty.
 392    */
 393   if (fabs (dy/dx) > ROUND_TO_ZERO_SLOPE
 394       && sign (dy_damp) != sign (dy))
 395     {
 396       dem += DAMPING_DIRECTION_PENALTY;
 397     }
 398
 399    dem += MUSICAL_DIRECTION_FACTOR * (0 >? (fabs (dy) - fabs (dy_mus)));
 400
 401
 402    Real slope_penalty = IDEAL_SLOPE_FACTOR;
 403
 404    /* Xstaff beams tend to use extreme slopes to get short stems. We
 405       put in a penalty here. */
 406    if (xstaff)
 407      slope_penalty *= 10;
 408
 409    /* Huh, why would a too steep beam be better than a too flat one ? */
 410    dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
 411      * slope_penalty;
 412
 413 #if 0
 414    /*
 415      almost zero slopes look like errors in horizontal beams.
 416     */
 417    /*
 418      This causes too much problems, because horizontal depends on
 419      horizontal spacing details.  These errors should be dealt with
 420      through concaveness. --hwn.
 421     */
 422    if (fabs (dy) > 1e-3
 423        && fabs (dy / dx) < ROUND_TO_ZERO_SLOPE)
 424      dem += ROUND_TO_ZERO_POINTS;
 425 #endif
 426
 427    return dem;
 428 }
 429
 430 static Real
 431 my_modf (Real x)
 432 {
 433   return x - floor (x);
 434 }
 435
 436
 437 /*
 438   TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
 439    because for 32nd and 64th beams the forbidden quants are relatively
 440    more important than stem lengths.
 441 */
 442 Real
 443 Beam::score_forbidden_quants (Real yl, Real yr,
 444                               Real radius,
 445                               Real slt,
 446                               Real thickness, Real beam_translation,
 447                               Drul_array<int> beam_counts,
 448                               Direction ldir, Direction rdir)
 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 = SECONDARY_BEAM_DEMERIT / (beam_counts[LEFT] >? beam_counts[RIGHT]);
 455
 456   /*
 457     Inside the staff, inter quants are forbidden.
 458    */
 459   Real dem = 0.0;
 460   Direction d = LEFT;
 461   do
 462     {
 463       if (fabs (y[d]) <= (radius + 0.5) && fabs (my_modf (y[d]) - 0.5) < BEAM_EPS)
 464         dem += INTER_QUANT_PENALTY;
 465     }
 466   while ((flip (&d))!= LEFT);
 467
 468
 469   do
 470     {
 471       for (int j = 1; j <= beam_counts[d]; j++)
 472         {
 473           /*
 474             see if the outer staffline falls in a beam-gap
 475
 476             This test is too weak; we should really check all lines.
 477            */
 478           Direction stem_dir = dirs[d];
 479
 480           /*
 481             The 2.2 factor is to provide a little leniency for
 482             borderline cases. If we do 2.0, then the upper outer line
 483             will be in the gap of the (2,sit) quant, leading to a
 484             false demerit.
 485            */
 486           Real gap1 =  y[d] - stem_dir * ((j-1) * beam_translation + thickness / 2 - slt/2.2 );
 487           Real gap2 = y[d] - stem_dir * (j * beam_translation - thickness / 2 + slt/2.2);
 488
 489           Interval gap;
 490           gap.add_point (gap1);
 491           gap.add_point (gap2);
 492
 493           for (Real k = - radius ;
 494                k <= radius + BEAM_EPS; k += 1.0)
 495             if (gap.contains (k))
 496               dem += extra_demerit;
 497         }
 498     }
 499   while ((flip (&d))!= LEFT);
 500
 501
 502   if ((beam_counts[LEFT] >? beam_counts[RIGHT]) >= 2)
 503     {
 504       Real straddle = 0.0;
 505       Real sit = (thickness - slt) / 2;
 506       Real inter = 0.5;
 507       Real hang = 1.0 - (thickness - slt) / 2;
 508
 509
 510       Direction d = LEFT;
 511       do
 512         {
 513           if (beam_counts[d] >= 2
 514               && fabs (y[d] - dirs[d] * beam_translation) < radius + inter)
 515             {
 516               if (dirs[d] == UP && dy <= BEAM_EPS
 517                   && fabs (my_modf (y[d]) - sit) < BEAM_EPS)
 518                 dem += extra_demerit;
 519
 520               if (dirs[d] == DOWN && dy >= BEAM_EPS
 521                   && fabs (my_modf (y[d]) - hang) < BEAM_EPS)
 522                 dem += extra_demerit;
 523             }
 524
 525           if (beam_counts[d] >= 3
 526               && fabs (y[d] - 2 * dirs[d] * beam_translation) < radius + inter)
 527             {
 528               if (dirs[d] == UP && dy <= BEAM_EPS
 529                   && fabs (my_modf (y[d]) - straddle) < BEAM_EPS)
 530                 dem += extra_demerit;
 531
 532               if (dirs[d] == DOWN && dy >= BEAM_EPS
 533                   && fabs (my_modf (y[d]) - straddle) < BEAM_EPS)
 534                 dem += extra_demerit;
 535             }
 536         }
 537       while (flip (&d) != LEFT);
 538     }
 539
 540   return dem;
 541 }
 542
 543