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