lily/note-collision.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1997--2009 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   if (merge_possible
 196       && head_up->get_property ("style") == ly_symbol2scm ("fa")
 197       && head_down->get_property ("style") == ly_symbol2scm ("fa"))
 198     {
 199       Interval uphead_size = head_up->extent (head_up, Y_AXIS);
 200       Offset att = Offset (0.0, -1.0);
 201       head_up->set_property ("stem-attachment", ly_offset2scm (att));
 202       head_up->set_property ("transparent", SCM_BOOL_T);
 203     }
 204
 205   if (merge_possible)
 206     {
 207       shift_amount = 0;
 208
 209       /* If possible, don't wipe any heads.  Else, wipe shortest head,
 210          or head with smallest amount of dots.  Note: when merging
 211          different heads, dots on the smaller one disappear. */
 212       Grob *wipe_ball = 0;
 213       Grob *dot_wipe_head = head_up;
 214
 215       if (up_ball_type == down_ball_type)
 216         {
 217           if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
 218             {
 219               wipe_ball = head_down;
 220               dot_wipe_head = head_down;
 221             }
 222           else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
 223             {
 224               dot_wipe_head = head_up;
 225               wipe_ball = head_up;
 226             }
 227           else
 228             dot_wipe_head = head_up;
 229         }
 230       else if (down_ball_type > up_ball_type)
 231         {
 232           wipe_ball = head_down;
 233           dot_wipe_head = head_down;
 234         }
 235       else if (down_ball_type < up_ball_type)
 236         {
 237           wipe_ball = head_up;
 238           dot_wipe_head = head_up;
 239           /*
 240             If upper head is eighth note or shorter, and lower head is half note,
 241             shift by the difference between the open and filled note head widths,
 242             otherwise upper stem will be misaligned slightly.
 243           */
 244           if (Stem::duration_log (stems[DOWN]) == 1
 245               && Stem::duration_log (stems[UP]) >= 3)
 246             shift_amount = (1 - head_up->extent (head_up, X_AXIS).length () /
 247                             head_down->extent (head_down, X_AXIS).length ()) * 0.5;
 248         }
 249
 250       if (dot_wipe_head)
 251         {
 252           if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
 253             d->suicide ();
 254         }
 255
 256       if (wipe_ball && wipe_ball->is_live ())
 257         wipe_ball->set_property ("transparent", SCM_BOOL_T);
 258     }
 259   /* TODO: these numbers are magic; should devise a set of grob props
 260      to tune this behavior. */
 261   else if (stem_to_stem)
 262     shift_amount = -abs (shift_amount) * 0.65;
 263   else if (close_half_collide && !touch)
 264     shift_amount *= 0.52;
 265   else if (distant_half_collide && !touch)
 266     shift_amount *= 0.4;
 267   else if (distant_half_collide || close_half_collide || full_collide)
 268     shift_amount *= 0.5;
 269
 270   /* we're meshing. */
 271   else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
 272     shift_amount *= 0.1;
 273   else
 274     shift_amount *= 0.17;
 275
 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
 361 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
 362 SCM
 363 Note_collision_interface::calc_positioning_done (SCM smob)
 364 {
 365   Grob *me = unsmob_grob (smob);
 366   me->set_property ("positioning-done", SCM_BOOL_T);
 367
 368   Drul_array<vector<Grob*> > clash_groups = get_clash_groups (me);
 369
 370   Direction d = UP;
 371   do
 372     {
 373       for (vsize i = clash_groups[d].size (); i--; )
 374         {
 375           /*
 376             Trigger positioning
 377           */
 378           clash_groups[d][i]->extent (me, X_AXIS);
 379         }
 380     }
 381   while (flip (&d) != UP);
 382
 383   SCM autos (automatic_shift (me, clash_groups));
 384   SCM hand (forced_shift (me));
 385
 386   Real wid = 0.0;
 387   do
 388     {
 389       if (clash_groups[d].size ())
 390         {
 391           Grob *h = clash_groups[d][0];
 392           Grob *fh = Note_column::first_head (h);
 393           if (fh)
 394             wid = fh->extent (h, X_AXIS).length ();
 395         }
 396     }
 397   while (flip (&d) != UP);
 398
 399   vector<Grob*> done;
 400   Real left_most = 1e6;
 401
 402   vector<Real> amounts;
 403   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 404     {
 405       Grob *s = unsmob_grob (scm_caar (hand));
 406       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 407
 408       done.push_back (s);
 409       amounts.push_back (amount);
 410       if (amount < left_most)
 411         left_most = amount;
 412     }
 413   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 414     {
 415       Grob *s = unsmob_grob (scm_caar (autos));
 416       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 417
 418       vsize x = find (done, s) - done.begin ();
 419       if (x == VPOS || x >= done.size ())
 420         {
 421           done.push_back (s);
 422           amounts.push_back (amount);
 423           if (amount < left_most)
 424             left_most = amount;
 425         }
 426     }
 427
 428   for (vsize i = 0; i < amounts.size (); i++)
 429     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 430
 431   return SCM_BOOL_T;
 432 }
 433
 434 Drul_array < vector<Grob*> >
 435 Note_collision_interface::get_clash_groups (Grob *me)
 436 {
 437   Drul_array<vector<Grob*> > clash_groups;
 438
 439   extract_grob_set (me, "elements", elements);
 440   for (vsize i = 0; i < elements.size (); i++)
 441     {
 442       Grob *se = elements[i];
 443       if (Note_column::has_interface (se))
 444         {
 445           if (!Note_column::dir (se))
 446             se->programming_error ("note-column has no direction");
 447           else
 448             clash_groups[Note_column::dir (se)].push_back (se);
 449         }
 450     }
 451
 452   Direction d = UP;
 453   do
 454     {
 455       vector<Grob*> &clashes (clash_groups[d]);
 456       vector_sort (clashes, Note_column::shift_less);
 457     }
 458   while ((flip (&d)) != UP);
 459
 460   return clash_groups;
 461 }
 462
 463 /*
 464   This complicated routine moves note columns around horizontally to
 465   ensure that notes don't clash.
 466 */
 467 SCM
 468 Note_collision_interface::automatic_shift (Grob *me,
 469                                            Drul_array<vector<Grob*> > clash_groups)
 470 {
 471   Drul_array < vector<int> > shifts;
 472   SCM tups = SCM_EOL;
 473
 474   Direction d = UP;
 475   do
 476     {
 477       vector<int> &shift (shifts[d]);
 478       vector<Grob*> &clashes (clash_groups[d]);
 479
 480       for (vsize i = 0; i < clashes.size (); i++)
 481         {
 482           SCM sh
 483             = clashes[i]->get_property ("horizontal-shift");
 484
 485           if (scm_is_number (sh))
 486             shift.push_back (scm_to_int (sh));
 487           else
 488             shift.push_back (0);
 489         }
 490
 491       for (vsize i = 1; i < shift.size (); i++)
 492         {
 493           if (shift[i - 1] == shift[i])
 494             {
 495               clashes[0]->warning (_ ("ignoring too many clashing note columns"));
 496               return tups;
 497             }
 498         }
 499     }
 500   while ((flip (&d)) != UP);
 501
 502   Drul_array<vector<Slice> > extents;
 503   Drul_array<vector<Real> > offsets;
 504   d = UP;
 505   do
 506     {
 507       for (vsize i = 0; i < clash_groups[d].size (); i++)
 508         {
 509           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 510           s[LEFT]--;
 511           s[RIGHT]++;
 512           extents[d].push_back (s);
 513           offsets[d].push_back (d * 0.5 * i);
 514         }
 515     }
 516   while ((flip (&d)) != UP);
 517
 518   /*
 519     do horizontal shifts of each direction
 520
 521     |
 522     x||
 523     x||
 524     x|
 525   */
 526
 527   do
 528     {
 529       for (vsize i = 1; i < clash_groups[d].size (); i++)
 530         {
 531           Slice prev = extents[d][i - 1];
 532           prev.intersect (extents[d][i]);
 533           if (prev.length () > 0
 534               || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 535             for (vsize j = i; j < clash_groups[d].size (); j++)
 536               offsets[d][j] += d * 0.5;
 537         }
 538     }
 539   while ((flip (&d)) != UP);
 540
 541
 542   /*
 543     see input/regression/dot-up-voice-collision.ly
 544   */
 545   for (vsize i = 0; i < clash_groups[UP].size (); i++)
 546     {
 547       Grob *g = clash_groups[UP][i];
 548       Grob *dc = Note_column::dot_column (g);
 549
 550       if (dc)
 551         for (vsize j = i + 1;  j < clash_groups[UP].size (); j++)
 552           {
 553             Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
 554             Side_position_interface::add_support (dc, stem);
 555           }
 556     }
 557
 558   /*
 559     Check if chords are meshing
 560   */
 561
 562   check_meshing_chords (me, &offsets, extents, clash_groups);
 563
 564   do
 565     {
 566       for (vsize i = 0; i < clash_groups[d].size (); i++)
 567         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 568                                    scm_from_double (offsets[d][i])),
 569                          tups);
 570     }
 571   while (flip (&d) != UP);
 572
 573   return tups;
 574 }
 575
 576 SCM
 577 Note_collision_interface::forced_shift (Grob *me)
 578 {
 579   SCM tups = SCM_EOL;
 580
 581   extract_grob_set (me, "elements", elements);
 582   for (vsize i = 0; i < elements.size (); i++)
 583     {
 584       Grob *se = elements[i];
 585
 586       SCM force = se->get_property ("force-hshift");
 587       if (scm_is_number (force))
 588         tups = scm_cons (scm_cons (se->self_scm (), force),
 589                          tups);
 590     }
 591   return tups;
 592 }
 593
 594 void
 595 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 596 {
 597   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 598   Axis_group_interface::add_element (me, ncol);
 599 }
 600
 601 ADD_INTERFACE (Note_collision_interface,
 602                "An object that handles collisions between notes with"
 603                " different stem directions and horizontal shifts.  Most of"
 604                " the interesting properties are to be set in"
 605                " @ref{note-column-interface}: these are @code{force-hshift}"
 606                " and @code{horizontal-shift}.",
 607
 608                /* properties */
 609                "merge-differently-dotted "
 610                "merge-differently-headed "
 611                "positioning-done "
 612                "prefer-dotted-right "
 613                );