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       && (up_style == ly_symbol2scm ("fa") || up_style == ly_symbol2scm ("faThin"))
 213       && (down_style == ly_symbol2scm ("fa") || down_style == ly_symbol2scm ("faThin")))
 214     {
 215       Offset att = Offset (0.0, -1.0);
 216       head_up->set_property ("stem-attachment", ly_offset2scm (att));
 217       head_up->set_property ("transparent", SCM_BOOL_T);
 218     }
 219
 220   if (merge_possible)
 221     {
 222       shift_amount = 0;
 223
 224       /* If possible, don't wipe any heads.  Else, wipe shortest head,
 225          or head with smallest amount of dots.  Note: when merging
 226          different heads, dots on the smaller one disappear; and when
 227          merging identical heads, dots on the down-stem head disappear */
 228       Grob *wipe_ball = 0;
 229       Grob *dot_wipe_head = head_up;
 230
 231       if (up_ball_type == down_ball_type)
 232         {
 233           if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
 234             {
 235               wipe_ball = head_down;
 236               dot_wipe_head = head_down;
 237             }
 238           else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
 239             {
 240               dot_wipe_head = head_up;
 241               wipe_ball = head_up;
 242             }
 243           else
 244             dot_wipe_head = head_down;
 245         }
 246       else if (down_ball_type > up_ball_type)
 247         {
 248           wipe_ball = head_down;
 249           dot_wipe_head = head_down;
 250         }
 251       else if (down_ball_type < up_ball_type)
 252         {
 253           wipe_ball = head_up;
 254           dot_wipe_head = head_up;
 255           /*
 256             If upper head is eighth note or shorter, and lower head is half note,
 257             shift by the difference between the open and filled note head widths,
 258             otherwise upper stem will be misaligned slightly.
 259           */
 260           if (Stem::duration_log (stems[DOWN]) == 1
 261               && Stem::duration_log (stems[UP]) >= 3)
 262             shift_amount = (1 - extent_up[RIGHT] / extent_down[RIGHT]) * 0.5;
 263         }
 264
 265       if (dot_wipe_head)
 266         {
 267           if (Grob *d = Grob::unsmob (dot_wipe_head->get_object ("dot")))
 268             d->suicide ();
 269         }
 270
 271       if (wipe_ball && wipe_ball->is_live ())
 272         wipe_ball->set_property ("transparent", SCM_BOOL_T);
 273     }
 274   /* TODO: these numbers are magic; should devise a set of grob props
 275      to tune this behavior. */
 276   else if (stem_to_stem)
 277     shift_amount *= 0.65;
 278   else if (touch)
 279     shift_amount *= 0.5;
 280   else if (close_half_collide)
 281     shift_amount *= 0.52;
 282   else if (full_collide)
 283     shift_amount *= 0.5;
 284   else if (distant_half_collide)
 285     shift_amount *= 0.4;
 286
 287   /* we're meshing. */
 288   else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
 289     shift_amount *= 0.1;
 290   else
 291     shift_amount *= 0.17;
 292
 293   /* The offsets computed in this routine are multiplied,
 294      in calc_positioning_done(), by the width of the downstem note.
 295      The shift required to clear collisions, however, depends on the extents
 296      of the note heads on the sides that interfere. */
 297   if (shift_amount < 0.0) // Down-stem shifts right.
 298     shift_amount *= (extent_up[RIGHT] - extent_down[LEFT]) / extent_down.length ();
 299   else // Up-stem shifts right.
 300     shift_amount *= (extent_down[RIGHT] - extent_up[LEFT]) / extent_down.length ();
 301
 302   /* If any dotted notes ended up on the left,
 303      tell the Dot_Columnn to avoid the note heads on the right.
 304    */
 305   if (shift_amount < -1e-6
 306       && Rhythmic_head::dot_count (head_up))
 307     {
 308       Grob *d = Grob::unsmob (head_up->get_object ("dot"));
 309       Grob *parent = d->get_parent (X_AXIS);
 310       if (Dot_column::has_interface (parent))
 311         Side_position_interface::add_support (parent, head_down);
 312     }
 313   else if (Rhythmic_head::dot_count (head_down))
 314     {
 315       Grob *d = Grob::unsmob (head_down->get_object ("dot"));
 316       Grob *parent = d->get_parent (X_AXIS);
 317       if (Dot_column::has_interface (parent))
 318         {
 319           Grob *stem = Grob::unsmob (head_up->get_object ("stem"));
 320           // Loop over all heads on an up-pointing-stem to see if dots
 321           // need to clear any heads suspended on its right side.
 322           extract_grob_set (stem, "note-heads", heads);
 323           for (vsize i = 0; i < heads.size (); i++)
 324             Side_position_interface::add_support (parent, heads[i]);
 325         }
 326     }
 327
 328   // In meshed chords with dots on the left, adjust dot direction
 329   if (shift_amount > 1e-6
 330       && Rhythmic_head::dot_count (head_down))
 331     {
 332       Grob *dot_down = Grob::unsmob (head_down->get_object ("dot"));
 333       Grob *col_down = dot_down->get_parent (X_AXIS);
 334       Direction dir = UP;
 335       if (Rhythmic_head::dot_count (head_up))
 336         {
 337           Grob *dot_up = Grob::unsmob (head_up->get_object ("dot"));
 338           Grob *col_up = dot_up->get_parent (X_AXIS);
 339           if (col_up == col_down) // let the common DotColumn arrange dots
 340             dir = CENTER;
 341           else // conform to the dot direction on the up-stem chord
 342             dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
 343         }
 344       if (dir != CENTER)
 345         {
 346           Grob *stem = Grob::unsmob (head_down->get_object ("stem"));
 347           extract_grob_set (stem, "note-heads", heads);
 348           for (vsize i = 0; i < heads.size (); i++)
 349             if (Grob *dot = Grob::unsmob (heads[i]->get_object ("dot")))
 350               dot->set_property ("direction", scm_from_int (dir));
 351         }
 352     }
 353
 354   return shift_amount;
 355 }
 356
 357 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
 358 SCM
 359 Note_collision_interface::calc_positioning_done (SCM smob)
 360 {
 361   Grob *me = Grob::unsmob (smob);
 362   me->set_property ("positioning-done", SCM_BOOL_T);
 363
 364   Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
 365
 366   for (UP_and_DOWN (d))
 367     {
 368       for (vsize i = clash_groups[d].size (); i--;)
 369         {
 370           /*
 371             Trigger positioning
 372           */
 373           clash_groups[d][i]->extent (me, X_AXIS);
 374         }
 375     }
 376
 377   SCM autos (automatic_shift (me, clash_groups));
 378   SCM hand (forced_shift (me));
 379
 380   Real wid = 0.0;
 381   for (UP_and_DOWN (d))
 382     {
 383       if (clash_groups[d].size ())
 384         {
 385           Grob *h = clash_groups[d][0];
 386           Grob *fh = Note_column::first_head (h);
 387           if (fh)
 388             wid = fh->extent (h, X_AXIS).length ();
 389         }
 390     }
 391
 392   vector<Grob *> done;
 393   Real left_most = 1e6;
 394
 395   vector<Real> amounts;
 396   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 397     {
 398       Grob *s = Grob::unsmob (scm_caar (hand));
 399       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 400
 401       done.push_back (s);
 402       amounts.push_back (amount);
 403       if (amount < left_most)
 404         left_most = amount;
 405     }
 406   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 407     {
 408       Grob *s = Grob::unsmob (scm_caar (autos));
 409       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 410
 411       vsize x = find (done, s) - done.begin ();
 412       if (x == VPOS || x >= done.size ())
 413         {
 414           done.push_back (s);
 415           amounts.push_back (amount);
 416           if (amount < left_most)
 417             left_most = amount;
 418         }
 419     }
 420
 421   for (vsize i = 0; i < amounts.size (); i++)
 422     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 423
 424   return SCM_BOOL_T;
 425 }
 426
 427 Drul_array < vector<Grob *> >
 428 Note_collision_interface::get_clash_groups (Grob *me)
 429 {
 430   Drul_array<vector<Grob *> > clash_groups;
 431
 432   extract_grob_set (me, "elements", elements);
 433   for (vsize i = 0; i < elements.size (); i++)
 434     {
 435       Grob *se = elements[i];
 436       if (Note_column::has_interface (se))
 437         {
 438           if (!Note_column::dir (se))
 439             se->programming_error ("note-column has no direction");
 440           else
 441             clash_groups[Note_column::dir (se)].push_back (se);
 442         }
 443     }
 444
 445   for (UP_and_DOWN (d))
 446     {
 447       vector<Grob *> &clashes (clash_groups[d]);
 448       vector_sort (clashes, Note_column::shift_less);
 449     }
 450
 451   return clash_groups;
 452 }
 453
 454 /*
 455   This complicated routine moves note columns around horizontally to
 456   ensure that notes don't clash.
 457 */
 458 SCM
 459 Note_collision_interface::automatic_shift (Grob *me,
 460                                            Drul_array<vector<Grob *> > clash_groups)
 461 {
 462   SCM tups = SCM_EOL;
 463
 464   Drul_array<vector<Slice> > extents;
 465   Drul_array<Slice> extent_union;
 466   Drul_array<vector<Grob *> > stems;
 467   for (UP_and_DOWN (d))
 468     {
 469       for (vsize i = 0; i < clash_groups[d].size (); i++)
 470         {
 471           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 472           s[LEFT]--;
 473           s[RIGHT]++;
 474           extents[d].push_back (s);
 475           extent_union[d].unite (s);
 476           stems[d].push_back (Note_column::get_stem (clash_groups[d][i]));
 477         }
 478     }
 479
 480   Real inner_offset
 481     = (clash_groups[UP].size () && clash_groups[DOWN].size ())
 482       ? check_meshing_chords (me, clash_groups[UP][0], clash_groups[DOWN][0])
 483       : 0.0;
 484
 485   /*
 486    * do horizontal shifts of each direction
 487    *
 488    *  |
 489    * x||
 490    *  x||
 491    *   x|
 492   */
 493   Drul_array<vector<Real> > offsets;
 494   for (UP_and_DOWN (d))
 495     {
 496       Real offset = inner_offset;
 497       vector<int> shifts;
 498       for (vsize i = 0; i < clash_groups[d].size (); i++)
 499         {
 500           Grob *col = clash_groups[d][i];
 501           SCM sh = col->get_property ("horizontal-shift");
 502           shifts.push_back (robust_scm2int (sh, 0));
 503
 504           if (i == 0)
 505             offset = inner_offset;
 506           else if (shifts[i] == shifts[i - 1])
 507             {
 508               // Match the previous notecolumn offset,
 509               // but warn if the user did not set these equal shifts explictly
 510               if (!scm_is_number (sh))
 511                 col->warning (_ ("ignoring too many clashing note columns"));
 512             }
 513           else if (extents[d][i][UP] > extents[d][i - 1][DOWN]
 514                    && extents[d][i][DOWN] < extents[d][i - 1][UP])
 515             offset += 1.0; // fully clear the inner-voice heads
 516           else
 517             {
 518               // check if we cross the inner voice
 519               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;
 522               else if (Stem::is_valid_stem (stems[d][i]))
 523                 offset += 0.5;
 524               // check if we cross the opposite-stemmed voices
 525               if (d * extents[d][i][-d] < d * extent_union[-d][d])
 526                 offset = max (offset, 0.5);
 527               if (extents[-d].size ()
 528                   && extents[d][i][UP] > extents[-d][0][DOWN]
 529                   && extents[d][i][DOWN] < extents[-d][0][UP])
 530                 offset = max (offset, 1.0);
 531             }
 532           offsets[d].push_back (d * offset);
 533         }
 534     }
 535
 536   /*
 537     see input/regression/dot-up-voice-collision.ly
 538   */
 539   for (vsize i = 0; i < clash_groups[UP].size (); i++)
 540     {
 541       Grob *g = clash_groups[UP][i];
 542       Grob *dc = Note_column::dot_column (g);
 543
 544       if (dc)
 545         for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
 546           Side_position_interface::add_support (dc, stems[UP][j]);
 547     }
 548
 549   for (UP_and_DOWN (d))
 550     {
 551       for (vsize i = 0; i < clash_groups[d].size (); i++)
 552         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 553                                    scm_from_double (offsets[d][i])),
 554                          tups);
 555     }
 556
 557   return tups;
 558 }
 559
 560 SCM
 561 Note_collision_interface::forced_shift (Grob *me)
 562 {
 563   SCM tups = SCM_EOL;
 564
 565   extract_grob_set (me, "elements", elements);
 566   for (vsize i = 0; i < elements.size (); i++)
 567     {
 568       Grob *se = elements[i];
 569
 570       SCM force = se->get_property ("force-hshift");
 571       if (scm_is_number (force))
 572         tups = scm_cons (scm_cons (se->self_scm (), force),
 573                          tups);
 574     }
 575   return tups;
 576 }
 577
 578 void
 579 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 580 {
 581   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 582   Axis_group_interface::add_element (me, ncol);
 583 }
 584
 585 vector<int>
 586 Note_collision_interface::note_head_positions (Grob *me)
 587 {
 588   vector<int> out;
 589   extract_grob_set (me, "elements", elts);
 590   for (vsize i = 0; i < elts.size (); i++)
 591     if (Grob *stem = Grob::unsmob (elts[i]->get_object ("stem")))
 592       {
 593         vector<int> nhp = Stem::note_head_positions (stem);
 594         out.insert (out.end (), nhp.begin (), nhp.end ());
 595       }
 596
 597   vector_sort (out, less<int> ());
 598   return out;
 599 }
 600
 601 ADD_INTERFACE (Note_collision_interface,
 602                "An object that handles collisions between notes with"
 603                " different stem directions and horizontal shifts.  Most of"
 604                " the interesting properties are to be set in"
 605                " @ref{note-column-interface}: these are @code{force-hshift}"
 606                " and @code{horizontal-shift}.",
 607
 608                /* properties */
 609                "merge-differently-dotted "
 610                "merge-differently-headed "
 611                "positioning-done "
 612                "prefer-dotted-right "
 613               );