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   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   //  ; /* silly gdb thinks best_idx is inside for loop. */
 226   for (int i = qscores.size (); i--;)
 227     if (qscores[i].demerits < reasonable_score)
 228       {
 229         qscores[i].demerits
 230           += score_stem_lengths (stems, stem_infos,
 231                                  base_lengths, stem_xposns,
 232                                  xl, xr,
 233                                  knee_b,
 234                                  qscores[i].yl, qscores[i].yr);
 235       }
 236
 237   //  ; /* silly gdb thinks best_idx is inside for loop. */
 238   int best_idx = best_quant_score_idx (qscores);
 239   me->set_grob_property ("positions",
 240                          gh_cons (gh_double2scm (qscores[best_idx].yl),
 241                                   gh_double2scm (qscores[best_idx].yr))
 242                          );
 243
 244 #if DEBUG_QUANTING
 245
 246   // debug quanting
 247   me->set_grob_property ("quant-score",
 248                          gh_double2scm (qscores[best_idx].demerits));
 249   me->set_grob_property ("best-idx", scm_int2num (best_idx));
 250 #endif
 251
 252   return SCM_UNSPECIFIED;
 253 }
 254
 255 Real
 256 Beam::score_stem_lengths (Link_array<Grob> const &stems,
 257                           Array<Stem_info> const &stem_infos,
 258                           Array<Real> const &base_stem_ys,
 259                           Array<Real> const &stem_xs,
 260                           Real xl, Real xr,
 261                           bool knee,
 262                           Real yl, Real yr)
 263 {
 264   Real limit_penalty = STEM_LENGTH_LIMIT_PENALTY;
 265   Drul_array<Real> score (0, 0);
 266   Drul_array<int> count (0, 0);
 267
 268   for (int i=0; i < stems.size (); i++)
 269     {
 270       Grob* s = stems[i];
 271       if (Stem::invisible_b (s))
 272         continue;
 273
 274       Real x = stem_xs[i];
 275       Real dx = xr-xl;
 276       Real beam_y = dx ? yr *(x - xl)/dx + yl * ( xr - x)/dx : (yr + yl)/2;
 277       Real current_y = beam_y + base_stem_ys[i];
 278       Real length_pen = STEM_LENGTH_DEMERIT_FACTOR;
 279
 280       Stem_info info = stem_infos[i];
 281       Direction d = info.dir_;
 282
 283       score[d] += limit_penalty * (0 >? (d * (info.shortest_y_ - current_y)));
 284
 285       Real ideal_diff = d * (current_y - info.ideal_y_);
 286       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
 287
 288       /* We introduce a power, to make the scoring strictly
 289          convex. Otherwise a symmetric knee beam (up/down/up/down)
 290          does not have an optimum in the middle. */
 291       if (knee)
 292         ideal_score = pow (ideal_score, 1.1);
 293
 294       score[d] += length_pen * ideal_score;
 295
 296       count[d] ++;
 297     }
 298
 299   Direction d = DOWN;
 300   do
 301     {
 302       score[d] /= (count[d] >? 1);
 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