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