lily/note-collision.cc

   1 /*
   2   collision.cc -- implement Collision
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1997--2008 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
  78      set. */
  79   if (merge_possible
  80       && up_ball_type != down_ball_type
  81       && !to_boolean (me->get_property ("merge-differently-headed")))
  82     merge_possible = false;
  83
  84   /* Should never merge quarter and half notes, as this would make
  85      them indistinguishable.  */
  86   if (merge_possible
  87       && ((Stem::duration_log (stems[UP]) == 1
  88            && Stem::duration_log (stems[DOWN]) == 2)
  89           || (Stem::duration_log (stems[UP]) == 2
  90               && Stem::duration_log (stems[DOWN]) == 1)))
  91     merge_possible = false;
  92
  93   /*
  94     this case (distant half collide),
  95
  96     |
  97     x |
  98     | x
  99     |
 100
 101     the noteheads may be closer than this case (close half collide)
 102
 103     |
 104     |
 105     x
 106     x
 107     |
 108     |
 109
 110   */
 111
 112   /* TODO: filter out the 'o's in this configuration, since they're no
 113      part in the collision.
 114
 115      |
 116      x|o
 117      x|o
 118      x
 119
 120   */
 121
 122   bool close_half_collide = false;
 123   bool distant_half_collide = false;
 124   bool full_collide = false;
 125
 126   for (vsize i = 0, j = 0; i < ups.size () && j < dps.size (); )
 127     {
 128       if (abs (ups[i] - dps[j]) == 1)
 129         {
 130           merge_possible = false;
 131           if (ups[i] > dps[j])
 132             close_half_collide = true;
 133           else
 134             distant_half_collide = true;
 135         }
 136       else if (ups[i] == dps[j])
 137         full_collide = true;
 138       else if (ups[i] > dps[0] && ups[i] < dps.back ())
 139         merge_possible = false;
 140       else if (dps[j] > ups[0] && dps[j] < ups.back ())
 141         merge_possible = false;
 142
 143       if (ups[i] < dps[j])
 144         i++;
 145       else if (ups[i] > dps[j])
 146         j++;
 147       else
 148         {
 149           i++;
 150           j++;
 151         }
 152     }
 153
 154   full_collide = full_collide || (close_half_collide
 155                                   && distant_half_collide);
 156
 157   Drul_array<Real> center_note_shifts;
 158   center_note_shifts[LEFT] = 0.0;
 159   center_note_shifts[RIGHT] = 0.0;
 160
 161   Real shift_amount = 1;
 162
 163   bool touch = (ups[0] >= dps.back ());
 164   /* As a special case, if the topmost part of the downstem chord is a second,
 165      the top note of which is the same pitch as the lowest upstem note, they
 166      shouldn't count as touching.
 167   */
 168   if (dps.back () == ups[0] && dps.size () > 1 && dps[dps.size() - 2] == ups[0] - 1)
 169     touch = false;
 170
 171   if (touch)
 172     shift_amount *= -1;
 173
 174   /* For full collisions, the right hand head may obscure dots, so
 175      make sure the dotted heads go to the right.  */
 176   bool stem_to_stem = false;
 177   if (full_collide)
 178     {
 179       if (Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
 180         shift_amount = 1;
 181       else if (Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
 182         stem_to_stem = true;
 183     }
 184
 185   /* The solfa is a triangle, which is inverted depending on stem
 186      direction. In case of a collision, one of them should be removed,
 187      so the resulting note does not look like a block.
 188   */
 189   if (merge_possible
 190       && head_up->get_property ("style") == ly_symbol2scm ("fa")
 191       && head_down->get_property ("style") == ly_symbol2scm ("fa"))
 192     {
 193       Interval uphead_size = head_up->extent (head_up, Y_AXIS);
 194       Offset att = Offset (0.0, -1.0);
 195       head_up->set_property ("stem-attachment", ly_offset2scm (att));
 196       head_up->set_property ("transparent", SCM_BOOL_T);
 197     }
 198
 199   if (merge_possible)
 200     {
 201       shift_amount = 0;
 202
 203       /* If possible, don't wipe any heads. Else, wipe shortest head,
 204          or head with smallest amount of dots.  Note: when merging
 205          different heads, dots on the smaller one disappear. */
 206       Grob *wipe_ball = 0;
 207       Grob *dot_wipe_head = head_up;
 208
 209       if (up_ball_type == down_ball_type)
 210         {
 211           if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
 212             {
 213               wipe_ball = head_down;
 214               dot_wipe_head = head_down;
 215             }
 216           else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
 217             {
 218               dot_wipe_head = head_up;
 219               wipe_ball = head_up;
 220             }
 221           else
 222             dot_wipe_head = head_up;
 223         }
 224       else if (down_ball_type > up_ball_type)
 225         {
 226           wipe_ball = head_down;
 227           dot_wipe_head = head_down;
 228         }
 229       else if (down_ball_type < up_ball_type)
 230         {
 231           wipe_ball = head_up;
 232           dot_wipe_head = head_up;
 233         }
 234
 235       if (dot_wipe_head)
 236         {
 237           if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
 238             d->suicide ();
 239         }
 240
 241       if (wipe_ball && wipe_ball->is_live ())
 242         {
 243           wipe_ball->set_property ("transparent", SCM_BOOL_T);
 244         }
 245     }
 246   /* TODO: these numbers are magic; should devise a set of grob props
 247      to tune this behavior.  */
 248   else if (stem_to_stem)
 249     shift_amount = -abs (shift_amount) * 0.65;
 250   else if (close_half_collide && !touch)
 251     shift_amount *= 0.52;
 252   else if (distant_half_collide && !touch)
 253     shift_amount *= 0.4;
 254   else if (distant_half_collide || close_half_collide || full_collide)
 255     shift_amount *= 0.5;
 256
 257   /* we're meshing.  */
 258   else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
 259     shift_amount *= 0.1;
 260   else
 261     shift_amount *= 0.17;
 262
 263   /*
 264
 265   */
 266   if (full_collide
 267       && down_ball_type * up_ball_type == 0)
 268     {
 269       if (up_ball_type == 0 && down_ball_type == 1)
 270         shift_amount *= 1.25;
 271       else if (up_ball_type == 0 && down_ball_type == 2)
 272         shift_amount *= 1.35;
 273       else if (down_ball_type == 0 && up_ball_type == 1)
 274         shift_amount *= 0.7;
 275       else if (down_ball_type == 0 && up_ball_type == 2)
 276         shift_amount *= 0.75;
 277     }
 278
 279   /*
 280    * Fix issue #44:
 281    *
 282    * Dots from left note head collide with right note head. Only occurs
 283    * with a close half collide, if the left note head is between
 284    * lines and the right note head is on a line, and if right note head
 285    * hasn't got any dots.
 286    */
 287   if (close_half_collide
 288       && Rhythmic_head::dot_count (head_up)
 289       && !Rhythmic_head::dot_count (head_down))
 290     {
 291       Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
 292       if (!Staff_symbol_referencer::on_line (staff, ups[0]))
 293         /*
 294           TODO: consider junking the else body.
 295         */
 296         if (to_boolean (me->get_property ("prefer-dotted-right")))
 297           {
 298             shift_amount = 0.5;
 299           }
 300         else
 301           {
 302             Grob *d = unsmob_grob (head_up->get_object ("dot"));
 303             Grob *parent = d->get_parent (X_AXIS);
 304             if (Dot_column::has_interface (parent))
 305               Side_position_interface::add_support (parent, head_down);
 306           }
 307     }
 308
 309   /* For full or close half collisions, the right hand head may
 310      obscure dots.  Move dots to the right.  */
 311   if (abs (shift_amount) > 1e-6
 312       && Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up)
 313       && (full_collide || close_half_collide))
 314     {
 315       Grob *d = unsmob_grob (head_down->get_object ("dot"));
 316       Grob *parent = d->get_parent (X_AXIS);
 317
 318       /*
 319         FIXME:
 320
 321         |
 322         x . o
 323         |
 324
 325
 326         the . is put right of o which is erroneous o force-shifted
 327         far to the right.
 328       */
 329       if (Dot_column::has_interface (parent))
 330         {
 331           Grob *stem = unsmob_grob (head_up->get_object ("stem"));
 332           extract_grob_set (stem, "note-heads", heads);
 333           for (vsize i = 0; i < heads.size (); i++)
 334             Side_position_interface::add_support (parent, heads[i]);
 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
 348 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
 349 SCM
 350 Note_collision_interface::calc_positioning_done (SCM smob)
 351 {
 352   Grob *me = unsmob_grob (smob);
 353   me->set_property ("positioning-done", SCM_BOOL_T);
 354
 355   Drul_array<vector<Grob*> > clash_groups = get_clash_groups (me);
 356
 357   Direction d = UP;
 358   do
 359     {
 360       for (vsize i = clash_groups[d].size (); i--; )
 361         {
 362           /*
 363             Trigger positioning
 364            */
 365           clash_groups[d][i]->extent (me, X_AXIS);
 366         }
 367     }
 368   while (flip (&d) != UP);
 369
 370   SCM autos (automatic_shift (me, clash_groups));
 371   SCM hand (forced_shift (me));
 372
 373   Real wid = 0.0;
 374   do
 375     {
 376       if (clash_groups[d].size ())
 377         {
 378           Grob *h = clash_groups[d][0];
 379           Grob *fh = Note_column::first_head (h);
 380           if (fh)
 381             wid = fh->extent (h, X_AXIS).length ();
 382         }
 383     }
 384   while (flip (&d) != UP);
 385
 386   vector<Grob*> done;
 387   Real left_most = 1e6;
 388
 389   vector<Real> amounts;
 390   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 391     {
 392       Grob *s = unsmob_grob (scm_caar (hand));
 393       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 394
 395       done.push_back (s);
 396       amounts.push_back (amount);
 397       if (amount < left_most)
 398         left_most = amount;
 399     }
 400   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 401     {
 402       Grob *s = unsmob_grob (scm_caar (autos));
 403       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 404
 405       vsize x = find (done, s) - done.begin ();
 406       if (x == VPOS || x >= done.size ())
 407         {
 408           done.push_back (s);
 409           amounts.push_back (amount);
 410           if (amount < left_most)
 411             left_most = amount;
 412         }
 413     }
 414
 415   for (vsize i = 0; i < amounts.size (); i++)
 416     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 417
 418   return SCM_BOOL_T;
 419 }
 420
 421 Drul_array < vector<Grob*> >
 422 Note_collision_interface::get_clash_groups (Grob *me)
 423 {
 424   Drul_array<vector<Grob*> > clash_groups;
 425
 426   extract_grob_set (me, "elements", elements);
 427   for (vsize i = 0; i < elements.size (); i++)
 428     {
 429       Grob *se = elements[i];
 430       if (Note_column::has_interface (se))
 431         {
 432           if (!Note_column::dir (se))
 433             {
 434               se->programming_error ("note-column has no direction");
 435             }
 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 /** This complicated routine moves note columns around horizontally to
 453     ensure that notes don't clash.
 454
 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         {
 578           tups = scm_cons (scm_cons (se->self_scm (), force),
 579                            tups);
 580         }
 581     }
 582   return tups;
 583 }
 584
 585 void
 586 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 587 {
 588   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 589   Axis_group_interface::add_element (me, ncol);
 590 }
 591
 592 ADD_INTERFACE (Note_collision_interface,
 593                "An object that handles collisions between notes with"
 594                " different stem directions and horizontal shifts.  Most of"
 595                " the interesting properties are to be set in"
 596                " @ref{note-column-interface}: these are @code{force-hshift}"
 597                " and @code{horizontal-shift}.",
 598
 599                /* properties */
 600                "merge-differently-dotted "
 601                "merge-differently-headed "
 602                "positioning-done "
 603                "prefer-dotted-right "
 604                );