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 = unsmob<Grob> (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 = unsmob<Grob> (head_up->get_object ("dot"));
 311       Grob *parent = d->get_parent (X_AXIS);
 312       if (has_interface<Dot_column> (parent))
 313         Side_position_interface::add_support (parent, head_down);
 314     }
 315   else if (Rhythmic_head::dot_count (head_down))
 316     {
 317       Grob *d = unsmob<Grob> (head_down->get_object ("dot"));
 318       Grob *parent = d->get_parent (X_AXIS);
 319       if (has_interface<Dot_column> (parent))
 320         {
 321           Grob *stem = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = 0.0;
 396
 397   vector<Real> amounts;
 398   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 399     {
 400       Grob *s = unsmob<Grob> (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     }
 406   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 407     {
 408       Grob *s = unsmob<Grob> (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 (has_interface<Note_column> (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
 507             {
 508               bool explicit_shift = scm_is_number (sh);
 509               if (!explicit_shift)
 510                 col->warning (_ ("this Voice needs a \\voiceXx or \\shiftXx setting"));
 511
 512               if (explicit_shift && shifts[i] == shifts[i - 1])
 513                 ; // Match the previous notecolumn offset
 514               else if (extents[d][i][UP] > extents[d][i - 1][DOWN]
 515                        && extents[d][i][DOWN] < extents[d][i - 1][UP])
 516                 offset += 1.0; // fully clear the previous-notecolumn heads
 517               else if (d * extents[d][i][-d] >= d * extents[d][i - 1][d])
 518                 offset += Stem::is_valid_stem (stems[d][i - 1])
 519                           ? 1.0 : 0.5; // we cross the previous notecolumn
 520               else if (Stem::is_valid_stem (stems[d][i]))
 521                 offset += 0.5;
 522
 523               // check if we cross the opposite-stemmed voices
 524               if (d * extents[d][i][-d] < d * extent_union[-d][d])
 525                 offset = max (offset, 0.5);
 526               if (extents[-d].size ()
 527                   && extents[d][i][UP] > extents[-d][0][DOWN]
 528                   && extents[d][i][DOWN] < extents[-d][0][UP])
 529                 offset = max (offset, 1.0);
 530             }
 531           offsets[d].push_back (d * offset);
 532         }
 533     }
 534
 535   /*
 536     see input/regression/dot-up-voice-collision.ly
 537   */
 538   for (vsize i = 0; i < clash_groups[UP].size (); i++)
 539     {
 540       Grob *g = clash_groups[UP][i];
 541       Grob *dc = Note_column::dot_column (g);
 542
 543       if (dc)
 544         for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
 545           Side_position_interface::add_support (dc, stems[UP][j]);
 546     }
 547
 548   for (UP_and_DOWN (d))
 549     {
 550       for (vsize i = 0; i < clash_groups[d].size (); i++)
 551         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 552                                    scm_from_double (offsets[d][i])),
 553                          tups);
 554     }
 555
 556   return tups;
 557 }
 558
 559 SCM
 560 Note_collision_interface::forced_shift (Grob *me)
 561 {
 562   SCM tups = SCM_EOL;
 563
 564   extract_grob_set (me, "elements", elements);
 565   for (vsize i = 0; i < elements.size (); i++)
 566     {
 567       Grob *se = elements[i];
 568
 569       SCM force = se->get_property ("force-hshift");
 570       if (scm_is_number (force))
 571         tups = scm_cons (scm_cons (se->self_scm (), force),
 572                          tups);
 573     }
 574   return tups;
 575 }
 576
 577 void
 578 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 579 {
 580   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 581   Axis_group_interface::add_element (me, ncol);
 582 }
 583
 584 vector<int>
 585 Note_collision_interface::note_head_positions (Grob *me)
 586 {
 587   vector<int> out;
 588   extract_grob_set (me, "elements", elts);
 589   for (vsize i = 0; i < elts.size (); i++)
 590     if (Grob *stem = unsmob<Grob> (elts[i]->get_object ("stem")))
 591       {
 592         vector<int> nhp = Stem::note_head_positions (stem);
 593         out.insert (out.end (), nhp.begin (), nhp.end ());
 594       }
 595
 596   vector_sort (out, less<int> ());
 597   return out;
 598 }
 599
 600 ADD_INTERFACE (Note_collision_interface,
 601                "An object that handles collisions between notes with"
 602                " different stem directions and horizontal shifts.  Most of"
 603                " the interesting properties are to be set in"
 604                " @ref{note-column-interface}: these are @code{force-hshift}"
 605                " and @code{horizontal-shift}.",
 606
 607                /* properties */
 608                "merge-differently-dotted "
 609                "merge-differently-headed "
 610                "positioning-done "
 611                "prefer-dotted-right "
 612               );