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