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  = 15;
  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   bool french = to_boolean (me->get_grob_property ("french-beaming"));
 145   for (int i= 0; i < stems.size(); i++)
 146     {
 147       Grob*s = stems[i];
 148       stem_infos.push (Stem::get_stem_info (s));
 149       dirs_found[stem_infos.top ().dir_] = true;
 150
 151       bool f = french && i > 0&& (i < stems.size  () -1);
 152       base_lengths.push (calc_stem_y (me, s, common, xl, xr,
 153                                       Interval (0,0), f));
 154       stem_xposns.push (s->relative_coordinate (common[X_AXIS], X_AXIS));
 155     }
 156
 157   bool xstaff= false;
 158   if (lvs && fvs)
 159     {
 160       Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
 161       xstaff = Align_interface::has_interface (commony);
 162     }
 163
 164   Direction ldir = Direction (stem_infos[0].dir_);
 165   Direction rdir = Direction (stem_infos.top ().dir_);
 166   bool knee_b = dirs_found[LEFT] && dirs_found[RIGHT];
 167
 168
 169   int region_size = REGION_SIZE;
 170   /*
 171     Knees are harder, lets try some more possibilities for knees.
 172    */
 173   if (knee_b)
 174     region_size += 2;
 175
 176   /*
 177     Asymetry ? should run to <= region_size ?
 178    */
 179   for (int i = -region_size ; i < region_size; i++)
 180     for (int j = 0; j < num_quants; j++)
 181       {
 182         quantsl.push (i + quants[j] + int (yl));
 183         quantsr.push (i + quants[j] + int (yr));
 184       }
 185
 186   Array<Quant_score> qscores;
 187
 188   for (int l =0; l < quantsl.size (); l++)
 189     for (int r =0; r < quantsr.size (); r++)
 190       {
 191         Quant_score qs;
 192         qs.yl = quantsl[l];
 193         qs.yr = quantsr[r];
 194         qs.demerits = 0.0;
 195
 196         qscores.push (qs);
 197       }
 198
 199   /* This is a longish function, but we don't separate this out into
 200      neat modular separate subfunctions, as the subfunctions would be
 201      called for many values of YL, YR. By precomputing various
 202      parameters outside of the loop, we can save a lot of time. */
 203   for (int i = qscores.size (); i--;)
 204     {
 205       qscores[i].demerits
 206         += score_slopes_dy (qscores[i].yl, qscores[i].yr,
 207                             dy_mus, yr- yl, xstaff);
 208     }
 209
 210   Real rad = Staff_symbol_referencer::staff_radius (me);
 211   int beam_count = get_beam_count (me);
 212   Real beam_translation = get_beam_translation (me);
 213
 214   Real reasonable_score = (knee_b) ? 200000 : 100;
 215   for (int i = qscores.size (); i--;)
 216     if (qscores[i].demerits < reasonable_score)
 217       {
 218         qscores[i].demerits
 219           += score_forbidden_quants (qscores[i].yl, qscores[i].yr,
 220                                      rad, slt, thickness, beam_translation,
 221                                      beam_count, ldir, rdir);
 222       }
 223
 224   //  ; /* silly gdb thinks best_idx is inside for loop. */
 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   //  ; /* silly gdb thinks best_idx is inside for loop. */
 237   int best_idx = best_quant_score_idx (qscores);
 238   me->set_grob_property ("positions",
 239                          gh_cons (gh_double2scm (qscores[best_idx].yl),
 240                                   gh_double2scm (qscores[best_idx].yr))
 241                          );
 242
 243 #if DEBUG_QUANTING
 244
 245   // debug quanting
 246   me->set_grob_property ("quant-score",
 247                          gh_double2scm (qscores[best_idx].demerits));
 248   me->set_grob_property ("best-idx", scm_int2num (best_idx));
 249 #endif
 250
 251   return SCM_UNSPECIFIED;
 252 }
 253
 254 Real
 255 Beam::score_stem_lengths (Link_array<Grob> const &stems,
 256                           Array<Stem_info> const &stem_infos,
 257                           Array<Real> const &base_stem_ys,
 258                           Array<Real> const &stem_xs,
 259                           Real xl, Real xr,
 260                           bool knee,
 261                           Real yl, Real yr)
 262 {
 263   Real limit_penalty = STEM_LENGTH_LIMIT_PENALTY;
 264   Drul_array<Real> score (0, 0);
 265   Drul_array<int> count (0, 0);
 266
 267   for (int i=0; i < stems.size (); i++)
 268     {
 269       Grob* s = stems[i];
 270       if (Stem::invisible_b (s))
 271         continue;
 272
 273       Real x = stem_xs[i];
 274       Real dx = xr-xl;
 275       Real beam_y = yr *(x - xl)/dx + yl * ( xr - x)/dx;
 276       Real current_y = beam_y + base_stem_ys[i];
 277       Real length_pen = STEM_LENGTH_DEMERIT_FACTOR;
 278
 279       Stem_info info = stem_infos[i];
 280       Direction d = info.dir_;
 281
 282       score[d] += limit_penalty * (0 >? (d * (info.shortest_y_ - current_y)));
 283
 284       Real ideal_diff = d * (current_y - info.ideal_y_);
 285       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
 286
 287       /* We introduce a power, to make the scoring strictly
 288          convex. Otherwise a symmetric knee beam (up/down/up/down)
 289          does not have an optimum in the middle. */
 290       if (knee)
 291         ideal_score = pow (ideal_score, 1.1);
 292
 293       score[d] += length_pen * ideal_score;
 294
 295       count[d] ++;
 296     }
 297
 298   Direction d = DOWN;
 299   do
 300     {
 301       if(count[d])
 302         score[d] /= count[d];
 303     }
 304   while (flip (&d) != DOWN);
 305
 306   return score[LEFT]+score[RIGHT];
 307 }
 308
 309 Real
 310 Beam::score_slopes_dy (Real yl, Real yr,
 311                        Real dy_mus, Real dy_damp,
 312                        bool xstaff)
 313 {
 314   Real dy = yr - yl;
 315
 316   Real dem = 0.0;
 317   if (sign (dy_damp) != sign (dy))
 318     {
 319       dem += DAMPING_DIRECTIION_PENALTY;
 320     }
 321
 322    dem += MUSICAL_DIRECTION_FACTOR * (0 >? (fabs (dy) - fabs (dy_mus)));
 323
 324
 325    Real slope_penalty = IDEAL_SLOPE_FACTOR;
 326
 327    /* Xstaff beams tend to use extreme slopes to get short stems. We
 328       put in a penalty here. */
 329    if (xstaff)
 330      slope_penalty *= 10;
 331
 332    /* Huh, why would a too steep beam be better than a too flat one ? */
 333    dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
 334      * slope_penalty;
 335    return dem;
 336 }
 337
 338 static Real
 339 my_modf (Real x)
 340 {
 341   return x - floor (x);
 342 }
 343
 344 Real
 345 Beam::score_forbidden_quants (Real yl, Real yr,
 346                               Real radius,
 347                               Real slt,
 348                               Real thickness, Real beam_translation,
 349                               int beam_count,
 350                               Direction ldir, Direction rdir)
 351 {
 352   Real dy = yr - yl;
 353
 354   Real dem = 0.0;
 355   for (int i = 0; i < 2; i++)
 356     {
 357       Real y = i? yl : yr;
 358       if (fabs (y) <= (radius + 0.5) && fabs ( my_modf (y) - 0.5) < 1e-3)
 359         dem += INTER_QUANT_PENALTY;
 360     }
 361
 362   // todo: use beam_count of outer stems.
 363   if (beam_count >= 2)
 364     {
 365       Real straddle = 0.0;
 366       Real sit = (thickness - slt) / 2;
 367       Real inter = 0.5;
 368       Real hang = 1.0 - (thickness - slt) / 2;
 369
 370
 371       if (fabs (yl - ldir * beam_translation) < radius
 372           && fabs (my_modf (yl) - inter) < 1e-3)
 373         dem += SECONDARY_BEAM_DEMERIT;
 374       if (fabs (yr - rdir * beam_translation) < radius
 375           && fabs (my_modf (yr) - inter) < 1e-3)
 376         dem += SECONDARY_BEAM_DEMERIT;
 377
 378       Real eps = 1e-3;
 379
 380       /*
 381         Can't we simply compute the distance between the nearest
 382         staffline and the secondary beam? That would get rid of the
 383         silly case analysis here (which is probably not valid when we
 384         have different beam-thicknesses.)
 385
 386         --hwn
 387        */
 388
 389
 390       // hmm, without Interval/Drul_array, you get ~ 4x same code...
 391       if (fabs (yl - ldir * beam_translation) < radius + inter)
 392         {
 393           if (ldir == UP && dy <= eps
 394               && fabs (my_modf (yl) - sit) < eps)
 395             dem += SECONDARY_BEAM_DEMERIT;
 396
 397           if (ldir == DOWN && dy >= eps
 398               && fabs (my_modf (yl) - hang) < eps)
 399             dem += SECONDARY_BEAM_DEMERIT;
 400         }
 401
 402       if (fabs (yr - rdir * beam_translation) < radius + inter)
 403         {
 404           if (rdir == UP && dy >= eps
 405               && fabs (my_modf (yr) - sit) < eps)
 406             dem += SECONDARY_BEAM_DEMERIT;
 407
 408           if (rdir == DOWN && dy <= eps
 409               && fabs (my_modf (yr) - hang) < eps)
 410             dem += SECONDARY_BEAM_DEMERIT;
 411         }
 412
 413       if (beam_count >= 3)
 414         {
 415           if (fabs (yl - 2 * ldir * beam_translation) < radius + inter)
 416             {
 417               if (ldir == UP && dy <= eps
 418                   && fabs (my_modf (yl) - straddle) < eps)
 419                 dem += SECONDARY_BEAM_DEMERIT;
 420
 421               if (ldir == DOWN && dy >= eps
 422                   && fabs (my_modf (yl) - straddle) < eps)
 423                 dem += SECONDARY_BEAM_DEMERIT;
 424             }
 425
 426           if (fabs (yr - 2 * rdir * beam_translation) < radius + inter)
 427             {
 428               if (rdir == UP && dy >= eps
 429                   && fabs (my_modf (yr) - straddle) < eps)
 430                 dem += SECONDARY_BEAM_DEMERIT;
 431
 432               if (rdir == DOWN && dy <= eps
 433                   && fabs (my_modf (yr) - straddle) < eps)
 434                 dem += SECONDARY_BEAM_DEMERIT;
 435             }
 436         }
 437     }
 438
 439   return dem;
 440 }
 441
 442