2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2012 Han-Wen Nienhuys <hanwen@xs4all.nl>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
20 #include "note-collision.hh"
22 #include "axis-group-interface.hh"
23 #include "dot-column.hh"
24 #include "international.hh"
25 #include "note-column.hh"
26 #include "note-head.hh"
27 #include "output-def.hh"
28 #include "pointer-group-interface.hh"
30 #include "rhythmic-head.hh"
31 #include "staff-symbol-referencer.hh"
32 #include "side-position-interface.hh"
37 check_meshing_chords (Grob *me,
38 Drul_array<vector<Real> > *offsets,
39 Drul_array<vector<Slice> > const &extents,
40 Drul_array<vector<Grob *> > const &clash_groups)
43 if (!extents[UP].size () || !extents[DOWN].size ())
46 Grob *clash_up = clash_groups[UP][0];
47 Grob *clash_down = clash_groups[DOWN][0];
49 /* Every note column should have a stem, but avoid a crash. */
50 if (!Note_column::get_stem (clash_up) || !Note_column::get_stem (clash_down))
53 Drul_array<Grob *> stems (Note_column::get_stem (clash_down),
54 Note_column::get_stem (clash_up));
56 Grob *head_up = Note_column::first_head (clash_up);
57 Grob *head_down = Note_column::first_head (clash_down);
59 vector<int> ups = Stem::note_head_positions (Note_column::get_stem (clash_up));
60 vector<int> dps = Stem::note_head_positions (Note_column::get_stem (clash_down));
62 /* Too far apart to collide. */
63 if (ups[0] > dps.back () + 1)
66 /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
67 above the "stem-down-note". */
68 bool merge_possible = (ups[0] >= dps[0]) && (ups.back () >= dps.back ());
70 /* Do not merge notes typeset in different style. */
71 if (!ly_is_equal (head_up->get_property ("style"),
72 head_down->get_property ("style")))
73 merge_possible = false;
75 int up_ball_type = Rhythmic_head::duration_log (head_up);
76 int down_ball_type = Rhythmic_head::duration_log (head_down);
78 /* Do not merge whole notes (or longer, like breve, longa, maxima). */
79 if (merge_possible && (up_ball_type <= 0 || down_ball_type <= 0))
80 merge_possible = false;
83 && Rhythmic_head::dot_count (head_up) != Rhythmic_head::dot_count (head_down)
84 && !to_boolean (me->get_property ("merge-differently-dotted")))
85 merge_possible = false;
87 /* Can only merge different heads if merge-differently-headed is set. */
89 && up_ball_type != down_ball_type
90 && !to_boolean (me->get_property ("merge-differently-headed")))
91 merge_possible = false;
93 /* Should never merge quarter and half notes, as this would make
94 them indistinguishable. */
96 && ((Stem::duration_log (stems[UP]) == 1
97 && Stem::duration_log (stems[DOWN]) == 2)
98 || (Stem::duration_log (stems[UP]) == 2
99 && Stem::duration_log (stems[DOWN]) == 1)))
100 merge_possible = false;
103 * this case (distant half collide),
110 * the noteheads may be closer than this case (close half collide)
121 /* TODO: filter out the 'o's in this configuration, since they're no
122 * part in the collision.
131 bool close_half_collide = false;
132 bool distant_half_collide = false;
133 bool full_collide = false;
135 for (vsize i = 0, j = 0; i < ups.size () && j < dps.size ();)
137 if (abs (ups[i] - dps[j]) == 1)
139 merge_possible = false;
141 close_half_collide = true;
143 distant_half_collide = true;
145 else if (ups[i] == dps[j])
147 else if (ups[i] > dps[0] && ups[i] < dps.back ())
148 merge_possible = false;
149 else if (dps[j] > ups[0] && dps[j] < ups.back ())
150 merge_possible = false;
154 else if (ups[i] > dps[j])
163 full_collide = full_collide || (close_half_collide
164 && distant_half_collide);
166 /* If the only collision is in the extreme noteheads,
167 then their stems can line up and the chords just 'touch'.
168 A half collision with the next note along the chord prevents touching.
171 if (ups[0] >= dps.back ()
172 && (dps.size () < 2 || ups[0] >= dps[dps.size () - 2] + 2)
173 && (ups.size () < 2 || ups[1] >= dps.back () + 2))
176 /* Determine which chord goes on the left, and which goes right.
177 Up-stem usually goes on the right, but if chords just 'touch' we can put
178 both stems on a common vertical line. In the presense of collisions,
179 right hand heads may obscure dots, so dotted heads to go the right.
181 Real shift_amount = 1;
182 bool stem_to_stem = false;
184 || ((close_half_collide || distant_half_collide)
185 && to_boolean (me->get_property ("prefer-dotted-right"))))
186 && Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
190 // remember to leave clearance between stems
195 // Up-stem note on a line has a raised dot, so no risk of collision
196 Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
198 || (!Staff_symbol_referencer::on_line (staff, ups[0])
199 && to_boolean (me->get_property ("prefer-dotted-right"))))
200 && Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
206 /* The solfa is a triangle, which is inverted depending on stem
207 direction. In case of a collision, one of them should be removed,
208 so the resulting note does not look like a block.
210 SCM up_style = head_up->get_property ("style");
211 SCM down_style = head_down->get_property ("style");
213 && (up_style == ly_symbol2scm ("fa") || up_style == ly_symbol2scm ("faThin"))
214 && (down_style == ly_symbol2scm ("fa") || down_style == ly_symbol2scm ("faThin")))
216 Offset att = Offset (0.0, -1.0);
217 head_up->set_property ("stem-attachment", ly_offset2scm (att));
218 head_up->set_property ("transparent", SCM_BOOL_T);
225 /* If possible, don't wipe any heads. Else, wipe shortest head,
226 or head with smallest amount of dots. Note: when merging
227 different heads, dots on the smaller one disappear. */
229 Grob *dot_wipe_head = head_up;
231 if (up_ball_type == down_ball_type)
233 if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
235 wipe_ball = head_down;
236 dot_wipe_head = head_down;
238 else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
240 dot_wipe_head = head_up;
244 dot_wipe_head = head_up;
246 else if (down_ball_type > up_ball_type)
248 wipe_ball = head_down;
249 dot_wipe_head = head_down;
251 else if (down_ball_type < up_ball_type)
254 dot_wipe_head = head_up;
256 If upper head is eighth note or shorter, and lower head is half note,
257 shift by the difference between the open and filled note head widths,
258 otherwise upper stem will be misaligned slightly.
260 if (Stem::duration_log (stems[DOWN]) == 1
261 && Stem::duration_log (stems[UP]) >= 3)
262 shift_amount = (1 - head_up->extent (head_up, X_AXIS).length ()
263 / head_down->extent (head_down, X_AXIS).length ()) * 0.5;
268 if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
272 if (wipe_ball && wipe_ball->is_live ())
273 wipe_ball->set_property ("transparent", SCM_BOOL_T);
275 /* TODO: these numbers are magic; should devise a set of grob props
276 to tune this behavior. */
277 else if (stem_to_stem)
278 shift_amount *= 0.65;
281 else if (close_half_collide)
282 shift_amount *= 0.52;
283 else if (full_collide)
285 else if (distant_half_collide)
289 else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
292 shift_amount *= 0.17;
297 && down_ball_type *up_ball_type == 0)
299 if (up_ball_type == 0 && down_ball_type == 1)
300 shift_amount *= 1.25;
301 else if (up_ball_type == 0 && down_ball_type == 2)
302 shift_amount *= 1.35;
303 else if (down_ball_type == 0 && up_ball_type == 1)
305 else if (down_ball_type == 0 && up_ball_type == 2)
306 shift_amount *= 0.75;
309 /* If any dotted notes ended up on the left,
310 tell the Dot_Columnn to avoid the note heads on the right.
312 if (shift_amount < -1e-6
313 && Rhythmic_head::dot_count (head_up))
315 Grob *d = unsmob_grob (head_up->get_object ("dot"));
316 Grob *parent = d->get_parent (X_AXIS);
317 if (Dot_column::has_interface (parent))
318 Side_position_interface::add_support (parent, head_down);
320 else if (Rhythmic_head::dot_count (head_down))
322 Grob *d = unsmob_grob (head_down->get_object ("dot"));
323 Grob *parent = d->get_parent (X_AXIS);
324 if (Dot_column::has_interface (parent))
326 Grob *stem = unsmob_grob (head_up->get_object ("stem"));
327 // Loop over all heads on an up-pointing-stem to see if dots
328 // need to clear any heads suspended on its right side.
329 extract_grob_set (stem, "note-heads", heads);
330 for (vsize i = 0; i < heads.size (); i++)
331 Side_position_interface::add_support (parent, heads[i]);
335 // In meshed chords with dots on the left, adjust dot direction
336 if (shift_amount > 1e-6
337 && Rhythmic_head::dot_count (head_down))
339 Grob *dot_down = unsmob_grob (head_down->get_object ("dot"));
340 Grob *col_down = dot_down->get_parent (X_AXIS);
342 if (Rhythmic_head::dot_count (head_up))
344 Grob *dot_up = unsmob_grob (head_up->get_object ("dot"));
345 Grob *col_up = dot_up->get_parent (X_AXIS);
346 if (col_up == col_down) // let the common DotColumn arrange dots
348 else // conform to the dot direction on the up-stem chord
349 dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
353 Grob *stem = unsmob_grob (head_down->get_object ("stem"));
354 extract_grob_set (stem, "note-heads", heads);
355 for (vsize i = 0; i < heads.size (); i++)
356 unsmob_grob (heads[i]->get_object ("dot"))
357 ->set_property ("direction", scm_from_int (dir));
364 for (vsize i = 0; i < clash_groups[d].size (); i++)
365 (*offsets)[d][i] += d * shift_amount;
367 while ((flip (&d)) != UP);
370 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
372 Note_collision_interface::calc_positioning_done (SCM smob)
374 Grob *me = unsmob_grob (smob);
375 me->set_property ("positioning-done", SCM_BOOL_T);
377 Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
382 for (vsize i = clash_groups[d].size (); i--;)
387 clash_groups[d][i]->extent (me, X_AXIS);
390 while (flip (&d) != UP);
392 SCM autos (automatic_shift (me, clash_groups));
393 SCM hand (forced_shift (me));
398 if (clash_groups[d].size ())
400 Grob *h = clash_groups[d][0];
401 Grob *fh = Note_column::first_head (h);
403 wid = fh->extent (h, X_AXIS).length ();
406 while (flip (&d) != UP);
409 Real left_most = 1e6;
411 vector<Real> amounts;
412 for (; scm_is_pair (hand); hand = scm_cdr (hand))
414 Grob *s = unsmob_grob (scm_caar (hand));
415 Real amount = scm_to_double (scm_cdar (hand)) * wid;
418 amounts.push_back (amount);
419 if (amount < left_most)
422 for (; scm_is_pair (autos); autos = scm_cdr (autos))
424 Grob *s = unsmob_grob (scm_caar (autos));
425 Real amount = scm_to_double (scm_cdar (autos)) * wid;
427 vsize x = find (done, s) - done.begin ();
428 if (x == VPOS || x >= done.size ())
431 amounts.push_back (amount);
432 if (amount < left_most)
437 for (vsize i = 0; i < amounts.size (); i++)
438 done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
443 Drul_array < vector<Grob *> >
444 Note_collision_interface::get_clash_groups (Grob *me)
446 Drul_array<vector<Grob *> > clash_groups;
448 extract_grob_set (me, "elements", elements);
449 for (vsize i = 0; i < elements.size (); i++)
451 Grob *se = elements[i];
452 if (Note_column::has_interface (se))
454 if (!Note_column::dir (se))
455 se->programming_error ("note-column has no direction");
457 clash_groups[Note_column::dir (se)].push_back (se);
464 vector<Grob *> &clashes (clash_groups[d]);
465 vector_sort (clashes, Note_column::shift_less);
467 while ((flip (&d)) != UP);
473 This complicated routine moves note columns around horizontally to
474 ensure that notes don't clash.
477 Note_collision_interface::automatic_shift (Grob *me,
478 Drul_array<vector<Grob *> > clash_groups)
480 Drul_array < vector<int> > shifts;
486 vector<int> &shift (shifts[d]);
487 vector<Grob *> &clashes (clash_groups[d]);
489 for (vsize i = 0; i < clashes.size (); i++)
492 = clashes[i]->get_property ("horizontal-shift");
494 if (scm_is_number (sh))
495 shift.push_back (scm_to_int (sh));
500 for (vsize i = 1; i < shift.size (); i++)
502 if (shift[i - 1] == shift[i])
504 clashes[0]->warning (_ ("ignoring too many clashing note columns"));
509 while ((flip (&d)) != UP);
511 Drul_array<vector<Slice> > extents;
512 Drul_array<vector<Real> > offsets;
516 for (vsize i = 0; i < clash_groups[d].size (); i++)
518 Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
521 extents[d].push_back (s);
522 offsets[d].push_back (d * 0.5 * i);
525 while ((flip (&d)) != UP);
528 do horizontal shifts of each direction
538 for (vsize i = 1; i < clash_groups[d].size (); i++)
540 Slice prev = extents[d][i - 1];
541 prev.intersect (extents[d][i]);
542 if (prev.length () > 0
543 || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
544 for (vsize j = i; j < clash_groups[d].size (); j++)
545 offsets[d][j] += d * 0.5;
548 while ((flip (&d)) != UP);
551 see input/regression/dot-up-voice-collision.ly
553 for (vsize i = 0; i < clash_groups[UP].size (); i++)
555 Grob *g = clash_groups[UP][i];
556 Grob *dc = Note_column::dot_column (g);
559 for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
561 Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
562 Side_position_interface::add_support (dc, stem);
567 Check if chords are meshing
570 check_meshing_chords (me, &offsets, extents, clash_groups);
574 for (vsize i = 0; i < clash_groups[d].size (); i++)
575 tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
576 scm_from_double (offsets[d][i])),
579 while (flip (&d) != UP);
585 Note_collision_interface::forced_shift (Grob *me)
589 extract_grob_set (me, "elements", elements);
590 for (vsize i = 0; i < elements.size (); i++)
592 Grob *se = elements[i];
594 SCM force = se->get_property ("force-hshift");
595 if (scm_is_number (force))
596 tups = scm_cons (scm_cons (se->self_scm (), force),
603 Note_collision_interface::add_column (Grob *me, Grob *ncol)
605 ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
606 Axis_group_interface::add_element (me, ncol);
609 ADD_INTERFACE (Note_collision_interface,
610 "An object that handles collisions between notes with"
611 " different stem directions and horizontal shifts. Most of"
612 " the interesting properties are to be set in"
613 " @ref{note-column-interface}: these are @code{force-hshift}"
614 " and @code{horizontal-shift}.",
617 "merge-differently-dotted "
618 "merge-differently-headed "
620 "prefer-dotted-right "