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