lily/accidental-placement.cc

   1 /*
   2 accidental-placement.cc --  implement Accidental_placement
   3
   4 source file of the GNU LilyPond music typesetter
   5
   6 (c) 2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8  */
   9
  10 #include <math.h>
  11 #include <libc-extension.hh>
  12 #include "item.hh"
  13 #include "skyline.hh"
  14 #include "music.hh"
  15 #include "pitch.hh"
  16 #include "warn.hh"
  17 #include "accidental-placement.hh"
  18
  19
  20 MAKE_SCHEME_CALLBACK(Accidental_placement,extent_callback, 2);
  21 SCM
  22 Accidental_placement::extent_callback(SCM s, SCM axis)
  23 {
  24   Grob * me =unsmob_grob (s);
  25   Axis a = Axis (gh_scm2int (axis));
  26
  27   assert (a == X_AXIS);
  28
  29   SCM w = position_accidentals (me);
  30   return w;
  31 }
  32
  33 MAKE_SCHEME_CALLBACK(Accidental_placement,alignment_callback, 2);
  34 SCM
  35 Accidental_placement::alignment_callback(SCM s, SCM )
  36 {
  37   Grob * me =unsmob_grob (s);
  38
  39   Grob * par = me->get_parent (X_AXIS);
  40   if (!to_boolean (par->get_grob_property ("alignment-done")))
  41     {
  42       par->set_grob_property ("alignment-done", SCM_BOOL_T);
  43       position_accidentals (par);
  44     }
  45
  46   return gh_int2scm (0);
  47 }
  48
  49
  50
  51 void
  52 Accidental_placement::add_accidental (Grob* me, Grob* a)
  53 {
  54   a->set_parent (me, X_AXIS);
  55   a->add_offset_callback (alignment_callback_proc, X_AXIS);
  56   SCM cause = a->get_parent (Y_AXIS)->get_grob_property("cause");
  57
  58   Music *mcause =unsmob_music (cause);
  59   if (!mcause)
  60     {
  61       programming_error ("Note head has no music cause!");
  62       return;
  63     }
  64
  65   Pitch *p= unsmob_pitch (mcause->get_mus_property ("pitch"));
  66
  67   int n = p->notename_i_;
  68
  69   SCM accs = me->get_grob_property ("accidentals");
  70   SCM key = gh_int2scm (n);
  71   SCM entry = scm_assq (key, accs);
  72   if (entry == SCM_BOOL_F)
  73     {
  74       entry = SCM_EOL;
  75     }
  76   else
  77     entry = gh_cdr (entry);
  78
  79   entry = gh_cons (a->self_scm (), entry);
  80
  81   accs = scm_assq_set_x (accs,  key, entry);
  82
  83   me->set_grob_property ("accidentals", accs);
  84 }
  85
  86 struct Accidental_placement_entry
  87 {
  88   Array<Skyline_entry> left_skyline_;
  89   Array<Skyline_entry> right_skyline_;
  90   Interval vertical_extent_;
  91   Array<Box> extents_;
  92   Link_array<Grob> grobs_;
  93   Real offset_;
  94   int notename_;
  95   Accidental_placement_entry()
  96   {
  97     offset_ =0.0;
  98     notename_ = -1;
  99   }
 100 };
 101
 102
 103 int ape_compare (Accidental_placement_entry *const &a,
 104                  Accidental_placement_entry *const &b)
 105 {
 106   return sign (a->vertical_extent_.length () - b->vertical_extent_.length());
 107 }
 108
 109 /*
 110   Return: width as SCM interval.
 111
 112
 113   This routine computes placements of accidentals. During
 114   add_accidental(), accidentals are already grouped by note, so that
 115   octaves are placed above each other; they form columns. Then the
 116   columns are sorted: the biggest columns go closest to the note.
 117   Then the columns are spaced as closely as possible (using skyline
 118   spacing).
 119
 120
 121   TODO: more advanced placement. Typically, the accs should be placed
 122   to form a C shape, like this
 123
 124
 125            ##
 126         b b
 127        # #
 128         b
 129           b b
 130
 131    The naturals should be left of the C as well; they should
 132    be separate accs.
 133
 134    TODO: Try to combine Apes before sorting them: this will allow a
 135    better placement.
 136
 137    Note that this placement problem is almost certainly NP hard, so we
 138    just use a simple strategy, not an optimal choice.
 139 */
 140
 141 SCM
 142 Accidental_placement::position_accidentals (Grob * me)
 143 {
 144   SCM accs = me->get_grob_property ("accidentals");
 145
 146   Link_array<Accidental_placement_entry> apes;
 147   for (SCM s = accs; gh_pair_p (s); s =gh_cdr (s))
 148     {
 149       Accidental_placement_entry *ape = new Accidental_placement_entry;
 150       ape->notename_ = gh_scm2int (gh_caar (s));
 151
 152       for (SCM t = gh_cdar (s); gh_pair_p (t); t =gh_cdr (t))
 153         ape->grobs_.push (unsmob_grob (gh_car (t)));
 154
 155       apes.push (ape);
 156     }
 157
 158
 159   Grob *commony =0 ;
 160   for (int i= apes.size (); i--;)
 161     commony = common_refpoint_of_array  (apes[i]->grobs_, commony, Y_AXIS);
 162
 163   Link_array<Grob> heads;
 164   for (int i= apes.size (); i--;)
 165     {
 166       Accidental_placement_entry * ape = apes[i];
 167       ape->left_skyline_ = empty_skyline ( LEFT);
 168       ape->right_skyline_ = empty_skyline ( RIGHT);
 169
 170       for (int j = apes[i]->grobs_.size(); j--;)
 171         {
 172           Grob * a = apes[i]->grobs_[j];
 173           Box b;
 174           b[X_AXIS] = a->extent (me, X_AXIS);
 175           b[Y_AXIS] = a->extent (commony, Y_AXIS);
 176
 177           Grob *head = a->get_parent (Y_AXIS);
 178           heads.push (head);
 179           commony = commony->common_refpoint (head, Y_AXIS);
 180
 181           ape->extents_.push (b);
 182
 183
 184           /*
 185             TODO: replace the extents of a flat by combination of two
 186             bboxes, so that we use the shape of the flat better.
 187           */
 188           insert_extent_into_skyline (&ape->left_skyline_, b, Y_AXIS, LEFT);
 189           insert_extent_into_skyline (&ape->right_skyline_ , b,Y_AXIS, RIGHT);
 190         }
 191     }
 192
 193   for (int i = apes.size(); i--;)
 194     {
 195       Interval y ;
 196
 197       for (int j = apes[i]->extents_.size(); j--;)
 198         {
 199           y.unite (apes[i]->extents_[j][Y_AXIS]);
 200         }
 201       apes[i]->vertical_extent_ = y;
 202     }
 203
 204   apes.sort (&ape_compare);
 205
 206   Accidental_placement_entry * head_ape = new Accidental_placement_entry;
 207   Grob *commonx = common_refpoint_of_array (heads, me, X_AXIS);
 208   Array<Skyline_entry> head_skyline (empty_skyline (LEFT));
 209   Array<Box> head_extents;
 210   for (int i = heads.size(); i--;)
 211     {
 212       Box b(heads[i]->extent (commonx, X_AXIS),
 213             heads[i]->extent (commony, Y_AXIS));
 214
 215       insert_extent_into_skyline (&head_skyline, b , Y_AXIS, LEFT);
 216     }
 217
 218   head_ape-> left_skyline_ = head_skyline;
 219   head_ape->offset_ = 0.0;
 220
 221   SCM rs = me->get_grob_property ("right-padding");
 222   if (gh_number_p (rs))
 223     head_ape->offset_ -= gh_scm2double (rs);
 224
 225   Real padding = 0.1;
 226   apes.push (head_ape);
 227   for (int i= apes.size () -1 ; i-- > 0;)
 228     {
 229       Accidental_placement_entry *ape = apes[i];
 230       Real d = 0.0;
 231       /*
 232         confusing naming: left_skyline is a skyline pointing to the
 233         left. It is on the right of the curent entry.
 234        */
 235
 236       int j = i+1;
 237       do {
 238         Array<Skyline_entry> const *right_sky =
 239           (j < apes.size())
 240           ? &apes[j]->left_skyline_
 241           : &head_skyline;
 242
 243         d = - skyline_meshing_distance (ape->right_skyline_,
 244                                              *right_sky);
 245
 246         if (!isinf(d)
 247             || j + 1 == apes.size())
 248           break;
 249
 250         j = j+ 1;
 251       } while (1);
 252
 253       if (isinf(d))
 254         d = 0.0;
 255
 256       d -= padding;
 257       ape->offset_ += apes[j]->offset_ + d;
 258     }
 259
 260   apes.pop();
 261   for (int i = apes.size(); i--;)
 262     {
 263       Accidental_placement_entry* ape = apes[i];
 264       for (int j  = ape->grobs_.size(); j--;)
 265         {
 266           ape->grobs_[j]->translate_axis (ape->offset_, X_AXIS);
 267         }
 268     }
 269
 270
 271   Interval left_extent, right_extent;
 272   Accidental_placement_entry *ape = apes[0];
 273
 274   for (int i = ape->extents_.size(); i--;)
 275     left_extent.unite (ape->offset_ +  ape->extents_[i][X_AXIS]);
 276
 277   ape = apes.top();
 278   for (int i = ape->extents_.size(); i--;)
 279     right_extent.unite (ape->offset_  + ape->extents_[i][X_AXIS]);
 280
 281   SCM ls = me->get_grob_property ("left-padding");
 282   if (gh_number_p (rs))
 283     left_extent[LEFT] -= gh_scm2double (ls);
 284
 285
 286   Interval width(left_extent[LEFT], right_extent[RIGHT]);
 287
 288   SCM scm_width = ly_interval2scm (width);
 289   me->set_extent (scm_width, X_AXIS);
 290
 291   for (int i = apes.size(); i--;)
 292     delete apes[i];
 293
 294   return scm_width;
 295 }
 296
 297 ADD_INTERFACE(Accidental_placement,
 298               "accidental-placement-interface",
 299               "Take care of complex accidental collisions.",
 300               "left-padding right-padding accidentals alignment-done")