lily/collision.cc

   1 /*
   2   collision.cc -- implement Collision
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c)  1997--2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "debug.hh"
  10 #include "collision.hh"
  11 #include "note-column.hh"
  12 #include "rhythmic-head.hh"
  13 #include "paper-def.hh"
  14 #include "axis-group-interface.hh"
  15 #include "item.hh"
  16 #include "stem.hh"
  17
  18 MAKE_SCHEME_CALLBACK (Collision,force_shift_callback,2);
  19
  20 SCM
  21 Collision::force_shift_callback (SCM element_smob, SCM axis)
  22 {
  23   Grob *me = unsmob_grob (element_smob);
  24   Axis a = (Axis) gh_scm2int (axis);
  25   assert (a == X_AXIS);
  26
  27    me = me->get_parent (a);
  28
  29    if (! to_boolean (me->get_grob_property ("collision-done")))
  30     {
  31       me->set_grob_property ("collision-done", SCM_BOOL_T);
  32       do_shifts (me);
  33     }
  34
  35   return gh_double2scm (0.0);
  36 }
  37
  38
  39 void
  40 check_meshing_chords (Grob*me,
  41                       Drul_array< Array < Real > > *offsets,
  42                       Drul_array< Array < Slice > > const &extents,
  43                       Drul_array<Link_array<Grob> > const &clash_groups)
  44
  45 {
  46   if (!extents[UP].size () || ! extents[DOWN].size ())
  47     return ;
  48
  49
  50   Grob *cu =clash_groups[UP][0];
  51   Grob *cd =clash_groups[DOWN][0];
  52
  53   Grob * nu_l= Note_column::first_head (cu);
  54   Grob * nd_l = Note_column::first_head (cd);
  55
  56
  57
  58   /*
  59     this case (distant half collide),
  60
  61         |
  62       x |
  63      | x
  64      |
  65
  66    the noteheads may be closer than this case (close half collide)
  67
  68        |
  69        |
  70       x
  71      x
  72     |
  73     |
  74
  75    */
  76
  77   bool close_half_collide = false;
  78   bool distant_half_collide = false;
  79   bool full_collide = false;
  80
  81   /*
  82     TODO:
  83
  84     filter out the 'o's in this configuration, since they're no part
  85     in the collision.
  86
  87      |
  88     x|o
  89     x|o
  90     x
  91
  92
  93    */
  94   Array<int> ups = Stem::note_head_positions (Note_column::stem_l (cu));
  95   Array<int> dps = Stem::note_head_positions (Note_column::stem_l (cd));
  96
  97   /*
  98     they're too far apart to collide.
  99
 100    */
 101
 102   if (ups[0] > dps.top () + 1)
 103     return ;
 104
 105   bool touch = (ups[0] - dps.top () >= 0);
 106
 107   bool merge_possible = (ups[0] >= dps[0]) && (ups.top () >= dps.top ());
 108
 109   merge_possible = merge_possible &&
 110     Rhythmic_head::balltype_i (nu_l) == Rhythmic_head::balltype_i (nd_l);
 111
 112
 113   /*
 114     don't merge whole notes (or longer, like breve, longa, maxima)
 115    */
 116   merge_possible = merge_possible && (Rhythmic_head::balltype_i (nu_l) > 0);
 117
 118   if (!to_boolean (me->get_grob_property ("merge-differently-dotted")))
 119     merge_possible = merge_possible && Rhythmic_head::dot_count (nu_l) == Rhythmic_head::dot_count (nd_l);
 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   Drul_array<Real> center_note_shifts;
 151   center_note_shifts[LEFT] = 0.0;
 152   center_note_shifts[RIGHT] = 0.0;
 153
 154
 155   Real shift_amount = 1;
 156
 157   if (touch)
 158     shift_amount *= -1;
 159
 160   /*
 161     for full collisions, the right hand head may obscure dots, so
 162     make sure the dotted heads go to the right.
 163    */
 164   if ((Rhythmic_head::dot_count (nu_l) > Rhythmic_head::dot_count (nd_l)
 165        && full_collide))
 166     shift_amount = 1;
 167
 168   /*
 169     TODO: these numbers are magic; should devise a set of grob props
 170     to tune this behavior.  */
 171
 172   if (merge_possible)
 173     shift_amount *= 0.0;
 174   else if (close_half_collide && !touch)
 175     shift_amount *= 0.52;
 176   else if (distant_half_collide && !touch)
 177     shift_amount *= 0.4;
 178   else if (distant_half_collide || close_half_collide || full_collide)
 179     shift_amount *= 0.5;
 180
 181   /*
 182     we're meshing.
 183   */
 184   else if (Rhythmic_head::dot_count (nu_l) || Rhythmic_head::dot_count (nd_l))
 185     shift_amount *= 0.1;
 186   else
 187     shift_amount *= 0.25;
 188
 189   Direction d = UP;
 190   do
 191     {
 192       for (int i=0; i < clash_groups[d].size (); i++)
 193         (*offsets)[d][i] += d * shift_amount;
 194     }
 195   while ((flip (&d))!= UP);
 196 }
 197
 198
 199 /*
 200   TODO: make callback of this.
 201
 202   TODO:
 203
 204   note-width is hardcoded, making it difficult to handle all note
 205   heads sanely. We should really look at the widths of the colliding
 206   columns, and have a separate setting for "align stems".
 207
 208
 209  */
 210 void
 211 Collision::do_shifts (Grob* me)
 212 {
 213   SCM autos (automatic_shift (me));
 214   SCM hand (forced_shift (me));
 215
 216   Link_array<Grob> done;
 217
 218
 219   Real wid
 220     = gh_scm2double (me->get_grob_property ("note-width"));
 221
 222   for (; gh_pair_p (hand); hand =ly_cdr (hand))
 223     {
 224       Grob * s = unsmob_grob (ly_caar (hand));
 225       Real amount = gh_scm2double (ly_cdar (hand));
 226
 227       s->translate_axis (amount *wid, X_AXIS);
 228       done.push (s);
 229     }
 230   for (; gh_pair_p (autos); autos =ly_cdr (autos))
 231     {
 232       Grob * s = unsmob_grob (ly_caar (autos));
 233       Real amount = gh_scm2double (ly_cdar (autos));
 234
 235       if (!done.find_l (s))
 236         s->translate_axis (amount * wid, X_AXIS);
 237     }
 238 }
 239
 240 /** This complicated routine moves note columns around horizontally to
 241   ensure that notes don't clash.
 242
 243   This should be put into Scheme.
 244   */
 245 SCM
 246 Collision::automatic_shift (Grob *me)
 247 {
 248   Drul_array<Link_array<Grob> > clash_groups;
 249   Drul_array<Array<int> > shifts;
 250   SCM  tups = SCM_EOL;
 251
 252   SCM s = me->get_grob_property ("elements");
 253   for (; gh_pair_p (s); s = ly_cdr (s))
 254     {
 255       SCM car = ly_car (s);
 256
 257       Grob * se = unsmob_grob (car);
 258       if (Note_column::has_interface (se))
 259         clash_groups[Note_column::dir (se)].push (se);
 260     }
 261
 262
 263   Direction d = UP;
 264   do
 265     {
 266       Array<int> & shift (shifts[d]);
 267       Link_array<Grob> & clashes (clash_groups[d]);
 268
 269       clashes.sort (Note_column::shift_compare);
 270
 271       for (int i=0; i < clashes.size (); i++)
 272         {
 273           SCM sh
 274             = clashes[i]->get_grob_property ("horizontal-shift");
 275
 276           if (gh_number_p (sh))
 277             shift.push (gh_scm2int (sh));
 278           else
 279             shift.push (0);
 280         }
 281
 282       for (int i=1; i < shift.size (); i++)
 283         {
 284           if (shift[i-1] == shift[i])
 285             {
 286               me->warning (_ ("Too many clashing notecolumns.  Ignoring them."));
 287               return tups;
 288             }
 289         }
 290     }
 291   while ((flip (&d))!= UP);
 292
 293   Drul_array< Array < Slice > > extents;
 294   Drul_array< Array < Real > > offsets;
 295   d = UP;
 296   do
 297     {
 298       for (int i=0; i < clash_groups[d].size (); i++)
 299         {
 300           Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
 301           s[LEFT] --;
 302           s[RIGHT]++;
 303           extents[d].push (s);
 304           offsets[d].push (d * 0.5 * i);
 305         }
 306     }
 307   while ((flip (&d))!= UP);
 308
 309   /*
 310     do horizontal shifts of each direction
 311
 312        |
 313       x||
 314        x||
 315         x|
 316    */
 317
 318   do
 319     {
 320       for (int i=1; i < clash_groups[d].size (); i++)
 321         {
 322           Slice prev =extents[d][i-1];
 323           prev.intersect (extents[d][i]);
 324           if (prev.length ()> 0 ||
 325  (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
 326             for (int j = i; j <  clash_groups[d].size (); j++)
 327               offsets[d][j] += d * 0.5;
 328         }
 329     }
 330   while ((flip (&d))!= UP);
 331
 332
 333   /*
 334     Check if chords are meshing
 335    */
 336
 337   check_meshing_chords (me, &offsets, extents, clash_groups);
 338
 339   do
 340     {
 341       for (int i=0; i < clash_groups[d].size (); i++)
 342         tups = gh_cons (gh_cons (clash_groups[d][i]->self_scm (), gh_double2scm (offsets[d][i])),
 343                                  tups);
 344     }
 345   while (flip (&d) != UP);
 346   return tups;
 347 }
 348
 349
 350 SCM
 351 Collision::forced_shift (Grob *me)
 352 {
 353   SCM tups = SCM_EOL;
 354
 355   SCM s = me->get_grob_property ("elements");
 356   for (; gh_pair_p (s); s = ly_cdr (s))
 357     {
 358       Grob * se = unsmob_grob (ly_car (s));
 359
 360       SCM force =  se->remove_grob_property ("force-hshift");
 361       if (gh_number_p (force))
 362         {
 363           tups = gh_cons (gh_cons (se->self_scm (), force),
 364                           tups);
 365         }
 366     }
 367   return tups;
 368 }
 369
 370 void
 371 Collision::add_column (Grob*me,Grob* ncol_l)
 372 {
 373   ncol_l->add_offset_callback (Collision::force_shift_callback_proc, X_AXIS);
 374   Axis_group_interface::add_element (me, ncol_l);
 375   me->add_dependency (ncol_l);
 376 }
 377
 378
 379 ADD_INTERFACE (Collision, "note-collision-interface",
 380   "An object that handles collisions between notes with different
 381 stem directions and horizontal shifts. Most of the interesting
 382 properties are to be set in @ref{note-column-interface}",
 383   "merge-differently-dotted note-width collision-done");