lily/note-collision.cc

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