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   Real shift_amount = 1;
 167
 168   bool touch = (ups[0] >= dps.back ());
 169   /* As a special case, if the topmost part of the downstem chord is a second,
 170      the top note of which is the same pitch as the lowest upstem note, they
 171      shouldn't count as touching.
 172   */
 173   if (dps.back () == ups[0] && dps.size () > 1 && dps[dps.size () - 2] == ups[0] - 1)
 174     touch = false;
 175
 176   if (touch)
 177     shift_amount *= -1;
 178
 179   /* For full collisions, the right hand head may obscure dots, so
 180      make sure the dotted heads go to the right. */
 181   bool stem_to_stem = false;
 182   if (full_collide)
 183     {
 184       if (Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
 185         shift_amount = 1;
 186       else if (Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
 187         stem_to_stem = true;
 188     }
 189
 190   /* The solfa is a triangle, which is inverted depending on stem
 191      direction.  In case of a collision, one of them should be removed,
 192      so the resulting note does not look like a block.
 193   */
 194   SCM up_style = head_up->get_property ("style");
 195   SCM down_style = head_down->get_property ("style");
 196   if (merge_possible
 197       && (up_style == ly_symbol2scm ("fa") || up_style == ly_symbol2scm ("faThin"))
 198       && (down_style == ly_symbol2scm ("fa") || down_style == ly_symbol2scm ("faThin")))
 199     {
 200       Interval uphead_size = head_up->extent (head_up, Y_AXIS);
 201       Offset att = Offset (0.0, -1.0);
 202       head_up->set_property ("stem-attachment", ly_offset2scm (att));
 203       head_up->set_property ("transparent", SCM_BOOL_T);
 204     }
 205
 206   if (merge_possible)
 207     {
 208       shift_amount = 0;
 209
 210       /* If possible, don't wipe any heads.  Else, wipe shortest head,
 211          or head with smallest amount of dots.  Note: when merging
 212          different heads, dots on the smaller one disappear. */
 213       Grob *wipe_ball = 0;
 214       Grob *dot_wipe_head = head_up;
 215
 216       if (up_ball_type == down_ball_type)
 217         {
 218           if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
 219             {
 220               wipe_ball = head_down;
 221               dot_wipe_head = head_down;
 222             }
 223           else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
 224             {
 225               dot_wipe_head = head_up;
 226               wipe_ball = head_up;
 227             }
 228           else
 229             dot_wipe_head = head_up;
 230         }
 231       else if (down_ball_type > up_ball_type)
 232         {
 233           wipe_ball = head_down;
 234           dot_wipe_head = head_down;
 235         }
 236       else if (down_ball_type < up_ball_type)
 237         {
 238           wipe_ball = head_up;
 239           dot_wipe_head = head_up;
 240           /*
 241             If upper head is eighth note or shorter, and lower head is half note,
 242             shift by the difference between the open and filled note head widths,
 243             otherwise upper stem will be misaligned slightly.
 244           */
 245           if (Stem::duration_log (stems[DOWN]) == 1
 246               && Stem::duration_log (stems[UP]) >= 3)
 247             shift_amount = (1 - head_up->extent (head_up, X_AXIS).length ()
 248                             / head_down->extent (head_down, X_AXIS).length ()) * 0.5;
 249         }
 250
 251       if (dot_wipe_head)
 252         {
 253           if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
 254             d->suicide ();
 255         }
 256
 257       if (wipe_ball && wipe_ball->is_live ())
 258         wipe_ball->set_property ("transparent", SCM_BOOL_T);
 259     }
 260   /* TODO: these numbers are magic; should devise a set of grob props
 261      to tune this behavior. */
 262   else if (stem_to_stem)
 263     shift_amount = -abs (shift_amount) * 0.65;
 264   else if (close_half_collide && !touch)
 265     shift_amount *= 0.52;
 266   else if (distant_half_collide && !touch)
 267     shift_amount *= 0.4;
 268   else if (distant_half_collide || close_half_collide || full_collide)
 269     shift_amount *= 0.5;
 270
 271   /* we're meshing. */
 272   else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
 273     shift_amount *= 0.1;
 274   else
 275     shift_amount *= 0.17;
 276
 277   /*
 278   */
 279   if (full_collide
 280       && down_ball_type *up_ball_type == 0)
 281     {
 282       if (up_ball_type == 0 && down_ball_type == 1)
 283         shift_amount *= 1.25;
 284       else if (up_ball_type == 0 && down_ball_type == 2)
 285         shift_amount *= 1.35;
 286       else if (down_ball_type == 0 && up_ball_type == 1)
 287         shift_amount *= 0.7;
 288       else if (down_ball_type == 0 && up_ball_type == 2)
 289         shift_amount *= 0.75;
 290     }
 291
 292   /*
 293    * Fix issue #44:
 294    *
 295    * Dots from left note head collide with right note head. Only occurs
 296    * with a close half collide, if the left note head is between
 297    * lines and the right note head is on a line, and if right note head
 298    * hasn't got any dots.
 299    */
 300   if (close_half_collide
 301       && Rhythmic_head::dot_count (head_up)
 302       && !Rhythmic_head::dot_count (head_down))
 303     {
 304       Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
 305       if (!Staff_symbol_referencer::on_line (staff, ups[0]))
 306         {
 307           /*
 308             TODO: consider junking the else body.
 309           */
 310           if (to_boolean (me->get_property ("prefer-dotted-right")))
 311             shift_amount = 0.5;
 312           else
 313             {
 314               Grob *d = unsmob_grob (head_up->get_object ("dot"));
 315               Grob *parent = d->get_parent (X_AXIS);
 316               if (Dot_column::has_interface (parent))
 317                 Side_position_interface::add_support (parent, head_down);
 318             }
 319         }
 320     }
 321
 322   /* For full or close half collisions, the right hand head may
 323      obscure dots.  Move dots to the right. */
 324   if (abs (shift_amount) > 1e-6
 325       && Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up)
 326       && (full_collide || close_half_collide))
 327     {
 328       Grob *d = unsmob_grob (head_down->get_object ("dot"));
 329       Grob *parent = d->get_parent (X_AXIS);
 330
 331       /*
 332         FIXME:
 333
 334         |
 335         x . o
 336         |
 337
 338
 339         the . is put right of o which is erroneous o force-shifted
 340         far to the right.
 341       */
 342       if (Dot_column::has_interface (parent))
 343         {
 344           Grob *stem = unsmob_grob (head_up->get_object ("stem"));
 345           extract_grob_set (stem, "note-heads", heads);
 346           for (vsize i = 0; i < heads.size (); i++)
 347             Side_position_interface::add_support (parent, heads[i]);
 348         }
 349     }
 350
 351   Direction d = UP;
 352   do
 353     {
 354       for (vsize i = 0; i < clash_groups[d].size (); i++)
 355         (*offsets)[d][i] += d * shift_amount;
 356     }
 357   while ((flip (&d)) != UP);
 358 }
 359
 360 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
 361 SCM
 362 Note_collision_interface::calc_positioning_done (SCM smob)
 363 {
 364   Grob *me = unsmob_grob (smob);
 365   me->set_property ("positioning-done", SCM_BOOL_T);
 366
 367   Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
 368
 369   Direction d = UP;
 370   do
 371     {
 372       for (vsize i = clash_groups[d].size (); i--;)
 373         {
 374           /*
 375             Trigger positioning
 376           */
 377           clash_groups[d][i]->extent (me, X_AXIS);
 378         }
 379     }
 380   while (flip (&d) != UP);
 381
 382   SCM autos (automatic_shift (me, clash_groups));
 383   SCM hand (forced_shift (me));
 384
 385   Real wid = 0.0;
 386   do
 387     {
 388       if (clash_groups[d].size ())
 389         {
 390           Grob *h = clash_groups[d][0];
 391           Grob *fh = Note_column::first_head (h);
 392           if (fh)
 393             wid = fh->extent (h, X_AXIS).length ();
 394         }
 395     }
 396   while (flip (&d) != UP);
 397
 398   vector<Grob *> done;
 399   Real left_most = 1e6;
 400
 401   vector<Real> amounts;
 402   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 403     {
 404       Grob *s = unsmob_grob (scm_caar (hand));
 405       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 406
 407       done.push_back (s);
 408       amounts.push_back (amount);
 409       if (amount < left_most)
 410         left_most = amount;
 411     }
 412   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 413     {
 414       Grob *s = unsmob_grob (scm_caar (autos));
 415       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 416
 417       vsize x = find (done, s) - done.begin ();
 418       if (x == VPOS || x >= done.size ())
 419         {
 420           done.push_back (s);
 421           amounts.push_back (amount);
 422           if (amount < left_most)
 423             left_most = amount;
 424         }
 425     }
 426
 427   for (vsize i = 0; i < amounts.size (); i++)
 428     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 429
 430   return SCM_BOOL_T;
 431 }
 432
 433 Drul_array < vector<Grob *> >
 434 Note_collision_interface::get_clash_groups (Grob *me)
 435 {
 436   Drul_array<vector<Grob *> > clash_groups;
 437
 438   extract_grob_set (me, "elements", elements);
 439   for (vsize i = 0; i < elements.size (); i++)
 440     {
 441       Grob *se = elements[i];
 442       if (Note_column::has_interface (se))
 443         {
 444           if (!Note_column::dir (se))
 445             se->programming_error ("note-column has no direction");
 446           else
 447             clash_groups[Note_column::dir (se)].push_back (se);
 448         }
 449     }
 450
 451   Direction d = UP;
 452   do
 453     {
 454       vector<Grob *> &clashes (clash_groups[d]);
 455       vector_sort (clashes, Note_column::shift_less);
 456     }
 457   while ((flip (&d)) != UP);
 458
 459   return clash_groups;
 460 }
 461
 462 /*
 463   This complicated routine moves note columns around horizontally to
 464   ensure that notes don't clash.
 465 */
 466 SCM
 467 Note_collision_interface::automatic_shift (Grob *me,
 468                                            Drul_array<vector<Grob *> > clash_groups)
 469 {
 470   Drul_array < vector<int> > shifts;
 471   SCM tups = SCM_EOL;
 472
 473   Direction d = UP;
 474   do
 475     {
 476       vector<int> &shift (shifts[d]);
 477       vector<Grob *> &clashes (clash_groups[d]);
 478
 479       for (vsize i = 0; i < clashes.size (); i++)
 480         {
 481           SCM sh
 482             = clashes[i]->get_property ("horizontal-shift");
 483
 484           if (scm_is_number (sh))
 485             shift.push_back (scm_to_int (sh));
 486           else
 487             shift.push_back (0);
 488         }
 489
 490       for (vsize i = 1; i < shift.size (); i++)
 491         {
 492           if (shift[i - 1] == shift[i])
 493             {
 494               clashes[0]->warning (_ ("ignoring too many clashing note columns"));
 495               return tups;
 496             }
 497         }
 498     }
 499   while ((flip (&d)) != UP);
 500
 501   Drul_array<vector<Slice> > extents;
 502   Drul_array<vector<Real> > offsets;
 503   d = UP;
 504   do
 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   while ((flip (&d)) != UP);
 516
 517   /*
 518     do horizontal shifts of each direction
 519
 520     |
 521     x||
 522     x||
 523     x|
 524   */
 525
 526   do
 527     {
 528       for (vsize i = 1; i < clash_groups[d].size (); i++)
 529         {
 530           Slice prev = extents[d][i - 1];
 531           prev.intersect (extents[d][i]);
 532           if (prev.length () > 0
 533               || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 534             for (vsize j = i; j < clash_groups[d].size (); j++)
 535               offsets[d][j] += d * 0.5;
 536         }
 537     }
 538   while ((flip (&d)) != UP);
 539
 540   /*
 541     see input/regression/dot-up-voice-collision.ly
 542   */
 543   for (vsize i = 0; i < clash_groups[UP].size (); i++)
 544     {
 545       Grob *g = clash_groups[UP][i];
 546       Grob *dc = Note_column::dot_column (g);
 547
 548       if (dc)
 549         for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
 550           {
 551             Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
 552             Side_position_interface::add_support (dc, stem);
 553           }
 554     }
 555
 556   /*
 557     Check if chords are meshing
 558   */
 559
 560   check_meshing_chords (me, &offsets, extents, clash_groups);
 561
 562   do
 563     {
 564       for (vsize i = 0; i < clash_groups[d].size (); i++)
 565         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 566                                    scm_from_double (offsets[d][i])),
 567                          tups);
 568     }
 569   while (flip (&d) != UP);
 570
 571   return tups;
 572 }
 573
 574 SCM
 575 Note_collision_interface::forced_shift (Grob *me)
 576 {
 577   SCM tups = SCM_EOL;
 578
 579   extract_grob_set (me, "elements", elements);
 580   for (vsize i = 0; i < elements.size (); i++)
 581     {
 582       Grob *se = elements[i];
 583
 584       SCM force = se->get_property ("force-hshift");
 585       if (scm_is_number (force))
 586         tups = scm_cons (scm_cons (se->self_scm (), force),
 587                          tups);
 588     }
 589   return tups;
 590 }
 591
 592 void
 593 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 594 {
 595   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 596   Axis_group_interface::add_element (me, ncol);
 597 }
 598
 599 ADD_INTERFACE (Note_collision_interface,
 600                "An object that handles collisions between notes with"
 601                " different stem directions and horizontal shifts.  Most of"
 602                " the interesting properties are to be set in"
 603                " @ref{note-column-interface}: these are @code{force-hshift}"
 604                " and @code{horizontal-shift}.",
 605
 606                /* properties */
 607                "merge-differently-dotted "
 608                "merge-differently-headed "
 609                "positioning-done "
 610                "prefer-dotted-right "
 611               );