lily/slur-configuration.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2004--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "slur-configuration.hh"
  21
  22 #include "item.hh"
  23 #include "libc-extension.hh"
  24 #include "misc.hh"
  25 #include "pointer-group-interface.hh"
  26 #include "slur-scoring.hh"
  27 #include "slur.hh"
  28 #include "spanner.hh"
  29 #include "staff-symbol-referencer.hh"
  30 #include "stem.hh"
  31 #include "warn.hh"
  32
  33 Bezier
  34 avoid_staff_line (Slur_score_state const &state,
  35                   Bezier bez)
  36 {
  37   Offset horiz (1, 0);
  38   vector<Real> ts = bez.solve_derivative (horiz);
  39
  40   /* TODO: handle case of broken slur.  */
  41   if (!ts.empty ()
  42       && (state.extremes_[LEFT].staff_ == state.extremes_[RIGHT].staff_)
  43       && state.extremes_[LEFT].staff_ && state.extremes_[RIGHT].staff_)
  44     {
  45       Real y = bez.curve_point (ts[0])[Y_AXIS];
  46
  47       Grob *staff = state.extremes_[LEFT].staff_;
  48
  49       Real p = 2 * (y - staff->relative_coordinate (state.common_[Y_AXIS], Y_AXIS))
  50                / state.staff_space_;
  51
  52       Real distance = fabs (my_round (p) - p);  //  in halfspaces
  53       if (distance < 4 * state.thickness_
  54           && (int) fabs (my_round (p))
  55           <= 2 * Staff_symbol_referencer::staff_radius (staff) + 0.1
  56           && (int (fabs (my_round (p))) % 2
  57               != Staff_symbol_referencer::line_count (staff) % 2))
  58         {
  59           Direction resolution_dir
  60             = (distance ? state.dir_ : Direction (sign (p - my_round (p))));
  61
  62           // TODO: parameter
  63           Real newp = my_round (p) + resolution_dir
  64                       * 5 * state.thickness_;
  65
  66           Real dy = (newp - p) * state.staff_space_ / 2.0;
  67
  68           bez.control_[1][Y_AXIS] += dy;
  69           bez.control_[2][Y_AXIS] += dy;
  70         }
  71     }
  72   return bez;
  73 }
  74
  75 Real
  76 fit_factor (Offset dz_unit, Offset dz_perp, Real close_to_edge_length,
  77             Bezier curve, Direction d, vector<Offset> const &avoid)
  78 {
  79   Real fit_factor = 0.0;
  80   Offset x0 = curve.control_[0];
  81   curve.translate (-x0);
  82   curve.rotate (-dz_unit.arg ());
  83   curve.scale (1, d);
  84
  85   Interval curve_xext;
  86   curve_xext.add_point (curve.control_[0][X_AXIS]);
  87   curve_xext.add_point (curve.control_[3][X_AXIS]);
  88
  89   for (vsize i = 0; i < avoid.size (); i++)
  90     {
  91       Offset z = (avoid[i] - x0);
  92       Offset p (dot_product (z, dz_unit),
  93                 d * dot_product (z, dz_perp));
  94
  95       bool close_to_edge = false;
  96       Direction d = LEFT;
  97       do
  98         close_to_edge = close_to_edge || -d * (p[X_AXIS] - curve_xext[d]) < close_to_edge_length;
  99       while (flip (&d) != LEFT);
 100
 101       if (close_to_edge)
 102         continue;
 103
 104       Real eps = 0.01;
 105       Interval pext = eps * Interval (-1, 1) + p[X_AXIS];
 106       pext.intersect (curve_xext);
 107
 108       if (pext.is_empty () || pext.length () <= 1.999 * eps)
 109         continue;
 110
 111       Real y = curve.get_other_coordinate (X_AXIS, p[X_AXIS]);
 112       if (y)
 113         fit_factor = max (fit_factor, (p[Y_AXIS] / y));
 114     }
 115   return fit_factor;
 116 }
 117
 118 void
 119 Slur_configuration::generate_curve (Slur_score_state const &state,
 120                                     Real r_0, Real h_inf,
 121                                     vector<Offset> const &avoid)
 122 {
 123   Offset dz = attachment_[RIGHT] - attachment_[LEFT];;
 124   Offset dz_unit = dz;
 125   dz_unit *= 1 / dz.length ();
 126   Offset dz_perp = dz_unit * Offset (0, 1);
 127
 128   Real indent, height;
 129   get_slur_indent_height (&indent, &height, dz.length (), h_inf, r_0);
 130
 131   Real len = dz.length ();
 132
 133   /* This condition,
 134
 135   len^2 > 4h^2 +  3 (i + 1/3len)^2  - 1/3 len^2
 136
 137   is equivalent to:
 138
 139   |bez' (0)| < | bez' (.5)|
 140
 141   when (control2 - control1) has the same direction as
 142   (control3 - control0).  */
 143
 144   Real max_indent = len / 3.1;
 145   indent = min (indent, max_indent);
 146
 147   Real a1 = sqr (len) / 3.0;
 148   Real a2 = 0.75 * sqr (indent + len / 3.0);
 149   Real max_h = a1 - a2;
 150
 151   if (max_h < 0)
 152     {
 153       programming_error ("slur indent too small");
 154       max_h = len / 3.0;
 155     }
 156   else
 157     max_h = sqrt (max_h);
 158
 159   Real eccentricity = robust_scm2double (state.slur_->get_property ("eccentricity"), 0);
 160
 161   Real x1 = (eccentricity + indent);
 162   Real x2 = (eccentricity - indent);
 163
 164   Bezier curve;
 165   curve.control_[0] = attachment_[LEFT];
 166   curve.control_[1] = attachment_[LEFT] + dz_perp * height * state.dir_
 167                       + dz_unit * x1;
 168   curve.control_[2] = attachment_[RIGHT] + dz_perp * height * state.dir_
 169                       + dz_unit * x2;
 170   curve.control_[3] = attachment_[RIGHT];
 171
 172   Real ff = fit_factor (dz_unit, dz_perp, state.parameters_.close_to_edge_length_,
 173                         curve, state.dir_, avoid);
 174
 175   height = max (height, min (height * ff, max_h));
 176
 177   curve.control_[0] = attachment_[LEFT];
 178   curve.control_[1] = attachment_[LEFT] + dz_perp * height * state.dir_
 179                       + dz_unit * x1;
 180   curve.control_[2] = attachment_[RIGHT] + dz_perp * height * state.dir_
 181                       + dz_unit * x2;
 182   curve.control_[3] = attachment_[RIGHT];
 183
 184   curve_ = avoid_staff_line (state, curve);
 185   height_ = height;
 186 }
 187
 188 Slur_configuration::Slur_configuration ()
 189 {
 190   score_ = 0.0;
 191   index_ = -1;
 192 };
 193
 194 void
 195 Slur_configuration::add_score (Real s, string desc)
 196 {
 197   if (s < 0)
 198     {
 199       programming_error ("Negative demerits found for slur. Ignoring");
 200       s = 0.0;
 201     }
 202
 203   if (s)
 204     {
 205       if (score_card_.length () > 0)
 206         score_card_ += ", ";
 207       score_card_ += to_string ("%s=%.2f", desc.c_str (), s);
 208       score_ += s;
 209     }
 210 }
 211
 212 void
 213 Slur_configuration::score_encompass (Slur_score_state const &state)
 214 {
 215   Bezier const &bez (curve_);
 216   Real demerit = 0.0;
 217
 218   /*
 219     Distances for heads that are between slur and line between
 220     attachment points.
 221   */
 222   vector<Real> convex_head_distances;
 223   for (vsize j = 0; j < state.encompass_infos_.size (); j++)
 224     {
 225       Real x = state.encompass_infos_[j].x_;
 226
 227       bool l_edge = j == 0;
 228       bool r_edge = j == state.encompass_infos_.size () - 1;
 229       bool edge = l_edge || r_edge;
 230
 231       if (! (x < attachment_[RIGHT][X_AXIS]
 232              && x > attachment_[LEFT][X_AXIS]))
 233         continue;
 234
 235       Real y = bez.get_other_coordinate (X_AXIS, x);
 236       if (!edge)
 237         {
 238           Real head_dy = (y - state.encompass_infos_[j].head_);
 239           if (state.dir_ * head_dy < 0)
 240             {
 241               demerit += state.parameters_.head_encompass_penalty_;
 242               convex_head_distances.push_back (0.0);
 243             }
 244           else
 245             {
 246               Real hd = (head_dy)
 247                         ? (1 / fabs (head_dy) - 1 / state.parameters_.free_head_distance_)
 248                         : state.parameters_.head_encompass_penalty_;
 249               hd = min (max (hd, 0.0), state.parameters_.head_encompass_penalty_);
 250
 251               demerit += hd;
 252             }
 253
 254           Real line_y = linear_interpolate (x,
 255                                             attachment_[RIGHT][X_AXIS],
 256                                             attachment_[LEFT][X_AXIS],
 257                                             attachment_[RIGHT][Y_AXIS],
 258                                             attachment_[LEFT][Y_AXIS]);
 259
 260           if (1) // state.dir_ * state.encompass_infos_[j].get_point (state.dir_) > state.dir_ *line_y )
 261             {
 262
 263               Real closest
 264                 = state.dir_ * max (state.dir_ * state.encompass_infos_[j].get_point (state.dir_), state.dir_ * line_y);
 265               Real d = fabs (closest - y);
 266
 267               convex_head_distances.push_back (d);
 268             }
 269         }
 270
 271       if (state.dir_ * (y - state.encompass_infos_[j].stem_) < 0)
 272         {
 273           Real stem_dem = state.parameters_.stem_encompass_penalty_;
 274           if ((l_edge && state.dir_ == UP)
 275               || (r_edge && state.dir_ == DOWN))
 276             stem_dem /= 5;
 277
 278           demerit += stem_dem;
 279         }
 280     }
 281   add_score (demerit, "encompass");
 282
 283   if (convex_head_distances.size ())
 284     {
 285       Real avg_distance = 0.0;
 286       Real min_dist = infinity_f;
 287       for (vsize j = 0; j < convex_head_distances.size (); j++)
 288         {
 289           min_dist = min (min_dist, convex_head_distances[j]);
 290           avg_distance += convex_head_distances[j];
 291         }
 292
 293       /*
 294         For slurs over 3 or 4 heads, the average distance is not a
 295         good normalizer.
 296       */
 297       Real n = convex_head_distances.size ();
 298       if (n <= 2)
 299         {
 300           Real fact = 1.0;
 301           avg_distance += height_ * fact;
 302           n += fact;
 303         }
 304
 305       /*
 306         TODO: maybe it's better to use (avgdist - mindist)*factor
 307         as penalty.
 308       */
 309       avg_distance /= n;
 310       Real variance_penalty = state.parameters_.head_slur_distance_max_ratio_;
 311       if (min_dist > 0.0)
 312         variance_penalty
 313           = min ((avg_distance / (min_dist + state.parameters_.absolute_closeness_measure_) - 1.0), variance_penalty);
 314
 315       variance_penalty = max (variance_penalty, 0.0);
 316       variance_penalty *= state.parameters_.head_slur_distance_factor_;
 317
 318       add_score (variance_penalty, "variance");
 319     }
 320 }
 321
 322 void
 323 Slur_configuration::score_extra_encompass (Slur_score_state const &state)
 324 {
 325   for (vsize j = 0; j < state.extra_encompass_infos_.size (); j++)
 326     {
 327       Drul_array<Offset> attachment = attachment_;
 328       Extra_collision_info const &info (state.extra_encompass_infos_[j]);
 329
 330       Interval slur_wid (attachment[LEFT][X_AXIS], attachment[RIGHT][X_AXIS]);
 331
 332       /*
 333         to prevent numerical inaccuracies in
 334         Bezier::get_other_coordinate ().
 335       */
 336       Direction d = LEFT;
 337       bool found = false;
 338       Real y = 0.0;
 339
 340       do
 341         {
 342           /*
 343             We need to check for the bound explicitly, since the
 344             slur-ending can be almost vertical, making the Y
 345             coordinate a bad approximation of the object-slur
 346             distance.
 347           */
 348           Item *as_item = dynamic_cast<Item *> (state.extra_encompass_infos_[j].grob_);
 349           if (!as_item)
 350             continue;
 351
 352           Interval item_x = as_item->extent (state.common_[X_AXIS], X_AXIS);
 353           item_x.intersect (state.extremes_[d].slur_head_x_extent_);
 354           if (!item_x.is_empty ())
 355             {
 356               y = attachment[d][Y_AXIS];
 357               found = true;
 358             }
 359
 360         }
 361       while (flip (&d) != LEFT);
 362
 363       if (!found)
 364         {
 365           Real x = info.extents_[X_AXIS].linear_combination (info.idx_);
 366
 367           if (!slur_wid.contains (x))
 368             continue;
 369
 370           y = curve_.get_other_coordinate (X_AXIS, x);
 371         }
 372
 373       Real dist = 0.0;
 374       if (info.type_ == ly_symbol2scm ("around"))
 375         dist = info.extents_[Y_AXIS].distance (y);
 376
 377       /*
 378         Have to score too: the curve enumeration is limited in its
 379         shape, and may produce curves which collide anyway.
 380        */
 381       else if (info.type_ == ly_symbol2scm ("inside"))
 382         dist = state.dir_ * (y - info.extents_[Y_AXIS][state.dir_]);
 383       else
 384         programming_error ("unknown avoidance type");
 385
 386       dist = max (dist, 0.0);
 387
 388       Real penalty = info.penalty_ * peak_around (0.1 * state.parameters_.extra_encompass_free_distance_,
 389                                                   state.parameters_.extra_encompass_free_distance_,
 390                                                   dist);
 391
 392       add_score (penalty, "extra");
 393     }
 394 }
 395
 396 void
 397 Slur_configuration::score_edges (Slur_score_state const &state)
 398 {
 399   Direction d = LEFT;
 400   Offset dz = attachment_[RIGHT]
 401               - attachment_[LEFT];
 402   Real slope = dz[Y_AXIS] / dz[X_AXIS];
 403   do
 404     {
 405       Real y = attachment_[d][Y_AXIS];
 406       Real dy = fabs (y - state.base_attachments_[d][Y_AXIS]);
 407
 408       Real factor = state.parameters_.edge_attraction_factor_;
 409       Real demerit = factor * dy;
 410       if (state.extremes_[d].stem_
 411           && state.extremes_[d].stem_dir_ == state.dir_
 412           // TODO - Stem::get_beaming() should be precomputed.
 413           && !Stem::get_beaming (state.extremes_[d].stem_, -d))
 414         demerit /= 5;
 415
 416       demerit *= exp (state.dir_ * d * slope
 417                       * state.parameters_.edge_slope_exponent_);
 418
 419       string dir_str = d == LEFT ? "L" : "R";
 420       add_score (demerit, dir_str + " edge");
 421     }
 422   while (flip (&d) != LEFT);
 423 }
 424
 425 void
 426 Slur_configuration::score_slopes (Slur_score_state const &state)
 427 {
 428   Real dy = state.musical_dy_;
 429   Offset slur_dz = attachment_[RIGHT] - attachment_[LEFT];
 430   Real slur_dy = slur_dz[Y_AXIS];
 431   Real demerit = 0.0;
 432
 433   demerit += max ((fabs (slur_dy / slur_dz[X_AXIS])
 434                    - state.parameters_.max_slope_), 0.0)
 435              * state.parameters_.max_slope_factor_;
 436
 437   /* 0.2: account for staffline offset. */
 438   Real max_dy = (fabs (dy) + 0.2);
 439   if (state.edge_has_beams_)
 440     max_dy += 1.0;
 441
 442   if (!state.is_broken_)
 443     demerit += state.parameters_.steeper_slope_factor_
 444                * (max (fabs (slur_dy) - max_dy, 0.0));
 445
 446   demerit += max ((fabs (slur_dy / slur_dz[X_AXIS])
 447                    - state.parameters_.max_slope_), 0.0)
 448              * state.parameters_.max_slope_factor_;
 449
 450   if (sign (dy) == 0
 451       && sign (slur_dy) != 0
 452       && !state.is_broken_)
 453     demerit += state.parameters_.non_horizontal_penalty_;
 454
 455   if (sign (dy)
 456       && !state.is_broken_
 457       && sign (slur_dy)
 458       && sign (slur_dy) != sign (dy))
 459     demerit += state.edge_has_beams_
 460                ? state.parameters_.same_slope_penalty_ / 10
 461                : state.parameters_.same_slope_penalty_;
 462
 463   add_score (demerit, "slope");
 464 }
 465
 466 // This is a temporary hack to see how much we can gain by using a
 467 // priority queue on the beams to score.
 468 static int score_count = 0;
 469 LY_DEFINE (ly_slur_score_count, "ly:slur-score-count", 0, 0, 0,
 470            (),
 471            "count number of slur scores.")
 472 {
 473   return scm_from_int (score_count);
 474 }
 475
 476 void
 477 Slur_configuration::run_next_scorer (Slur_score_state const &state)
 478 {
 479   switch (next_scorer_todo)
 480     {
 481     case EXTRA_ENCOMPASS:
 482       score_extra_encompass (state);
 483       break;
 484     case SLOPE:
 485       score_slopes (state);
 486       break;
 487     case EDGES:
 488       score_edges (state);
 489       break;
 490     case ENCOMPASS:
 491       score_encompass (state);
 492       break;
 493     default:
 494       assert (false);
 495     }
 496   next_scorer_todo++;
 497   score_count++;
 498 }
 499
 500 bool
 501 Slur_configuration::done () const
 502 {
 503   return next_scorer_todo >= NUM_SCORERS;
 504 }
 505
 506 Slur_configuration *
 507 Slur_configuration::new_config (Drul_array<Offset> const &offs, int idx)
 508 {
 509   Slur_configuration *conf = new Slur_configuration;
 510   conf->attachment_ = offs;
 511   conf->index_ = idx;
 512   conf->next_scorer_todo = INITIAL_SCORE + 1;
 513   return conf;
 514 }