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 "directional-element-interface.hh"
  13 #include "staff-symbol-referencer.hh"
  14 #include "tie.hh"
  15
  16 #include "item.hh"
  17 #include "spanner.hh"
  18
  19 #include "stem.hh"
  20 #include "note-head.hh"
  21 #include "rhythmic-head.hh"
  22
  23 Interval
  24 Tie_formatting_problem::get_attachment (Real y) const
  25 {
  26   Interval attachments;
  27   Direction d = LEFT;
  28   do
  29     {
  30       attachments[d] = skyline_height (chord_outlines_[d], y, -d);
  31     }
  32   while (flip (&d) != LEFT);
  33
  34   return attachments;
  35 }
  36
  37 Tie_formatting_problem::Tie_formatting_problem()
  38 {
  39   x_refpoint_ = 0;
  40 }
  41
  42 Tie_formatting_problem::~Tie_formatting_problem ()
  43 {
  44   for (Tie_configuration_map::const_iterator i (possibilities_.begin ());
  45        i != possibilities_.end (); i++)
  46     delete (*i).second;
  47 }
  48
  49 void
  50 Tie_formatting_problem::set_chord_outline (Link_array<Item> bounds,
  51                                            Direction d)
  52 {
  53   Real staff_space = Staff_symbol_referencer::staff_space (bounds[0]);
  54
  55   Array<Box> boxes;
  56
  57   Grob *stem = 0;
  58   for (int i = 0; i < bounds.size (); i++)
  59     {
  60       Grob *head = bounds[i];
  61       if (!Note_head::has_interface (head))
  62         continue;
  63
  64       if (!stem)
  65         stem = unsmob_grob (head->get_object ("stem"));
  66
  67       Real p = Staff_symbol_referencer::get_position (head);
  68       Interval y ((p-1) * 0.5 * staff_space,
  69                   (p+1) * 0.5 * staff_space);
  70
  71       Interval x = head->extent (x_refpoint_, X_AXIS);
  72       boxes.push (Box (x, y));
  73
  74       Grob *dots = Rhythmic_head::get_dots (head);
  75       if (d == LEFT && dots)
  76         {
  77           Interval x = dots->extent (x_refpoint_, X_AXIS);
  78           Interval y (-0.5, 0.5);
  79           int p = int (Staff_symbol_referencer::get_position (dots));
  80           y.translate (p);
  81
  82           dot_positions_.insert (p);
  83
  84           y *= staff_space * 0.5;
  85           // boxes.push (Box (x, y));
  86         }
  87     }
  88
  89   chord_outlines_[d] = empty_skyline (-d);
  90
  91   if (bounds[0]->break_status_dir ())
  92     {
  93       Real x = robust_relative_extent (bounds[0],  x_refpoint_, X_AXIS)[-d];
  94       chord_outlines_[d].elem_ref (0).height_ = x;
  95     }
  96
  97   for (int i = 0; i < boxes.size (); i++)
  98     insert_extent_into_skyline (&chord_outlines_[d]  ,
  99                                 boxes[i], Y_AXIS, -d);
 100
 101   if (stem
 102       && !Stem::is_invisible (stem))
 103     {
 104       Interval x;
 105       x.add_point (stem->relative_coordinate (x_refpoint_, X_AXIS));
 106       x.widen (staff_space / 20); // ugh.
 107       Interval y;
 108       y.add_point (Stem::stem_end_position (stem) * staff_space * .5);
 109
 110       Direction stemdir = get_grob_direction (stem);
 111       y.add_point (Stem::head_positions (stem)[-stemdir]
 112                    * staff_space * .5);
 113
 114       insert_extent_into_skyline (&chord_outlines_[d], Box (x,y), Y_AXIS, -d);
 115
 116
 117
 118       if (d == LEFT)
 119         {
 120           Box flag_box = Stem::get_translated_flag (stem).extent_box ();
 121           flag_box.translate( Offset (x[RIGHT], X_AXIS));
 122           insert_extent_into_skyline (&chord_outlines_[d], flag_box,
 123                                       Y_AXIS, -d);
 124         }
 125     }
 126
 127   Direction updowndir = DOWN;
 128   do
 129     {
 130       Interval x ;
 131       Interval y;
 132       if (boxes.size())
 133         {
 134           Box b = boxes.boundary (updowndir, 0);
 135           x = b[X_AXIS];
 136           x[-d] =  b[X_AXIS].linear_combination (-d / 2);
 137           y[-updowndir] = b[Y_AXIS][updowndir];
 138           y[updowndir] = updowndir * infinity_f;
 139         }
 140
 141       if (!x.is_empty ())
 142         insert_extent_into_skyline (&chord_outlines_[d],
 143                                     Box (x,y),
 144                                     Y_AXIS, -d);
 145     }
 146   while (flip (&updowndir) != DOWN);
 147 }
 148
 149
 150 void
 151 Tie_formatting_problem::from_tie (Grob *tie)
 152 {
 153   Link_array<Grob> ties;
 154   ties.push (tie);
 155
 156   from_ties (ties);
 157
 158   details_.from_grob (tie);
 159 }
 160
 161 Grob *
 162 Tie_formatting_problem::common_x_refpoint () const
 163 {
 164   return x_refpoint_;
 165 }
 166
 167 void
 168 Tie_formatting_problem::from_ties (Link_array<Grob> const &ties)
 169 {
 170   if (ties.is_empty ())
 171     return;
 172
 173   x_refpoint_ = ties[0];
 174   for (int i = 0; i < ties.size (); i++)
 175     {
 176       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (LEFT)->common_refpoint (x_refpoint_, X_AXIS);
 177       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (RIGHT)->common_refpoint (x_refpoint_, X_AXIS);
 178     }
 179
 180   details_.from_grob (ties[0]);
 181
 182   Direction d = LEFT;
 183   do
 184     {
 185       Link_array<Item> bounds;
 186
 187       for (int i = 0; i < ties.size (); i++)
 188         {
 189           Item *it = dynamic_cast<Spanner*> (ties[i])->get_bound (d);
 190
 191           bounds.push (it);
 192         }
 193
 194       set_chord_outline (bounds, d);
 195     }
 196   while (flip (&d) != LEFT);
 197 }
 198
 199 void
 200 Tie_formatting_problem::from_lv_ties (Link_array<Grob> const &lv_ties)
 201 {
 202   if (lv_ties.is_empty ())
 203     return ;
 204
 205   details_.from_grob (lv_ties[0]);
 206   Link_array<Item> heads;
 207   for (int i = 0; i < lv_ties.size (); i++)
 208     {
 209       Item *head = unsmob_item (lv_ties[i]->get_object ("note-head"));
 210       if (!head)
 211         continue;
 212
 213       heads.push (head);
 214     }
 215
 216   x_refpoint_ = lv_ties [0];
 217   for (int i = 0; i < lv_ties.size (); i++)
 218     {
 219       x_refpoint_ = lv_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 220     }
 221
 222   set_chord_outline (heads, LEFT);
 223
 224   Real right_most = - infinity_f;
 225
 226   for (int i = 0; i < chord_outlines_[LEFT].size (); i++)
 227     {
 228       right_most = max (right_most, chord_outlines_[LEFT][i].height_);
 229     }
 230
 231   Skyline_entry right_entry;
 232   right_entry.width_.set_full ();
 233   right_entry.height_ = right_most + 1.5;
 234
 235   chord_outlines_[RIGHT].push (right_entry);
 236 }
 237
 238 Tie_configuration*
 239 Tie_formatting_problem::get_configuration (int pos, Direction dir)
 240 {
 241   pair<int,int> key (pos, dir);
 242   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 243
 244   if (f != possibilities_.end ())
 245     {
 246       return (*f).second;
 247     }
 248
 249
 250   Tie_configuration *conf = generate_configuration (pos,dir);
 251   possibilities_[key] = conf;
 252   return conf;
 253 }
 254
 255 Tie_configuration*
 256 Tie_formatting_problem::generate_configuration (int pos, Direction dir)
 257 {
 258   Tie_configuration *conf = new Tie_configuration;
 259   conf->position_ = pos;
 260   conf->dir_ = dir;
 261   Real y = conf->position_ * 0.5 * details_.staff_space_;
 262
 263   if (dot_positions_.find (pos) != dot_positions_.end ())
 264     {
 265       conf->delta_y_ += 0.25 * details_.staff_space_;
 266     }
 267   conf->attachment_x_ = get_attachment (y + conf->delta_y_);
 268
 269   Real h =  conf->height (details_);
 270   if (!conf->delta_y_)
 271     {
 272       if (h < 0.5 * details_.staff_space_
 273           && !Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_, pos))
 274         {
 275           conf->center_tie_vertically (details_);
 276         }
 277       else if (h < 0.5 * details_.staff_space_
 278                && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_, pos))
 279         {
 280           conf->delta_y_ += dir * 0.2 * details_.staff_space_;
 281         }
 282     }
 283
 284   conf->attachment_x_.widen ( - details_.x_gap_);
 285   return conf;
 286 }
 287
 288 Real
 289 Tie_formatting_problem::score_aptitude (Tie_configuration const &conf,
 290                                         int tie_position)
 291 {
 292   Real wrong_direction_offset_penalty_;
 293   Real distance_penalty_factor_;
 294
 295   wrong_direction_offset_penalty_ = 10;
 296   distance_penalty_factor_ = 5;
 297
 298   Real penalty = 0.0;
 299   Real curve_y = conf.position_ * details_.staff_space_ * 0.5 + conf.delta_y_;
 300   Real tie_y = tie_position * details_.staff_space_ * 0.5;
 301   if (sign (curve_y - tie_y) != conf.dir_)
 302     penalty += wrong_direction_offset_penalty_;
 303
 304   penalty += distance_penalty_factor_ * fabs (curve_y - tie_y);
 305   return penalty;
 306 }
 307
 308
 309 Real
 310 Tie_formatting_problem::score_configuration (Tie_configuration const &conf)
 311 {
 312   Real length_penalty_factor = 1.0;
 313   Real min_length = 0.333;
 314   Real staff_line_clearance = 0.1;
 315   Real staff_line_collision_penalty = 5;
 316
 317   Real penalty = 0.0;
 318   Real length = conf.attachment_x_.length ();
 319   if (length < min_length)
 320     penalty += length_penalty_factor / max (0.01, length);
 321
 322   Real tip_pos = conf.position_ + conf.delta_y_ / 0.5 * details_.staff_space_;
 323   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 324   Real height =  conf.height (details_);
 325
 326   Real top_y = tip_y + conf.dir_ * height;
 327   Real top_pos = 2 * top_y / details_.staff_space_;
 328   Real round_top_pos = rint (top_pos);
 329   if (fabs (top_pos - round_top_pos) < staff_line_clearance
 330       && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_,
 331                                                 int (round_top_pos))
 332       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 333     {
 334       penalty += staff_line_collision_penalty;
 335     }
 336
 337   if (fabs (tip_pos - rint (tip_pos)) < staff_line_clearance
 338       && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_,
 339                                                 int (rint (tip_pos))))
 340     {
 341       penalty += staff_line_collision_penalty;
 342     }
 343
 344   return penalty;
 345 }
 346
 347 Tie_configuration
 348 Tie_formatting_problem::find_optimal_tie_configuration (int pos, Direction dir)
 349 {
 350   Link_array<Tie_configuration> confs;
 351
 352   int region_size = 3;
 353   for (int i = 0; i < region_size; i ++)
 354     {
 355       confs.push (generate_configuration (pos + i * dir, dir));
 356     }
 357
 358   Array<Real> scores;
 359
 360   int best_idx = -1;
 361   Real best_score = 1e6;
 362   for (int i = 0; i < confs.size (); i ++)
 363     {
 364       Real score = 0.0;
 365       score += score_configuration (*confs[i]);
 366       score += score_aptitude (*confs[i], pos);
 367
 368       if (score < best_score)
 369         {
 370           best_score = score;
 371           best_idx = i;
 372         }
 373     }
 374
 375   Tie_configuration best = *confs[best_idx];
 376   for (int i = 0; i < confs.size (); i++)
 377     delete confs[i];
 378
 379   return best;
 380 }