lily/note-collision.cc

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