lily/tie-formatting-problem.cc

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