lily/note-collision.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1997--2012 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 "note-collision.hh"
  21
  22 #include "axis-group-interface.hh"
  23 #include "dot-column.hh"
  24 #include "international.hh"
  25 #include "note-column.hh"
  26 #include "note-head.hh"
  27 #include "output-def.hh"
  28 #include "pointer-group-interface.hh"
  29 #include "item.hh"
  30 #include "rhythmic-head.hh"
  31 #include "staff-symbol-referencer.hh"
  32 #include "side-position-interface.hh"
  33 #include "stem.hh"
  34 #include "warn.hh"
  35
  36 void
  37 check_meshing_chords (Grob *me,
  38                       Drul_array<vector<Real> > *offsets,
  39                       Drul_array<vector<Slice> > const &extents,
  40                       Drul_array<vector<Grob *> > const &clash_groups)
  41
  42 {
  43   if (!extents[UP].size () || !extents[DOWN].size ())
  44     return;
  45
  46   Grob *clash_up = clash_groups[UP][0];
  47   Grob *clash_down = clash_groups[DOWN][0];
  48
  49   /* Every note column should have a stem, but avoid a crash. */
  50   if (!Note_column::get_stem (clash_up) || !Note_column::get_stem (clash_down))
  51     return;
  52
  53   Drul_array<Grob *> stems (Note_column::get_stem (clash_down),
  54                             Note_column::get_stem (clash_up));
  55
  56   Grob *head_up = Note_column::first_head (clash_up);
  57   Grob *head_down = Note_column::first_head (clash_down);
  58
  59   /* Staff-positions of all noteheads on each stem */
  60   vector<int> ups = Stem::note_head_positions (stems[UP]);
  61   vector<int> dps = Stem::note_head_positions (stems[DOWN]);
  62
  63   /* Too far apart to collide. */
  64   if (ups[0] > dps.back () + 1)
  65     return;
  66
  67   /* If the chords just 'touch' their extreme noteheads,
  68      then we can align their stems.
  69   */
  70   bool touch = false;
  71   if (ups[0] >= dps.back ()
  72       && (dps.size () < 2 || ups[0] >= dps[dps.size () - 2] + 2)
  73       && (ups.size () < 2 || ups[1] >= dps.back () + 2))
  74     touch = true;
  75
  76   /* Filter out the 'o's in this configuration, since they're no
  77    * part in the collision.
  78    *
  79    *  |
  80    * x|o
  81    * x|o
  82    * x
  83    *
  84    */
  85   ups = Stem::note_head_positions (stems[UP], true);
  86   dps = Stem::note_head_positions (stems[DOWN], true);
  87
  88   /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
  89      above the "stem-down-note". */
  90   bool merge_possible = (ups[0] >= dps[0]) && (ups.back () >= dps.back ());
  91
  92   /* Do not merge notes typeset in different style. */
  93   if (!ly_is_equal (head_up->get_property ("style"),
  94                     head_down->get_property ("style")))
  95     merge_possible = false;
  96
  97   int up_ball_type = Rhythmic_head::duration_log (head_up);
  98   int down_ball_type = Rhythmic_head::duration_log (head_down);
  99
 100   /* Do not merge whole notes (or longer, like breve, longa, maxima). */
 101   if (merge_possible && (up_ball_type <= 0 || down_ball_type <= 0))
 102     merge_possible = false;
 103
 104   if (merge_possible
 105       && Rhythmic_head::dot_count (head_up) != Rhythmic_head::dot_count (head_down)
 106       && !to_boolean (me->get_property ("merge-differently-dotted")))
 107     merge_possible = false;
 108
 109   /* Can only merge different heads if merge-differently-headed is set. */
 110   if (merge_possible
 111       && up_ball_type != down_ball_type
 112       && !to_boolean (me->get_property ("merge-differently-headed")))
 113     merge_possible = false;
 114
 115   /* Should never merge quarter and half notes, as this would make
 116      them indistinguishable.  */
 117   if (merge_possible
 118       && ((Stem::duration_log (stems[UP]) == 1
 119            && Stem::duration_log (stems[DOWN]) == 2)
 120           || (Stem::duration_log (stems[UP]) == 2
 121               && Stem::duration_log (stems[DOWN]) == 1)))
 122     merge_possible = false;
 123
 124   /*
 125    * this case (distant half collide),
 126    *
 127    *    |
 128    *  x |
 129    * | x
 130    * |
 131    *
 132    * the noteheads may be closer than this case (close half collide)
 133    *
 134    *    |
 135    *    |
 136    *   x
 137    *  x
 138    * |
 139    * |
 140    *
 141    */
 142
 143   bool close_half_collide = false;
 144   bool distant_half_collide = false;
 145   bool full_collide = false;
 146
 147   for (vsize i = 0, j = 0; i < ups.size () && j < dps.size ();)
 148     {
 149       if (abs (ups[i] - dps[j]) == 1)
 150         {
 151           merge_possible = false;
 152           if (ups[i] > dps[j])
 153             close_half_collide = true;
 154           else
 155             distant_half_collide = true;
 156         }
 157       else if (ups[i] == dps[j])
 158         full_collide = true;
 159       else if (ups[i] > dps[0] && ups[i] < dps.back ())
 160         merge_possible = false;
 161       else if (dps[j] > ups[0] && dps[j] < ups.back ())
 162         merge_possible = false;
 163
 164       if (ups[i] < dps[j])
 165         i++;
 166       else if (ups[i] > dps[j])
 167         j++;
 168       else
 169         {
 170           i++;
 171           j++;
 172         }
 173     }
 174
 175   full_collide = full_collide || (close_half_collide
 176                                   && distant_half_collide);
 177
 178   /* Determine which chord goes on the left, and which goes right.
 179      Up-stem usually goes on the right, but if chords just 'touch' we can put
 180      both stems on a common vertical line.  In the presense of collisions,
 181      right hand heads may obscure dots, so dotted heads to go the right.
 182   */
 183   Real shift_amount = 1;
 184   bool stem_to_stem = false;
 185   if ((full_collide
 186        || ((close_half_collide || distant_half_collide)
 187            && to_boolean (me->get_property ("prefer-dotted-right"))))
 188       && Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
 189     {
 190       shift_amount = -1;
 191       if (!touch)
 192         // remember to leave clearance between stems
 193         stem_to_stem = true;
 194     }
 195   else if (touch)
 196     {
 197       // Up-stem note on a line has a raised dot, so no risk of collision
 198       Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
 199       if ((full_collide
 200            || (!Staff_symbol_referencer::on_line (staff, ups[0])
 201                && to_boolean (me->get_property ("prefer-dotted-right"))))
 202           && Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
 203         touch = false;
 204       else
 205         shift_amount = -1;
 206     }
 207
 208   /* The solfa is a triangle, which is inverted depending on stem
 209      direction.  In case of a collision, one of them should be removed,
 210      so the resulting note does not look like a block.
 211   */
 212   SCM up_style = head_up->get_property ("style");
 213   SCM down_style = head_down->get_property ("style");
 214   if (merge_possible
 215       && (up_style == ly_symbol2scm ("fa") || up_style == ly_symbol2scm ("faThin"))
 216       && (down_style == ly_symbol2scm ("fa") || down_style == ly_symbol2scm ("faThin")))
 217     {
 218       Offset att = Offset (0.0, -1.0);
 219       head_up->set_property ("stem-attachment", ly_offset2scm (att));
 220       head_up->set_property ("transparent", SCM_BOOL_T);
 221     }
 222
 223   if (merge_possible)
 224     {
 225       shift_amount = 0;
 226
 227       /* If possible, don't wipe any heads.  Else, wipe shortest head,
 228          or head with smallest amount of dots.  Note: when merging
 229          different heads, dots on the smaller one disappear. */
 230       Grob *wipe_ball = 0;
 231       Grob *dot_wipe_head = head_up;
 232
 233       if (up_ball_type == down_ball_type)
 234         {
 235           if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
 236             {
 237               wipe_ball = head_down;
 238               dot_wipe_head = head_down;
 239             }
 240           else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
 241             {
 242               dot_wipe_head = head_up;
 243               wipe_ball = head_up;
 244             }
 245           else
 246             dot_wipe_head = head_up;
 247         }
 248       else if (down_ball_type > up_ball_type)
 249         {
 250           wipe_ball = head_down;
 251           dot_wipe_head = head_down;
 252         }
 253       else if (down_ball_type < up_ball_type)
 254         {
 255           wipe_ball = head_up;
 256           dot_wipe_head = head_up;
 257           /*
 258             If upper head is eighth note or shorter, and lower head is half note,
 259             shift by the difference between the open and filled note head widths,
 260             otherwise upper stem will be misaligned slightly.
 261           */
 262           if (Stem::duration_log (stems[DOWN]) == 1
 263               && Stem::duration_log (stems[UP]) >= 3)
 264             shift_amount = (1 - head_up->extent (head_up, X_AXIS).length ()
 265                             / head_down->extent (head_down, X_AXIS).length ()) * 0.5;
 266         }
 267
 268       if (dot_wipe_head)
 269         {
 270           if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
 271             d->suicide ();
 272         }
 273
 274       if (wipe_ball && wipe_ball->is_live ())
 275         wipe_ball->set_property ("transparent", SCM_BOOL_T);
 276     }
 277   /* TODO: these numbers are magic; should devise a set of grob props
 278      to tune this behavior. */
 279   else if (stem_to_stem)
 280     shift_amount *= 0.65;
 281   else if (touch)
 282     shift_amount *= 0.5;
 283   else if (close_half_collide)
 284     shift_amount *= 0.52;
 285   else if (full_collide)
 286     shift_amount *= 0.5;
 287   else if (distant_half_collide)
 288     shift_amount *= 0.4;
 289
 290   /* we're meshing. */
 291   else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
 292     shift_amount *= 0.1;
 293   else
 294     shift_amount *= 0.17;
 295
 296   /*
 297   */
 298   if (full_collide
 299       && down_ball_type *up_ball_type == 0)
 300     {
 301       if (up_ball_type == 0 && down_ball_type == 1)
 302         shift_amount *= 1.25;
 303       else if (up_ball_type == 0 && down_ball_type == 2)
 304         shift_amount *= 1.35;
 305       else if (down_ball_type == 0 && up_ball_type == 1)
 306         shift_amount *= 0.7;
 307       else if (down_ball_type == 0 && up_ball_type == 2)
 308         shift_amount *= 0.75;
 309     }
 310
 311   /* If any dotted notes ended up on the left,
 312      tell the Dot_Columnn to avoid the note heads on the right.
 313    */
 314   if (shift_amount < -1e-6
 315       && Rhythmic_head::dot_count (head_up))
 316     {
 317       Grob *d = unsmob_grob (head_up->get_object ("dot"));
 318       Grob *parent = d->get_parent (X_AXIS);
 319       if (Dot_column::has_interface (parent))
 320         Side_position_interface::add_support (parent, head_down);
 321     }
 322   else if (Rhythmic_head::dot_count (head_down))
 323     {
 324       Grob *d = unsmob_grob (head_down->get_object ("dot"));
 325       Grob *parent = d->get_parent (X_AXIS);
 326       if (Dot_column::has_interface (parent))
 327         {
 328           Grob *stem = unsmob_grob (head_up->get_object ("stem"));
 329           // Loop over all heads on an up-pointing-stem to see if dots
 330           // need to clear any heads suspended on its right side.
 331           extract_grob_set (stem, "note-heads", heads);
 332           for (vsize i = 0; i < heads.size (); i++)
 333             Side_position_interface::add_support (parent, heads[i]);
 334         }
 335     }
 336
 337   // In meshed chords with dots on the left, adjust dot direction
 338   if (shift_amount > 1e-6
 339       && Rhythmic_head::dot_count (head_down))
 340     {
 341       Grob *dot_down = unsmob_grob (head_down->get_object ("dot"));
 342       Grob *col_down = dot_down->get_parent (X_AXIS);
 343       Direction dir = UP;
 344       if (Rhythmic_head::dot_count (head_up))
 345         {
 346           Grob *dot_up = unsmob_grob (head_up->get_object ("dot"));
 347           Grob *col_up = dot_up->get_parent (X_AXIS);
 348           if (col_up == col_down) // let the common DotColumn arrange dots
 349             dir = CENTER;
 350           else // conform to the dot direction on the up-stem chord
 351             dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
 352         }
 353       if (dir != CENTER)
 354         {
 355           Grob *stem = unsmob_grob (head_down->get_object ("stem"));
 356           extract_grob_set (stem, "note-heads", heads);
 357           for (vsize i = 0; i < heads.size (); i++)
 358             unsmob_grob (heads[i]->get_object ("dot"))
 359             ->set_property ("direction", scm_from_int (dir));
 360         }
 361     }
 362
 363   for (UP_and_DOWN (d))
 364     {
 365       for (vsize i = 0; i < clash_groups[d].size (); i++)
 366         (*offsets)[d][i] += d * shift_amount;
 367     }
 368 }
 369
 370 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
 371 SCM
 372 Note_collision_interface::calc_positioning_done (SCM smob)
 373 {
 374   Grob *me = unsmob_grob (smob);
 375   me->set_property ("positioning-done", SCM_BOOL_T);
 376
 377   Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
 378
 379   for (UP_and_DOWN (d))
 380     {
 381       for (vsize i = clash_groups[d].size (); i--;)
 382         {
 383           /*
 384             Trigger positioning
 385           */
 386           clash_groups[d][i]->extent (me, X_AXIS);
 387         }
 388     }
 389
 390   SCM autos (automatic_shift (me, clash_groups));
 391   SCM hand (forced_shift (me));
 392
 393   Real wid = 0.0;
 394   for (UP_and_DOWN (d))
 395     {
 396       if (clash_groups[d].size ())
 397         {
 398           Grob *h = clash_groups[d][0];
 399           Grob *fh = Note_column::first_head (h);
 400           if (fh)
 401             wid = fh->extent (h, X_AXIS).length ();
 402         }
 403     }
 404
 405   vector<Grob *> done;
 406   Real left_most = 1e6;
 407
 408   vector<Real> amounts;
 409   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 410     {
 411       Grob *s = unsmob_grob (scm_caar (hand));
 412       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 413
 414       done.push_back (s);
 415       amounts.push_back (amount);
 416       if (amount < left_most)
 417         left_most = amount;
 418     }
 419   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 420     {
 421       Grob *s = unsmob_grob (scm_caar (autos));
 422       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 423
 424       vsize x = find (done, s) - done.begin ();
 425       if (x == VPOS || x >= done.size ())
 426         {
 427           done.push_back (s);
 428           amounts.push_back (amount);
 429           if (amount < left_most)
 430             left_most = amount;
 431         }
 432     }
 433
 434   for (vsize i = 0; i < amounts.size (); i++)
 435     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 436
 437   return SCM_BOOL_T;
 438 }
 439
 440 Drul_array < vector<Grob *> >
 441 Note_collision_interface::get_clash_groups (Grob *me)
 442 {
 443   Drul_array<vector<Grob *> > clash_groups;
 444
 445   extract_grob_set (me, "elements", elements);
 446   for (vsize i = 0; i < elements.size (); i++)
 447     {
 448       Grob *se = elements[i];
 449       if (Note_column::has_interface (se))
 450         {
 451           if (!Note_column::dir (se))
 452             se->programming_error ("note-column has no direction");
 453           else
 454             clash_groups[Note_column::dir (se)].push_back (se);
 455         }
 456     }
 457
 458   for (UP_and_DOWN (d))
 459     {
 460       vector<Grob *> &clashes (clash_groups[d]);
 461       vector_sort (clashes, Note_column::shift_less);
 462     }
 463
 464   return clash_groups;
 465 }
 466
 467 /*
 468   This complicated routine moves note columns around horizontally to
 469   ensure that notes don't clash.
 470 */
 471 SCM
 472 Note_collision_interface::automatic_shift (Grob *me,
 473                                            Drul_array<vector<Grob *> > clash_groups)
 474 {
 475   Drul_array < vector<int> > shifts;
 476   SCM tups = SCM_EOL;
 477
 478   for (UP_and_DOWN (d))
 479     {
 480       vector<int> &shift (shifts[d]);
 481       vector<Grob *> &clashes (clash_groups[d]);
 482
 483       for (vsize i = 0; i < clashes.size (); i++)
 484         {
 485           SCM sh
 486             = clashes[i]->get_property ("horizontal-shift");
 487
 488           if (scm_is_number (sh))
 489             shift.push_back (scm_to_int (sh));
 490           else
 491             shift.push_back (0);
 492         }
 493
 494       for (vsize i = 1; i < shift.size (); i++)
 495         {
 496           if (shift[i - 1] == shift[i])
 497             {
 498               clashes[0]->warning (_ ("ignoring too many clashing note columns"));
 499               return tups;
 500             }
 501         }
 502     }
 503
 504   Drul_array<vector<Slice> > extents;
 505   Drul_array<vector<Real> > offsets;
 506   for (UP_and_DOWN (d))
 507     {
 508       for (vsize i = 0; i < clash_groups[d].size (); i++)
 509         {
 510           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 511           s[LEFT]--;
 512           s[RIGHT]++;
 513           extents[d].push_back (s);
 514           offsets[d].push_back (d * 0.5 * i);
 515         }
 516     }
 517
 518   /*
 519    * do horizontal shifts of each direction
 520    *
 521    *  |
 522    * x||
 523    *  x||
 524    *   x|
 525   */
 526
 527   for (UP_and_DOWN (d))
 528     {
 529       for (vsize i = 1; i < clash_groups[d].size (); i++)
 530         {
 531           Slice prev = extents[d][i - 1];
 532           prev.intersect (extents[d][i]);
 533           if (prev.length () > 0
 534               || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 535             for (vsize j = i; j < clash_groups[d].size (); j++)
 536               offsets[d][j] += d * 0.5;
 537         }
 538     }
 539
 540   /*
 541     see input/regression/dot-up-voice-collision.ly
 542   */
 543   for (vsize i = 0; i < clash_groups[UP].size (); i++)
 544     {
 545       Grob *g = clash_groups[UP][i];
 546       Grob *dc = Note_column::dot_column (g);
 547
 548       if (dc)
 549         for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
 550           {
 551             Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
 552             Side_position_interface::add_support (dc, stem);
 553           }
 554     }
 555
 556   /*
 557     Check if chords are meshing
 558   */
 559
 560   check_meshing_chords (me, &offsets, extents, clash_groups);
 561
 562   for (UP_and_DOWN (d))
 563     {
 564       for (vsize i = 0; i < clash_groups[d].size (); i++)
 565         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 566                                    scm_from_double (offsets[d][i])),
 567                          tups);
 568     }
 569
 570   return tups;
 571 }
 572
 573 SCM
 574 Note_collision_interface::forced_shift (Grob *me)
 575 {
 576   SCM tups = SCM_EOL;
 577
 578   extract_grob_set (me, "elements", elements);
 579   for (vsize i = 0; i < elements.size (); i++)
 580     {
 581       Grob *se = elements[i];
 582
 583       SCM force = se->get_property ("force-hshift");
 584       if (scm_is_number (force))
 585         tups = scm_cons (scm_cons (se->self_scm (), force),
 586                          tups);
 587     }
 588   return tups;
 589 }
 590
 591 void
 592 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 593 {
 594   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 595   Axis_group_interface::add_element (me, ncol);
 596 }
 597
 598 ADD_INTERFACE (Note_collision_interface,
 599                "An object that handles collisions between notes with"
 600                " different stem directions and horizontal shifts.  Most of"
 601                " the interesting properties are to be set in"
 602                " @ref{note-column-interface}: these are @code{force-hshift}"
 603                " and @code{horizontal-shift}.",
 604
 605                /* properties */
 606                "merge-differently-dotted "
 607                "merge-differently-headed "
 608                "positioning-done "
 609                "prefer-dotted-right "
 610               );