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   /* Too far apart to collide. */
  59   if (ups[0] > dps.back () + 1)
  60     return 0.0;
  61
  62   /* If the chords just 'touch' their extreme noteheads,
  63      then we can align their stems.
  64   */
  65   bool touch = false;
  66   if (ups[0] >= dps.back ()
  67       && (dps.size () < 2 || ups[0] >= dps[dps.size () - 2] + 2)
  68       && (ups.size () < 2 || ups[1] >= dps.back () + 2))
  69     touch = true;
  70
  71   /* Filter out the 'o's in this configuration, since they're no
  72    * part in the collision.
  73    *
  74    *  |
  75    * x|o
  76    * x|o
  77    * x
  78    *
  79    */
  80   ups = Stem::note_head_positions (stems[UP], true);
  81   dps = Stem::note_head_positions (stems[DOWN], true);
  82
  83   /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
  84      above the "stem-down-note". */
  85   bool merge_possible = (ups[0] >= dps[0]) && (ups.back () >= dps.back ());
  86
  87   /* Do not merge notes typeset in different style. */
  88   if (!ly_is_equal (head_up->get_property ("style"),
  89                     head_down->get_property ("style")))
  90     merge_possible = false;
  91
  92   int up_ball_type = Rhythmic_head::duration_log (head_up);
  93   int down_ball_type = Rhythmic_head::duration_log (head_down);
  94
  95   /* Do not merge whole notes (or longer, like breve, longa, maxima). */
  96   if (merge_possible && (up_ball_type <= 0 || down_ball_type <= 0))
  97     merge_possible = false;
  98
  99   if (merge_possible
 100       && Rhythmic_head::dot_count (head_up) != Rhythmic_head::dot_count (head_down)
 101       && !to_boolean (me->get_property ("merge-differently-dotted")))
 102     merge_possible = false;
 103
 104   /* Can only merge different heads if merge-differently-headed is set. */
 105   if (merge_possible
 106       && up_ball_type != down_ball_type
 107       && !to_boolean (me->get_property ("merge-differently-headed")))
 108     merge_possible = false;
 109
 110   /* Should never merge quarter and half notes, as this would make
 111      them indistinguishable.  */
 112   if (merge_possible
 113       && ((Stem::duration_log (stems[UP]) == 1
 114            && Stem::duration_log (stems[DOWN]) == 2)
 115           || (Stem::duration_log (stems[UP]) == 2
 116               && Stem::duration_log (stems[DOWN]) == 1)))
 117     merge_possible = false;
 118
 119   /*
 120    * this case (distant half collide),
 121    *
 122    *    |
 123    *  x |
 124    * | x
 125    * |
 126    *
 127    * the noteheads may be closer than this case (close half collide)
 128    *
 129    *    |
 130    *    |
 131    *   x
 132    *  x
 133    * |
 134    * |
 135    *
 136    */
 137
 138   bool close_half_collide = false;
 139   bool distant_half_collide = false;
 140   bool full_collide = false;
 141
 142   for (vsize i = 0, j = 0; i < ups.size () && j < dps.size ();)
 143     {
 144       if (abs (ups[i] - dps[j]) == 1)
 145         {
 146           merge_possible = false;
 147           if (ups[i] > dps[j])
 148             close_half_collide = true;
 149           else
 150             distant_half_collide = true;
 151         }
 152       else if (ups[i] == dps[j])
 153         full_collide = true;
 154       else if (ups[i] > dps[0] && ups[i] < dps.back ())
 155         merge_possible = false;
 156       else if (dps[j] > ups[0] && dps[j] < ups.back ())
 157         merge_possible = false;
 158
 159       if (ups[i] < dps[j])
 160         i++;
 161       else if (ups[i] > dps[j])
 162         j++;
 163       else
 164         {
 165           i++;
 166           j++;
 167         }
 168     }
 169
 170   full_collide = full_collide || (close_half_collide
 171                                   && distant_half_collide)
 172                  || ( distant_half_collide // like full_ for wholes and longer
 173                       && (up_ball_type <= 0 || down_ball_type <= 0));
 174
 175   /* Determine which chord goes on the left, and which goes right.
 176      Up-stem usually goes on the right, but if chords just 'touch' we can put
 177      both stems on a common vertical line.  In the presense of collisions,
 178      right hand heads may obscure dots, so dotted heads to go the right.
 179   */
 180   Real shift_amount = 1;
 181   bool stem_to_stem = false;
 182   if ((full_collide
 183        || ((close_half_collide || distant_half_collide)
 184            && to_boolean (me->get_property ("prefer-dotted-right"))))
 185       && Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
 186     {
 187       shift_amount = -1;
 188       if (!touch)
 189         // remember to leave clearance between stems
 190         stem_to_stem = true;
 191     }
 192   else if (touch)
 193     {
 194       // Up-stem note on a line has a raised dot, so no risk of collision
 195       Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
 196       if ((full_collide
 197            || (!Staff_symbol_referencer::on_line (staff, ups[0])
 198                && to_boolean (me->get_property ("prefer-dotted-right"))))
 199           && Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
 200         touch = false;
 201       else
 202         shift_amount = -1;
 203     }
 204
 205   /* The solfa is a triangle, which is inverted depending on stem
 206      direction.  In case of a collision, one of them should be removed,
 207      so the resulting note does not look like a block.
 208   */
 209   SCM up_style = head_up->get_property ("style");
 210   SCM down_style = head_down->get_property ("style");
 211   if (merge_possible
 212       && (scm_is_eq (up_style, ly_symbol2scm ("fa"))
 213           || scm_is_eq (up_style, ly_symbol2scm ("faThin")))
 214       && (scm_is_eq (down_style, ly_symbol2scm ("fa"))
 215           || scm_is_eq (down_style, ly_symbol2scm ("faThin"))))
 216     {
 217       Offset att = Offset (0.0, -1.0);
 218       head_up->set_property ("stem-attachment", ly_offset2scm (att));
 219       head_up->set_property ("transparent", SCM_BOOL_T);
 220     }
 221
 222   if (merge_possible)
 223     {
 224       shift_amount = 0;
 225
 226       /* If possible, don't wipe any heads.  Else, wipe shortest head,
 227          or head with smallest amount of dots.  Note: when merging
 228          different heads, dots on the smaller one disappear; and when
 229          merging identical heads, dots on the down-stem head 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_down;
 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 - extent_up[RIGHT] / extent_down[RIGHT]) * 0.5;
 265         }
 266
 267       if (dot_wipe_head)
 268         {
 269           if (Grob *d = Grob::unsmob (dot_wipe_head->get_object ("dot")))
 270             d->suicide ();
 271         }
 272
 273       if (wipe_ball && wipe_ball->is_live ())
 274         wipe_ball->set_property ("transparent", SCM_BOOL_T);
 275     }
 276   /* TODO: these numbers are magic; should devise a set of grob props
 277      to tune this behavior. */
 278   else if (stem_to_stem)
 279     shift_amount *= 0.65;
 280   else if (touch)
 281     shift_amount *= 0.5;
 282   else if (close_half_collide)
 283     shift_amount *= 0.52;
 284   else if (full_collide)
 285     shift_amount *= 0.5;
 286   else if (distant_half_collide)
 287     shift_amount *= 0.4;
 288
 289   /* we're meshing. */
 290   else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
 291     shift_amount *= 0.1;
 292   else
 293     shift_amount *= 0.17;
 294
 295   /* The offsets computed in this routine are multiplied,
 296      in calc_positioning_done(), by the width of the downstem note.
 297      The shift required to clear collisions, however, depends on the extents
 298      of the note heads on the sides that interfere. */
 299   if (shift_amount < 0.0) // Down-stem shifts right.
 300     shift_amount *= (extent_up[RIGHT] - extent_down[LEFT]) / extent_down.length ();
 301   else // Up-stem shifts right.
 302     shift_amount *= (extent_down[RIGHT] - extent_up[LEFT]) / extent_down.length ();
 303
 304   /* If any dotted notes ended up on the left,
 305      tell the Dot_Columnn to avoid the note heads on the right.
 306    */
 307   if (shift_amount < -1e-6
 308       && Rhythmic_head::dot_count (head_up))
 309     {
 310       Grob *d = Grob::unsmob (head_up->get_object ("dot"));
 311       Grob *parent = d->get_parent (X_AXIS);
 312       if (Dot_column::has_interface (parent))
 313         Side_position_interface::add_support (parent, head_down);
 314     }
 315   else if (Rhythmic_head::dot_count (head_down))
 316     {
 317       Grob *d = Grob::unsmob (head_down->get_object ("dot"));
 318       Grob *parent = d->get_parent (X_AXIS);
 319       if (Dot_column::has_interface (parent))
 320         {
 321           Grob *stem = Grob::unsmob (head_up->get_object ("stem"));
 322           // Loop over all heads on an up-pointing-stem to see if dots
 323           // need to clear any heads suspended on its right side.
 324           extract_grob_set (stem, "note-heads", heads);
 325           for (vsize i = 0; i < heads.size (); i++)
 326             Side_position_interface::add_support (parent, heads[i]);
 327         }
 328     }
 329
 330   // In meshed chords with dots on the left, adjust dot direction
 331   if (shift_amount > 1e-6
 332       && Rhythmic_head::dot_count (head_down))
 333     {
 334       Grob *dot_down = Grob::unsmob (head_down->get_object ("dot"));
 335       Grob *col_down = dot_down->get_parent (X_AXIS);
 336       Direction dir = UP;
 337       if (Rhythmic_head::dot_count (head_up))
 338         {
 339           Grob *dot_up = Grob::unsmob (head_up->get_object ("dot"));
 340           Grob *col_up = dot_up->get_parent (X_AXIS);
 341           if (col_up == col_down) // let the common DotColumn arrange dots
 342             dir = CENTER;
 343           else // conform to the dot direction on the up-stem chord
 344             dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
 345         }
 346       if (dir != CENTER)
 347         {
 348           Grob *stem = Grob::unsmob (head_down->get_object ("stem"));
 349           extract_grob_set (stem, "note-heads", heads);
 350           for (vsize i = 0; i < heads.size (); i++)
 351             if (Grob *dot = Grob::unsmob (heads[i]->get_object ("dot")))
 352               dot->set_property ("direction", scm_from_int (dir));
 353         }
 354     }
 355
 356   return shift_amount;
 357 }
 358
 359 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
 360 SCM
 361 Note_collision_interface::calc_positioning_done (SCM smob)
 362 {
 363   Grob *me = Grob::unsmob (smob);
 364   me->set_property ("positioning-done", SCM_BOOL_T);
 365
 366   Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
 367
 368   for (UP_and_DOWN (d))
 369     {
 370       for (vsize i = clash_groups[d].size (); i--;)
 371         {
 372           /*
 373             Trigger positioning
 374           */
 375           clash_groups[d][i]->extent (me, X_AXIS);
 376         }
 377     }
 378
 379   SCM autos (automatic_shift (me, clash_groups));
 380   SCM hand (forced_shift (me));
 381
 382   Real wid = 0.0;
 383   for (UP_and_DOWN (d))
 384     {
 385       if (clash_groups[d].size ())
 386         {
 387           Grob *h = clash_groups[d][0];
 388           Grob *fh = Note_column::first_head (h);
 389           if (fh)
 390             wid = fh->extent (h, X_AXIS).length ();
 391         }
 392     }
 393
 394   vector<Grob *> done;
 395   Real left_most = 1e6;
 396
 397   vector<Real> amounts;
 398   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 399     {
 400       Grob *s = Grob::unsmob (scm_caar (hand));
 401       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 402
 403       done.push_back (s);
 404       amounts.push_back (amount);
 405       if (amount < left_most)
 406         left_most = amount;
 407     }
 408   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 409     {
 410       Grob *s = Grob::unsmob (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 (Note_column::has_interface (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 = Grob::unsmob (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                "positioning-done "
 613                "prefer-dotted-right "
 614               );