2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2011 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))
189 if (!touch || full_collide)
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 Interval uphead_size = head_up->extent (head_up, Y_AXIS);
217 Offset att = Offset (0.0, -1.0);
218 head_up->set_property ("stem-attachment", ly_offset2scm (att));
219 head_up->set_property ("transparent", SCM_BOOL_T);
226 /* If possible, don't wipe any heads. Else, wipe shortest head,
227 or head with smallest amount of dots. Note: when merging
228 different heads, dots on the smaller one disappear. */
230 Grob *dot_wipe_head = head_up;
232 if (up_ball_type == down_ball_type)
234 if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
236 wipe_ball = head_down;
237 dot_wipe_head = head_down;
239 else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
241 dot_wipe_head = head_up;
245 dot_wipe_head = head_up;
247 else if (down_ball_type > up_ball_type)
249 wipe_ball = head_down;
250 dot_wipe_head = head_down;
252 else if (down_ball_type < up_ball_type)
255 dot_wipe_head = head_up;
257 If upper head is eighth note or shorter, and lower head is half note,
258 shift by the difference between the open and filled note head widths,
259 otherwise upper stem will be misaligned slightly.
261 if (Stem::duration_log (stems[DOWN]) == 1
262 && Stem::duration_log (stems[UP]) >= 3)
263 shift_amount = (1 - head_up->extent (head_up, X_AXIS).length ()
264 / head_down->extent (head_down, X_AXIS).length ()) * 0.5;
269 if (Grob *d = unsmob_grob (dot_wipe_head->get_object ("dot")))
273 if (wipe_ball && wipe_ball->is_live ())
274 wipe_ball->set_property ("transparent", SCM_BOOL_T);
276 /* TODO: these numbers are magic; should devise a set of grob props
277 to tune this behavior. */
278 else if (stem_to_stem)
279 shift_amount *= 0.65;
282 else if (close_half_collide)
283 shift_amount *= 0.52;
284 else if (full_collide)
286 else if (distant_half_collide)
290 else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
293 shift_amount *= 0.17;
298 && down_ball_type *up_ball_type == 0)
300 if (up_ball_type == 0 && down_ball_type == 1)
301 shift_amount *= 1.25;
302 else if (up_ball_type == 0 && down_ball_type == 2)
303 shift_amount *= 1.35;
304 else if (down_ball_type == 0 && up_ball_type == 1)
306 else if (down_ball_type == 0 && up_ball_type == 2)
307 shift_amount *= 0.75;
310 /* If the dotted notes ended up on the left, and there are collisions,
311 tell the Dot_Columnn to avoid the notes on the right.
313 if (full_collide || close_half_collide || distant_half_collide)
315 if (shift_amount < -1e-6
316 && Rhythmic_head::dot_count (head_up)
317 && !Rhythmic_head::dot_count (head_down))
319 Grob *d = unsmob_grob (head_up->get_object ("dot"));
320 Grob *parent = d->get_parent (X_AXIS);
321 if (Dot_column::has_interface (parent))
322 Side_position_interface::add_support (parent, head_down);
324 else if (Rhythmic_head::dot_count (head_down)
325 && !Rhythmic_head::dot_count (head_up))
327 Grob *d = unsmob_grob (head_down->get_object ("dot"));
328 Grob *parent = d->get_parent (X_AXIS);
329 if (Dot_column::has_interface (parent))
331 Grob *stem = unsmob_grob (head_up->get_object ("stem"));
332 extract_grob_set (stem, "note-heads", heads);
333 for (vsize i = 0; i < heads.size (); i++)
334 Side_position_interface::add_support (parent, heads[i]);
342 for (vsize i = 0; i < clash_groups[d].size (); i++)
343 (*offsets)[d][i] += d * shift_amount;
345 while ((flip (&d)) != UP);
348 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
350 Note_collision_interface::calc_positioning_done (SCM smob)
352 Grob *me = unsmob_grob (smob);
353 me->set_property ("positioning-done", SCM_BOOL_T);
355 Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
360 for (vsize i = clash_groups[d].size (); i--;)
365 clash_groups[d][i]->extent (me, X_AXIS);
368 while (flip (&d) != UP);
370 SCM autos (automatic_shift (me, clash_groups));
371 SCM hand (forced_shift (me));
376 if (clash_groups[d].size ())
378 Grob *h = clash_groups[d][0];
379 Grob *fh = Note_column::first_head (h);
381 wid = fh->extent (h, X_AXIS).length ();
384 while (flip (&d) != UP);
387 Real left_most = 1e6;
389 vector<Real> amounts;
390 for (; scm_is_pair (hand); hand = scm_cdr (hand))
392 Grob *s = unsmob_grob (scm_caar (hand));
393 Real amount = scm_to_double (scm_cdar (hand)) * wid;
396 amounts.push_back (amount);
397 if (amount < left_most)
400 for (; scm_is_pair (autos); autos = scm_cdr (autos))
402 Grob *s = unsmob_grob (scm_caar (autos));
403 Real amount = scm_to_double (scm_cdar (autos)) * wid;
405 vsize x = find (done, s) - done.begin ();
406 if (x == VPOS || x >= done.size ())
409 amounts.push_back (amount);
410 if (amount < left_most)
415 for (vsize i = 0; i < amounts.size (); i++)
416 done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
421 Drul_array < vector<Grob *> >
422 Note_collision_interface::get_clash_groups (Grob *me)
424 Drul_array<vector<Grob *> > clash_groups;
426 extract_grob_set (me, "elements", elements);
427 for (vsize i = 0; i < elements.size (); i++)
429 Grob *se = elements[i];
430 if (Note_column::has_interface (se))
432 if (!Note_column::dir (se))
433 se->programming_error ("note-column has no direction");
435 clash_groups[Note_column::dir (se)].push_back (se);
442 vector<Grob *> &clashes (clash_groups[d]);
443 vector_sort (clashes, Note_column::shift_less);
445 while ((flip (&d)) != UP);
451 This complicated routine moves note columns around horizontally to
452 ensure that notes don't clash.
455 Note_collision_interface::automatic_shift (Grob *me,
456 Drul_array<vector<Grob *> > clash_groups)
458 Drul_array < vector<int> > shifts;
464 vector<int> &shift (shifts[d]);
465 vector<Grob *> &clashes (clash_groups[d]);
467 for (vsize i = 0; i < clashes.size (); i++)
470 = clashes[i]->get_property ("horizontal-shift");
472 if (scm_is_number (sh))
473 shift.push_back (scm_to_int (sh));
478 for (vsize i = 1; i < shift.size (); i++)
480 if (shift[i - 1] == shift[i])
482 clashes[0]->warning (_ ("ignoring too many clashing note columns"));
487 while ((flip (&d)) != UP);
489 Drul_array<vector<Slice> > extents;
490 Drul_array<vector<Real> > offsets;
494 for (vsize i = 0; i < clash_groups[d].size (); i++)
496 Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
499 extents[d].push_back (s);
500 offsets[d].push_back (d * 0.5 * i);
503 while ((flip (&d)) != UP);
506 do horizontal shifts of each direction
516 for (vsize i = 1; i < clash_groups[d].size (); i++)
518 Slice prev = extents[d][i - 1];
519 prev.intersect (extents[d][i]);
520 if (prev.length () > 0
521 || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
522 for (vsize j = i; j < clash_groups[d].size (); j++)
523 offsets[d][j] += d * 0.5;
526 while ((flip (&d)) != UP);
529 see input/regression/dot-up-voice-collision.ly
531 for (vsize i = 0; i < clash_groups[UP].size (); i++)
533 Grob *g = clash_groups[UP][i];
534 Grob *dc = Note_column::dot_column (g);
537 for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
539 Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
540 Side_position_interface::add_support (dc, stem);
545 Check if chords are meshing
548 check_meshing_chords (me, &offsets, extents, clash_groups);
552 for (vsize i = 0; i < clash_groups[d].size (); i++)
553 tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
554 scm_from_double (offsets[d][i])),
557 while (flip (&d) != UP);
563 Note_collision_interface::forced_shift (Grob *me)
567 extract_grob_set (me, "elements", elements);
568 for (vsize i = 0; i < elements.size (); i++)
570 Grob *se = elements[i];
572 SCM force = se->get_property ("force-hshift");
573 if (scm_is_number (force))
574 tups = scm_cons (scm_cons (se->self_scm (), force),
581 Note_collision_interface::add_column (Grob *me, Grob *ncol)
583 ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
584 Axis_group_interface::add_element (me, ncol);
587 ADD_INTERFACE (Note_collision_interface,
588 "An object that handles collisions between notes with"
589 " different stem directions and horizontal shifts. Most of"
590 " the interesting properties are to be set in"
591 " @ref{note-column-interface}: these are @code{force-hshift}"
592 " and @code{horizontal-shift}.",
595 "merge-differently-dotted "
596 "merge-differently-headed "
598 "prefer-dotted-right "