2 collision.cc -- implement Collision
4 source file of the GNU LilyPond music typesetter
6 (c) 1997--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
9 #include "note-collision.hh"
11 #include "axis-group-interface.hh"
12 #include "dot-column.hh"
13 #include "international.hh"
14 #include "note-column.hh"
15 #include "note-head.hh"
16 #include "output-def.hh"
17 #include "pointer-group-interface.hh"
19 #include "rhythmic-head.hh"
20 #include "staff-symbol-referencer.hh"
21 #include "side-position-interface.hh"
27 check_meshing_chords (Grob
*me
,
28 Drul_array
<vector
<Real
> > *offsets
,
29 Drul_array
<vector
<Slice
> > const &extents
,
30 Drul_array
<vector
<Grob
*> > const &clash_groups
)
33 if (!extents
[UP
].size () || ! extents
[DOWN
].size ())
36 Grob
*clash_up
= clash_groups
[UP
][0];
37 Grob
*clash_down
= clash_groups
[DOWN
][0];
39 /* Every note column should have a stem, but avoid a crash. */
40 if (!Note_column::get_stem (clash_up
) || !Note_column::get_stem (clash_down
))
43 Drul_array
<Grob
*> stems (Note_column::get_stem (clash_down
),
44 Note_column::get_stem (clash_up
));
46 Grob
*head_up
= Note_column::first_head (clash_up
);
47 Grob
*head_down
= Note_column::first_head (clash_down
);
49 vector
<int> ups
= Stem::note_head_positions (Note_column::get_stem (clash_up
));
50 vector
<int> dps
= Stem::note_head_positions (Note_column::get_stem (clash_down
));
52 /* Too far apart to collide. */
53 if (ups
[0] > dps
.back () + 1)
56 /* Merge heads if the notes lie the same line, or if the "stem-up-note" is
57 above the "stem-down-note". */
58 bool merge_possible
= (ups
[0] >= dps
[0]) && (ups
.back () >= dps
.back ());
60 /* Do not merge notes typeset in different style. */
61 if (!ly_is_equal (head_up
->get_property ("style"),
62 head_down
->get_property ("style")))
63 merge_possible
= false;
65 int up_ball_type
= Rhythmic_head::duration_log (head_up
);
66 int down_ball_type
= Rhythmic_head::duration_log (head_down
);
68 /* Do not merge whole notes (or longer, like breve, longa, maxima). */
69 if (merge_possible
&& (up_ball_type
<= 0 || down_ball_type
<= 0))
70 merge_possible
= false;
73 && Rhythmic_head::dot_count (head_up
) != Rhythmic_head::dot_count (head_down
)
74 && !to_boolean (me
->get_property ("merge-differently-dotted")))
75 merge_possible
= false;
77 /* Can only merge different heads if merge-differently-headed is
80 && up_ball_type
!= down_ball_type
81 && !to_boolean (me
->get_property ("merge-differently-headed")))
82 merge_possible
= false;
84 /* Should never merge quarter and half notes, as this would make
85 them indistinguishable. */
87 && ((Stem::duration_log (stems
[UP
]) == 1
88 && Stem::duration_log (stems
[DOWN
]) == 2)
89 || (Stem::duration_log (stems
[UP
]) == 2
90 && Stem::duration_log (stems
[DOWN
]) == 1)))
91 merge_possible
= false;
94 this case (distant half collide),
101 the noteheads may be closer than this case (close half collide)
112 /* TODO: filter out the 'o's in this configuration, since they're no
113 part in the collision.
122 bool close_half_collide
= false;
123 bool distant_half_collide
= false;
124 bool full_collide
= false;
126 for (vsize i
= 0, j
= 0; i
< ups
.size () && j
< dps
.size (); )
128 if (abs (ups
[i
] - dps
[j
]) == 1)
130 merge_possible
= false;
132 close_half_collide
= true;
134 distant_half_collide
= true;
136 else if (ups
[i
] == dps
[j
])
138 else if (ups
[i
] > dps
[0] && ups
[i
] < dps
.back ())
139 merge_possible
= false;
140 else if (dps
[j
] > ups
[0] && dps
[j
] < ups
.back ())
141 merge_possible
= false;
145 else if (ups
[i
] > dps
[j
])
154 full_collide
= full_collide
|| (close_half_collide
155 && distant_half_collide
);
157 Drul_array
<Real
> center_note_shifts
;
158 center_note_shifts
[LEFT
] = 0.0;
159 center_note_shifts
[RIGHT
] = 0.0;
161 Real shift_amount
= 1;
163 bool touch
= (ups
[0] >= dps
.back ());
167 /* For full collisions, the right hand head may obscure dots, so
168 make sure the dotted heads go to the right. */
169 bool stem_to_stem
= false;
172 if (Rhythmic_head::dot_count (head_up
) > Rhythmic_head::dot_count (head_down
))
174 else if (Rhythmic_head::dot_count (head_up
) < Rhythmic_head::dot_count (head_down
))
178 /* The solfa is a triangle, which is inverted depending on stem
179 direction. In case of a collision, one of them should be removed,
180 so the resulting note does not look like a block.
183 && head_up
->get_property ("style") == ly_symbol2scm ("fa")
184 && head_down
->get_property ("style") == ly_symbol2scm ("fa"))
186 Interval uphead_size
= head_up
->extent (head_up
, Y_AXIS
);
187 Offset att
= Offset (0.0, -1.0);
188 head_up
->set_property ("stem-attachment", ly_offset2scm (att
));
189 head_up
->set_property ("transparent", SCM_BOOL_T
);
196 /* If possible, don't wipe any heads. Else, wipe shortest head,
197 or head with smallest amount of dots. Note: when merging
198 different heads, dots on the smaller one disappear. */
200 Grob
*dot_wipe_head
= head_up
;
202 if (up_ball_type
== down_ball_type
)
204 if (Rhythmic_head::dot_count (head_down
) < Rhythmic_head::dot_count (head_up
))
206 wipe_ball
= head_down
;
207 dot_wipe_head
= head_down
;
209 else if (Rhythmic_head::dot_count (head_down
) > Rhythmic_head::dot_count (head_up
))
211 dot_wipe_head
= head_up
;
215 dot_wipe_head
= head_up
;
217 else if (down_ball_type
> up_ball_type
)
219 wipe_ball
= head_down
;
220 dot_wipe_head
= head_down
;
222 else if (down_ball_type
< up_ball_type
)
225 dot_wipe_head
= head_up
;
230 if (Grob
*d
= unsmob_grob (dot_wipe_head
->get_object ("dot")))
234 if (wipe_ball
&& wipe_ball
->is_live ())
236 wipe_ball
->set_property ("transparent", SCM_BOOL_T
);
239 /* TODO: these numbers are magic; should devise a set of grob props
240 to tune this behavior. */
241 else if (stem_to_stem
)
242 shift_amount
= -abs (shift_amount
) * 0.65;
243 else if (close_half_collide
&& !touch
)
244 shift_amount
*= 0.52;
245 else if (distant_half_collide
&& !touch
)
247 else if (distant_half_collide
|| close_half_collide
|| full_collide
)
251 else if (Rhythmic_head::dot_count (head_up
) || Rhythmic_head::dot_count (head_down
))
254 shift_amount
*= 0.17;
260 && down_ball_type
* up_ball_type
== 0)
262 if (up_ball_type
== 0 && down_ball_type
== 1)
263 shift_amount
*= 1.25;
264 else if (up_ball_type
== 0 && down_ball_type
== 2)
265 shift_amount
*= 1.35;
266 else if (down_ball_type
== 0 && up_ball_type
== 1)
268 else if (down_ball_type
== 0 && up_ball_type
== 2)
269 shift_amount
*= 0.75;
275 * Dots from left note head collide with right note head. Only occurs
276 * with a close half collide, if the left note head is between
277 * lines and the right note head is on a line, and if right note head
278 * hasn't got any dots.
280 if (close_half_collide
281 && Rhythmic_head::dot_count (head_up
)
282 && !Rhythmic_head::dot_count (head_down
))
284 Grob
*staff
= Staff_symbol_referencer::get_staff_symbol (me
);
285 if (!Staff_symbol_referencer::on_line (staff
, ups
[0]))
287 TODO: consider junking the else body.
289 if (to_boolean (me
->get_property ("prefer-dotted-right")))
295 Grob
*d
= unsmob_grob (head_up
->get_object ("dot"));
296 Grob
*parent
= d
->get_parent (X_AXIS
);
297 if (Dot_column::has_interface (parent
))
298 Side_position_interface::add_support (parent
, head_down
);
302 /* For full or close half collisions, the right hand head may
303 obscure dots. Move dots to the right. */
304 if (abs (shift_amount
) > 1e-6
305 && Rhythmic_head::dot_count (head_down
) > Rhythmic_head::dot_count (head_up
)
306 && (full_collide
|| close_half_collide
))
308 Grob
*d
= unsmob_grob (head_down
->get_object ("dot"));
309 Grob
*parent
= d
->get_parent (X_AXIS
);
319 the . is put right of o which is erroneous o force-shifted
322 if (Dot_column::has_interface (parent
))
324 Grob
*stem
= unsmob_grob (head_up
->get_object ("stem"));
325 extract_grob_set (stem
, "note-heads", heads
);
326 for (vsize i
= 0; i
< heads
.size (); i
++)
327 Side_position_interface::add_support (parent
, heads
[i
]);
334 for (vsize i
= 0; i
< clash_groups
[d
].size (); i
++)
335 (*offsets
)[d
][i
] += d
* shift_amount
;
337 while ((flip (&d
)) != UP
);
341 MAKE_SCHEME_CALLBACK (Note_collision_interface
, calc_positioning_done
, 1)
343 Note_collision_interface::calc_positioning_done (SCM smob
)
345 Grob
*me
= unsmob_grob (smob
);
346 me
->set_property ("positioning-done", SCM_BOOL_T
);
348 Drul_array
<vector
<Grob
*> > clash_groups
= get_clash_groups (me
);
353 for (vsize i
= clash_groups
[d
].size (); i
--; )
358 clash_groups
[d
][i
]->extent (me
, X_AXIS
);
361 while (flip (&d
) != UP
);
363 SCM
autos (automatic_shift (me
, clash_groups
));
364 SCM
hand (forced_shift (me
));
369 if (clash_groups
[d
].size ())
371 Grob
*h
= clash_groups
[d
][0];
372 Grob
*fh
= Note_column::first_head (h
);
374 wid
= fh
->extent (h
, X_AXIS
).length ();
377 while (flip (&d
) != UP
);
380 Real left_most
= 1e6
;
382 vector
<Real
> amounts
;
383 for (; scm_is_pair (hand
); hand
= scm_cdr (hand
))
385 Grob
*s
= unsmob_grob (scm_caar (hand
));
386 Real amount
= scm_to_double (scm_cdar (hand
)) * wid
;
389 amounts
.push_back (amount
);
390 if (amount
< left_most
)
393 for (; scm_is_pair (autos
); autos
= scm_cdr (autos
))
395 Grob
*s
= unsmob_grob (scm_caar (autos
));
396 Real amount
= scm_to_double (scm_cdar (autos
)) * wid
;
398 vsize x
= find (done
, s
) - done
.begin ();
399 if (x
== VPOS
|| x
>= done
.size ())
402 amounts
.push_back (amount
);
403 if (amount
< left_most
)
408 for (vsize i
= 0; i
< amounts
.size (); i
++)
409 done
[i
]->translate_axis (amounts
[i
] - left_most
, X_AXIS
);
414 Drul_array
< vector
<Grob
*> >
415 Note_collision_interface::get_clash_groups (Grob
*me
)
417 Drul_array
<vector
<Grob
*> > clash_groups
;
419 extract_grob_set (me
, "elements", elements
);
420 for (vsize i
= 0; i
< elements
.size (); i
++)
422 Grob
*se
= elements
[i
];
423 if (Note_column::has_interface (se
))
425 if (!Note_column::dir (se
))
427 se
->programming_error ("note-column has no direction");
430 clash_groups
[Note_column::dir (se
)].push_back (se
);
437 vector
<Grob
*> &clashes (clash_groups
[d
]);
438 vector_sort (clashes
, Note_column::shift_less
);
440 while ((flip (&d
)) != UP
);
445 /** This complicated routine moves note columns around horizontally to
446 ensure that notes don't clash.
450 Note_collision_interface::automatic_shift (Grob
*me
,
451 Drul_array
<vector
<Grob
*> > clash_groups
)
453 Drul_array
< vector
<int> > shifts
;
459 vector
<int> &shift (shifts
[d
]);
460 vector
<Grob
*> &clashes (clash_groups
[d
]);
462 for (vsize i
= 0; i
< clashes
.size (); i
++)
465 = clashes
[i
]->get_property ("horizontal-shift");
467 if (scm_is_number (sh
))
468 shift
.push_back (scm_to_int (sh
));
473 for (vsize i
= 1; i
< shift
.size (); i
++)
475 if (shift
[i
- 1] == shift
[i
])
477 clashes
[0]->warning (_ ("ignoring too many clashing note columns"));
482 while ((flip (&d
)) != UP
);
484 Drul_array
<vector
<Slice
> > extents
;
485 Drul_array
<vector
<Real
> > offsets
;
489 for (vsize i
= 0; i
< clash_groups
[d
].size (); i
++)
491 Slice
s (Note_column::head_positions_interval (clash_groups
[d
][i
]));
494 extents
[d
].push_back (s
);
495 offsets
[d
].push_back (d
* 0.5 * i
);
498 while ((flip (&d
)) != UP
);
501 do horizontal shifts of each direction
511 for (vsize i
= 1; i
< clash_groups
[d
].size (); i
++)
513 Slice prev
= extents
[d
][i
- 1];
514 prev
.intersect (extents
[d
][i
]);
515 if (prev
.length () > 0
516 || (extents
[-d
].size () && d
* (extents
[d
][i
][-d
] - extents
[-d
][0][d
]) < 0))
517 for (vsize j
= i
; j
< clash_groups
[d
].size (); j
++)
518 offsets
[d
][j
] += d
* 0.5;
521 while ((flip (&d
)) != UP
);
525 see input/regression/dot-up-voice-collision.ly
527 for (vsize i
= 0; i
< clash_groups
[UP
].size (); i
++)
529 Grob
*g
= clash_groups
[UP
][i
];
530 Grob
*dc
= Note_column::dot_column (g
);
533 for (vsize j
= i
+ 1; j
< clash_groups
[UP
].size (); j
++)
535 Grob
*stem
= Note_column::get_stem (clash_groups
[UP
][j
]);
536 Side_position_interface::add_support (dc
, stem
);
541 Check if chords are meshing
544 check_meshing_chords (me
, &offsets
, extents
, clash_groups
);
548 for (vsize i
= 0; i
< clash_groups
[d
].size (); i
++)
549 tups
= scm_cons (scm_cons (clash_groups
[d
][i
]->self_scm (),
550 scm_from_double (offsets
[d
][i
])),
553 while (flip (&d
) != UP
);
559 Note_collision_interface::forced_shift (Grob
*me
)
563 extract_grob_set (me
, "elements", elements
);
564 for (vsize i
= 0; i
< elements
.size (); i
++)
566 Grob
*se
= elements
[i
];
568 SCM force
= se
->get_property ("force-hshift");
569 if (scm_is_number (force
))
571 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
);
585 ADD_INTERFACE (Note_collision_interface
,
586 "An object that handles collisions between notes with"
587 " different stem directions and horizontal shifts. Most of"
588 " the interesting properties are to be set in"
589 " @ref{note-column-interface}: these are @code{force-hshift}"
590 " and @code{horizontal-shift}.",
593 "merge-differently-dotted "
594 "merge-differently-headed "
596 "prefer-dotted-right "