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 = 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;
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 = unsmob<Grob> (head_up->get_object ("dot"));
311 Grob *parent = d->get_parent (X_AXIS);
312 if (has_interface<Dot_column> (parent))
313 Side_position_interface::add_support (parent, head_down);
315 else if (Rhythmic_head::dot_count (head_down))
317 Grob *d = unsmob<Grob> (head_down->get_object ("dot"));
318 Grob *parent = d->get_parent (X_AXIS);
319 if (has_interface<Dot_column> (parent))
321 Grob *stem = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = unsmob<Grob> (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 = 0.0;
397 vector<Real> amounts;
398 for (; scm_is_pair (hand); hand = scm_cdr (hand))
400 Grob *s = unsmob<Grob> (scm_caar (hand));
401 Real amount = scm_to_double (scm_cdar (hand)) * wid;
404 amounts.push_back (amount);
406 for (; scm_is_pair (autos); autos = scm_cdr (autos))
408 Grob *s = unsmob<Grob> (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 (has_interface<Note_column> (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 = unsmob<Grob> (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 "