lily/tie-formatting-problem.cc

   1 /*
   2   tie-formatting-problem.cc -- implement Tie_formatting_problem6
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2005 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7
   8 */
   9
  10 #include "tie-formatting-problem.hh"
  11
  12 #include "tie-configuration.hh"
  13 #include "directional-element-interface.hh"
  14 #include "staff-symbol-referencer.hh"
  15 #include "tie.hh"
  16 #include "item.hh"
  17 #include "spanner.hh"
  18 #include "bezier.hh"
  19 #include "stem.hh"
  20 #include "note-head.hh"
  21 #include "rhythmic-head.hh"
  22 #include "warn.hh"
  23
  24 Interval
  25 Tie_formatting_problem::get_attachment (Real y) const
  26 {
  27   Interval attachments;
  28   Direction d = LEFT;
  29   do
  30     {
  31       attachments[d] = skyline_height (chord_outlines_[d], y, -d);
  32     }
  33   while (flip (&d) != LEFT);
  34
  35   return attachments;
  36 }
  37
  38 Tie_formatting_problem::Tie_formatting_problem()
  39 {
  40   x_refpoint_ = 0;
  41 }
  42
  43 Tie_formatting_problem::~Tie_formatting_problem ()
  44 {
  45   for (Tie_configuration_map::const_iterator i (possibilities_.begin ());
  46        i != possibilities_.end (); i++)
  47     delete (*i).second;
  48 }
  49
  50 void
  51 Tie_formatting_problem::set_chord_outline (Link_array<Item> bounds,
  52                                            Direction d)
  53 {
  54   Real staff_space = Staff_symbol_referencer::staff_space (bounds[0]);
  55
  56   Array<Box> boxes;
  57
  58   Grob *stem = 0;
  59   for (int i = 0; i < bounds.size (); i++)
  60     {
  61       Grob *head = bounds[i];
  62       if (!Note_head::has_interface (head))
  63         continue;
  64
  65       if (!stem)
  66         stem = unsmob_grob (head->get_object ("stem"));
  67
  68       Real p = Staff_symbol_referencer::get_position (head);
  69       Interval y ((p-1) * 0.5 * staff_space,
  70                   (p+1) * 0.5 * staff_space);
  71
  72       Interval x = head->extent (x_refpoint_, X_AXIS);
  73       boxes.push (Box (x, y));
  74
  75       Grob *dots = Rhythmic_head::get_dots (head);
  76       if (d == LEFT && dots)
  77         {
  78           Interval x = dots->extent (x_refpoint_, X_AXIS);
  79           Interval y (-0.5, 0.5);
  80           int p = int (Staff_symbol_referencer::get_position (dots));
  81           y.translate (p);
  82
  83           dot_positions_.insert (p);
  84           dot_x_.unite (x);
  85
  86           y *= staff_space * 0.5;
  87           // boxes.push (Box (x, y));
  88         }
  89     }
  90
  91   chord_outlines_[d] = empty_skyline (-d);
  92
  93   if (bounds[0]->break_status_dir ())
  94     {
  95       Real x = robust_relative_extent (bounds[0],  x_refpoint_, X_AXIS)[-d];
  96       chord_outlines_[d].elem_ref (0).height_ = x;
  97     }
  98
  99   for (int i = 0; i < boxes.size (); i++)
 100     insert_extent_into_skyline (&chord_outlines_[d]  ,
 101                                 boxes[i], Y_AXIS, -d);
 102
 103   if (stem
 104       && !Stem::is_invisible (stem))
 105     {
 106       Interval x;
 107       x.add_point (stem->relative_coordinate (x_refpoint_, X_AXIS));
 108       x.widen (staff_space / 20); // ugh.
 109       Interval y;
 110       y.add_point (Stem::stem_end_position (stem) * staff_space * .5);
 111
 112       Direction stemdir = get_grob_direction (stem);
 113       y.add_point (Stem::head_positions (stem)[-stemdir]
 114                    * staff_space * .5);
 115
 116       insert_extent_into_skyline (&chord_outlines_[d], Box (x,y), Y_AXIS, -d);
 117
 118
 119
 120       if (d == LEFT)
 121         {
 122           Box flag_box = Stem::get_translated_flag (stem).extent_box ();
 123           flag_box.translate( Offset (x[RIGHT], X_AXIS));
 124           insert_extent_into_skyline (&chord_outlines_[d], flag_box,
 125                                       Y_AXIS, -d);
 126         }
 127     }
 128
 129   Direction updowndir = DOWN;
 130   do
 131     {
 132       Interval x ;
 133       Interval y;
 134       if (boxes.size())
 135         {
 136           Box b = boxes.boundary (updowndir, 0);
 137           x = b[X_AXIS];
 138           x[-d] =  b[X_AXIS].linear_combination (-d / 2);
 139           y[-updowndir] = b[Y_AXIS][updowndir];
 140           y[updowndir] = updowndir * infinity_f;
 141         }
 142
 143       if (!x.is_empty ())
 144         insert_extent_into_skyline (&chord_outlines_[d],
 145                                     Box (x,y),
 146                                     Y_AXIS, -d);
 147     }
 148   while (flip (&updowndir) != DOWN);
 149 }
 150
 151
 152 void
 153 Tie_formatting_problem::from_tie (Grob *tie)
 154 {
 155   Link_array<Grob> ties;
 156   ties.push (tie);
 157
 158   from_ties (ties);
 159
 160   details_.from_grob (tie);
 161 }
 162
 163 Grob *
 164 Tie_formatting_problem::common_x_refpoint () const
 165 {
 166   return x_refpoint_;
 167 }
 168
 169 void
 170 Tie_formatting_problem::from_ties (Link_array<Grob> const &ties)
 171 {
 172   if (ties.is_empty ())
 173     return;
 174
 175   x_refpoint_ = ties[0];
 176   for (int i = 0; i < ties.size (); i++)
 177     {
 178       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (LEFT)->common_refpoint (x_refpoint_, X_AXIS);
 179       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (RIGHT)->common_refpoint (x_refpoint_, X_AXIS);
 180     }
 181
 182   details_.from_grob (ties[0]);
 183
 184   Direction d = LEFT;
 185   do
 186     {
 187       Link_array<Item> bounds;
 188
 189       for (int i = 0; i < ties.size (); i++)
 190         {
 191           Item *it = dynamic_cast<Spanner*> (ties[i])->get_bound (d);
 192
 193           bounds.push (it);
 194         }
 195
 196       set_chord_outline (bounds, d);
 197     }
 198   while (flip (&d) != LEFT);
 199
 200
 201   for (int i = 0; i < ties.size (); i++)
 202     {
 203       Tie_specification spec;
 204
 205       if (scm_is_number (ties[i]->get_property_data (ly_symbol2scm ("direction"))))
 206         {
 207           spec.manual_dir_ = to_dir (ties[i]->get_property ("direction"));
 208           spec.has_manual_dir_ = true;
 209         }
 210
 211       spec.position_ = Tie::get_position (ties[i]);
 212
 213       specifications_.push (spec);
 214     }
 215 }
 216
 217 void
 218 Tie_formatting_problem::from_lv_ties (Link_array<Grob> const &lv_ties)
 219 {
 220   if (lv_ties.is_empty ())
 221     return ;
 222
 223   details_.from_grob (lv_ties[0]);
 224   Link_array<Item> heads;
 225
 226   for (int i = 0; i < lv_ties.size (); i++)
 227     {
 228       Tie_specification spec;
 229       Item *head = unsmob_item (lv_ties[i]->get_object ("note-head"));
 230
 231       if (!head)
 232         programming_error ("LV tie without head?!");
 233
 234       if (head)
 235         {
 236           spec.position_ = int (Staff_symbol_referencer::get_position (head));
 237         }
 238
 239       heads.push (head);
 240     }
 241
 242   x_refpoint_ = lv_ties [0];
 243   for (int i = 0; i < lv_ties.size (); i++)
 244     {
 245       x_refpoint_ = lv_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 246     }
 247
 248   set_chord_outline (heads, LEFT);
 249
 250   Real right_most = - infinity_f;
 251
 252   for (int i = 0; i < chord_outlines_[LEFT].size (); i++)
 253     {
 254       right_most = max (right_most, chord_outlines_[LEFT][i].height_);
 255     }
 256
 257   Skyline_entry right_entry;
 258   right_entry.width_.set_full ();
 259   right_entry.height_ = right_most + 1.5;
 260
 261   chord_outlines_[RIGHT].push (right_entry);
 262 }
 263
 264 Tie_configuration*
 265 Tie_formatting_problem::get_configuration (int pos, Direction dir)
 266 {
 267   pair<int,int> key (pos, dir);
 268   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 269
 270   if (f != possibilities_.end ())
 271     {
 272       return (*f).second;
 273     }
 274
 275
 276   Tie_configuration *conf = generate_configuration (pos,dir);
 277   possibilities_[key] = conf;
 278   return conf;
 279 }
 280
 281 Tie_configuration*
 282 Tie_formatting_problem::generate_configuration (int pos, Direction dir) const
 283 {
 284   Tie_configuration *conf = new Tie_configuration;
 285   conf->position_ = pos;
 286   conf->dir_ = dir;
 287   Real y = conf->position_ * 0.5 * details_.staff_space_;
 288
 289   if (dot_positions_.find (pos) != dot_positions_.end ())
 290     {
 291       conf->delta_y_ += 0.25 * details_.staff_space_;
 292     }
 293
 294   conf->attachment_x_ = get_attachment (y + conf->delta_y_);
 295
 296   Real h =  conf->height (details_);
 297   if (!conf->delta_y_)
 298     {
 299       if (h < 0.5 * details_.staff_space_
 300           && !Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_, pos))
 301         {
 302           conf->center_tie_vertically (details_);
 303         }
 304       else if (h < 0.5 * details_.staff_space_
 305                && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_, pos))
 306         {
 307           conf->delta_y_ += dir * 0.2 * details_.staff_space_;
 308         }
 309     }
 310
 311   conf->attachment_x_.widen ( - details_.x_gap_);
 312   return conf;
 313 }
 314
 315 Real
 316 Tie_formatting_problem::score_aptitude (Tie_configuration const &conf,
 317                                         int tie_position) const
 318 {
 319   Real wrong_direction_offset_penalty_;
 320   Real distance_penalty_factor_;
 321
 322   wrong_direction_offset_penalty_ = 10;
 323   distance_penalty_factor_ = 5;
 324
 325   Real penalty = 0.0;
 326   Real curve_y = conf.position_ * details_.staff_space_ * 0.5 + conf.delta_y_;
 327   Real tie_y = tie_position * details_.staff_space_ * 0.5;
 328   if (sign (curve_y - tie_y) != conf.dir_)
 329     penalty += wrong_direction_offset_penalty_;
 330
 331   penalty += distance_penalty_factor_ * fabs (curve_y - tie_y);
 332   return penalty;
 333 }
 334
 335
 336 Real
 337 Tie_formatting_problem::score_configuration (Tie_configuration const &conf) const
 338 {
 339   Real length_penalty_factor = 1.0;
 340   Real min_length = 0.333;
 341   Real staff_line_clearance = 0.1;
 342   Real staff_line_collision_penalty = 5;
 343   Real dot_collision_clearance = 0.25;
 344   Real dot_collision_penalty = 10;
 345
 346
 347   Real penalty = 0.0;
 348   Real length = conf.attachment_x_.length ();
 349   if (length < min_length)
 350     penalty += length_penalty_factor / max (0.01, length);
 351
 352   Real tip_pos = conf.position_ + conf.delta_y_ / 0.5 * details_.staff_space_;
 353   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 354   Real height =  conf.height (details_);
 355
 356   Real top_y = tip_y + conf.dir_ * height;
 357   Real top_pos = 2 * top_y / details_.staff_space_;
 358   Real round_top_pos = rint (top_pos);
 359   if (fabs (top_pos - round_top_pos) < staff_line_clearance
 360       && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_,
 361                                                 int (round_top_pos))
 362       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 363     {
 364       penalty += staff_line_collision_penalty;
 365     }
 366
 367   if (fabs (tip_pos - rint (tip_pos)) < staff_line_clearance
 368       && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_,
 369                                                 int (rint (tip_pos))))
 370     {
 371       penalty += staff_line_collision_penalty;
 372     }
 373
 374   if (!dot_x_.is_empty ())
 375     {
 376       /* use left edge? */
 377       Real x = dot_x_.center ();
 378
 379       Bezier b = conf.get_transformed_bezier (details_);
 380       if (b.control_point_extent (X_AXIS).contains (x))
 381         {
 382           Real y = b.get_other_coordinate (X_AXIS, x);
 383
 384           for (set<int>::const_iterator i (dot_positions_.begin ());
 385                i != dot_positions_.end (); i ++)
 386             {
 387               int dot_pos = (*i);
 388               if (fabs (dot_pos * details_.staff_space_ * 0.5 - y) < dot_collision_clearance)
 389                 {
 390                   penalty += dot_collision_penalty;
 391                 }
 392             }
 393         }
 394     }
 395
 396   return penalty;
 397 }
 398
 399 Tie_configuration
 400 Tie_formatting_problem::find_optimal_tie_configuration (int pos, Direction dir) const
 401 {
 402   Link_array<Tie_configuration> confs;
 403
 404   int region_size = 3;
 405   for (int i = 0; i < region_size; i ++)
 406     {
 407       confs.push (generate_configuration (pos + i * dir, dir));
 408     }
 409
 410   Array<Real> scores;
 411
 412   int best_idx = -1;
 413   Real best_score = 1e6;
 414   for (int i = 0; i < confs.size (); i ++)
 415     {
 416       Real score = 0.0;
 417       score += score_configuration (*confs[i]);
 418       score += score_aptitude (*confs[i], pos);
 419
 420       if (score < best_score)
 421         {
 422           best_score = score;
 423           best_idx = i;
 424         }
 425     }
 426
 427   Tie_configuration best = *confs[best_idx];
 428   for (int i = 0; i < confs.size (); i++)
 429     delete confs[i];
 430
 431   return best;
 432 }
 433
 434 Tie_specification::Tie_specification ()
 435 {
 436   has_manual_position_ = false;
 437   has_manual_dir_ = false;
 438   position_ = 0;
 439   manual_position_ = 0;
 440   manual_dir_ = CENTER;
 441 }
 442
 443
 444 Real
 445 Tie_formatting_problem::score_ties_aptitude (Ties_configuration const &ties) const
 446 {
 447   Real score = 0.0;
 448   if  (ties.size () != specifications_.size ())
 449     {
 450       programming_error ("Huh? Mismatch between sizes.");
 451       return infinity_f;
 452     }
 453
 454   for (int i = 0; i < ties.size (); i++)
 455     score += score_aptitude (ties[i], specifications_[i].position_);
 456
 457   return score;
 458 }
 459
 460 Real
 461 Tie_formatting_problem::score_ties (Ties_configuration const &ties) const
 462 {
 463   return score_ties_configuration (ties)
 464     + score_ties_aptitude (ties);
 465 }
 466
 467 Real
 468 Tie_formatting_problem::score_ties_configuration (Ties_configuration const &ties) const
 469 {
 470   const Real tie_monotonicity_penalty = 100;
 471   const Real tie_collision_penalty = 30;
 472   const Real tie_collision_distance = 0.25;
 473
 474   Real score = 0.0;
 475   for (int i = 0; i < ties.size (); i++)
 476     {
 477       score += score_configuration (ties[i]);
 478     }
 479
 480
 481   Real last_edge = 0.0;
 482   Real last_center = 0.0;
 483   for (int i = 0; i < ties.size (); i++)
 484     {
 485       Bezier b (ties[i].get_transformed_bezier (details_));
 486
 487       Real center = b.curve_point (0.5)[Y_AXIS];
 488       Real edge = b.curve_point (0.0)[Y_AXIS];
 489
 490       if (i)
 491         {
 492           if (edge <= last_edge)
 493             score += tie_monotonicity_penalty;
 494           if (center <= last_center)
 495             score += tie_monotonicity_penalty;
 496
 497           score +=
 498             tie_collision_penalty
 499             * max (tie_collision_distance - fabs (center - last_center), 0.0) / tie_collision_distance;
 500           score +=
 501             tie_collision_penalty
 502             * max (tie_collision_distance - fabs (edge - last_edge), 0.0) / tie_collision_distance;
 503         }
 504
 505       last_edge = edge;
 506       last_center = center;
 507     }
 508
 509   return score;
 510 }
 511
 512 /*
 513   Generate with correct X-attachments and beziers, copying delta_y_
 514   from TIES_CONFIG if necessary.
 515 */
 516 Ties_configuration
 517 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
 518 {
 519   Ties_configuration copy;
 520   for (int i = 0; i < ties_config.size (); i++)
 521     {
 522       Tie_configuration * ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_);
 523       if (specifications_[i].has_manual_position_)
 524         {
 525           ptr->delta_y_
 526             = (specifications_[i].manual_position_ - ties_config[i].position_)
 527             * 0.5 * details_.staff_space_;
 528         }
 529       copy.push (*ptr);
 530     }
 531
 532   return copy;
 533 }
 534
 535 Ties_configuration
 536 Tie_formatting_problem::generate_base_chord_configuration ()
 537 {
 538   Ties_configuration ties_config;
 539   for (int i = 0;  i < specifications_.size (); i ++)
 540     {
 541       Tie_configuration conf;
 542       if (specifications_[i].has_manual_dir_)
 543         conf.dir_ = specifications_[i].manual_dir_;
 544       if (specifications_[i].has_manual_position_)
 545         {
 546           conf.position_ = (int) round (specifications_[i].manual_position_);
 547           conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
 548             * 0.5 * details_.staff_space_;
 549         }
 550       else
 551         conf.position_ = specifications_[i].position_;
 552
 553       ties_config.push (conf);
 554     }
 555
 556   set_ties_config_standard_directions (&ties_config);
 557
 558   ties_config = generate_ties_configuration (ties_config);
 559
 560   return ties_config;
 561 }
 562
 563 Ties_configuration
 564 Tie_formatting_problem::generate_optimal_chord_configuration ()
 565 {
 566   Ties_configuration base = generate_base_chord_configuration ();
 567   Array<Tie_configuration_variation> vars = get_variations (base);
 568
 569   Ties_configuration best = base;
 570   Real best_score = score_ties_configuration (best);
 571
 572   /*
 573     This simply is 1-opt: we have K substitions, and we try applying
 574     exactly every one for each.
 575   */
 576   for (int i = 0; i < vars.size (); i++)
 577     {
 578       Ties_configuration variant = base;
 579       variant[vars[i].index_] = *vars[i].suggestion_;
 580
 581       Real score = (score_ties_configuration (variant)
 582                     + score_ties_aptitude (variant));
 583       if (score < best_score)
 584         {
 585           best = variant;
 586           best_score = score;
 587         }
 588     }
 589
 590   return best;
 591 }
 592
 593 void
 594 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
 595 {
 596   if (!tie_configs->elem (0).dir_)
 597     tie_configs->elem_ref (0).dir_ = DOWN;
 598   if (!tie_configs->top().dir_)
 599     tie_configs->top().dir_ = UP;
 600
 601   /*
 602     Seconds
 603    */
 604   for (int i = 1; i < tie_configs->size (); i++)
 605     {
 606       Real diff = (tie_configs->elem (i-1).position_
 607                    - tie_configs->elem (i).position_);
 608
 609       if (fabs (diff) <= 1)
 610         {
 611           if (!tie_configs->elem (i-1).dir_)
 612             tie_configs->elem_ref (i-1).dir_ = DOWN;
 613           if (!tie_configs->elem (i).dir_)
 614             tie_configs->elem_ref (i).dir_ = UP;
 615         }
 616     }
 617
 618   for (int i = 1; i < tie_configs->size() - 1; i++)
 619     {
 620       Tie_configuration &conf = tie_configs->elem_ref (i);
 621       if (conf.dir_)
 622         continue;
 623
 624       Direction position_dir =
 625         Direction (sign (conf.position_));
 626       if (!position_dir)
 627         position_dir = DOWN;
 628
 629       conf.dir_ = position_dir;
 630     }
 631 }
 632
 633 Tie_configuration_variation::Tie_configuration_variation ()
 634 {
 635   index_ = 0;
 636   suggestion_ = 0;
 637 }
 638
 639 Array<Tie_configuration_variation>
 640 Tie_formatting_problem::get_variations (Ties_configuration const &ties)
 641 {
 642   Real center_distance_tolerance = 0.25;
 643
 644   Array<Tie_configuration_variation> vars;
 645   Real last_center = 0.0;
 646   for (int i = 0; i < ties.size (); i++)
 647     {
 648       Bezier b (ties[i].get_transformed_bezier (details_));
 649
 650       Real center = b.curve_point (0.5)[Y_AXIS];
 651
 652       if (i)
 653         {
 654           if (center <= last_center + center_distance_tolerance)
 655             {
 656               if (!specifications_[i].has_manual_dir_)
 657                 {
 658                   Tie_configuration_variation var;
 659                   var.index_ = i;
 660                   var.suggestion_ = get_configuration (ties[i].position_,
 661                                                        -ties[i].dir_);
 662
 663                   vars.push (var);
 664                 }
 665
 666               if (!specifications_[i-1].has_manual_dir_)
 667                 {
 668                   Tie_configuration_variation var;
 669                   var.index_ = i-1;
 670                   var.suggestion_ = get_configuration (ties[i-1].position_,
 671                                                        -ties[i-1].dir_);
 672
 673                   vars.push (var);
 674                 }
 675             }
 676         }
 677
 678       last_center = center;
 679     }
 680
 681   return vars;
 682
 683 }
 684
 685 void
 686 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
 687 {
 688   int k = 0;
 689   for (SCM s = manual_configs;
 690        scm_is_pair (s) && k < specifications_.size(); s = scm_cdr (s))
 691     {
 692       SCM entry = scm_car (s);
 693       if (!scm_is_pair (entry))
 694         continue;
 695
 696       Tie_specification &spec = specifications_[k];
 697
 698       if (scm_is_number (scm_cdr (entry)))
 699         {
 700           spec.has_manual_dir_ = true;
 701           spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry)));
 702         }
 703       if (scm_is_number (scm_car (entry)))
 704         {
 705           spec.has_manual_position_ = true;
 706           spec.manual_position_ = scm_to_double (scm_car (entry));
 707         }
 708
 709       k ++;
 710     }
 711 }
 712