lily/note-collision.cc

   1 /*
   2   note-collision.cc -- implement Note_collision
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1997--2009 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #include "note-collision.hh"
  10
  11 #include "axis-group-interface.hh"
  12 #include "dot-column.hh"
  13 #include "international.hh"
  14 #include "note-column.hh"
  15 #include "note-head.hh"
  16 #include "output-def.hh"
  17 #include "pointer-group-interface.hh"
  18 #include "item.hh"
  19 #include "rhythmic-head.hh"
  20 #include "staff-symbol-referencer.hh"
  21 #include "side-position-interface.hh"
  22 #include "stem.hh"
  23 #include "warn.hh"
  24
  25
  26 void
  27 check_meshing_chords (Grob *me,
  28                       Drul_array<vector<Real> > *offsets,
  29                       Drul_array<vector<Slice> > const &extents,
  30                       Drul_array<vector<Grob*> > const &clash_groups)
  31
  32 {
  33   if (!extents[UP].size () || !extents[DOWN].size ())
  34     return;
  35
  36   Grob *clash_up = clash_groups[UP][0];
  37   Grob *clash_down = clash_groups[DOWN][0];
  38
  39   /* Every note column should have a stem, but avoid a crash. */
  40   if (!Note_column::get_stem (clash_up) || !Note_column::get_stem (clash_down))
  41     return;
  42
  43   Drul_array<Grob*> stems (Note_column::get_stem (clash_down),
  44                            Note_column::get_stem (clash_up));
  45
  46   Grob *head_up = Note_column::first_head (clash_up);
  47   Grob *head_down = Note_column::first_head (clash_down);
  48
  49   vector<int> ups = Stem::note_head_positions (Note_column::get_stem (clash_up));
  50   vector<int> dps = Stem::note_head_positions (Note_column::get_stem (clash_down));
  51
  52   /* Too far apart to collide. */
  53   if (ups[0] > dps.back () + 1)
  54     return;
  55
  56   /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
  57      above the "stem-down-note". */
  58   bool merge_possible = (ups[0] >= dps[0]) && (ups.back () >= dps.back ());
  59
  60   /* Do not merge notes typeset in different style. */
  61   if (!ly_is_equal (head_up->get_property ("style"),
  62                     head_down->get_property ("style")))
  63     merge_possible = false;
  64
  65   int up_ball_type = Rhythmic_head::duration_log (head_up);
  66   int down_ball_type = Rhythmic_head::duration_log (head_down);
  67
  68   /* Do not merge whole notes (or longer, like breve, longa, maxima). */
  69   if (merge_possible && (up_ball_type <= 0 || down_ball_type <= 0))
  70     merge_possible = false;
  71
  72   if (merge_possible
  73       && Rhythmic_head::dot_count (head_up) != Rhythmic_head::dot_count (head_down)
  74       && !to_boolean (me->get_property ("merge-differently-dotted")))
  75     merge_possible = false;
  76
  77   /* Can only merge different heads if merge-differently-headed is set. */
  78   if (merge_possible
  79       && up_ball_type != down_ball_type
  80       && !to_boolean (me->get_property ("merge-differently-headed")))
  81     merge_possible = false;
  82
  83   /* Should never merge quarter and half notes, as this would make
  84      them indistinguishable.  */
  85   if (merge_possible
  86       && ((Stem::duration_log (stems[UP]) == 1
  87            && Stem::duration_log (stems[DOWN]) == 2)
  88           || (Stem::duration_log (stems[UP]) == 2
  89               && Stem::duration_log (stems[DOWN]) == 1)))
  90     merge_possible = false;
  91
  92   /*
  93     this case (distant half collide),
  94
  95     |
  96     x |
  97     | x
  98     |
  99
 100     the noteheads may be closer than this case (close half collide)
 101
 102     |
 103     |
 104     x
 105     x
 106     |
 107     |
 108
 109   */
 110
 111   /* TODO: filter out the 'o's in this configuration, since they're no
 112      part in the collision.
 113
 114      |
 115      x|o
 116      x|o
 117      x
 118
 119   */
 120
 121   bool close_half_collide = false;
 122   bool distant_half_collide = false;
 123   bool full_collide = false;
 124
 125   for (vsize i = 0, j = 0; i < ups.size () && j < dps.size (); )
 126     {
 127       if (abs (ups[i] - dps[j]) == 1)
 128         {
 129           merge_possible = false;
 130           if (ups[i] > dps[j])
 131             close_half_collide = true;
 132           else
 133             distant_half_collide = true;
 134         }
 135       else if (ups[i] == dps[j])
 136         full_collide = true;
 137       else if (ups[i] > dps[0] && ups[i] < dps.back ())
 138         merge_possible = false;
 139       else if (dps[j] > ups[0] && dps[j] < ups.back ())
 140         merge_possible = false;
 141
 142       if (ups[i] < dps[j])
 143         i++;
 144       else if (ups[i] > dps[j])
 145         j++;
 146       else
 147         {
 148           i++;
 149           j++;
 150         }
 151     }
 152
 153   full_collide = full_collide || (close_half_collide
 154                                   && distant_half_collide);
 155
 156   Real shift_amount = 1;
 157
 158   bool touch = (ups[0] >= dps.back ());
 159   /* As a special case, if the topmost part of the downstem chord is a second,
 160      the top note of which is the same pitch as the lowest upstem note, they
 161      shouldn't count as touching.
 162   */
 163   if (dps.back () == ups[0] && dps.size () > 1 && dps[dps.size() - 2] == ups[0] - 1)
 164     touch = false;
 165
 166   if (touch)
 167     shift_amount *= -1;
 168
 169   /* For full collisions, the right hand head may obscure dots, so
 170      make sure the dotted heads go to the right. */
 171   bool stem_to_stem = false;
 172   if (full_collide)
 173     {
 174       if (Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
 175         shift_amount = 1;
 176       else if (Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
 177         stem_to_stem = true;
 178     }
 179
 180   /* The solfa is a triangle, which is inverted depending on stem
 181      direction.  In case of a collision, one of them should be removed,
 182      so the resulting note does not look like a block.
 183   */
 184   if (merge_possible
 185       && head_up->get_property ("style") == ly_symbol2scm ("fa")
 186       && head_down->get_property ("style") == ly_symbol2scm ("fa"))
 187     {
 188       Interval uphead_size = head_up->extent (head_up, Y_AXIS);
 189       Offset att = Offset (0.0, -1.0);
 190       head_up->set_property ("stem-attachment", ly_offset2scm (att));
 191       head_up->set_property ("transparent", SCM_BOOL_T);
 192     }
 193
 194   if (merge_possible)
 195     {
 196       shift_amount = 0;
 197
 198       /* If possible, don't wipe any heads.  Else, wipe shortest head,
 199          or head with smallest amount of dots.  Note: when merging
 200          different heads, dots on the smaller one disappear. */
 201       Grob *wipe_ball = 0;
 202       Grob *dot_wipe_head = head_up;
 203
 204       if (up_ball_type == down_ball_type)
 205         {
 206           if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
 207             {
 208               wipe_ball = head_down;
 209               dot_wipe_head = head_down;
 210             }
 211           else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
 212             {
 213               dot_wipe_head = head_up;
 214               wipe_ball = head_up;
 215             }
 216           else
 217             dot_wipe_head = head_up;
 218         }
 219       else if (down_ball_type > up_ball_type)
 220         {
 221           wipe_ball = head_down;
 222           dot_wipe_head = head_down;
 223         }
 224       else if (down_ball_type < up_ball_type)
 225         {
 226           wipe_ball = head_up;
 227           dot_wipe_head = head_up;
 228           /*
 229             If upper head is eighth note or shorter, and lower head is half note,
 230             shift by the difference between the open and filled note head widths,
 231             otherwise upper stem will be misaligned slightly.
 232           */
 233           if (Stem::duration_log (stems[DOWN]) == 1
 234               && Stem::duration_log (stems[UP]) >= 3)
 235             shift_amount = (1 - head_up->extent (head_up, X_AXIS).length () /
 236                             head_down->extent (head_down, X_AXIS).length ()) * 0.5;
 237         }
 238
 239       if (dot_wipe_head)
 240         {
 241           if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
 242             d->suicide ();
 243         }
 244
 245       if (wipe_ball && wipe_ball->is_live ())
 246         wipe_ball->set_property ("transparent", SCM_BOOL_T);
 247     }
 248   /* TODO: these numbers are magic; should devise a set of grob props
 249      to tune this behavior. */
 250   else if (stem_to_stem)
 251     shift_amount = -abs (shift_amount) * 0.65;
 252   else if (close_half_collide && !touch)
 253     shift_amount *= 0.52;
 254   else if (distant_half_collide && !touch)
 255     shift_amount *= 0.4;
 256   else if (distant_half_collide || close_half_collide || full_collide)
 257     shift_amount *= 0.5;
 258
 259   /* we're meshing. */
 260   else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
 261     shift_amount *= 0.1;
 262   else
 263     shift_amount *= 0.17;
 264
 265   /*
 266
 267   */
 268   if (full_collide
 269       && down_ball_type * up_ball_type == 0)
 270     {
 271       if (up_ball_type == 0 && down_ball_type == 1)
 272         shift_amount *= 1.25;
 273       else if (up_ball_type == 0 && down_ball_type == 2)
 274         shift_amount *= 1.35;
 275       else if (down_ball_type == 0 && up_ball_type == 1)
 276         shift_amount *= 0.7;
 277       else if (down_ball_type == 0 && up_ball_type == 2)
 278         shift_amount *= 0.75;
 279     }
 280
 281   /*
 282    * Fix issue #44:
 283    *
 284    * Dots from left note head collide with right note head. Only occurs
 285    * with a close half collide, if the left note head is between
 286    * lines and the right note head is on a line, and if right note head
 287    * hasn't got any dots.
 288    */
 289   if (close_half_collide
 290       && Rhythmic_head::dot_count (head_up)
 291       && !Rhythmic_head::dot_count (head_down))
 292     {
 293       Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
 294       if (!Staff_symbol_referencer::on_line (staff, ups[0]))
 295         {
 296           /*
 297             TODO: consider junking the else body.
 298           */
 299           if (to_boolean (me->get_property ("prefer-dotted-right")))
 300             shift_amount = 0.5;
 301           else
 302             {
 303               Grob *d = unsmob_grob (head_up->get_object ("dot"));
 304               Grob *parent = d->get_parent (X_AXIS);
 305               if (Dot_column::has_interface (parent))
 306                 Side_position_interface::add_support (parent, head_down);
 307             }
 308         }
 309     }
 310
 311   /* For full or close half collisions, the right hand head may
 312      obscure dots.  Move dots to the right. */
 313   if (abs (shift_amount) > 1e-6
 314       && Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up)
 315       && (full_collide || close_half_collide))
 316     {
 317       Grob *d = unsmob_grob (head_down->get_object ("dot"));
 318       Grob *parent = d->get_parent (X_AXIS);
 319
 320       /*
 321         FIXME:
 322
 323         |
 324         x . o
 325         |
 326
 327
 328         the . is put right of o which is erroneous o force-shifted
 329         far to the right.
 330       */
 331       if (Dot_column::has_interface (parent))
 332         {
 333           Grob *stem = unsmob_grob (head_up->get_object ("stem"));
 334           extract_grob_set (stem, "note-heads", heads);
 335           for (vsize i = 0; i < heads.size (); i++)
 336             Side_position_interface::add_support (parent, heads[i]);
 337         }
 338     }
 339
 340   Direction d = UP;
 341   do
 342     {
 343       for (vsize i = 0; i < clash_groups[d].size (); i++)
 344         (*offsets)[d][i] += d * shift_amount;
 345     }
 346   while ((flip (&d)) != UP);
 347 }
 348
 349
 350 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
 351 SCM
 352 Note_collision_interface::calc_positioning_done (SCM smob)
 353 {
 354   Grob *me = unsmob_grob (smob);
 355   me->set_property ("positioning-done", SCM_BOOL_T);
 356
 357   Drul_array<vector<Grob*> > clash_groups = get_clash_groups (me);
 358
 359   Direction d = UP;
 360   do
 361     {
 362       for (vsize i = clash_groups[d].size (); i--; )
 363         {
 364           /*
 365             Trigger positioning
 366           */
 367           clash_groups[d][i]->extent (me, X_AXIS);
 368         }
 369     }
 370   while (flip (&d) != UP);
 371
 372   SCM autos (automatic_shift (me, clash_groups));
 373   SCM hand (forced_shift (me));
 374
 375   Real wid = 0.0;
 376   do
 377     {
 378       if (clash_groups[d].size ())
 379         {
 380           Grob *h = clash_groups[d][0];
 381           Grob *fh = Note_column::first_head (h);
 382           if (fh)
 383             wid = fh->extent (h, X_AXIS).length ();
 384         }
 385     }
 386   while (flip (&d) != UP);
 387
 388   vector<Grob*> done;
 389   Real left_most = 1e6;
 390
 391   vector<Real> amounts;
 392   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 393     {
 394       Grob *s = unsmob_grob (scm_caar (hand));
 395       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 396
 397       done.push_back (s);
 398       amounts.push_back (amount);
 399       if (amount < left_most)
 400         left_most = amount;
 401     }
 402   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 403     {
 404       Grob *s = unsmob_grob (scm_caar (autos));
 405       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 406
 407       vsize x = find (done, s) - done.begin ();
 408       if (x == VPOS || x >= done.size ())
 409         {
 410           done.push_back (s);
 411           amounts.push_back (amount);
 412           if (amount < left_most)
 413             left_most = amount;
 414         }
 415     }
 416
 417   for (vsize i = 0; i < amounts.size (); i++)
 418     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 419
 420   return SCM_BOOL_T;
 421 }
 422
 423 Drul_array < vector<Grob*> >
 424 Note_collision_interface::get_clash_groups (Grob *me)
 425 {
 426   Drul_array<vector<Grob*> > clash_groups;
 427
 428   extract_grob_set (me, "elements", elements);
 429   for (vsize i = 0; i < elements.size (); i++)
 430     {
 431       Grob *se = elements[i];
 432       if (Note_column::has_interface (se))
 433         {
 434           if (!Note_column::dir (se))
 435             se->programming_error ("note-column has no direction");
 436           else
 437             clash_groups[Note_column::dir (se)].push_back (se);
 438         }
 439     }
 440
 441   Direction d = UP;
 442   do
 443     {
 444       vector<Grob*> &clashes (clash_groups[d]);
 445       vector_sort (clashes, Note_column::shift_less);
 446     }
 447   while ((flip (&d)) != UP);
 448
 449   return clash_groups;
 450 }
 451
 452 /*
 453   This complicated routine moves note columns around horizontally to
 454   ensure that notes don't clash.
 455 */
 456 SCM
 457 Note_collision_interface::automatic_shift (Grob *me,
 458                                            Drul_array<vector<Grob*> > clash_groups)
 459 {
 460   Drul_array < vector<int> > shifts;
 461   SCM tups = SCM_EOL;
 462
 463   Direction d = UP;
 464   do
 465     {
 466       vector<int> &shift (shifts[d]);
 467       vector<Grob*> &clashes (clash_groups[d]);
 468
 469       for (vsize i = 0; i < clashes.size (); i++)
 470         {
 471           SCM sh
 472             = clashes[i]->get_property ("horizontal-shift");
 473
 474           if (scm_is_number (sh))
 475             shift.push_back (scm_to_int (sh));
 476           else
 477             shift.push_back (0);
 478         }
 479
 480       for (vsize i = 1; i < shift.size (); i++)
 481         {
 482           if (shift[i - 1] == shift[i])
 483             {
 484               clashes[0]->warning (_ ("ignoring too many clashing note columns"));
 485               return tups;
 486             }
 487         }
 488     }
 489   while ((flip (&d)) != UP);
 490
 491   Drul_array<vector<Slice> > extents;
 492   Drul_array<vector<Real> > offsets;
 493   d = UP;
 494   do
 495     {
 496       for (vsize i = 0; i < clash_groups[d].size (); i++)
 497         {
 498           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 499           s[LEFT]--;
 500           s[RIGHT]++;
 501           extents[d].push_back (s);
 502           offsets[d].push_back (d * 0.5 * i);
 503         }
 504     }
 505   while ((flip (&d)) != UP);
 506
 507   /*
 508     do horizontal shifts of each direction
 509
 510     |
 511     x||
 512     x||
 513     x|
 514   */
 515
 516   do
 517     {
 518       for (vsize i = 1; i < clash_groups[d].size (); i++)
 519         {
 520           Slice prev = extents[d][i - 1];
 521           prev.intersect (extents[d][i]);
 522           if (prev.length () > 0
 523               || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 524             for (vsize j = i; j < clash_groups[d].size (); j++)
 525               offsets[d][j] += d * 0.5;
 526         }
 527     }
 528   while ((flip (&d)) != UP);
 529
 530
 531   /*
 532     see input/regression/dot-up-voice-collision.ly
 533   */
 534   for (vsize i = 0; i < clash_groups[UP].size (); i++)
 535     {
 536       Grob *g = clash_groups[UP][i];
 537       Grob *dc = Note_column::dot_column (g);
 538
 539       if (dc)
 540         for (vsize j = i + 1;  j < clash_groups[UP].size (); j++)
 541           {
 542             Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
 543             Side_position_interface::add_support (dc, stem);
 544           }
 545     }
 546
 547   /*
 548     Check if chords are meshing
 549   */
 550
 551   check_meshing_chords (me, &offsets, extents, clash_groups);
 552
 553   do
 554     {
 555       for (vsize i = 0; i < clash_groups[d].size (); i++)
 556         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 557                                    scm_from_double (offsets[d][i])),
 558                          tups);
 559     }
 560   while (flip (&d) != UP);
 561
 562   return tups;
 563 }
 564
 565 SCM
 566 Note_collision_interface::forced_shift (Grob *me)
 567 {
 568   SCM tups = SCM_EOL;
 569
 570   extract_grob_set (me, "elements", elements);
 571   for (vsize i = 0; i < elements.size (); i++)
 572     {
 573       Grob *se = elements[i];
 574
 575       SCM force = se->get_property ("force-hshift");
 576       if (scm_is_number (force))
 577         tups = scm_cons (scm_cons (se->self_scm (), force),
 578                          tups);
 579     }
 580   return tups;
 581 }
 582
 583 void
 584 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 585 {
 586   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 587   Axis_group_interface::add_element (me, ncol);
 588 }
 589
 590 ADD_INTERFACE (Note_collision_interface,
 591                "An object that handles collisions between notes with"
 592                " different stem directions and horizontal shifts.  Most of"
 593                " the interesting properties are to be set in"
 594                " @ref{note-column-interface}: these are @code{force-hshift}"
 595                " and @code{horizontal-shift}.",
 596
 597                /* properties */
 598                "merge-differently-dotted "
 599                "merge-differently-headed "
 600                "positioning-done "
 601                "prefer-dotted-right "
 602                );