lily/note-collision.cc

   1 /*
   2   collision.cc -- implement 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
  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           /*
 295             TODO: consider junking the else body.
 296           */
 297           if (to_boolean (me->get_property ("prefer-dotted-right")))
 298             {
 299               shift_amount = 0.5;
 300             }
 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             {
 436               se->programming_error ("note-column has no direction");
 437             }
 438           else
 439             clash_groups[Note_column::dir (se)].push_back (se);
 440         }
 441     }
 442
 443   Direction d = UP;
 444   do
 445     {
 446       vector<Grob*> &clashes (clash_groups[d]);
 447       vector_sort (clashes, Note_column::shift_less);
 448     }
 449   while ((flip (&d)) != UP);
 450
 451   return clash_groups;
 452 }
 453
 454 /** This complicated routine moves note columns around horizontally to
 455     ensure that notes don't clash.
 456
 457 */
 458 SCM
 459 Note_collision_interface::automatic_shift (Grob *me,
 460                                            Drul_array<vector<Grob*> > clash_groups)
 461 {
 462   Drul_array < vector<int> > shifts;
 463   SCM tups = SCM_EOL;
 464
 465   Direction d = UP;
 466   do
 467     {
 468       vector<int> &shift (shifts[d]);
 469       vector<Grob*> &clashes (clash_groups[d]);
 470
 471       for (vsize i = 0; i < clashes.size (); i++)
 472         {
 473           SCM sh
 474             = clashes[i]->get_property ("horizontal-shift");
 475
 476           if (scm_is_number (sh))
 477             shift.push_back (scm_to_int (sh));
 478           else
 479             shift.push_back (0);
 480         }
 481
 482       for (vsize i = 1; i < shift.size (); i++)
 483         {
 484           if (shift[i - 1] == shift[i])
 485             {
 486               clashes[0]->warning (_ ("ignoring too many clashing note columns"));
 487               return tups;
 488             }
 489         }
 490     }
 491   while ((flip (&d)) != UP);
 492
 493   Drul_array<vector<Slice> > extents;
 494   Drul_array<vector<Real> > offsets;
 495   d = UP;
 496   do
 497     {
 498       for (vsize i = 0; i < clash_groups[d].size (); i++)
 499         {
 500           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 501           s[LEFT]--;
 502           s[RIGHT]++;
 503           extents[d].push_back (s);
 504           offsets[d].push_back (d * 0.5 * i);
 505         }
 506     }
 507   while ((flip (&d)) != UP);
 508
 509   /*
 510     do horizontal shifts of each direction
 511
 512     |
 513     x||
 514     x||
 515     x|
 516   */
 517
 518   do
 519     {
 520       for (vsize i = 1; i < clash_groups[d].size (); i++)
 521         {
 522           Slice prev = extents[d][i - 1];
 523           prev.intersect (extents[d][i]);
 524           if (prev.length () > 0
 525               || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 526             for (vsize j = i; j < clash_groups[d].size (); j++)
 527               offsets[d][j] += d * 0.5;
 528         }
 529     }
 530   while ((flip (&d)) != UP);
 531
 532
 533   /*
 534     see input/regression/dot-up-voice-collision.ly
 535    */
 536   for (vsize i = 0; i < clash_groups[UP].size (); i++)
 537     {
 538       Grob *g = clash_groups[UP][i];
 539       Grob *dc = Note_column::dot_column (g);
 540
 541       if (dc)
 542         for (vsize j = i + 1;  j < clash_groups[UP].size (); j++)
 543           {
 544             Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
 545             Side_position_interface::add_support (dc, stem);
 546           }
 547     }
 548
 549   /*
 550     Check if chords are meshing
 551   */
 552
 553   check_meshing_chords (me, &offsets, extents, clash_groups);
 554
 555   do
 556     {
 557       for (vsize i = 0; i < clash_groups[d].size (); i++)
 558         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 559                                    scm_from_double (offsets[d][i])),
 560                          tups);
 561     }
 562   while (flip (&d) != UP);
 563
 564   return tups;
 565 }
 566
 567 SCM
 568 Note_collision_interface::forced_shift (Grob *me)
 569 {
 570   SCM tups = SCM_EOL;
 571
 572   extract_grob_set (me, "elements", elements);
 573   for (vsize i = 0; i < elements.size (); i++)
 574     {
 575       Grob *se = elements[i];
 576
 577       SCM force = se->get_property ("force-hshift");
 578       if (scm_is_number (force))
 579         {
 580           tups = scm_cons (scm_cons (se->self_scm (), force),
 581                            tups);
 582         }
 583     }
 584   return tups;
 585 }
 586
 587 void
 588 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 589 {
 590   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 591   Axis_group_interface::add_element (me, ncol);
 592 }
 593
 594 ADD_INTERFACE (Note_collision_interface,
 595                "An object that handles collisions between notes with"
 596                " different stem directions and horizontal shifts.  Most of"
 597                " the interesting properties are to be set in"
 598                " @ref{note-column-interface}: these are @code{force-hshift}"
 599                " and @code{horizontal-shift}.",
 600
 601                /* properties */
 602                "merge-differently-dotted "
 603                "merge-differently-headed "
 604                "positioning-done "
 605                "prefer-dotted-right "
 606                );