2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2015 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 Grob *clash_up, Grob *clash_down)
41 /* Every note column should have a stem, but avoid a crash. */
42 if (!Note_column::get_stem (clash_up) || !Note_column::get_stem (clash_down))
45 Drul_array<Grob *> stems (Note_column::get_stem (clash_down),
46 Note_column::get_stem (clash_up));
48 Grob *head_up = Note_column::first_head (clash_up);
49 Grob *head_down = Note_column::first_head (clash_down);
51 Interval extent_up = head_up->extent (head_up, X_AXIS);
52 Interval extent_down = head_down->extent (head_down, X_AXIS);
54 /* Staff-positions of all noteheads on each stem */
55 vector<int> ups = Stem::note_head_positions (stems[UP]);
56 vector<int> dps = Stem::note_head_positions (stems[DOWN]);
58 /* Too far apart to collide. */
59 if (ups[0] > dps.back () + 1)
62 /* If the chords just 'touch' their extreme noteheads,
63 then we can align their stems.
66 if (ups[0] >= dps.back ()
67 && (dps.size () < 2 || ups[0] >= dps[dps.size () - 2] + 2)
68 && (ups.size () < 2 || ups[1] >= dps.back () + 2))
71 /* Filter out the 'o's in this configuration, since they're no
72 * part in the collision.
80 ups = Stem::note_head_positions (stems[UP], true);
81 dps = Stem::note_head_positions (stems[DOWN], true);
83 /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
84 above the "stem-down-note". */
85 bool merge_possible = (ups[0] >= dps[0]) && (ups.back () >= dps.back ());
87 /* Do not merge notes typeset in different style. */
88 if (!ly_is_equal (head_up->get_property ("style"),
89 head_down->get_property ("style")))
90 merge_possible = false;
92 int up_ball_type = Rhythmic_head::duration_log (head_up);
93 int down_ball_type = Rhythmic_head::duration_log (head_down);
95 /* Do not merge whole notes (or longer, like breve, longa, maxima). */
96 if (merge_possible && (up_ball_type <= 0 || down_ball_type <= 0))
97 merge_possible = false;
100 && Rhythmic_head::dot_count (head_up) != Rhythmic_head::dot_count (head_down)
101 && !to_boolean (me->get_property ("merge-differently-dotted")))
102 merge_possible = false;
104 /* Can only merge different heads if merge-differently-headed is set. */
106 && up_ball_type != down_ball_type
107 && !to_boolean (me->get_property ("merge-differently-headed")))
108 merge_possible = false;
110 /* Should never merge quarter and half notes, as this would make
111 them indistinguishable. */
113 && ((Stem::duration_log (stems[UP]) == 1
114 && Stem::duration_log (stems[DOWN]) == 2)
115 || (Stem::duration_log (stems[UP]) == 2
116 && Stem::duration_log (stems[DOWN]) == 1)))
117 merge_possible = false;
120 * this case (distant half collide),
127 * the noteheads may be closer than this case (close half collide)
138 bool close_half_collide = false;
139 bool distant_half_collide = false;
140 bool full_collide = false;
142 for (vsize i = 0, j = 0; i < ups.size () && j < dps.size ();)
144 if (abs (ups[i] - dps[j]) == 1)
146 merge_possible = false;
148 close_half_collide = true;
150 distant_half_collide = true;
152 else if (ups[i] == dps[j])
154 else if (ups[i] > dps[0] && ups[i] < dps.back ())
155 merge_possible = false;
156 else if (dps[j] > ups[0] && dps[j] < ups.back ())
157 merge_possible = false;
161 else if (ups[i] > dps[j])
170 full_collide = full_collide || (close_half_collide
171 && distant_half_collide)
172 || ( distant_half_collide // like full_ for wholes and longer
173 && (up_ball_type <= 0 || down_ball_type <= 0));
175 /* Determine which chord goes on the left, and which goes right.
176 Up-stem usually goes on the right, but if chords just 'touch' we can put
177 both stems on a common vertical line. In the presense of collisions,
178 right hand heads may obscure dots, so dotted heads to go the right.
180 Real shift_amount = 1;
181 bool stem_to_stem = false;
183 || ((close_half_collide || distant_half_collide)
184 && to_boolean (me->get_property ("prefer-dotted-right"))))
185 && Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
189 // remember to leave clearance between stems
194 // Up-stem note on a line has a raised dot, so no risk of collision
195 Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
197 || (!Staff_symbol_referencer::on_line (staff, ups[0])
198 && to_boolean (me->get_property ("prefer-dotted-right"))))
199 && Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
205 /* The solfa is a triangle, which is inverted depending on stem
206 direction. In case of a collision, one of them should be removed,
207 so the resulting note does not look like a block.
209 SCM up_style = head_up->get_property ("style");
210 SCM down_style = head_down->get_property ("style");
212 && (scm_is_eq (up_style, ly_symbol2scm ("fa"))
213 || scm_is_eq (up_style, ly_symbol2scm ("faThin")))
214 && (scm_is_eq (down_style, ly_symbol2scm ("fa"))
215 || scm_is_eq (down_style, ly_symbol2scm ("faThin"))))
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; and when
229 merging identical heads, dots on the down-stem head disappear */
231 Grob *dot_wipe_head = head_up;
233 if (up_ball_type == down_ball_type)
235 if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
237 wipe_ball = head_down;
238 dot_wipe_head = head_down;
240 else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
242 dot_wipe_head = head_up;
246 dot_wipe_head = head_down;
248 else if (down_ball_type > up_ball_type)
250 wipe_ball = head_down;
251 dot_wipe_head = head_down;
253 else if (down_ball_type < up_ball_type)
256 dot_wipe_head = head_up;
258 If upper head is eighth note or shorter, and lower head is half note,
259 shift by the difference between the open and filled note head widths,
260 otherwise upper stem will be misaligned slightly.
262 if (Stem::duration_log (stems[DOWN]) == 1
263 && Stem::duration_log (stems[UP]) >= 3)
264 shift_amount = (1 - extent_up[RIGHT] / extent_down[RIGHT]) * 0.5;
269 if (Grob *d = Grob::unsmob (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;
295 /* The offsets computed in this routine are multiplied,
296 in calc_positioning_done(), by the width of the downstem note.
297 The shift required to clear collisions, however, depends on the extents
298 of the note heads on the sides that interfere. */
299 if (shift_amount < 0.0) // Down-stem shifts right.
300 shift_amount *= (extent_up[RIGHT] - extent_down[LEFT]) / extent_down.length ();
301 else // Up-stem shifts right.
302 shift_amount *= (extent_down[RIGHT] - extent_up[LEFT]) / extent_down.length ();
304 /* If any dotted notes ended up on the left,
305 tell the Dot_Columnn to avoid the note heads on the right.
307 if (shift_amount < -1e-6
308 && Rhythmic_head::dot_count (head_up))
310 Grob *d = Grob::unsmob (head_up->get_object ("dot"));
311 Grob *parent = d->get_parent (X_AXIS);
312 if (Dot_column::has_interface (parent))
313 Side_position_interface::add_support (parent, head_down);
315 else if (Rhythmic_head::dot_count (head_down))
317 Grob *d = Grob::unsmob (head_down->get_object ("dot"));
318 Grob *parent = d->get_parent (X_AXIS);
319 if (Dot_column::has_interface (parent))
321 Grob *stem = Grob::unsmob (head_up->get_object ("stem"));
322 // Loop over all heads on an up-pointing-stem to see if dots
323 // need to clear any heads suspended on its right side.
324 extract_grob_set (stem, "note-heads", heads);
325 for (vsize i = 0; i < heads.size (); i++)
326 Side_position_interface::add_support (parent, heads[i]);
330 // In meshed chords with dots on the left, adjust dot direction
331 if (shift_amount > 1e-6
332 && Rhythmic_head::dot_count (head_down))
334 Grob *dot_down = Grob::unsmob (head_down->get_object ("dot"));
335 Grob *col_down = dot_down->get_parent (X_AXIS);
337 if (Rhythmic_head::dot_count (head_up))
339 Grob *dot_up = Grob::unsmob (head_up->get_object ("dot"));
340 Grob *col_up = dot_up->get_parent (X_AXIS);
341 if (col_up == col_down) // let the common DotColumn arrange dots
343 else // conform to the dot direction on the up-stem chord
344 dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
348 Grob *stem = Grob::unsmob (head_down->get_object ("stem"));
349 extract_grob_set (stem, "note-heads", heads);
350 for (vsize i = 0; i < heads.size (); i++)
351 if (Grob *dot = Grob::unsmob (heads[i]->get_object ("dot")))
352 dot->set_property ("direction", scm_from_int (dir));
359 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
361 Note_collision_interface::calc_positioning_done (SCM smob)
363 Grob *me = Grob::unsmob (smob);
364 me->set_property ("positioning-done", SCM_BOOL_T);
366 Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
368 for (UP_and_DOWN (d))
370 for (vsize i = clash_groups[d].size (); i--;)
375 clash_groups[d][i]->extent (me, X_AXIS);
379 SCM autos (automatic_shift (me, clash_groups));
380 SCM hand (forced_shift (me));
383 for (UP_and_DOWN (d))
385 if (clash_groups[d].size ())
387 Grob *h = clash_groups[d][0];
388 Grob *fh = Note_column::first_head (h);
390 wid = fh->extent (h, X_AXIS).length ();
395 Real left_most = 1e6;
397 vector<Real> amounts;
398 for (; scm_is_pair (hand); hand = scm_cdr (hand))
400 Grob *s = Grob::unsmob (scm_caar (hand));
401 Real amount = scm_to_double (scm_cdar (hand)) * wid;
404 amounts.push_back (amount);
405 if (amount < left_most)
408 for (; scm_is_pair (autos); autos = scm_cdr (autos))
410 Grob *s = Grob::unsmob (scm_caar (autos));
411 Real amount = scm_to_double (scm_cdar (autos)) * wid;
413 vsize x = find (done, s) - done.begin ();
414 if (x == VPOS || x >= done.size ())
417 amounts.push_back (amount);
418 if (amount < left_most)
423 for (vsize i = 0; i < amounts.size (); i++)
424 done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
429 Drul_array < vector<Grob *> >
430 Note_collision_interface::get_clash_groups (Grob *me)
432 Drul_array<vector<Grob *> > clash_groups;
434 extract_grob_set (me, "elements", elements);
435 for (vsize i = 0; i < elements.size (); i++)
437 Grob *se = elements[i];
438 if (Note_column::has_interface (se))
440 if (!Note_column::dir (se))
441 se->programming_error ("note-column has no direction");
443 clash_groups[Note_column::dir (se)].push_back (se);
447 for (UP_and_DOWN (d))
449 vector<Grob *> &clashes (clash_groups[d]);
450 vector_sort (clashes, Note_column::shift_less);
457 This complicated routine moves note columns around horizontally to
458 ensure that notes don't clash.
461 Note_collision_interface::automatic_shift (Grob *me,
462 Drul_array<vector<Grob *> > clash_groups)
466 Drul_array<vector<Slice> > extents;
467 Drul_array<Slice> extent_union;
468 Drul_array<vector<Grob *> > stems;
469 for (UP_and_DOWN (d))
471 for (vsize i = 0; i < clash_groups[d].size (); i++)
473 Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
476 extents[d].push_back (s);
477 extent_union[d].unite (s);
478 stems[d].push_back (Note_column::get_stem (clash_groups[d][i]));
483 = (clash_groups[UP].size () && clash_groups[DOWN].size ())
484 ? check_meshing_chords (me, clash_groups[UP][0], clash_groups[DOWN][0])
488 * do horizontal shifts of each direction
495 Drul_array<vector<Real> > offsets;
496 for (UP_and_DOWN (d))
498 Real offset = inner_offset;
500 for (vsize i = 0; i < clash_groups[d].size (); i++)
502 Grob *col = clash_groups[d][i];
503 SCM sh = col->get_property ("horizontal-shift");
504 shifts.push_back (robust_scm2int (sh, 0));
507 offset = inner_offset;
510 bool explicit_shift = scm_is_number (sh);
512 col->warning (_ ("this Voice needs a \\voiceXx or \\shiftXx setting"));
514 if (explicit_shift && shifts[i] == shifts[i - 1])
515 ; // Match the previous notecolumn offset
516 else if (extents[d][i][UP] > extents[d][i - 1][DOWN]
517 && extents[d][i][DOWN] < extents[d][i - 1][UP])
518 offset += 1.0; // fully clear the previous-notecolumn heads
519 else if (d * extents[d][i][-d] >= d * extents[d][i - 1][d])
520 offset += Stem::is_valid_stem (stems[d][i - 1])
521 ? 1.0 : 0.5; // we cross the previous notecolumn
522 else if (Stem::is_valid_stem (stems[d][i]))
525 // check if we cross the opposite-stemmed voices
526 if (d * extents[d][i][-d] < d * extent_union[-d][d])
527 offset = max (offset, 0.5);
528 if (extents[-d].size ()
529 && extents[d][i][UP] > extents[-d][0][DOWN]
530 && extents[d][i][DOWN] < extents[-d][0][UP])
531 offset = max (offset, 1.0);
533 offsets[d].push_back (d * offset);
538 see input/regression/dot-up-voice-collision.ly
540 for (vsize i = 0; i < clash_groups[UP].size (); i++)
542 Grob *g = clash_groups[UP][i];
543 Grob *dc = Note_column::dot_column (g);
546 for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
547 Side_position_interface::add_support (dc, stems[UP][j]);
550 for (UP_and_DOWN (d))
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])),
562 Note_collision_interface::forced_shift (Grob *me)
566 extract_grob_set (me, "elements", elements);
567 for (vsize i = 0; i < elements.size (); i++)
569 Grob *se = elements[i];
571 SCM force = se->get_property ("force-hshift");
572 if (scm_is_number (force))
573 tups = scm_cons (scm_cons (se->self_scm (), force),
580 Note_collision_interface::add_column (Grob *me, Grob *ncol)
582 ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
583 Axis_group_interface::add_element (me, ncol);
587 Note_collision_interface::note_head_positions (Grob *me)
590 extract_grob_set (me, "elements", elts);
591 for (vsize i = 0; i < elts.size (); i++)
592 if (Grob *stem = Grob::unsmob (elts[i]->get_object ("stem")))
594 vector<int> nhp = Stem::note_head_positions (stem);
595 out.insert (out.end (), nhp.begin (), nhp.end ());
598 vector_sort (out, less<int> ());
602 ADD_INTERFACE (Note_collision_interface,
603 "An object that handles collisions between notes with"
604 " different stem directions and horizontal shifts. Most of"
605 " the interesting properties are to be set in"
606 " @ref{note-column-interface}: these are @code{force-hshift}"
607 " and @code{horizontal-shift}.",
610 "merge-differently-dotted "
611 "merge-differently-headed "
613 "prefer-dotted-right "