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 #include "bezier.hh"
  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           dot_x_.unite (x);
  84
  85           y *= staff_space * 0.5;
  86           // boxes.push (Box (x, y));
  87         }
  88     }
  89
  90   chord_outlines_[d] = empty_skyline (-d);
  91
  92   if (bounds[0]->break_status_dir ())
  93     {
  94       Real x = robust_relative_extent (bounds[0],  x_refpoint_, X_AXIS)[-d];
  95       chord_outlines_[d].elem_ref (0).height_ = x;
  96     }
  97
  98   for (int i = 0; i < boxes.size (); i++)
  99     insert_extent_into_skyline (&chord_outlines_[d]  ,
 100                                 boxes[i], Y_AXIS, -d);
 101
 102   if (stem
 103       && !Stem::is_invisible (stem))
 104     {
 105       Interval x;
 106       x.add_point (stem->relative_coordinate (x_refpoint_, X_AXIS));
 107       x.widen (staff_space / 20); // ugh.
 108       Interval y;
 109       y.add_point (Stem::stem_end_position (stem) * staff_space * .5);
 110
 111       Direction stemdir = get_grob_direction (stem);
 112       y.add_point (Stem::head_positions (stem)[-stemdir]
 113                    * staff_space * .5);
 114
 115       insert_extent_into_skyline (&chord_outlines_[d], Box (x,y), Y_AXIS, -d);
 116
 117
 118
 119       if (d == LEFT)
 120         {
 121           Box flag_box = Stem::get_translated_flag (stem).extent_box ();
 122           flag_box.translate( Offset (x[RIGHT], X_AXIS));
 123           insert_extent_into_skyline (&chord_outlines_[d], flag_box,
 124                                       Y_AXIS, -d);
 125         }
 126     }
 127
 128   Direction updowndir = DOWN;
 129   do
 130     {
 131       Interval x ;
 132       Interval y;
 133       if (boxes.size())
 134         {
 135           Box b = boxes.boundary (updowndir, 0);
 136           x = b[X_AXIS];
 137           x[-d] =  b[X_AXIS].linear_combination (-d / 2);
 138           y[-updowndir] = b[Y_AXIS][updowndir];
 139           y[updowndir] = updowndir * infinity_f;
 140         }
 141
 142       if (!x.is_empty ())
 143         insert_extent_into_skyline (&chord_outlines_[d],
 144                                     Box (x,y),
 145                                     Y_AXIS, -d);
 146     }
 147   while (flip (&updowndir) != DOWN);
 148 }
 149
 150
 151 void
 152 Tie_formatting_problem::from_tie (Grob *tie)
 153 {
 154   Link_array<Grob> ties;
 155   ties.push (tie);
 156
 157   from_ties (ties);
 158
 159   details_.from_grob (tie);
 160 }
 161
 162 Grob *
 163 Tie_formatting_problem::common_x_refpoint () const
 164 {
 165   return x_refpoint_;
 166 }
 167
 168 void
 169 Tie_formatting_problem::from_ties (Link_array<Grob> const &ties)
 170 {
 171   if (ties.is_empty ())
 172     return;
 173
 174   x_refpoint_ = ties[0];
 175   for (int i = 0; i < ties.size (); i++)
 176     {
 177       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (LEFT)->common_refpoint (x_refpoint_, X_AXIS);
 178       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (RIGHT)->common_refpoint (x_refpoint_, X_AXIS);
 179     }
 180
 181   details_.from_grob (ties[0]);
 182
 183   Direction d = LEFT;
 184   do
 185     {
 186       Link_array<Item> bounds;
 187
 188       for (int i = 0; i < ties.size (); i++)
 189         {
 190           Item *it = dynamic_cast<Spanner*> (ties[i])->get_bound (d);
 191
 192           bounds.push (it);
 193         }
 194
 195       set_chord_outline (bounds, d);
 196     }
 197   while (flip (&d) != LEFT);
 198 }
 199
 200 void
 201 Tie_formatting_problem::from_lv_ties (Link_array<Grob> const &lv_ties)
 202 {
 203   if (lv_ties.is_empty ())
 204     return ;
 205
 206   details_.from_grob (lv_ties[0]);
 207   Link_array<Item> heads;
 208   for (int i = 0; i < lv_ties.size (); i++)
 209     {
 210       Item *head = unsmob_item (lv_ties[i]->get_object ("note-head"));
 211       if (!head)
 212         continue;
 213
 214       heads.push (head);
 215     }
 216
 217   x_refpoint_ = lv_ties [0];
 218   for (int i = 0; i < lv_ties.size (); i++)
 219     {
 220       x_refpoint_ = lv_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 221     }
 222
 223   set_chord_outline (heads, LEFT);
 224
 225   Real right_most = - infinity_f;
 226
 227   for (int i = 0; i < chord_outlines_[LEFT].size (); i++)
 228     {
 229       right_most = max (right_most, chord_outlines_[LEFT][i].height_);
 230     }
 231
 232   Skyline_entry right_entry;
 233   right_entry.width_.set_full ();
 234   right_entry.height_ = right_most + 1.5;
 235
 236   chord_outlines_[RIGHT].push (right_entry);
 237 }
 238
 239 Tie_configuration*
 240 Tie_formatting_problem::get_configuration (int pos, Direction dir)
 241 {
 242   pair<int,int> key (pos, dir);
 243   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 244
 245   if (f != possibilities_.end ())
 246     {
 247       return (*f).second;
 248     }
 249
 250
 251   Tie_configuration *conf = generate_configuration (pos,dir);
 252   possibilities_[key] = conf;
 253   return conf;
 254 }
 255
 256 Tie_configuration*
 257 Tie_formatting_problem::generate_configuration (int pos, Direction dir)
 258 {
 259   Tie_configuration *conf = new Tie_configuration;
 260   conf->position_ = pos;
 261   conf->dir_ = dir;
 262   Real y = conf->position_ * 0.5 * details_.staff_space_;
 263
 264   if (dot_positions_.find (pos) != dot_positions_.end ())
 265     {
 266       conf->delta_y_ += 0.25 * details_.staff_space_;
 267     }
 268
 269   conf->attachment_x_ = get_attachment (y + conf->delta_y_);
 270
 271   Real h =  conf->height (details_);
 272   if (!conf->delta_y_)
 273     {
 274       if (h < 0.5 * details_.staff_space_
 275           && !Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_, pos))
 276         {
 277           conf->center_tie_vertically (details_);
 278         }
 279       else if (h < 0.5 * details_.staff_space_
 280                && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_, pos))
 281         {
 282           conf->delta_y_ += dir * 0.2 * details_.staff_space_;
 283         }
 284     }
 285
 286   conf->attachment_x_.widen ( - details_.x_gap_);
 287   return conf;
 288 }
 289
 290 Real
 291 Tie_formatting_problem::score_aptitude (Tie_configuration const &conf,
 292                                         int tie_position)
 293 {
 294   Real wrong_direction_offset_penalty_;
 295   Real distance_penalty_factor_;
 296
 297   wrong_direction_offset_penalty_ = 10;
 298   distance_penalty_factor_ = 5;
 299
 300   Real penalty = 0.0;
 301   Real curve_y = conf.position_ * details_.staff_space_ * 0.5 + conf.delta_y_;
 302   Real tie_y = tie_position * details_.staff_space_ * 0.5;
 303   if (sign (curve_y - tie_y) != conf.dir_)
 304     penalty += wrong_direction_offset_penalty_;
 305
 306   penalty += distance_penalty_factor_ * fabs (curve_y - tie_y);
 307   return penalty;
 308 }
 309
 310
 311 Real
 312 Tie_formatting_problem::score_configuration (Tie_configuration const &conf)
 313 {
 314   Real length_penalty_factor = 1.0;
 315   Real min_length = 0.333;
 316   Real staff_line_clearance = 0.1;
 317   Real staff_line_collision_penalty = 5;
 318   Real dot_collision_clearance = 0.25;
 319   Real dot_collision_penalty = 10;
 320
 321
 322   Real penalty = 0.0;
 323   Real length = conf.attachment_x_.length ();
 324   if (length < min_length)
 325     penalty += length_penalty_factor / max (0.01, length);
 326
 327   Real tip_pos = conf.position_ + conf.delta_y_ / 0.5 * details_.staff_space_;
 328   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 329   Real height =  conf.height (details_);
 330
 331   Real top_y = tip_y + conf.dir_ * height;
 332   Real top_pos = 2 * top_y / details_.staff_space_;
 333   Real round_top_pos = rint (top_pos);
 334   if (fabs (top_pos - round_top_pos) < staff_line_clearance
 335       && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_,
 336                                                 int (round_top_pos))
 337       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 338     {
 339       penalty += staff_line_collision_penalty;
 340     }
 341
 342   if (fabs (tip_pos - rint (tip_pos)) < staff_line_clearance
 343       && Staff_symbol_referencer::on_staffline (details_.staff_symbol_referencer_,
 344                                                 int (rint (tip_pos))))
 345     {
 346       penalty += staff_line_collision_penalty;
 347     }
 348
 349   if (!dot_x_.is_empty ())
 350     {
 351       /* use left edge? */
 352       Real x = dot_x_.center ();
 353
 354       Bezier b = conf.get_transformed_bezier (details_);
 355       if (b.control_point_extent (X_AXIS).contains (x))
 356         {
 357           Real y = b.get_other_coordinate (X_AXIS, x);
 358
 359           for (set<int>::const_iterator i (dot_positions_.begin ());
 360                i != dot_positions_.end (); i ++)
 361             {
 362               int dot_pos = (*i);
 363               if (fabs (dot_pos * details_.staff_space_ * 0.5 - y) < dot_collision_clearance)
 364                 {
 365                   penalty += dot_collision_penalty;
 366                 }
 367             }
 368         }
 369     }
 370
 371   return penalty;
 372 }
 373
 374 Tie_configuration
 375 Tie_formatting_problem::find_optimal_tie_configuration (int pos, Direction dir)
 376 {
 377   Link_array<Tie_configuration> confs;
 378
 379   int region_size = 3;
 380   for (int i = 0; i < region_size; i ++)
 381     {
 382       confs.push (generate_configuration (pos + i * dir, dir));
 383     }
 384
 385   Array<Real> scores;
 386
 387   int best_idx = -1;
 388   Real best_score = 1e6;
 389   for (int i = 0; i < confs.size (); i ++)
 390     {
 391       Real score = 0.0;
 392       score += score_configuration (*confs[i]);
 393       score += score_aptitude (*confs[i], pos);
 394
 395       if (score < best_score)
 396         {
 397           best_score = score;
 398           best_idx = i;
 399         }
 400     }
 401
 402   Tie_configuration best = *confs[best_idx];
 403   for (int i = 0; i < confs.size (); i++)
 404     delete confs[i];
 405
 406   return best;
 407 }