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