lily/note-collision.cc

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