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--2003 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7   Jan Nieuwenhuizen <janneke@gnu.org>
   8
   9 */
  10
  11
  12
  13 #include <math.h>
  14
  15 #include "grob.hh"
  16 #include "staff-symbol-referencer.hh"
  17 #include "beam.hh"
  18 #include "stem.hh"
  19 #include "paper-def.hh"
  20 #include "group-interface.hh"
  21 #include "align-interface.hh"
  22
  23 const int INTER_QUANT_PENALTY = 1000;
  24 const int SECONDARY_BEAM_DEMERIT  = 5;
  25 const int STEM_LENGTH_DEMERIT_FACTOR = 5;
  26
  27 // possibly ridiculous, but too short stems just won't do
  28 const int STEM_LENGTH_LIMIT_PENALTY = 5000;
  29 const int DAMPING_DIRECTIION_PENALTY = 800;
  30 const int MUSICAL_DIRECTION_FACTOR = 400;
  31 const int IDEAL_SLOPE_FACTOR = 10;
  32
  33
  34 static Real
  35 shrink_extra_weight (Real x, Real fac)
  36 {
  37   return fabs (x) * ((x < 0) ? fac : 1.0);
  38 }
  39
  40
  41 struct Quant_score
  42 {
  43   Real yl;
  44   Real yr;
  45   Real demerits;
  46 };
  47
  48
  49 /*
  50   TODO:
  51
  52    - Make all demerits customisable
  53
  54    - One sensible check per demerit (what's this --hwn)
  55
  56    - Add demerits for quants per se, as to forbid a specific quant
  57      entirely
  58
  59 */
  60
  61 int best_quant_score_idx (Array<Quant_score>  const & qscores)
  62 {
  63   Real best = 1e6;
  64   int best_idx = -1;
  65   for (int i = qscores.size (); i--;)
  66     {
  67       if (qscores[i].demerits < best)
  68         {
  69           best = qscores [i].demerits ;
  70           best_idx = i;
  71         }
  72     }
  73
  74   return best_idx;
  75 }
  76
  77 MAKE_SCHEME_CALLBACK (Beam, quanting, 1);
  78 SCM
  79 Beam::quanting (SCM smob)
  80 {
  81   Grob *me = unsmob_grob (smob);
  82
  83   SCM s = me->get_grob_property ("positions");
  84   Real yl = gh_scm2double (gh_car (s));
  85   Real yr = gh_scm2double (gh_cdr (s));
  86
  87   Real ss = Staff_symbol_referencer::staff_space (me);
  88   Real thickness = gh_scm2double (me->get_grob_property ("thickness")) / ss;
  89   Real slt = me->get_paper ()->get_realvar (ly_symbol2scm ("linethickness")) / ss;
  90
  91
  92   SCM sdy = me->get_grob_property ("least-squares-dy");
  93   Real dy_mus = gh_number_p (sdy) ? gh_scm2double (sdy) : 0.0;
  94
  95   Real straddle = 0.0;
  96   Real sit = (thickness - slt) / 2;
  97   Real inter = 0.5;
  98   Real hang = 1.0 - (thickness - slt) / 2;
  99   Real quants [] = {straddle, sit, inter, hang };
 100
 101   int num_quants = int (sizeof (quants)/sizeof (Real));
 102   Array<Real> quantsl;
 103   Array<Real> quantsr;
 104
 105   /*
 106     going to REGION_SIZE == 2, yields another 0.6 second with
 107     wtk1-fugue2.
 108
 109
 110     (result indexes between 70 and 575)  ? --hwn.
 111
 112   */
 113
 114
 115
 116   /*
 117     Do stem computations.  These depend on YL and YR linearly, so we can
 118     precompute for every stem 2 factors.
 119    */
 120   Link_array<Grob> stems=
 121     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
 122   Array<Stem_info> stem_infos;
 123   Array<Real> base_lengths;
 124   Array<Real> stem_xposns;
 125
 126   Drul_array<bool> dirs_found(0,0);
 127   Grob *common[2];
 128   for (int a = 2; a--;)
 129     common[a] = common_refpoint_of_array (stems, me, Axis(a));
 130
 131   Grob * fvs = first_visible_stem (me);
 132   Grob *lvs = last_visible_stem (me);
 133   Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 134   Real xr = fvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
 135
 136   /*
 137     We store some info to quickly interpolate.
 138
 139     Sometimes my head is screwed on backwards.  The stemlength are
 140     AFFINE linear in YL and YR. If YL == YR == 0, then we might have
 141     stem_y != 0.0, when we're cross staff.
 142
 143    */
 144   for (int i= 0; i < stems.size(); i++)
 145     {
 146       Grob*s = stems[i];
 147       stem_infos.push (Stem::get_stem_info (s));
 148       dirs_found[stem_infos.top ().dir_] = true;
 149
 150       bool f = to_boolean (s->get_grob_property ("french-beaming"))
 151          && s != lvs && s != fvs;
 152
 153       base_lengths.push (calc_stem_y (me, s, common, xl, xr,
 154                                       Interval (0,0), f));
 155       stem_xposns.push (s->relative_coordinate (common[X_AXIS], X_AXIS));
 156     }
 157
 158   bool xstaff= false;
 159   if (lvs && fvs)
 160     {
 161       Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
 162       xstaff = Align_interface::has_interface (commony);
 163     }
 164
 165   Direction ldir = Direction (stem_infos[0].dir_);
 166   Direction rdir = Direction (stem_infos.top ().dir_);
 167   bool knee_b = dirs_found[LEFT] && dirs_found[RIGHT];
 168
 169
 170   int region_size = REGION_SIZE;
 171   /*
 172     Knees are harder, lets try some more possibilities for knees.
 173    */
 174   if (knee_b)
 175     region_size += 2;
 176
 177   /*
 178     Asymetry ? should run to <= region_size ?
 179    */
 180   for (int i = -region_size ; i < region_size; i++)
 181     for (int j = 0; j < num_quants; j++)
 182       {
 183         quantsl.push (i + quants[j] + int (yl));
 184         quantsr.push (i + quants[j] + int (yr));
 185       }
 186
 187   Array<Quant_score> qscores;
 188
 189   for (int l =0; l < quantsl.size (); l++)
 190     for (int r =0; r < quantsr.size (); r++)
 191       {
 192         Quant_score qs;
 193         qs.yl = quantsl[l];
 194         qs.yr = quantsr[r];
 195         qs.demerits = 0.0;
 196
 197         qscores.push (qs);
 198       }
 199
 200   /* This is a longish function, but we don't separate this out into
 201      neat modular separate subfunctions, as the subfunctions would be
 202      called for many values of YL, YR. By precomputing various
 203      parameters outside of the loop, we can save a lot of time. */
 204   for (int i = qscores.size (); i--;)
 205     {
 206       qscores[i].demerits
 207         += score_slopes_dy (qscores[i].yl, qscores[i].yr,
 208                             dy_mus, yr- yl, xstaff);
 209     }
 210
 211   Real rad = Staff_symbol_referencer::staff_radius (me);
 212   int beam_count = get_beam_count (me);
 213   Real beam_translation = get_beam_translation (me);
 214
 215   Real reasonable_score = (knee_b) ? 200000 : 100;
 216   for (int i = qscores.size (); i--;)
 217     if (qscores[i].demerits < reasonable_score)
 218       {
 219         qscores[i].demerits
 220           += score_forbidden_quants (qscores[i].yl, qscores[i].yr,
 221                                      rad, slt, thickness, beam_translation,
 222                                      beam_count, ldir, rdir);
 223       }
 224
 225   for (int i = qscores.size (); i--;)
 226     if (qscores[i].demerits < reasonable_score)
 227       {
 228         qscores[i].demerits
 229           += score_stem_lengths (stems, stem_infos,
 230                                  base_lengths, stem_xposns,
 231                                  xl, xr,
 232                                  knee_b,
 233                                  qscores[i].yl, qscores[i].yr);
 234       }
 235
 236   int best_idx = best_quant_score_idx (qscores);
 237   me->set_grob_property ("positions",
 238                          gh_cons (gh_double2scm (qscores[best_idx].yl),
 239                                   gh_double2scm (qscores[best_idx].yr))
 240                          );
 241
 242 #if DEBUG_QUANTING
 243
 244   // debug quanting
 245   me->set_grob_property ("quant-score",
 246                          gh_double2scm (qscores[best_idx].demerits));
 247   me->set_grob_property ("best-idx", scm_int2num (best_idx));
 248 #endif
 249
 250   return SCM_UNSPECIFIED;
 251 }
 252
 253 Real
 254 Beam::score_stem_lengths (Link_array<Grob> const &stems,
 255                           Array<Stem_info> const &stem_infos,
 256                           Array<Real> const &base_stem_ys,
 257                           Array<Real> const &stem_xs,
 258                           Real xl, Real xr,
 259                           bool knee,
 260                           Real yl, Real yr)
 261 {
 262   Real limit_penalty = STEM_LENGTH_LIMIT_PENALTY;
 263   Drul_array<Real> score (0, 0);
 264   Drul_array<int> count (0, 0);
 265
 266   for (int i=0; i < stems.size (); i++)
 267     {
 268       Grob* s = stems[i];
 269       if (Stem::invisible_b (s))
 270         continue;
 271
 272       Real x = stem_xs[i];
 273       Real dx = xr-xl;
 274       Real beam_y = dx ? yr *(x - xl)/dx + yl * ( xr - x)/dx : (yr + yl)/2;
 275       Real current_y = beam_y + base_stem_ys[i];
 276       Real length_pen = STEM_LENGTH_DEMERIT_FACTOR;
 277
 278       Stem_info info = stem_infos[i];
 279       Direction d = info.dir_;
 280
 281       score[d] += limit_penalty * (0 >? (d * (info.shortest_y_ - current_y)));
 282
 283       Real ideal_diff = d * (current_y - info.ideal_y_);
 284       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
 285
 286       /* We introduce a power, to make the scoring strictly
 287          convex. Otherwise a symmetric knee beam (up/down/up/down)
 288          does not have an optimum in the middle. */
 289       if (knee)
 290         ideal_score = pow (ideal_score, 1.1);
 291
 292       score[d] += length_pen * ideal_score;
 293
 294       count[d] ++;
 295     }
 296
 297   Direction d = DOWN;
 298   do
 299     {
 300       score[d] /= (count[d] >? 1);
 301     }
 302   while (flip (&d) != DOWN);
 303
 304   return score[LEFT]+score[RIGHT];
 305 }
 306
 307 Real
 308 Beam::score_slopes_dy (Real yl, Real yr,
 309                        Real dy_mus, Real dy_damp,
 310                        bool xstaff)
 311 {
 312   Real dy = yr - yl;
 313
 314   Real dem = 0.0;
 315   if (sign (dy_damp) != sign (dy))
 316     {
 317       dem += DAMPING_DIRECTIION_PENALTY;
 318     }
 319
 320    dem += MUSICAL_DIRECTION_FACTOR * (0 >? (fabs (dy) - fabs (dy_mus)));
 321
 322
 323    Real slope_penalty = IDEAL_SLOPE_FACTOR;
 324
 325    /* Xstaff beams tend to use extreme slopes to get short stems. We
 326       put in a penalty here. */
 327    if (xstaff)
 328      slope_penalty *= 10;
 329
 330    /* Huh, why would a too steep beam be better than a too flat one ? */
 331    dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
 332      * slope_penalty;
 333    return dem;
 334 }
 335
 336 static Real
 337 my_modf (Real x)
 338 {
 339   return x - floor (x);
 340 }
 341
 342
 343 /*
 344   TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
 345    because for 32nd and 64th beams the forbidden quants are relatively
 346    more important than stem lengths.
 347 */
 348 Real
 349 Beam::score_forbidden_quants (Real yl, Real yr,
 350                               Real radius,
 351                               Real slt,
 352                               Real thickness, Real beam_translation,
 353                               int beam_count,
 354                               Direction ldir, Direction rdir)
 355 {
 356   Real dy = yr - yl;
 357
 358   Real dem = 0.0;
 359   for (int i = 0; i < 2; i++)
 360     {
 361       Real y = i? yl : yr;
 362       if (fabs (y) <= (radius + 0.5) && fabs ( my_modf (y) - 0.5) < 1e-3)
 363         dem += INTER_QUANT_PENALTY;
 364     }
 365
 366   // todo: use beam_count of outer stems.
 367   if (beam_count >= 2)
 368     {
 369       Real straddle = 0.0;
 370       Real sit = (thickness - slt) / 2;
 371       Real inter = 0.5;
 372       Real hang = 1.0 - (thickness - slt) / 2;
 373
 374
 375       if (fabs (yl - ldir * beam_translation) < radius
 376           && fabs (my_modf (yl) - inter) < 1e-3)
 377         dem += SECONDARY_BEAM_DEMERIT;
 378       if (fabs (yr - rdir * beam_translation) < radius
 379           && fabs (my_modf (yr) - inter) < 1e-3)
 380         dem += SECONDARY_BEAM_DEMERIT;
 381
 382       Real eps = 1e-3;
 383
 384       /*
 385         Can't we simply compute the distance between the nearest
 386         staffline and the secondary beam? That would get rid of the
 387         silly case analysis here (which is probably not valid when we
 388         have different beam-thicknesses.)
 389
 390         --hwn
 391        */
 392
 393
 394       // hmm, without Interval/Drul_array, you get ~ 4x same code...
 395       if (fabs (yl - ldir * beam_translation) < radius + inter)
 396         {
 397           if (ldir == UP && dy <= eps
 398               && fabs (my_modf (yl) - sit) < eps)
 399             dem += SECONDARY_BEAM_DEMERIT;
 400
 401           if (ldir == DOWN && dy >= eps
 402               && fabs (my_modf (yl) - hang) < eps)
 403             dem += SECONDARY_BEAM_DEMERIT;
 404         }
 405
 406       if (fabs (yr - rdir * beam_translation) < radius + inter)
 407         {
 408           if (rdir == UP && dy >= eps
 409               && fabs (my_modf (yr) - sit) < eps)
 410             dem += SECONDARY_BEAM_DEMERIT;
 411
 412           if (rdir == DOWN && dy <= eps
 413               && fabs (my_modf (yr) - hang) < eps)
 414             dem += SECONDARY_BEAM_DEMERIT;
 415         }
 416
 417       if (beam_count >= 3)
 418         {
 419           if (fabs (yl - 2 * ldir * beam_translation) < radius + inter)
 420             {
 421               if (ldir == UP && dy <= eps
 422                   && fabs (my_modf (yl) - straddle) < eps)
 423                 dem += SECONDARY_BEAM_DEMERIT;
 424
 425               if (ldir == DOWN && dy >= eps
 426                   && fabs (my_modf (yl) - straddle) < eps)
 427                 dem += SECONDARY_BEAM_DEMERIT;
 428             }
 429
 430           if (fabs (yr - 2 * rdir * beam_translation) < radius + inter)
 431             {
 432               if (rdir == UP && dy >= eps
 433                   && fabs (my_modf (yr) - straddle) < eps)
 434                 dem += SECONDARY_BEAM_DEMERIT;
 435
 436               if (rdir == DOWN && dy <= eps
 437                   && fabs (my_modf (yr) - straddle) < eps)
 438                 dem += SECONDARY_BEAM_DEMERIT;
 439             }
 440         }
 441     }
 442
 443   return dem;
 444 }
 445
 446