lily/note-collision.cc

   1 /*
   2   collision.cc -- implement Collision
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.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   /* Should never merge quarter and half notes, as this would make
  80      them indistinguishable.  */
  81   if (merge_possible
  82       && ((Rhythmic_head::duration_log (nu) == 1
  83            && Rhythmic_head::duration_log (nd) == 2)
  84           || (Rhythmic_head::duration_log (nu) == 2
  85               && Rhythmic_head::duration_log (nd) == 1)))
  86     merge_possible = false;
  87
  88   /*
  89     this case (distant half collide),
  90
  91     |
  92     x |
  93     | x
  94     |
  95
  96     the noteheads may be closer than this case (close half collide)
  97
  98     |
  99     |
 100     x
 101     x
 102     |
 103     |
 104
 105   */
 106
 107   /* TODO: filter out the 'o's in this configuration, since they're no
 108      part in the collision.
 109
 110      |
 111      x|o
 112      x|o
 113      x
 114
 115   */
 116
 117   bool close_half_collide = false;
 118   bool distant_half_collide = false;
 119   bool full_collide = false;
 120
 121   int i = 0, j = 0;
 122   while (i < ups.size () && j < dps.size ())
 123     {
 124       if (abs (ups[i] - dps[j]) == 1)
 125         {
 126           merge_possible = false;
 127           if (ups[i] > dps[j])
 128             close_half_collide = true;
 129           else
 130             distant_half_collide = true;
 131         }
 132       else if (ups[i] == dps[j])
 133         full_collide = true;
 134       else if (ups[i] > dps[0] && ups[i] < dps.top ())
 135         merge_possible = false;
 136       else if (dps[j] > ups[0] && dps[j] < ups.top ())
 137         merge_possible = false;
 138
 139       if (ups[i] < dps[j])
 140         i++;
 141       else if (ups[i] > dps[j])
 142         j++;
 143       else
 144         {
 145           i++;
 146           j++;
 147         }
 148     }
 149
 150   full_collide = full_collide || (close_half_collide
 151                                   && distant_half_collide);
 152
 153   Drul_array<Real> center_note_shifts;
 154   center_note_shifts[LEFT] = 0.0;
 155   center_note_shifts[RIGHT] = 0.0;
 156
 157   Real shift_amount = 1;
 158
 159   bool touch = (ups[0] >= dps.top ());
 160   if (touch)
 161     shift_amount *= -1;
 162
 163   /* For full collisions, the right hand head may obscure dots, so
 164      make sure the dotted heads go to the right.  */
 165   bool stem_to_stem = false;
 166   if (full_collide)
 167     if (Rhythmic_head::dot_count (nu) > Rhythmic_head::dot_count (nd))
 168       shift_amount = 1;
 169     else if (Rhythmic_head::dot_count (nu) < Rhythmic_head::dot_count (nd))
 170       stem_to_stem = true;
 171
 172   if (merge_possible)
 173     {
 174       shift_amount = 0;
 175
 176       /* If possible, don't wipe any heads. Else, wipe shortest head,
 177          or head with smallest amount of dots.  Note: when merging
 178          different heads, dots on the smaller one disappear. */
 179       Grob *wipe_ball = 0;
 180       Grob *dot_wipe_head = nu;
 181
 182       if (upball_type == dnball_type)
 183         {
 184           if (Rhythmic_head::dot_count (nd) < Rhythmic_head::dot_count (nu))
 185             {
 186               wipe_ball = nd;
 187               dot_wipe_head = nd;
 188             }
 189           else if (Rhythmic_head::dot_count (nd) > Rhythmic_head::dot_count (nu))
 190             {
 191               dot_wipe_head = nu;
 192               wipe_ball = nu;
 193             }
 194           else
 195             dot_wipe_head = nu;
 196         }
 197       else if (dnball_type > upball_type)
 198         {
 199           wipe_ball = nd;
 200           dot_wipe_head = nd;
 201         }
 202       else if (dnball_type < upball_type)
 203         {
 204           wipe_ball = nu;
 205           dot_wipe_head = nu;
 206         }
 207
 208       if (dot_wipe_head)
 209         {
 210           if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
 211             d->suicide ();
 212         }
 213
 214       if (wipe_ball && wipe_ball->is_live ())
 215         {
 216           wipe_ball->set_property ("transparent", SCM_BOOL_T);
 217           wipe_ball->set_property ("stencil", SCM_EOL);
 218         }
 219     }
 220   /* TODO: these numbers are magic; should devise a set of grob props
 221      to tune this behavior.  */
 222   else if (stem_to_stem)
 223     shift_amount = -abs (shift_amount) * 0.65;
 224   else if (close_half_collide && !touch)
 225     shift_amount *= 0.52;
 226   else if (distant_half_collide && !touch)
 227     shift_amount *= 0.4;
 228   else if (distant_half_collide || close_half_collide || full_collide)
 229     shift_amount *= 0.5;
 230
 231   /* we're meshing.  */
 232   else if (Rhythmic_head::dot_count (nu) || Rhythmic_head::dot_count (nd))
 233     shift_amount *= 0.1;
 234   else
 235     shift_amount *= 0.17;
 236
 237   /* For full or close half collisions, the right hand head may
 238      obscure dots.  Move dots to the right.  */
 239   if (abs (shift_amount) > 1e-6
 240       && Rhythmic_head::dot_count (nd) > Rhythmic_head::dot_count (nu)
 241       && (full_collide || close_half_collide))
 242     {
 243       Grob *d = unsmob_grob (nd->get_object ("dot"));
 244       Grob *parent = d->get_parent (X_AXIS);
 245
 246       /*
 247         FIXME:
 248
 249         |
 250         x . o
 251         |
 252
 253
 254         the . is put right of o which is erroneous o force-shifted
 255         far to the right.
 256       */
 257       if (Dot_column::has_interface (parent))
 258         Side_position_interface::add_support (parent, nu);
 259     }
 260
 261   Direction d = UP;
 262   do
 263     {
 264       for (int i = 0; i < clash_groups[d].size (); i++)
 265         (*offsets)[d][i] += d * shift_amount;
 266     }
 267   while ((flip (&d)) != UP);
 268 }
 269
 270
 271 MAKE_SCHEME_CALLBACK(Note_collision_interface, calc_positioning_done, 1)
 272 SCM
 273 Note_collision_interface::calc_positioning_done (SCM smob)
 274 {
 275   Grob *me = unsmob_grob (smob);
 276   Drul_array<Link_array<Grob> > cg = get_clash_groups (me);
 277
 278   SCM autos (automatic_shift (me, cg));
 279   SCM hand (forced_shift (me));
 280
 281   Direction d = UP;
 282   Real wid = 0.0;
 283   do
 284     {
 285       if (cg[d].size ())
 286         {
 287           Grob *h = cg[d][0];
 288           wid = Note_column::first_head (h)->extent (h, X_AXIS).length ();
 289         }
 290     }
 291   while (flip (&d) != UP);
 292
 293   Link_array<Grob> done;
 294   Real left_most = 1e6;
 295
 296   Array<Real> amounts;
 297   for (; scm_is_pair (hand); hand = scm_cdr (hand))
 298     {
 299       Grob *s = unsmob_grob (scm_caar (hand));
 300       Real amount = scm_to_double (scm_cdar (hand)) * wid;
 301
 302       done.push (s);
 303       amounts.push (amount);
 304       if (amount < left_most)
 305         left_most = amount;
 306     }
 307   for (; scm_is_pair (autos); autos = scm_cdr (autos))
 308     {
 309       Grob *s = unsmob_grob (scm_caar (autos));
 310       Real amount = scm_to_double (scm_cdar (autos)) * wid;
 311
 312       if (!done.find (s))
 313         {
 314           done.push (s);
 315           amounts.push (amount);
 316           if (amount < left_most)
 317             left_most = amount;
 318         }
 319     }
 320
 321   for (int i = 0; i < amounts.size (); i++)
 322     done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
 323
 324   return SCM_BOOL_T;
 325 }
 326
 327 Drul_array < Link_array<Grob> >
 328 Note_collision_interface::get_clash_groups (Grob *me)
 329 {
 330   Drul_array<Link_array<Grob> > clash_groups;
 331
 332   extract_grob_set (me, "elements", elements);
 333   for (int i = 0; i < elements.size (); i++)
 334     {
 335       Grob *se = elements[i];
 336       if (Note_column::has_interface (se))
 337         clash_groups[Note_column::dir (se)].push (se);
 338     }
 339
 340   Direction d = UP;
 341   do
 342     {
 343       Link_array<Grob> &clashes (clash_groups[d]);
 344       clashes.sort (Note_column::shift_compare);
 345     }
 346   while ((flip (&d)) != UP);
 347
 348   return clash_groups;
 349 }
 350
 351 /** This complicated routine moves note columns around horizontally to
 352     ensure that notes don't clash.
 353
 354     This should be put into Scheme.
 355 */
 356 SCM
 357 Note_collision_interface::automatic_shift (Grob *me,
 358                                            Drul_array < Link_array<Grob>
 359                                            > clash_groups)
 360 {
 361   Drul_array < Array<int> > shifts;
 362   SCM tups = SCM_EOL;
 363
 364   Direction d = UP;
 365   do
 366     {
 367       Array<int> &shift (shifts[d]);
 368       Link_array<Grob> &clashes (clash_groups[d]);
 369
 370       for (int i = 0; i < clashes.size (); i++)
 371         {
 372           SCM sh
 373             = clashes[i]->get_property ("horizontal-shift");
 374
 375           if (scm_is_number (sh))
 376             shift.push (scm_to_int (sh));
 377           else
 378             shift.push (0);
 379         }
 380
 381       for (int i = 1; i < shift.size (); i++)
 382         {
 383           if (shift[i - 1] == shift[i])
 384             {
 385               clashes[0]->warning (_ ("ignoring too many clashing note columns"));
 386               return tups;
 387             }
 388         }
 389     }
 390   while ((flip (&d)) != UP);
 391
 392   Drul_array<Array<Slice> > extents;
 393   Drul_array<Array<Real> > offsets;
 394   d = UP;
 395   do
 396     {
 397       for (int i = 0; i < clash_groups[d].size (); i++)
 398         {
 399           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 400           s[LEFT]--;
 401           s[RIGHT]++;
 402           extents[d].push (s);
 403           offsets[d].push (d * 0.5 * i);
 404         }
 405     }
 406   while ((flip (&d)) != UP);
 407
 408   /*
 409     do horizontal shifts of each direction
 410
 411     |
 412     x||
 413     x||
 414     x|
 415   */
 416
 417   do
 418     {
 419       for (int i = 1; i < clash_groups[d].size (); i++)
 420         {
 421           Slice prev = extents[d][i - 1];
 422           prev.intersect (extents[d][i]);
 423           if (prev.length () > 0
 424               || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 425             for (int j = i; j < clash_groups[d].size (); j++)
 426               offsets[d][j] += d * 0.5;
 427         }
 428     }
 429   while ((flip (&d)) != UP);
 430
 431   /*
 432     Check if chords are meshing
 433   */
 434
 435   check_meshing_chords (me, &offsets, extents, clash_groups);
 436
 437   do
 438     {
 439       for (int i = 0; i < clash_groups[d].size (); i++)
 440         tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
 441                                    scm_from_double (offsets[d][i])),
 442                          tups);
 443     }
 444   while (flip (&d) != UP);
 445
 446   return tups;
 447 }
 448
 449 SCM
 450 Note_collision_interface::forced_shift (Grob *me)
 451 {
 452   SCM tups = SCM_EOL;
 453
 454   extract_grob_set (me, "elements", elements);
 455   for (int i = 0; i < elements.size (); i++)
 456     {
 457       Grob *se = elements[i];
 458
 459       SCM force = se->get_property ("force-hshift");
 460       if (scm_is_number (force))
 461         {
 462           tups = scm_cons (scm_cons (se->self_scm (), force),
 463                            tups);
 464         }
 465     }
 466   return tups;
 467 }
 468
 469 void
 470 Note_collision_interface::add_column (Grob *me, Grob *ncol)
 471 {
 472   ncol->add_offset_callback (Grob::same_axis_parent_positioning_proc, X_AXIS);
 473   Axis_group_interface::add_element (me, ncol);
 474 }
 475
 476 ADD_INTERFACE (Note_collision_interface, "note-collision-interface",
 477                "An object that handles collisions between notes with different stem "
 478                "directions and horizontal shifts. Most of the interesting properties "
 479                "are to be set in @ref{note-column-interface}: these are "
 480                "@code{force-hshift} and @code{horizontal-shift}.",
 481
 482                /* properties */
 483                "merge-differently-dotted "
 484                "merge-differently-headed "
 485                "positioning-done");