Take collisions into account in Beam::shift_region_to_valid().

4 files changed, 246 insertions, 32 deletions

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 <algorithm>
 #include <queue>  
 #include <set>
-#include <algorithm>
 using namespace std;
 
 #include "align-interface.hh"
@@ -194,13 +194,11 @@ void Beam_scoring_problem::init_collisions (vector<Grob*> grobs)
   set<Grob*> 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<Real> 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<Real> 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<Interval> collision_free (feasible_left_point,
+                                       feasible_left_point);
+
+  vector<Grob*> 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<Real> (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<Real> (beam_left_y, (beam_left_y + beam_dy));
   scale_drul (&pos, 1 / Staff_symbol_referencer::staff_space (me));
 
   return ly_interval2scm (pos);