lily/note-collision.cc

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