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 int threshold = robust_scm2int (me->get_property ("note-collision-threshold"), 1);
60 /* Too far apart to collide. */
61 if (ups[0] > dps.back () + threshold)
64 /* If the chords just 'touch' their extreme noteheads,
65 then we can align their stems.
68 if (ups[0] >= dps.back ()
69 && (dps.size () < 2 || ups[0] >= dps[dps.size () - 2] + threshold + 1)
70 && (ups.size () < 2 || ups[1] >= dps.back () + threshold + 1))
73 /* Filter out the 'o's in this configuration, since they're no
74 * part in the collision.
82 ups = Stem::note_head_positions (stems[UP], true);
83 dps = Stem::note_head_positions (stems[DOWN], true);
85 /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
86 above the "stem-down-note". */
87 bool merge_possible = (ups[0] >= dps[0]) && (ups.back () >= dps.back ());
89 /* Do not merge notes typeset in different style. */
90 if (!ly_is_equal (head_up->get_property ("style"),
91 head_down->get_property ("style")))
92 merge_possible = false;
94 int up_ball_type = Rhythmic_head::duration_log (head_up);
95 int down_ball_type = Rhythmic_head::duration_log (head_down);
97 /* Do not merge whole notes (or longer, like breve, longa, maxima). */
98 if (merge_possible && (up_ball_type <= 0 || down_ball_type <= 0))
99 merge_possible = false;
102 && Rhythmic_head::dot_count (head_up) != Rhythmic_head::dot_count (head_down)
103 && !to_boolean (me->get_property ("merge-differently-dotted")))
104 merge_possible = false;
106 /* Can only merge different heads if merge-differently-headed is set. */
108 && up_ball_type != down_ball_type
109 && !to_boolean (me->get_property ("merge-differently-headed")))
110 merge_possible = false;
112 /* Should never merge quarter and half notes, as this would make
113 them indistinguishable. */
115 && ((Stem::duration_log (stems[UP]) == 1
116 && Stem::duration_log (stems[DOWN]) == 2)
117 || (Stem::duration_log (stems[UP]) == 2
118 && Stem::duration_log (stems[DOWN]) == 1)))
119 merge_possible = false;
122 * this case (distant half collide),
129 * the noteheads may be closer than this case (close half collide)
140 bool close_half_collide = false;
141 bool distant_half_collide = false;
142 bool full_collide = false;
144 for (vsize i = 0, j = 0; i < ups.size () && j < dps.size ();)
146 if (ups[i] == dps[j])
148 else if (abs (ups[i] - dps[j]) <= threshold)
150 merge_possible = false;
152 close_half_collide = true;
154 distant_half_collide = true;
156 else if (ups[i] > dps[0] && ups[i] < dps.back ())
157 merge_possible = false;
158 else if (dps[j] > ups[0] && dps[j] < ups.back ())
159 merge_possible = false;
163 else if (ups[i] > dps[j])
172 full_collide = full_collide || (close_half_collide
173 && distant_half_collide)
174 || ( distant_half_collide // like full_ for wholes and longer
175 && (up_ball_type <= 0 || down_ball_type <= 0));
177 /* Determine which chord goes on the left, and which goes right.
178 Up-stem usually goes on the right, but if chords just 'touch' we can put
179 both stems on a common vertical line. In the presense of collisions,
180 right hand heads may obscure dots, so dotted heads to go the right.
182 Real shift_amount = 1;
183 bool stem_to_stem = false;
185 || ((close_half_collide || distant_half_collide)
186 && to_boolean (me->get_property ("prefer-dotted-right"))))
187 && Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
191 // remember to leave clearance between stems
196 // Up-stem note on a line has a raised dot, so no risk of collision
197 Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
199 || (!Staff_symbol_referencer::on_line (staff, ups[0])
200 && to_boolean (me->get_property ("prefer-dotted-right"))))
201 && Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
207 /* The solfa is a triangle, which is inverted depending on stem
208 direction. In case of a collision, one of them should be removed,
209 so the resulting note does not look like a block.
211 SCM up_style = head_up->get_property ("style");
212 SCM down_style = head_down->get_property ("style");
214 && (scm_is_eq (up_style, ly_symbol2scm ("fa"))
215 || scm_is_eq (up_style, ly_symbol2scm ("faThin")))
216 && (scm_is_eq (down_style, ly_symbol2scm ("fa"))
217 || scm_is_eq (down_style, ly_symbol2scm ("faThin"))))
219 Offset att = Offset (0.0, -1.0);
220 head_up->set_property ("stem-attachment", ly_offset2scm (att));
221 head_up->set_property ("transparent", SCM_BOOL_T);
228 /* If possible, don't wipe any heads. Else, wipe shortest head,
229 or head with smallest amount of dots. Note: when merging
230 different heads, dots on the smaller one disappear; and when
231 merging identical heads, dots on the down-stem head disappear */
233 Grob *dot_wipe_head = head_up;
235 if (up_ball_type == down_ball_type)
237 if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
239 wipe_ball = head_down;
240 dot_wipe_head = head_down;
242 else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
244 dot_wipe_head = head_up;
248 dot_wipe_head = head_down;
250 else if (down_ball_type > up_ball_type)
252 wipe_ball = head_down;
253 dot_wipe_head = head_down;
255 else if (down_ball_type < up_ball_type)
258 dot_wipe_head = head_up;
260 If upper head is eighth note or shorter, and lower head is half note,
261 shift by the difference between the open and filled note head widths,
262 otherwise upper stem will be misaligned slightly.
264 if (Stem::duration_log (stems[DOWN]) == 1
265 && Stem::duration_log (stems[UP]) >= 3)
266 shift_amount = (1 - extent_up[RIGHT] / extent_down[RIGHT]) * 0.5;
271 if (Grob *d = unsmob<Grob> (dot_wipe_head->get_object ("dot")))
275 if (wipe_ball && wipe_ball->is_live ())
276 wipe_ball->set_property ("transparent", SCM_BOOL_T);
278 /* TODO: these numbers are magic; should devise a set of grob props
279 to tune this behavior. */
280 else if (stem_to_stem)
281 shift_amount *= 0.65;
284 else if (close_half_collide)
285 shift_amount *= 0.52;
286 else if (full_collide)
288 else if (distant_half_collide)
292 else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
295 shift_amount *= 0.17;
297 /* The offsets computed in this routine are multiplied,
298 in calc_positioning_done(), by the width of the downstem note.
299 The shift required to clear collisions, however, depends on the extents
300 of the note heads on the sides that interfere. */
301 if (shift_amount < 0.0) // Down-stem shifts right.
302 shift_amount *= (extent_up[RIGHT] - extent_down[LEFT]) / extent_down.length ();
303 else // Up-stem shifts right.
304 shift_amount *= (extent_down[RIGHT] - extent_up[LEFT]) / extent_down.length ();
306 /* If any dotted notes ended up on the left,
307 tell the Dot_Columnn to avoid the note heads on the right.
309 if (shift_amount < -1e-6
310 && Rhythmic_head::dot_count (head_up))
312 Grob *d = unsmob<Grob> (head_up->get_object ("dot"));
313 Grob *parent = d->get_parent (X_AXIS);
314 if (has_interface<Dot_column> (parent))
315 Side_position_interface::add_support (parent, head_down);
317 else if (Rhythmic_head::dot_count (head_down))
319 Grob *d = unsmob<Grob> (head_down->get_object ("dot"));
320 Grob *parent = d->get_parent (X_AXIS);
321 if (has_interface<Dot_column> (parent))
323 Grob *stem = unsmob<Grob> (head_up->get_object ("stem"));
324 // Loop over all heads on an up-pointing-stem to see if dots
325 // need to clear any heads suspended on its right side.
326 extract_grob_set (stem, "note-heads", heads);
327 for (vsize i = 0; i < heads.size (); i++)
328 Side_position_interface::add_support (parent, heads[i]);
332 // In meshed chords with dots on the left, adjust dot direction
333 if (shift_amount > 1e-6
334 && Rhythmic_head::dot_count (head_down))
336 Grob *dot_down = unsmob<Grob> (head_down->get_object ("dot"));
337 Grob *col_down = dot_down->get_parent (X_AXIS);
339 if (Rhythmic_head::dot_count (head_up))
341 Grob *dot_up = unsmob<Grob> (head_up->get_object ("dot"));
342 Grob *col_up = dot_up->get_parent (X_AXIS);
343 if (col_up == col_down) // let the common DotColumn arrange dots
345 else // conform to the dot direction on the up-stem chord
346 dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
350 Grob *stem = unsmob<Grob> (head_down->get_object ("stem"));
351 extract_grob_set (stem, "note-heads", heads);
352 for (vsize i = 0; i < heads.size (); i++)
353 if (Grob *dot = unsmob<Grob> (heads[i]->get_object ("dot")))
354 dot->set_property ("direction", scm_from_int (dir));
361 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
363 Note_collision_interface::calc_positioning_done (SCM smob)
365 Grob *me = unsmob<Grob> (smob);
366 me->set_property ("positioning-done", SCM_BOOL_T);
368 Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
370 for (UP_and_DOWN (d))
372 for (vsize i = clash_groups[d].size (); i--;)
377 clash_groups[d][i]->extent (me, X_AXIS);
381 SCM autos (automatic_shift (me, clash_groups));
382 SCM hand (forced_shift (me));
385 for (UP_and_DOWN (d))
387 if (clash_groups[d].size ())
389 Grob *h = clash_groups[d][0];
390 Grob *fh = Note_column::first_head (h);
392 wid = fh->extent (h, X_AXIS).length ();
397 Real left_most = 0.0;
399 vector<Real> amounts;
400 for (; scm_is_pair (hand); hand = scm_cdr (hand))
402 Grob *s = unsmob<Grob> (scm_caar (hand));
403 Real amount = scm_to_double (scm_cdar (hand)) * wid;
406 amounts.push_back (amount);
408 for (; scm_is_pair (autos); autos = scm_cdr (autos))
410 Grob *s = unsmob<Grob> (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 (has_interface<Note_column> (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 = unsmob<Grob> (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 "
612 "note-collision-threshold "
614 "prefer-dotted-right "