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 && (up_style == ly_symbol2scm ("fa") || up_style == ly_symbol2scm ("faThin"))
213 && (down_style == ly_symbol2scm ("fa") || down_style == ly_symbol2scm ("faThin")))
215 Offset att = Offset (0.0, -1.0);
216 head_up->set_property ("stem-attachment", ly_offset2scm (att));
217 head_up->set_property ("transparent", SCM_BOOL_T);
224 /* If possible, don't wipe any heads. Else, wipe shortest head,
225 or head with smallest amount of dots. Note: when merging
226 different heads, dots on the smaller one disappear; and when
227 merging identical heads, dots on the down-stem head 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_down;
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 - extent_up[RIGHT] / extent_down[RIGHT]) * 0.5;
267 if (Grob *d = Grob::unsmob (dot_wipe_head->get_object ("dot")))
271 if (wipe_ball && wipe_ball->is_live ())
272 wipe_ball->set_property ("transparent", SCM_BOOL_T);
274 /* TODO: these numbers are magic; should devise a set of grob props
275 to tune this behavior. */
276 else if (stem_to_stem)
277 shift_amount *= 0.65;
280 else if (close_half_collide)
281 shift_amount *= 0.52;
282 else if (full_collide)
284 else if (distant_half_collide)
288 else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
291 shift_amount *= 0.17;
293 /* The offsets computed in this routine are multiplied,
294 in calc_positioning_done(), by the width of the downstem note.
295 The shift required to clear collisions, however, depends on the extents
296 of the note heads on the sides that interfere. */
297 if (shift_amount < 0.0) // Down-stem shifts right.
298 shift_amount *= (extent_up[RIGHT] - extent_down[LEFT]) / extent_down.length ();
299 else // Up-stem shifts right.
300 shift_amount *= (extent_down[RIGHT] - extent_up[LEFT]) / extent_down.length ();
302 /* If any dotted notes ended up on the left,
303 tell the Dot_Columnn to avoid the note heads on the right.
305 if (shift_amount < -1e-6
306 && Rhythmic_head::dot_count (head_up))
308 Grob *d = Grob::unsmob (head_up->get_object ("dot"));
309 Grob *parent = d->get_parent (X_AXIS);
310 if (Dot_column::has_interface (parent))
311 Side_position_interface::add_support (parent, head_down);
313 else if (Rhythmic_head::dot_count (head_down))
315 Grob *d = Grob::unsmob (head_down->get_object ("dot"));
316 Grob *parent = d->get_parent (X_AXIS);
317 if (Dot_column::has_interface (parent))
319 Grob *stem = Grob::unsmob (head_up->get_object ("stem"));
320 // Loop over all heads on an up-pointing-stem to see if dots
321 // need to clear any heads suspended on its right side.
322 extract_grob_set (stem, "note-heads", heads);
323 for (vsize i = 0; i < heads.size (); i++)
324 Side_position_interface::add_support (parent, heads[i]);
328 // In meshed chords with dots on the left, adjust dot direction
329 if (shift_amount > 1e-6
330 && Rhythmic_head::dot_count (head_down))
332 Grob *dot_down = Grob::unsmob (head_down->get_object ("dot"));
333 Grob *col_down = dot_down->get_parent (X_AXIS);
335 if (Rhythmic_head::dot_count (head_up))
337 Grob *dot_up = Grob::unsmob (head_up->get_object ("dot"));
338 Grob *col_up = dot_up->get_parent (X_AXIS);
339 if (col_up == col_down) // let the common DotColumn arrange dots
341 else // conform to the dot direction on the up-stem chord
342 dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
346 Grob *stem = Grob::unsmob (head_down->get_object ("stem"));
347 extract_grob_set (stem, "note-heads", heads);
348 for (vsize i = 0; i < heads.size (); i++)
349 if (Grob *dot = Grob::unsmob (heads[i]->get_object ("dot")))
350 dot->set_property ("direction", scm_from_int (dir));
357 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
359 Note_collision_interface::calc_positioning_done (SCM smob)
361 Grob *me = Grob::unsmob (smob);
362 me->set_property ("positioning-done", SCM_BOOL_T);
364 Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
366 for (UP_and_DOWN (d))
368 for (vsize i = clash_groups[d].size (); i--;)
373 clash_groups[d][i]->extent (me, X_AXIS);
377 SCM autos (automatic_shift (me, clash_groups));
378 SCM hand (forced_shift (me));
381 for (UP_and_DOWN (d))
383 if (clash_groups[d].size ())
385 Grob *h = clash_groups[d][0];
386 Grob *fh = Note_column::first_head (h);
388 wid = fh->extent (h, X_AXIS).length ();
393 Real left_most = 1e6;
395 vector<Real> amounts;
396 for (; scm_is_pair (hand); hand = scm_cdr (hand))
398 Grob *s = Grob::unsmob (scm_caar (hand));
399 Real amount = scm_to_double (scm_cdar (hand)) * wid;
402 amounts.push_back (amount);
403 if (amount < left_most)
406 for (; scm_is_pair (autos); autos = scm_cdr (autos))
408 Grob *s = Grob::unsmob (scm_caar (autos));
409 Real amount = scm_to_double (scm_cdar (autos)) * wid;
411 vsize x = find (done, s) - done.begin ();
412 if (x == VPOS || x >= done.size ())
415 amounts.push_back (amount);
416 if (amount < left_most)
421 for (vsize i = 0; i < amounts.size (); i++)
422 done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
427 Drul_array < vector<Grob *> >
428 Note_collision_interface::get_clash_groups (Grob *me)
430 Drul_array<vector<Grob *> > clash_groups;
432 extract_grob_set (me, "elements", elements);
433 for (vsize i = 0; i < elements.size (); i++)
435 Grob *se = elements[i];
436 if (Note_column::has_interface (se))
438 if (!Note_column::dir (se))
439 se->programming_error ("note-column has no direction");
441 clash_groups[Note_column::dir (se)].push_back (se);
445 for (UP_and_DOWN (d))
447 vector<Grob *> &clashes (clash_groups[d]);
448 vector_sort (clashes, Note_column::shift_less);
455 This complicated routine moves note columns around horizontally to
456 ensure that notes don't clash.
459 Note_collision_interface::automatic_shift (Grob *me,
460 Drul_array<vector<Grob *> > clash_groups)
464 Drul_array<vector<Slice> > extents;
465 Drul_array<Slice> extent_union;
466 Drul_array<vector<Grob *> > stems;
467 for (UP_and_DOWN (d))
469 for (vsize i = 0; i < clash_groups[d].size (); i++)
471 Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
474 extents[d].push_back (s);
475 extent_union[d].unite (s);
476 stems[d].push_back (Note_column::get_stem (clash_groups[d][i]));
481 = (clash_groups[UP].size () && clash_groups[DOWN].size ())
482 ? check_meshing_chords (me, clash_groups[UP][0], clash_groups[DOWN][0])
486 * do horizontal shifts of each direction
493 Drul_array<vector<Real> > offsets;
494 for (UP_and_DOWN (d))
496 Real offset = inner_offset;
498 for (vsize i = 0; i < clash_groups[d].size (); i++)
500 Grob *col = clash_groups[d][i];
501 SCM sh = col->get_property ("horizontal-shift");
502 shifts.push_back (robust_scm2int (sh, 0));
505 offset = inner_offset;
508 bool explicit_shift = scm_is_number (sh);
510 col->warning (_ ("this Voice needs a \\voiceXx or \\shiftXx setting"));
512 if (explicit_shift && shifts[i] == shifts[i - 1])
513 ; // Match the previous notecolumn offset
514 else if (extents[d][i][UP] > extents[d][i - 1][DOWN]
515 && extents[d][i][DOWN] < extents[d][i - 1][UP])
516 offset += 1.0; // fully clear the previous-notecolumn heads
517 else if (d * extents[d][i][-d] >= d * extents[d][i - 1][d])
518 offset += Stem::is_valid_stem (stems[d][i - 1])
519 ? 1.0 : 0.5; // we cross the previous notecolumn
520 else if (Stem::is_valid_stem (stems[d][i]))
523 // check if we cross the opposite-stemmed voices
524 if (d * extents[d][i][-d] < d * extent_union[-d][d])
525 offset = max (offset, 0.5);
526 if (extents[-d].size ()
527 && extents[d][i][UP] > extents[-d][0][DOWN]
528 && extents[d][i][DOWN] < extents[-d][0][UP])
529 offset = max (offset, 1.0);
531 offsets[d].push_back (d * offset);
536 see input/regression/dot-up-voice-collision.ly
538 for (vsize i = 0; i < clash_groups[UP].size (); i++)
540 Grob *g = clash_groups[UP][i];
541 Grob *dc = Note_column::dot_column (g);
544 for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
545 Side_position_interface::add_support (dc, stems[UP][j]);
548 for (UP_and_DOWN (d))
550 for (vsize i = 0; i < clash_groups[d].size (); i++)
551 tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
552 scm_from_double (offsets[d][i])),
560 Note_collision_interface::forced_shift (Grob *me)
564 extract_grob_set (me, "elements", elements);
565 for (vsize i = 0; i < elements.size (); i++)
567 Grob *se = elements[i];
569 SCM force = se->get_property ("force-hshift");
570 if (scm_is_number (force))
571 tups = scm_cons (scm_cons (se->self_scm (), force),
578 Note_collision_interface::add_column (Grob *me, Grob *ncol)
580 ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
581 Axis_group_interface::add_element (me, ncol);
585 Note_collision_interface::note_head_positions (Grob *me)
588 extract_grob_set (me, "elements", elts);
589 for (vsize i = 0; i < elts.size (); i++)
590 if (Grob *stem = Grob::unsmob (elts[i]->get_object ("stem")))
592 vector<int> nhp = Stem::note_head_positions (stem);
593 out.insert (out.end (), nhp.begin (), nhp.end ());
596 vector_sort (out, less<int> ());
600 ADD_INTERFACE (Note_collision_interface,
601 "An object that handles collisions between notes with"
602 " different stem directions and horizontal shifts. Most of"
603 " the interesting properties are to be set in"
604 " @ref{note-column-interface}: these are @code{force-hshift}"
605 " and @code{horizontal-shift}.",
608 "merge-differently-dotted "
609 "merge-differently-headed "
611 "prefer-dotted-right "