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