lily/note-collision.cc

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