2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2014 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 Drul_array<vector<Real> > *offsets,
39 Drul_array<vector<Slice> > const &extents,
40 Drul_array<vector<Grob *> > const &clash_groups)
43 if (!extents[UP].size () || !extents[DOWN].size ())
46 Grob *clash_up = clash_groups[UP][0];
47 Grob *clash_down = clash_groups[DOWN][0];
49 /* Every note column should have a stem, but avoid a crash. */
50 if (!Note_column::get_stem (clash_up) || !Note_column::get_stem (clash_down))
53 Drul_array<Grob *> stems (Note_column::get_stem (clash_down),
54 Note_column::get_stem (clash_up));
56 Grob *head_up = Note_column::first_head (clash_up);
57 Grob *head_down = Note_column::first_head (clash_down);
59 Interval extent_up = head_up->extent (head_up, X_AXIS);
60 Interval extent_down = head_down->extent (head_down, X_AXIS);
62 /* Staff-positions of all noteheads on each stem */
63 vector<int> ups = Stem::note_head_positions (stems[UP]);
64 vector<int> dps = Stem::note_head_positions (stems[DOWN]);
66 /* Too far apart to collide. */
67 if (ups[0] > dps.back () + 1)
70 /* If the chords just 'touch' their extreme noteheads,
71 then we can align their stems.
74 if (ups[0] >= dps.back ()
75 && (dps.size () < 2 || ups[0] >= dps[dps.size () - 2] + 2)
76 && (ups.size () < 2 || ups[1] >= dps.back () + 2))
79 /* Filter out the 'o's in this configuration, since they're no
80 * part in the collision.
88 ups = Stem::note_head_positions (stems[UP], true);
89 dps = Stem::note_head_positions (stems[DOWN], true);
91 /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
92 above the "stem-down-note". */
93 bool merge_possible = (ups[0] >= dps[0]) && (ups.back () >= dps.back ());
95 /* Do not merge notes typeset in different style. */
96 if (!ly_is_equal (head_up->get_property ("style"),
97 head_down->get_property ("style")))
98 merge_possible = false;
100 int up_ball_type = Rhythmic_head::duration_log (head_up);
101 int down_ball_type = Rhythmic_head::duration_log (head_down);
103 /* Do not merge whole notes (or longer, like breve, longa, maxima). */
104 if (merge_possible && (up_ball_type <= 0 || down_ball_type <= 0))
105 merge_possible = false;
108 && Rhythmic_head::dot_count (head_up) != Rhythmic_head::dot_count (head_down)
109 && !to_boolean (me->get_property ("merge-differently-dotted")))
110 merge_possible = false;
112 /* Can only merge different heads if merge-differently-headed is set. */
114 && up_ball_type != down_ball_type
115 && !to_boolean (me->get_property ("merge-differently-headed")))
116 merge_possible = false;
118 /* Should never merge quarter and half notes, as this would make
119 them indistinguishable. */
121 && ((Stem::duration_log (stems[UP]) == 1
122 && Stem::duration_log (stems[DOWN]) == 2)
123 || (Stem::duration_log (stems[UP]) == 2
124 && Stem::duration_log (stems[DOWN]) == 1)))
125 merge_possible = false;
128 * this case (distant half collide),
135 * the noteheads may be closer than this case (close half collide)
146 bool close_half_collide = false;
147 bool distant_half_collide = false;
148 bool full_collide = false;
150 for (vsize i = 0, j = 0; i < ups.size () && j < dps.size ();)
152 if (abs (ups[i] - dps[j]) == 1)
154 merge_possible = false;
156 close_half_collide = true;
158 distant_half_collide = true;
160 else if (ups[i] == dps[j])
162 else if (ups[i] > dps[0] && ups[i] < dps.back ())
163 merge_possible = false;
164 else if (dps[j] > ups[0] && dps[j] < ups.back ())
165 merge_possible = false;
169 else if (ups[i] > dps[j])
178 full_collide = full_collide || (close_half_collide
179 && distant_half_collide)
180 || ( distant_half_collide // like full_ for wholes and longer
181 && (up_ball_type <= 0 || down_ball_type <= 0));
183 /* Determine which chord goes on the left, and which goes right.
184 Up-stem usually goes on the right, but if chords just 'touch' we can put
185 both stems on a common vertical line. In the presense of collisions,
186 right hand heads may obscure dots, so dotted heads to go the right.
188 Real shift_amount = 1;
189 bool stem_to_stem = false;
191 || ((close_half_collide || distant_half_collide)
192 && to_boolean (me->get_property ("prefer-dotted-right"))))
193 && Rhythmic_head::dot_count (head_up) < Rhythmic_head::dot_count (head_down))
197 // remember to leave clearance between stems
202 // Up-stem note on a line has a raised dot, so no risk of collision
203 Grob *staff = Staff_symbol_referencer::get_staff_symbol (me);
205 || (!Staff_symbol_referencer::on_line (staff, ups[0])
206 && to_boolean (me->get_property ("prefer-dotted-right"))))
207 && Rhythmic_head::dot_count (head_up) > Rhythmic_head::dot_count (head_down))
213 /* The solfa is a triangle, which is inverted depending on stem
214 direction. In case of a collision, one of them should be removed,
215 so the resulting note does not look like a block.
217 SCM up_style = head_up->get_property ("style");
218 SCM down_style = head_down->get_property ("style");
220 && (up_style == ly_symbol2scm ("fa") || up_style == ly_symbol2scm ("faThin"))
221 && (down_style == ly_symbol2scm ("fa") || down_style == ly_symbol2scm ("faThin")))
223 Offset att = Offset (0.0, -1.0);
224 head_up->set_property ("stem-attachment", ly_offset2scm (att));
225 head_up->set_property ("transparent", SCM_BOOL_T);
232 /* If possible, don't wipe any heads. Else, wipe shortest head,
233 or head with smallest amount of dots. Note: when merging
234 different heads, dots on the smaller one disappear; and when
235 merging identical heads, dots on the down-stem head disappear */
237 Grob *dot_wipe_head = head_up;
239 if (up_ball_type == down_ball_type)
241 if (Rhythmic_head::dot_count (head_down) < Rhythmic_head::dot_count (head_up))
243 wipe_ball = head_down;
244 dot_wipe_head = head_down;
246 else if (Rhythmic_head::dot_count (head_down) > Rhythmic_head::dot_count (head_up))
248 dot_wipe_head = head_up;
252 dot_wipe_head = head_down;
254 else if (down_ball_type > up_ball_type)
256 wipe_ball = head_down;
257 dot_wipe_head = head_down;
259 else if (down_ball_type < up_ball_type)
262 dot_wipe_head = head_up;
264 If upper head is eighth note or shorter, and lower head is half note,
265 shift by the difference between the open and filled note head widths,
266 otherwise upper stem will be misaligned slightly.
268 if (Stem::duration_log (stems[DOWN]) == 1
269 && Stem::duration_log (stems[UP]) >= 3)
270 shift_amount = (1 - extent_up[RIGHT] / extent_down[RIGHT]) * 0.5;
275 if (Grob *d = Grob::unsmob (dot_wipe_head->get_object ("dot")))
279 if (wipe_ball && wipe_ball->is_live ())
280 wipe_ball->set_property ("transparent", SCM_BOOL_T);
282 /* TODO: these numbers are magic; should devise a set of grob props
283 to tune this behavior. */
284 else if (stem_to_stem)
285 shift_amount *= 0.65;
288 else if (close_half_collide)
289 shift_amount *= 0.52;
290 else if (full_collide)
292 else if (distant_half_collide)
296 else if (Rhythmic_head::dot_count (head_up) || Rhythmic_head::dot_count (head_down))
299 shift_amount *= 0.17;
301 /* The offsets computed in this routine are multiplied,
302 in calc_positioning_done(), by the width of the downstem note.
303 The shift required to clear collisions, however, depends on the extents
304 of the note heads on the sides that interfere. */
305 if (shift_amount < 0.0) // Down-stem shifts right.
306 shift_amount *= (extent_up[RIGHT] - extent_down[LEFT]) / extent_down.length ();
307 else // Up-stem shifts right.
308 shift_amount *= (extent_down[RIGHT] - extent_up[LEFT]) / extent_down.length ();
310 /* If any dotted notes ended up on the left,
311 tell the Dot_Columnn to avoid the note heads on the right.
313 if (shift_amount < -1e-6
314 && Rhythmic_head::dot_count (head_up))
316 Grob *d = Grob::unsmob (head_up->get_object ("dot"));
317 Grob *parent = d->get_parent (X_AXIS);
318 if (Dot_column::has_interface (parent))
319 Side_position_interface::add_support (parent, head_down);
321 else if (Rhythmic_head::dot_count (head_down))
323 Grob *d = Grob::unsmob (head_down->get_object ("dot"));
324 Grob *parent = d->get_parent (X_AXIS);
325 if (Dot_column::has_interface (parent))
327 Grob *stem = Grob::unsmob (head_up->get_object ("stem"));
328 // Loop over all heads on an up-pointing-stem to see if dots
329 // need to clear any heads suspended on its right side.
330 extract_grob_set (stem, "note-heads", heads);
331 for (vsize i = 0; i < heads.size (); i++)
332 Side_position_interface::add_support (parent, heads[i]);
336 // In meshed chords with dots on the left, adjust dot direction
337 if (shift_amount > 1e-6
338 && Rhythmic_head::dot_count (head_down))
340 Grob *dot_down = Grob::unsmob (head_down->get_object ("dot"));
341 Grob *col_down = dot_down->get_parent (X_AXIS);
343 if (Rhythmic_head::dot_count (head_up))
345 Grob *dot_up = Grob::unsmob (head_up->get_object ("dot"));
346 Grob *col_up = dot_up->get_parent (X_AXIS);
347 if (col_up == col_down) // let the common DotColumn arrange dots
349 else // conform to the dot direction on the up-stem chord
350 dir = robust_scm2dir (dot_up->get_property ("direction"), UP);
354 Grob *stem = Grob::unsmob (head_down->get_object ("stem"));
355 extract_grob_set (stem, "note-heads", heads);
356 for (vsize i = 0; i < heads.size (); i++)
357 if (Grob *dot = Grob::unsmob (heads[i]->get_object ("dot")))
358 dot->set_property ("direction", scm_from_int (dir));
362 for (UP_and_DOWN (d))
364 for (vsize i = 0; i < clash_groups[d].size (); i++)
365 (*offsets)[d][i] += d * shift_amount;
369 MAKE_SCHEME_CALLBACK (Note_collision_interface, calc_positioning_done, 1)
371 Note_collision_interface::calc_positioning_done (SCM smob)
373 Grob *me = Grob::unsmob (smob);
374 me->set_property ("positioning-done", SCM_BOOL_T);
376 Drul_array<vector<Grob *> > clash_groups = get_clash_groups (me);
378 for (UP_and_DOWN (d))
380 for (vsize i = clash_groups[d].size (); i--;)
385 clash_groups[d][i]->extent (me, X_AXIS);
389 SCM autos (automatic_shift (me, clash_groups));
390 SCM hand (forced_shift (me));
393 for (UP_and_DOWN (d))
395 if (clash_groups[d].size ())
397 Grob *h = clash_groups[d][0];
398 Grob *fh = Note_column::first_head (h);
400 wid = fh->extent (h, X_AXIS).length ();
405 Real left_most = 1e6;
407 vector<Real> amounts;
408 for (; scm_is_pair (hand); hand = scm_cdr (hand))
410 Grob *s = Grob::unsmob (scm_caar (hand));
411 Real amount = scm_to_double (scm_cdar (hand)) * wid;
414 amounts.push_back (amount);
415 if (amount < left_most)
418 for (; scm_is_pair (autos); autos = scm_cdr (autos))
420 Grob *s = Grob::unsmob (scm_caar (autos));
421 Real amount = scm_to_double (scm_cdar (autos)) * wid;
423 vsize x = find (done, s) - done.begin ();
424 if (x == VPOS || x >= done.size ())
427 amounts.push_back (amount);
428 if (amount < left_most)
433 for (vsize i = 0; i < amounts.size (); i++)
434 done[i]->translate_axis (amounts[i] - left_most, X_AXIS);
439 Drul_array < vector<Grob *> >
440 Note_collision_interface::get_clash_groups (Grob *me)
442 Drul_array<vector<Grob *> > clash_groups;
444 extract_grob_set (me, "elements", elements);
445 for (vsize i = 0; i < elements.size (); i++)
447 Grob *se = elements[i];
448 if (Note_column::has_interface (se))
450 if (!Note_column::dir (se))
451 se->programming_error ("note-column has no direction");
453 clash_groups[Note_column::dir (se)].push_back (se);
457 for (UP_and_DOWN (d))
459 vector<Grob *> &clashes (clash_groups[d]);
460 vector_sort (clashes, Note_column::shift_less);
467 This complicated routine moves note columns around horizontally to
468 ensure that notes don't clash.
471 Note_collision_interface::automatic_shift (Grob *me,
472 Drul_array<vector<Grob *> > clash_groups)
474 Drul_array < vector<int> > shifts;
477 for (UP_and_DOWN (d))
479 vector<int> &shift (shifts[d]);
480 vector<Grob *> &clashes (clash_groups[d]);
482 for (vsize i = 0; i < clashes.size (); i++)
485 = clashes[i]->get_property ("horizontal-shift");
487 if (scm_is_number (sh))
488 shift.push_back (scm_to_int (sh));
493 for (vsize i = 1; i < shift.size (); i++)
495 if (shift[i - 1] == shift[i])
497 clashes[0]->warning (_ ("ignoring too many clashing note columns"));
503 Drul_array<vector<Slice> > extents;
504 Drul_array<vector<Real> > offsets;
505 for (UP_and_DOWN (d))
507 for (vsize i = 0; i < clash_groups[d].size (); i++)
509 Slice s (Note_column::head_positions_interval (clash_groups[d][i]));
512 extents[d].push_back (s);
513 offsets[d].push_back (d * 0.5 * i);
518 * do horizontal shifts of each direction
526 for (UP_and_DOWN (d))
528 for (vsize i = 1; i < clash_groups[d].size (); i++)
530 Slice prev = extents[d][i - 1];
531 prev.intersect (extents[d][i]);
532 if (prev.length () > 0
533 || (extents[-d].size () && d * (extents[d][i][-d] - extents[-d][0][d]) < 0))
534 for (vsize j = i; j < clash_groups[d].size (); j++)
535 offsets[d][j] += d * 0.5;
540 see input/regression/dot-up-voice-collision.ly
542 for (vsize i = 0; i < clash_groups[UP].size (); i++)
544 Grob *g = clash_groups[UP][i];
545 Grob *dc = Note_column::dot_column (g);
548 for (vsize j = i + 1; j < clash_groups[UP].size (); j++)
550 Grob *stem = Note_column::get_stem (clash_groups[UP][j]);
551 Side_position_interface::add_support (dc, stem);
556 Check if chords are meshing
559 check_meshing_chords (me, &offsets, extents, clash_groups);
561 for (UP_and_DOWN (d))
563 for (vsize i = 0; i < clash_groups[d].size (); i++)
564 tups = scm_cons (scm_cons (clash_groups[d][i]->self_scm (),
565 scm_from_double (offsets[d][i])),
573 Note_collision_interface::forced_shift (Grob *me)
577 extract_grob_set (me, "elements", elements);
578 for (vsize i = 0; i < elements.size (); i++)
580 Grob *se = elements[i];
582 SCM force = se->get_property ("force-hshift");
583 if (scm_is_number (force))
584 tups = scm_cons (scm_cons (se->self_scm (), force),
591 Note_collision_interface::add_column (Grob *me, Grob *ncol)
593 ncol->set_property ("X-offset", Grob::x_parent_positioning_proc);
594 Axis_group_interface::add_element (me, ncol);
598 Note_collision_interface::note_head_positions (Grob *me)
601 extract_grob_set (me, "elements", elts);
602 for (vsize i = 0; i < elts.size (); i++)
603 if (Grob *stem = Grob::unsmob (elts[i]->get_object ("stem")))
605 vector<int> nhp = Stem::note_head_positions (stem);
606 out.insert (out.end (), nhp.begin (), nhp.end ());
609 vector_sort (out, less<int> ());
613 ADD_INTERFACE (Note_collision_interface,
614 "An object that handles collisions between notes with"
615 " different stem directions and horizontal shifts. Most of"
616 " the interesting properties are to be set in"
617 " @ref{note-column-interface}: these are @code{force-hshift}"
618 " and @code{horizontal-shift}.",
621 "merge-differently-dotted "
622 "merge-differently-headed "
624 "prefer-dotted-right "