lily/note-collision.cc

   1 /*
   2   collision.cc -- implement Collision
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1997--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #include "note-collision.hh"
  10
  11
  12 #include "warn.hh"
  13 #include "note-column.hh"
  14 #include "note-head.hh"
  15 #include "rhythmic-head.hh"
  16 #include "output-def.hh"
  17 #include "axis-group-interface.hh"
  18 #include "stem.hh"
  19 #include "side-position-interface.hh"
  20 #include "dot-column.hh"
  21 #include "pointer-group-interface.hh"
  22
  23
  24
  25 void
  26 check_meshing_chords (Grob *me,
  27                       Drul_array<Array<Real> > *offsets,
  28                       Drul_array<Array<Slice> > const &extents,
  29                       Drul_array<Link_array<Grob> > const &clash_groups)
  30
  31 {
  32   if (!extents[UP].size () || ! extents[DOWN].size ())
  33     return;
  34
  35   Grob *cu = clash_groups[UP][0];
  36   Grob *cd = clash_groups[DOWN][0];
  37
  38   /* Every note column should have a stem, but avoid a crash. */
  39   if (!Note_column::get_stem (cu) || !Note_column::get_stem (cd))
  40     return;
  41
  42   Grob *nu = Note_column::first_head (cu);
  43   Grob *nd = Note_column::first_head (cd);
  44
  45   Array<int> ups = Stem::note_head_positions (Note_column::get_stem (cu));
  46   Array<int> dps = Stem::note_head_positions (Note_column::get_stem (cd));
  47
  48   /* Too far apart to collide.  */
  49   if (ups[0] > dps.top () + 1)
  50     return;
  51
  52   // FIXME: what's this?
  53   bool merge_possible = (ups[0] >= dps[0]) && (ups.top () >= dps.top ());
  54
  55   /* Do not merge notes typeset in different style. */
  56   if (!ly_is_equal (nu->get_property ("style"),
  57                     nd->get_property ("style")))
  58     merge_possible = false;
  59
  60   int upball_type = Note_head::get_balltype (nu);
  61   int dnball_type = Note_head::get_balltype (nd);
  62
  63   /* Do not merge whole notes (or longer, like breve, longa, maxima).  */
  64   if (merge_possible && (upball_type <= 0 || dnball_type <= 0))
  65     merge_possible = false;
  66
  67   if (merge_possible
  68       && Rhythmic_head::dot_count (nu) != Rhythmic_head::dot_count (nd)
  69       && !to_boolean (me->get_property ("merge-differently-dotted")))
  70     merge_possible = false;
  71
  72   /* Can only merge different heads if merge-differently-headed is
  73      set. */
  74   if (merge_possible
  75       && upball_type != dnball_type
  76       && !to_boolean (me->get_property ("merge-differently-headed")))
  77     merge_possible = false;
  78
  79   merge_possible = merge_possible &&
  80     !(nu->get_property ("style") == ly_symbol2scm ("fa")
  81       && nd->get_property ("style") == ly_symbol2scm ("fa"));
  82
  83
  84   /* Should never merge quarter and half notes, as this would make
  85      them indistinguishable.  */
  86   if (merge_possible
  87       && ((Rhythmic_head::duration_log (nu) == 1
  88            && Rhythmic_head::duration_log (nd) == 2)
  89           || (Rhythmic_head::duration_log (nu) == 2
  90               && Rhythmic_head::duration_log (nd) == 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   int i = 0, j = 0;
 127   while (i < ups.size () && j < dps.size ())
 128     {
 129       if (abs (ups[i] - dps[j]) == 1)
 130         {
 131           merge_possible = false;
 132           if (ups[i] > dps[j])
 133             close_half_collide = true;
 134           else
 135             distant_half_collide = true;
 136         }
 137       else if (ups[i] == dps[j])
 138         full_collide = true;
 139       else if (ups[i] > dps[0] && ups[i] < dps.top ())
 140         merge_possible = false;
 141       else if (dps[j] > ups[0] && dps[j] < ups.top ())
 142         merge_possible = false;
 143
 144       if (ups[i] < dps[j])
 145         i++;
 146       else if (ups[i] > dps[j])
 147         j++;
 148       else
 149         {
 150           i++;
 151           j++;
 152         }
 153     }
 154
 155   full_collide = full_collide || (close_half_collide
 156                                   && distant_half_collide);
 157
 158   Drul_array<Real> center_note_shifts;
 159   center_note_shifts[LEFT] = 0.0;
 160   center_note_shifts[RIGHT] = 0.0;
 161
 162   Real shift_amount = 1;
 163
 164   bool touch = (ups[0] >= dps.top ());
 165   if (touch)
 166     shift_amount *= -1;
 167
 168   /* For full collisions, the right hand head may obscure dots, so
 169      make sure the dotted heads go to the right.  */
 170   bool stem_to_stem = false;
 171   if (full_collide)
 172     if (Rhythmic_head::dot_count (nu) > Rhythmic_head::dot_count (nd))
 173       shift_amount = 1;
 174     else if (Rhythmic_head::dot_count (nu) < Rhythmic_head::dot_count (nd))
 175       stem_to_stem = true;
 176
 177   if (merge_possible)
 178     {
 179       shift_amount = 0;
 180
 181       /* If possible, don't wipe any heads. Else, wipe shortest head,
 182          or head with smallest amount of dots.  Note: when merging
 183          different heads, dots on the smaller one disappear. */
 184       Grob *wipe_ball = 0;
 185       Grob *dot_wipe_head = nu;
 186
 187       if (upball_type == dnball_type)
 188         {
 189           if (Rhythmic_head::dot_count (nd) < Rhythmic_head::dot_count (nu))
 190             {
 191               wipe_ball = nd;
 192               dot_wipe_head = nd;
 193             }
 194           else if (Rhythmic_head::dot_count (nd) > Rhythmic_head::dot_count (nu))
 195             {
 196               dot_wipe_head = nu;
 197               wipe_ball = nu;
 198             }
 199           else
 200             dot_wipe_head = nu;
 201         }
 202       else if (dnball_type > upball_type)
 203         {
 204           wipe_ball = nd;
 205           dot_wipe_head = nd;
 206         }
 207       else if (dnball_type < upball_type)
 208         {
 209           wipe_ball = nu;
 210           dot_wipe_head = nu;
 211         }
 212
 213       if (dot_wipe_head)
 214         {
 215           if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
 216             d->suicide ();
 217         }
 218
 219       if (wipe_ball && wipe_ball->is_live ())
 220         {
 221           wipe_ball->set_property ("transparent", SCM_BOOL_T);
 222         }
 223     }
 224   /* TODO: these numbers are magic; should devise a set of grob props
 225      to tune this behavior.  */
 226   else if (stem_to_stem)
 227     shift_amount = -abs (shift_amount) * 0.65;
 228   else if (close_half_collide && !touch)
 229     shift_amount *= 0.52;
 230   else if (distant_half_collide && !touch)
 231     shift_amount *= 0.4;
 232   else if (distant_half_collide || close_half_collide || full_collide)
 233     shift_amount *= 0.5;
 234
 235   /* we're meshing.  */
 236   else if (Rhythmic_head::dot_count (nu) || Rhythmic_head::dot_count (nd))
 237     shift_amount *= 0.1;
 238   else
 239     shift_amount *= 0.17;
 240
 241   /* For full or close half collisions, the right hand head may
 242      obscure dots.  Move dots to the right.  */
 243   if (abs (shift_amount) > 1e-6
 244       && Rhythmic_head::dot_count (nd) > Rhythmic_head::dot_count (nu)
 245       && (full_collide || close_half_collide))
 246     {
 247       Grob *d = unsmob_grob (nd->get_object ("dot"));
 248       Grob *parent = d->get_parent (X_AXIS);
 249
 250       /*
 251         FIXME:
 252
 253         |
 254         x . o
 255         |
 256
 257
 258         the . is put right of o which is erroneous o force-shifted
 259         far to the right.
 260       */
 261       if (Dot_column::has_interface (parent))
 262         Side_position_interface::add_support (parent, nu);
 263     }
 264
 265   Direction d = UP;
 266   do
 267     {
 268       for (int i = 0; i < clash_groups[d].size (); i++)
 269         (*offsets)[d][i] += d * shift_amount;
 270     }
 271   while ((flip (&d)) != UP);
 272 }
 273
 274
 275 MAKE_SCHEME_CALLBACK(Note_collision_interface, calc_positioning_done, 1)
 276 SCM
 277 Note_collision_interface::calc_positioning_done (SCM smob)
 278 {
 279   Grob *me = unsmob_grob (smob);
 280   Drul_array<Link_array<Grob> > cg = get_clash_groups (me);
 281
 282   Direction d = UP;
 283   do
 284     {
 285       for (int i = cg[d].size(); i--; )
 286         {
 287           /*
 288             Trigger positioning
 289            */
 290           cg[d][i]->extent (me, X_AXIS);
 291         }
 292     }
 293   while (flip (&d) != UP);
 294
 295   SCM autos (automatic_shift (me, cg));
 296   SCM hand (forced_shift (me));
 297
 298   Real wid = 0.0;
 299   do
 300     {
 301       if (cg[d].size ())
 302         {
 303           Grob *h = cg[d][0];
 304           wid = Note_column::first_head (h)->extent (h, X_AXIS).length ();
 305         }
 306     }
 307   while (flip (&d) != UP);
 308
 309   Link_array<Grob> done;
 310   Real left_most = 1e6;
 311
 312   Array<Real> amounts;
 313   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 314     {
 315       Grob *s = unsmob_grob (scm_caar (hand));
 316       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 317
 318       done.push (s);
 319       amounts.push (amount);
 320       if (amount < left_most)
 321         left_most = amount;
 322     }
 323   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 324     {
 325       Grob *s = unsmob_grob (scm_caar (autos));
 326       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 327
 328       if (!done.find (s))
 329         {
 330           done.push (s);
 331           amounts.push (amount);
 332           if (amount < left_most)
 333             left_most = amount;
 334         }
 335     }
 336
 337   for (int i = 0; i < amounts.size (); i++)
 338     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 339
 340   return SCM_BOOL_T;
 341 }
 342
 343 Drul_array < Link_array<Grob> >
 344 Note_collision_interface::get_clash_groups (Grob *me)
 345 {
 346   Drul_array<Link_array<Grob> > clash_groups;
 347
 348   extract_grob_set (me, "elements", elements);
 349   for (int i = 0; i < elements.size (); i++)
 350     {
 351       Grob *se = elements[i];
 352       if (Note_column::has_interface (se))
 353         clash_groups[Note_column::dir (se)].push (se);
 354     }
 355
 356   Direction d = UP;
 357   do
 358     {
 359       Link_array<Grob> &clashes (clash_groups[d]);
 360       clashes.sort (Note_column::shift_compare);
 361     }
 362   while ((flip (&d)) != UP);
 363
 364   return clash_groups;
 365 }
 366
 367 /** This complicated routine moves note columns around horizontally to
 368     ensure that notes don't clash.
 369
 370     This should be put into Scheme.
 371 */
 372 SCM
 373 Note_collision_interface::automatic_shift (Grob *me,
 374                                            Drul_array < Link_array<Grob>
 375                                            > clash_groups)
 376 {
 377   Drul_array < Array<int> > shifts;
 378   SCM tups = SCM_EOL;
 379
 380   Direction d = UP;
 381   do
 382     {
 383       Array<int> &shift (shifts[d]);
 384       Link_array<Grob> &clashes (clash_groups[d]);
 385
 386       for (int i = 0; i < clashes.size (); i++)
 387         {
 388           SCM sh
 389             = clashes[i]->get_property ("horizontal-shift");
 390
 391           if (scm_is_number (sh))
 392             shift.push (scm_to_int (sh));
 393           else
 394             shift.push (0);
 395         }
 396
 397       for (int i = 1; i < shift.size (); i++)
 398         {
 399           if (shift[i - 1] == shift[i])
 400             {
 401               clashes[0]->warning (_ ("ignoring too many clashing note columns"));
 402               return tups;
 403             }
 404         }
 405     }
 406   while ((flip (&d)) != UP);
 407
 408   Drul_array<Array<Slice> > extents;
 409   Drul_array<Array<Real> > offsets;
 410   d = UP;
 411   do
 412     {
 413       for (int i = 0; i < clash_groups[d].size (); i++)
 414         {
 415           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 416           s[LEFT]--;
 417           s[RIGHT]++;
 418           extents[d].push (s);
 419           offsets[d].push (d * 0.5 * i);
 420         }
 421     }
 422   while ((flip (&d)) != UP);
 423
 424   /*
 425     do horizontal shifts of each direction
 426
 427     |
 428     x||
 429     x||
 430     x|
 431   */
 432
 433   do
 434     {
 435       for (int i = 1; i < clash_groups[d].size (); i++)
 436         {
 437           Slice prev = extents[d][i - 1];
 438           prev.intersect (extents[d][i]);
 439           if (prev.length () > 0
 440               || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 441             for (int j = i; j < clash_groups[d].size (); j++)
 442               offsets[d][j] += d * 0.5;
 443         }
 444     }
 445   while ((flip (&d)) != UP);
 446
 447   /*
 448     Check if chords are meshing
 449   */
 450
 451   check_meshing_chords (me, &offsets, extents, clash_groups);
 452
 453   do
 454     {
 455       for (int i = 0; i < clash_groups[d].size (); i++)
 456         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 457                                    scm_from_double (offsets[d][i])),
 458                          tups);
 459     }
 460   while (flip (&d) != UP);
 461
 462   return tups;
 463 }
 464
 465 SCM
 466 Note_collision_interface::forced_shift (Grob *me)
 467 {
 468   SCM tups = SCM_EOL;
 469
 470   extract_grob_set (me, "elements", elements);
 471   for (int i = 0; i < elements.size (); i++)
 472     {
 473       Grob *se = elements[i];
 474
 475       SCM force = se->get_property ("force-hshift");
 476       if (scm_is_number (force))
 477         {
 478           tups = scm_cons (scm_cons (se->self_scm (), force),
 479                            tups);
 480         }
 481     }
 482   return tups;
 483 }
 484
 485 void
 486 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 487 {
 488   ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
 489   Axis_group_interface::add_element (me, ncol);
 490 }
 491
 492 ADD_INTERFACE (Note_collision_interface, "note-collision-interface",
 493                "An object that handles collisions between notes with different stem "
 494                "directions and horizontal shifts. Most of the interesting properties "
 495                "are to be set in @ref{note-column-interface}: these are "
 496                "@code{force-hshift} and @code{horizontal-shift}.",
 497
 498                /* properties */
 499                "merge-differently-dotted "
 500                "merge-differently-headed "
 501                "positioning-done");