From cccce5cadfae74d26c56ab3f22cb1c7c81093249 Mon Sep 17 00:00:00 2001 From: Han-Wen Nienhuys Date: Mon, 28 Feb 2011 22:34:15 -0300 Subject: [PATCH] Take collisions into account in Beam::shift_region_to_valid(). --- .../beam-collision-feasible-region.ly | 42 ++++ .../beam-collision-opposite-stem.ly | 29 +++ lily/beam-quanting.cc | 8 +- lily/beam.cc | 199 +++++++++++++++--- 4 files changed, 246 insertions(+), 32 deletions(-) create mode 100644 input/regression/beam-collision-feasible-region.ly create mode 100644 input/regression/beam-collision-opposite-stem.ly diff --git a/input/regression/beam-collision-feasible-region.ly b/input/regression/beam-collision-feasible-region.ly new file mode 100644 index 0000000000..dbc1c2eca1 --- /dev/null +++ b/input/regression/beam-collision-feasible-region.ly @@ -0,0 +1,42 @@ +\version "2.13.52" + +\header { + texidoc = "A rough guess for collisions is taken into account when + choosing initial beam configurations; the initial position may be + chosen to be either above or below large collisions." +} + +\layout { + ragged-right = ##t +} + +partOne = << + { s4 s8 \key f \major s8 } + { + g8[ c'''8] + g8[ c'''8] + } +>> + +partTwo = << + { \clef bass \key c \major s4 s8 \key f \major s8 } + { + c,8[ e'8] + c,8[ e'8] + } +>> + +partThree = << + { \clef bass \key c \major s4 s8 \key f \major s8 } + { + b,,8[ e'8] + b,,8[ e'8] + } +>> + +\new Voice { + \partOne + \partTwo + \partThree +} + diff --git a/input/regression/beam-collision-opposite-stem.ly b/input/regression/beam-collision-opposite-stem.ly new file mode 100644 index 0000000000..89fe7af161 --- /dev/null +++ b/input/regression/beam-collision-opposite-stem.ly @@ -0,0 +1,29 @@ +\header { + texidoc = "Meshing stems in oppositely directed beams are handled + correctly." +} + +\version "2.13.46" + +\layout { + ragged-right = ##t +} + +{ + \relative c'' { << { s16 e16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 e16 [ s cis, ] } \\ { b''16 [ s b ] } >> } + \relative c'' { << { s16 d16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 c16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 b16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 a16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 g16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 c,16 [ s cis' ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 c,16 [ s cis'' ] } \\ { b16 [ s b ] } >> } + \relative c'' { << { s16 f,16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 e,16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 d,16 [ s cis ] } \\ { b'16 [ s b ] } >> } + \relative c'' { << { s16 e16 [ s cis ] } \\ { b'16 [ s d ] } >> } + \relative c'' { << { s16 e16 [ s cis ] } \\ { b'16 [ s f' ] } >> } + \relative c'' { << { s16 e16 [ s cis ] } \\ { b'16 [ s a ] } >> } + \relative c'' { << { s16 e16 [ s cis ] } \\ { b'16 [ s gis ] } >> } +} diff --git a/lily/beam-quanting.cc b/lily/beam-quanting.cc index 6b495b3794..cc2c707dff 100644 --- a/lily/beam-quanting.cc +++ b/lily/beam-quanting.cc @@ -20,9 +20,9 @@ #include "beam-scoring-problem.hh" +#include #include #include -#include using namespace std; #include "align-interface.hh" @@ -194,13 +194,11 @@ void Beam_scoring_problem::init_collisions (vector grobs) set stems; for (vsize i = 0; i < grobs.size (); i++) { Box b; - for (Axis a = X_AXIS; a < NO_AXES; incr (a)) b[a] = grobs[i]->extent(common[a], a); - Real width = b[X_AXIS].length(); - - Real width_factor = sqrt(width / staff_space); + Real width = b[X_AXIS].length (); + Real width_factor = sqrt (width / staff_space); Direction d = LEFT; do diff --git a/lily/beam.cc b/lily/beam.cc index 58ac5d44d2..53fda81743 100644 --- a/lily/beam.cc +++ b/lily/beam.cc @@ -48,8 +48,10 @@ #include "lookup.hh" #include "main.hh" #include "misc.hh" +#include "note-head.hh" #include "output-def.hh" #include "pointer-group-interface.hh" +#include "rhythmic-head.hh" #include "spanner.hh" #include "staff-symbol-referencer.hh" #include "stem.hh" @@ -1035,6 +1037,19 @@ Beam::calc_least_squares_positions (SCM smob, SCM /* posns */) return ly_interval2scm (pos); } + +// Assuming V is not empty, pick a 'reasonable' point inside V. +static Real +point_in_interval (Interval v, Real dist) +{ + if (isinf (v[DOWN])) + return v[UP] - dist; + else if (isinf (v[UP])) + return v[DOWN] + dist; + else + return v.center (); +} + /* We can't combine with previous function, since check concave and slope damping comes first. @@ -1047,41 +1062,43 @@ SCM Beam::shift_region_to_valid (SCM grob, SCM posns) { Grob *me = unsmob_grob (grob); + /* Code dup. */ vector x_posns; extract_grob_set (me, "stems", stems); - Grob *commonx = common_refpoint_of_array (stems, me, X_AXIS); - Grob *commony = common_refpoint_of_array (stems, me, Y_AXIS); + extract_grob_set (me, "covered-grobs", covered); + Grob *common[NO_AXES] = { me, me }; + for (Axis a = X_AXIS; a < NO_AXES; incr (a)) { + common[a] = common_refpoint_of_array (stems, me, a); + common[a] = common_refpoint_of_array (covered, common[a], a); + } Grob *fvs = first_normal_stem (me); if (!fvs) return posns; - - Real x0 = fvs->relative_coordinate (commonx, X_AXIS); + Interval x_span; + x_span[LEFT] = fvs->relative_coordinate (common[X_AXIS], X_AXIS); for (vsize i = 0; i < stems.size (); i++) { Grob *s = stems[i]; - Real x = s->relative_coordinate (commonx, X_AXIS) - x0; + Real x = s->relative_coordinate (common[X_AXIS], X_AXIS) - x_span[LEFT]; x_posns.push_back (x); } - + Grob *lvs = last_normal_stem (me); - if (!lvs) - return posns; - - Real dx = lvs->relative_coordinate (commonx, X_AXIS) - x0; + x_span[RIGHT] = lvs->relative_coordinate (common[X_AXIS], X_AXIS); Drul_array pos = ly_scm2interval (posns); scale_drul (&pos, Staff_symbol_referencer::staff_space (me)); - Real dy = pos[RIGHT] - pos[LEFT]; - Real y = pos[LEFT]; - Real slope = dx ? (dy / dx) : 0.0; + Real beam_dy = pos[RIGHT] - pos[LEFT]; + Real beam_left_y = pos[LEFT]; + Real slope = x_span.delta () ? (beam_dy / x_span.delta ()) : 0.0; /* Shift the positions so that we have a chance of finding good @@ -1089,6 +1106,7 @@ Beam::shift_region_to_valid (SCM grob, SCM posns) */ Interval feasible_left_point; feasible_left_point.set_full (); + for (vsize i = 0; i < stems.size (); i++) { Grob *s = stems[i]; @@ -1096,7 +1114,6 @@ Beam::shift_region_to_valid (SCM grob, SCM posns) continue; Direction d = get_grob_direction (s); - Real left_y = Stem::get_stem_info (s).shortest_y_ - slope * x_posns [i]; @@ -1106,8 +1123,8 @@ Beam::shift_region_to_valid (SCM grob, SCM posns) ourselves, so translate: */ left_y - += + s->relative_coordinate (commony, Y_AXIS) - - me->relative_coordinate (commony, Y_AXIS); + += + s->relative_coordinate (common[Y_AXIS], Y_AXIS) + - me->relative_coordinate (common[Y_AXIS], Y_AXIS); Interval flp; flp.set_full (); @@ -1116,20 +1133,148 @@ Beam::shift_region_to_valid (SCM grob, SCM posns) feasible_left_point.intersect (flp); } - if (feasible_left_point.is_empty ()) - warning (_ ("no viable initial configuration found: may not find good beam slope")); - else if (!feasible_left_point.contains (y)) + /* + We have two intervals here, one for the up variant (beams goes + over the collision) one for the down. + */ + Drul_array collision_free (feasible_left_point, + feasible_left_point); + + vector filtered; + /* + We only update these for objects that are too large for quanting + to find a workaround. Typically, these are notes with + stems, and timesig/keysig/clef, which take out the entire area + inside the staff as feasible. + + The code below disregards the thickness and multiplicity of the + beam. This should not be a problem, as the beam quanting will + take care of computing the impact those exactly. + */ + Real min_y_size = 2.0; + for (vsize i = 0; i < covered.size(); i++) + { + if (!covered[i]->is_live()) + continue; + + Box b; + for (Axis a = X_AXIS; a < NO_AXES; incr (a)) + b[a] = covered[i]->extent (common[a], a); + + if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ()) + continue; + + if (intersection (b[X_AXIS], x_span).is_empty ()) + continue; + + filtered.push_back (covered[i]); + Grob *head_stem = Rhythmic_head::get_stem (covered[i]); + if (head_stem && Stem::is_normal_stem (head_stem) + && Note_head::has_interface (covered[i])) + { + if (Stem::get_beam (head_stem)) + { + /* + We must assume that stems are infinitely long in this + case, as asking for the length of the stem typically + leads to circular dependencies. + + This strategy assumes that we don't want to handle the + collision of beams in opposite non-forced directions + with this code, where shortening the stems of both + would resolve the problem, eg. + + x x + | | + ===== + + ===== + | | + x x + + Such beams would need a coordinating grob to resolve + the collision, since both will likely want to occupy + the centerline. + */ + Direction stemdir = get_grob_direction (head_stem); + b[Y_AXIS][stemdir] = stemdir * infinity_f; + } + else + { + // TODO - should we include the extent of the stem here? + } + } + + if (b[Y_AXIS].length () < min_y_size) + continue; + + Direction d = LEFT; + do + { + Real x = b[X_AXIS][d] - x_span[LEFT]; + Real dy = slope * x; + + Direction yd = DOWN; + do + { + Real left_y = b[Y_AXIS][yd]; + + if (left_y == yd * infinity_f) + { + collision_free[yd].set_empty (); + continue; + } + + left_y -= dy; + + // Translate back to beam as ref point. + left_y -= -me->relative_coordinate (common[Y_AXIS], Y_AXIS); + + Interval allowed; + allowed.set_full (); + + allowed[-yd] = left_y; + collision_free[yd].intersect (allowed); + } + while (flip (&yd) != DOWN); + } + while (flip (&d) != LEFT); + } + + Grob_array *arr = + Pointer_group_interface::get_grob_array (me, + ly_symbol2scm ("covered-grobs")); + arr->set_array (filtered); + + if (collision_free[DOWN].contains (beam_left_y) + || collision_free[UP].contains (beam_left_y)) { - const int REGION_SIZE = 2; // UGH UGH - if (isinf (feasible_left_point[DOWN])) - y = feasible_left_point[UP] - REGION_SIZE; - else if (isinf (feasible_left_point[UP])) - y = feasible_left_point[DOWN]+ REGION_SIZE; - else - y = feasible_left_point.center (); + // We're good to go. Do nothing. } + else if (!collision_free[DOWN].is_empty () + || !collision_free[UP].is_empty ()) + { + // We have space above or below collisions (or, no collisions at + // all). + Interval best = + (collision_free[DOWN].length () > collision_free[UP].length ()) ? + collision_free[DOWN] : collision_free[UP]; - pos = Drul_array (y, (y + dy)); + beam_left_y = point_in_interval (best, 2.0); + } + else if (!feasible_left_point.is_empty ()) + { + // We are somewhat screwed: we have a collision, but at least + // there is a way to satisfy stem length constraints. + beam_left_y = point_in_interval (feasible_left_point, 2.0); + } + else + { + // We are completely screwed. + warning (_ ("no viable initial configuration found: may not find good beam slope")); + } + + pos = Drul_array (beam_left_y, (beam_left_y + beam_dy)); scale_drul (&pos, 1 / Staff_symbol_referencer::staff_space (me)); return ly_interval2scm (pos); -- 2.39.2