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;
506 else if (shifts[i] == shifts[i - 1])
508 // Match the previous notecolumn offset,
509 // but warn if the user did not set these equal shifts explictly
510 if (!scm_is_number (sh))
511 col->warning (_ ("ignoring too many clashing note columns"));
513 else if (extents[d][i][UP] > extents[d][i - 1][DOWN]
514 && extents[d][i][DOWN] < extents[d][i - 1][UP])
515 offset += 1.0; // fully clear the inner-voice heads
518 // check if we cross the inner voice
519 if (d * extents[d][i][-d] >= d * extents[d][i - 1][d])
520 offset += Stem::is_valid_stem (stems[d][i - 1])
522 else if (Stem::is_valid_stem (stems[d][i]))
524 // check if we cross the opposite-stemmed voices
525 if (d * extents[d][i][-d] < d * extent_union[-d][d])
526 offset = max (offset, 0.5);
527 if (extents[-d].size ()
528 && extents[d][i][UP] > extents[-d][0][DOWN]
529 && extents[d][i][DOWN] < extents[-d][0][UP])
530 offset = max (offset, 1.0);
532 offsets[d].push_back (d * offset);
537 see input/regression/dot-up-voice-collision.ly
539 for (vsize i = 0; i < clash_groups[UP].size (); i++)
541 Grob *g = clash_groups[UP][i];
542 Grob *dc = Note_column::dot_column (g);
545 for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
546 Side_position_interface::add_support (dc, stems[UP][j]);
549 for (UP_and_DOWN (d))
551 for (vsize i = 0; i < clash_groups[d].size (); i++)
552 tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
553 scm_from_double (offsets[d][i])),
561 Note_collision_interface::forced_shift (Grob *me)
565 extract_grob_set (me, "elements", elements);
566 for (vsize i = 0; i < elements.size (); i++)
568 Grob *se = elements[i];
570 SCM force = se->get_property ("force-hshift");
571 if (scm_is_number (force))
572 tups = scm_cons (scm_cons (se->self_scm (), force),
579 Note_collision_interface::add_column (Grob *me, Grob *ncol)
581 ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
582 Axis_group_interface::add_element (me, ncol);
586 Note_collision_interface::note_head_positions (Grob *me)
589 extract_grob_set (me, "elements", elts);
590 for (vsize i = 0; i < elts.size (); i++)
591 if (Grob *stem = Grob::unsmob (elts[i]->get_object ("stem")))
593 vector<int> nhp = Stem::note_head_positions (stem);
594 out.insert (out.end (), nhp.begin (), nhp.end ());
597 vector_sort (out, less<int> ());
601 ADD_INTERFACE (Note_collision_interface,
602 "An object that handles collisions between notes with"
603 " different stem directions and horizontal shifts. Most of"
604 " the interesting properties are to be set in"
605 " @ref{note-column-interface}: these are @code{force-hshift}"
606 " and @code{horizontal-shift}.",
609 "merge-differently-dotted "
610 "merge-differently-headed "
612 "prefer-dotted-right "