commit aa271b4aaf5bb48bdeea41da6e44a883de1ed0de
Author: Han-Wen Nienhuys <address@hidden>
Date:   Mon Jan 24 12:15:48 2011 -0200

    Proof of concept: use scoring for beam collisions.

diff --git a/input/regression/beam-collision.ly b/input/regression/beam-collision.ly
index b73ce8a..b91d060 100644
--- a/input/regression/beam-collision.ly
+++ b/input/regression/beam-collision.ly
@@ -1,19 +1,46 @@
 \version "2.13.47"
 \header {
-  texidoc = "When set manually, beams do not collide in polyphonic textures.
-"
+  texidoc = "Manual beams do not collide with notes, accidentals, etc."
+  tagline = ""
 }
 
-\relative c'' {
-  \time 4/4
-  << { s128 e[ s cis,] } \\ { b''[ s b] } >> r8..
-  << { s8 d,,[ s d] } \\ { f'8[ s fis] } >>
-  << { s16 c,16[ s c''] } \\ { b16[ s d,,] } >> |
-  \time 3/4
-  << { \times 4/5 { s32 e[ s g s g, s e'' s b'] } } \\
-     { \times 4/5 { c,,32[ s c'' s g, s b s d s] } } >>
-  \clef bass g,,,8[ \clef treble d''8]
-  b8[ c |
-  \time 2/4
-  d e] r4 |
+\relative \new Staff {
+
+  <<
+    \new Voice {
+    \voiceOne
+    \repeat unfold 8 { c8[ c] }
+  }
+    
+    \new Voice \relative c'' {
+      \voiceThree
+      \autoBeamOff
+      f f e e
+      d d c c
+      b b a a
+      g g f f
+      \break
+    } 
+  >>
+   <<
+     \new Voice {
+       \repeat unfold 8 \relative {
+	 \voiceOne
+	 c8[
+	 \voiceTwo
+	 c'']
+       }
+     }
+     \new Voice \relative {
+       \voiceFour
+       s8 f 
+       s8 g
+       s8 a
+       s8 b
+       s8 c
+       s8 d
+       s8 e
+     }
+   >>
 }
+
diff --git a/lily/beam-quanting.cc b/lily/beam-quanting.cc
index 2ecf070..f6338e7 100644
--- a/lily/beam-quanting.cc
+++ b/lily/beam-quanting.cc
@@ -58,6 +58,8 @@ Beam_quant_parameters::fill (Grob *him)
   MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
   IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
   ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
+  COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
+  COLLISION_DISTANCE = get_detail (details, ly_symbol2scm ("collision-distance"), 0.5);
 }
 
 static Real
@@ -150,6 +152,9 @@ Beam::quanting (SCM smob, SCM posns)
   */
   vector<Grob*> stems
     = extract_grob_array (me, "stems");
+  
+  extract_grob_set (me, "covered-grobs", covered_grobs);
+      
   vector<Stem_info> stem_infos;
   vector<Real> base_lengths;
   vector<Real> stem_xposns;
@@ -157,8 +162,11 @@ Beam::quanting (SCM smob, SCM posns)
   Drul_array<bool> dirs_found (0, 0);
   Grob *common[2];
   for (int a = 2; a--;)
-    common[a] = common_refpoint_of_array (stems, me, Axis (a));
-
+    {
+      common[a] = common_refpoint_of_array (stems, me, Axis (a));
+      common[a] = common_refpoint_of_array (covered_grobs, me, Axis (a));
+    }
+  
   Grob *fvs = first_normal_stem (me);
   Grob *lvs = last_normal_stem (me);
   Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
@@ -194,6 +202,18 @@ Beam::quanting (SCM smob, SCM posns)
 
       stem_xposns.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
     }
+
+  /*
+    Get dimensions of possible collisions.
+   */
+  vector<Box> covered;
+  for (vsize i = 0; i < covered_grobs.size(); i++)
+    {
+      Grob* g = covered_grobs[i];
+      covered.push_back (Box(g->extent (common[X_AXIS], X_AXIS),
+                             g->extent (common[Y_AXIS], Y_AXIS)));
+    }
+  
   bool xstaff = Align_interface::has_interface (common[Y_AXIS]);
 
   Direction ldir = Direction (stem_infos[0].dir_);
@@ -237,6 +257,20 @@ Beam::quanting (SCM smob, SCM posns)
      parameters outside of the loop, we can save a lot of time. */
   for (vsize i = qscores.size (); i--;)
     {
+      Real d = score_collisions (qscores[i].yl, qscores[i].yr,
+                                 covered,
+                                 beam_thickness,
+                                 xl, xr, 
+                                 &parameters);
+      qscores[i].demerits += d;
+
+#if DEBUG_BEAM_SCORING
+      qscores[i].score_card_ += to_string (" C %.2f", d);
+#endif
+    }
+  
+  for (vsize i = qscores.size (); i--;)
+    {
       Real d = score_slopes_dy (qscores[i].yl, qscores[i].yr,
 				dy_mus, yr- yl,
 				xr - xl,
@@ -308,6 +342,7 @@ Beam::quanting (SCM smob, SCM posns)
     }
 #endif
 
+  
   Interval final_positions;
   if (best_idx < 0)
     {
@@ -546,3 +581,41 @@ Beam::score_forbidden_quants (Real yl, Real yr,
   return dem;
 }
 
+
+/*
+  TODO
+
+  - handle beam multiplicity correctly
+  - tune parameters
+  - feathered beams? (probably overkill?)
+*/
+Real
+Beam::score_collisions (Real yl, Real yr,
+                        vector<Box> grob_dimensions,
+                        Real beam_thickness,
+                        Real xl, Real xr,
+                        Beam_quant_parameters const *parameters)
+{
+  Real demerits = 0.0;
+  for (vsize i = 0; i < grob_dimensions.size (); i++)
+    {
+      Interval y_dims = grob_dimensions[i][Y_AXIS];
+      Direction d = LEFT;
+      do
+        {
+          Real x = grob_dimensions[i][X_AXIS][d];
+          Real beam_y = yl + (yr - yl) / (xr - xl) * (x - xl);
+          Interval beam_y_extent = Interval(-.5, .5) * beam_thickness + beam_y;
+
+          Real dist = min(beam_y_extent.distance(y_dims[DOWN]),
+                          beam_y_extent.distance(y_dims[UP]));
+          Real scale_free = 
+            max(parameters->COLLISION_DISTANCE - dist, 0.0)/
+            parameters->COLLISION_DISTANCE;
+          demerits +=
+            pow(scale_free, 3) * parameters->COLLISION_PENALTY;
+        }
+      while ((flip (&d)) != LEFT);
+    }
+  return demerits;
+} 
diff --git a/lily/beam.cc b/lily/beam.cc
index 1f70dfb..89fbac2 100644
--- a/lily/beam.cc
+++ b/lily/beam.cc
@@ -928,134 +928,6 @@ Beam::no_visible_stem_positions (Grob *me, Interval default_value)
 }
 
 /*
-  Raise the quanted beam for collisions.
-*/
-MAKE_SCHEME_CALLBACK (Beam, move_to_avoid_collisions, 2);
-SCM
-Beam::move_to_avoid_collisions (SCM smob, SCM posns)
-{
-  Grob *me = unsmob_grob (smob);
-  extract_grob_set (me, "normal-stems", stems);
-
-  if (!is_knee (me) && !is_cross_staff (me) && first_normal_stem (me) && last_normal_stem (me))
-    {
-      Direction dir = to_dir (first_normal_stem (me)->get_property ("direction"));
-      Real offset = 0.0;
-      Interval pos = ly_scm2interval (posns);
-      extract_grob_set (me, "covered-grobs", covered_grobs);
-      Grob *common_x = common_refpoint_of_array (stems, me, X_AXIS);
-      Grob *common_y = common_refpoint_of_array (stems, me, Y_AXIS);
-      vector<Beam_segment> segments = get_beam_segments (me, &common_x);
-
-
-      Real beam_translation = get_beam_translation (me);
-      Real beam_thickness = get_beam_thickness (me);
-
-      Interval span;
-      span[LEFT] = first_normal_stem (me)->relative_coordinate (common_x, X_AXIS);
-      span[RIGHT] = last_normal_stem (me)->relative_coordinate (common_x, X_AXIS);
-
-      /* blech...kludge
-         for some reason, the leftmost segments[i].horizontal_[LEFT] is not equal to
-         span[LEFT] above.  I believe that span[LEFT] is the correct X coordinate,
-         and thus, I use this corrective to do the calculations (usually, it is a very
-         small number, but sometimes matters.
-      */
-      Real left_guess = 100000.0;
-      for (vsize i = 0; i < segments.size(); i++)
-        left_guess = min(segments[i].horizontal_[LEFT], left_guess);
-      Real left_corrective = span[LEFT] - left_guess;
-      /* end kludge */
-
-      Direction feather_dir = to_dir (me->get_property ("grow-direction"));
-
-      Real slope = (pos[LEFT] - pos[RIGHT]) / (span[LEFT] - span[RIGHT]);
-
-      for (vsize i = 0; i < segments.size(); i++)
-        {
-          Real temp_offset = 0.0;
-
-          /* ugh...code dup from the print function */
-          Real local_slope = slope;
-          if (feather_dir)
-	    local_slope += feather_dir * segments[i].vertical_count_ * beam_translation / span.length ();
-
-          Interval local_span;
-          local_span[LEFT] = segments[i].horizontal_[LEFT] + left_corrective;
-          local_span[RIGHT] = segments[i].horizontal_[RIGHT] + left_corrective;
-          Real local_down = local_slope
-			* (local_span[LEFT] - span.linear_combination (feather_dir))
-			+ pos.linear_combination (feather_dir)
-			+ beam_translation * segments[i].vertical_count_;
-          Real local_width = local_span[RIGHT] - local_span[LEFT];
-
-          for (vsize j = 0; j < covered_grobs.size (); j++)
-            {
-              Grob *covered_grob = covered_grobs.at (j);
-              Real left = 0.0;
-              Real down = 0.0;
-              Real width = 0.0;
-              Real height = 0.0;
-
-              if (covered_grob->is_live ())
-                {
-                  left = covered_grob->extent(common_x, X_AXIS)[LEFT] - local_span[LEFT];
-                  down = covered_grob->extent(common_y, Y_AXIS)[DOWN] - local_down;
-                  width = covered_grob->extent(common_x, X_AXIS).length ();
-
-                  if (left > local_width)
-                    continue;
-                  if (left + width < 0)
-                    continue;
-                  height = covered_grob->extent(common_y, Y_AXIS).length ();
-                  if (height <= 0.0)
-                    continue;
-                }
-              else
-                continue;
-
-              /* seems to be the correct amount of breathing room */
-              Real y_val = beam_thickness;
-              if (dir == DOWN)
-                y_val *= -1.0;
-              if (dir == UP)
-                y_val += down + height;
-              else
-                y_val += down;
-
-              Real beam_y1 = local_slope * left;
-              Real beam_y2 = local_slope * (left + width);
-
-              if (dir == UP)
-                {
-                  if (y_val > beam_y1)
-                    temp_offset = max (y_val - beam_y1, temp_offset);
-                  if (y_val > beam_y2)
-                    temp_offset = max (y_val - beam_y2, temp_offset);
-                }
-              else
-                {
-                  if (y_val < beam_y1)
-                    temp_offset = min(y_val - beam_y1, temp_offset);
-                  if (y_val < beam_y2)
-                    temp_offset = min(y_val - beam_y2, temp_offset);
-                }
-            }
-
-          if (dir == UP)
-            offset = max (offset, temp_offset);
-          else
-            offset = min (offset, temp_offset);
-        }
-
-      pos[LEFT] += offset;
-      pos[RIGHT] += offset;
-      return ly_interval2scm (pos);
-    }
-    else
-      return posns;
-}
-/*
   Compute a first approximation to the beam slope.
 */
 MAKE_SCHEME_CALLBACK (Beam, calc_least_squares_positions, 2);
diff --git a/lily/include/beam.hh b/lily/include/beam.hh
index 2263752..47cbf34 100644
--- a/lily/include/beam.hh
+++ b/lily/include/beam.hh
@@ -47,6 +47,8 @@ struct Beam_quant_parameters
   Real HINT_DIRECTION_PENALTY;
   Real IDEAL_SLOPE_FACTOR;
   Real ROUND_TO_ZERO_SLOPE;
+  Real COLLISION_PENALTY;
+  Real COLLISION_DISTANCE;
 
   void fill (Grob *him);
 };
@@ -113,8 +115,14 @@ public:
   DECLARE_SCHEME_CALLBACK (slope_damping, (SCM, SCM));
   DECLARE_SCHEME_CALLBACK (quanting, (SCM, SCM));
   
-static Real score_slopes_dy (Real, Real, Real, Real, Real, bool, Beam_quant_parameters const *);
+  static Real score_slopes_dy (Real, Real, Real, Real, Real, bool, Beam_quant_parameters const *);
 
+  static Real score_collisions (Real yl, Real yr,
+                                vector<Box> grob_dimensions,
+                                Real beam_thickness,
+                                Real xl, Real xr,
+                                Beam_quant_parameters const *parameters);
+  
   static Real score_stem_lengths (vector<Grob*> const &stems,
 				  vector<Stem_info> const &stem_infos,
 				  vector<Real> const &base_stem_ys,
diff --git a/scm/define-grobs.scm b/scm/define-grobs.scm
index 18d9378..02160ee 100644
--- a/scm/define-grobs.scm
+++ b/scm/define-grobs.scm
@@ -377,7 +377,6 @@
 			   ly:beam::slope-damping
 			   ly:beam::shift-region-to-valid
 			   ly:beam::quanting
-			   ly:beam::move-to-avoid-collisions
 			   ))))
 
 	;; this is a hack to set stem lengths, if positions is set.