]> git.donarmstrong.com Git - lilypond.git/blobdiff - lily/beam.cc
Imported Upstream version 2.14.2
[lilypond.git] / lily / beam.cc
index 83d82e3ccabb91e0725d06ef5053f92f184a2f80..66c58ef8dcc2fc271c6ccd318c43c74825bd216d 100644 (file)
@@ -1,10 +1,21 @@
 /*
-  beam.cc -- implement Beam
+  This file is part of LilyPond, the GNU music typesetter.
 
-  source file of the GNU LilyPond music typesetter
-
-  (c) 1997--2009 Han-Wen Nienhuys <hanwen@xs4all.nl>
+  Copyright (C) 1997--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
   Jan Nieuwenhuizen <janneke@gnu.org>
+
+  LilyPond is free software: you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation, either version 3 of the License, or
+  (at your option) any later version.
+
+  LilyPond is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
 */
 
 /*
 
 #include "beam.hh"
 
+#include "align-interface.hh"
+#include "beam-scoring-problem.hh"
 #include "beaming-pattern.hh"
 #include "directional-element-interface.hh"
-#include "main.hh"
+#include "grob-array.hh"
 #include "international.hh"
 #include "interval-set.hh"
 #include "item.hh"
 #include "least-squares.hh"
 #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"
 #include "warn.hh"
-#include "grob-array.hh"
 
 #if DEBUG_BEAM_SCORING
 #include "text-interface.hh" // debug output.
@@ -62,6 +77,12 @@ Beam_stem_segment::Beam_stem_segment ()
   dir_ = CENTER;
 }
 
+bool
+beam_segment_less (Beam_segment const& a, Beam_segment const& b)
+{
+  return a.horizontal_[LEFT] < b.horizontal_[LEFT];
+}
+
 Beam_segment::Beam_segment ()
 {
   vertical_count_ = 0;
@@ -82,9 +103,9 @@ Beam::add_stem (Grob *me, Grob *s)
 }
 
 Real
-Beam::get_thickness (Grob *me)
+Beam::get_beam_thickness (Grob *me)
 {
-  return robust_scm2double (me->get_property ("thickness"), 0)
+  return robust_scm2double (me->get_property ("beam-thickness"), 0)
     * Staff_symbol_referencer::staff_space (me);
 }
 
@@ -95,12 +116,12 @@ Beam::get_beam_translation (Grob *me)
   int beam_count = get_beam_count (me);
   Real staff_space = Staff_symbol_referencer::staff_space (me);
   Real line = Staff_symbol_referencer::line_thickness (me);
-  Real thickness = get_thickness (me);
+  Real beam_thickness = get_beam_thickness (me);
   Real fract = robust_scm2double (me->get_property ("length-fraction"), 1.0);
-  
+
   Real beam_translation = beam_count < 4
-    ? (2 * staff_space + line - thickness) / 2.0
-    : (3 * staff_space + line - thickness) / 3.0;
+    ? (2 * staff_space + line - beam_thickness) / 2.0
+    : (3 * staff_space + line - beam_thickness) / 3.0;
 
   return fract * beam_translation;
 }
@@ -125,15 +146,15 @@ SCM
 Beam::calc_normal_stems (SCM smob)
 {
   Grob *me = unsmob_grob (smob);
-  
+
   extract_grob_set (me, "stems", stems);
   SCM val = Grob_array::make_array ();
   Grob_array *ga = unsmob_grob_array (val);
   for (vsize i = 0; i < stems.size ();  i++)
     if (Stem::is_normal_stem (stems[i]))
       ga->add (stems[i]);
-  
-  return val;  
+
+  return val;
 }
 
 MAKE_SCHEME_CALLBACK (Beam, calc_direction, 1);
@@ -162,7 +183,7 @@ Beam::calc_direction (SCM smob)
 
          return SCM_UNSPECIFIED;
        }
-      else 
+      else
        {
          Grob *stem = first_normal_stem (me);
 
@@ -171,8 +192,8 @@ Beam::calc_direction (SCM smob)
          */
          if (!stem)
            stem = stems[0];
-         
-         if (is_direction (stem->get_property_data ("direction"))) 
+
+         if (is_direction (stem->get_property_data ("direction")))
            dir = to_dir (stem->get_property_data ("direction"));
          else
            dir = to_dir (stem->get_property ("default-direction"));
@@ -183,7 +204,7 @@ Beam::calc_direction (SCM smob)
     {
       if (!dir)
        dir = get_default_dir (me);
-      
+
       consider_auto_knees (me);
     }
 
@@ -191,7 +212,7 @@ Beam::calc_direction (SCM smob)
     {
       set_stem_directions (me, dir);
     }
-  
+
   return scm_from_int (dir);
 }
 
@@ -244,12 +265,12 @@ SCM
 Beam::calc_beaming (SCM smob)
 {
   Grob *me = unsmob_grob (smob);
-  
+
   extract_grob_set (me, "stems", stems);
 
   Slice last_int;
   last_int.set_empty ();
-  
+
   SCM last_beaming = scm_cons (SCM_EOL, scm_list_1 (scm_from_int (0)));
   Direction last_dir = CENTER;
   for (vsize i = 0; i < stems.size (); i++)
@@ -288,7 +309,7 @@ Beam::calc_beaming (SCM smob)
       else
        {
          /*
-           FIXME: what's this for? 
+           FIXME: what's this for?
           */
          SCM s = scm_cdr (this_beaming);
          for (; scm_is_pair (s); s = scm_cdr (s))
@@ -298,7 +319,7 @@ Beam::calc_beaming (SCM smob)
              last_int.add_point (np);
            }
        }
-      
+
       if (scm_ilength (scm_cdr (this_beaming)) > 0)
        {
          last_beaming = this_beaming;
@@ -316,8 +337,9 @@ operator <(Beam_stem_segment const &a,
   return a.rank_ < b.rank_;
 }
 
-typedef map<int, vector<Beam_stem_segment> >  Position_stem_segments_map; 
+typedef map<int, vector<Beam_stem_segment> >  Position_stem_segments_map;
 
+// TODO - should store result in a property?
 vector<Beam_segment>
 Beam::get_beam_segments (Grob *me_grob, Grob **common)
 {
@@ -334,7 +356,7 @@ Beam::get_beam_segments (Grob *me_grob, Grob **common)
   commonx = me->get_bound (RIGHT)->common_refpoint (commonx, X_AXIS);
 
   *common = commonx;
-  
+
   int gap_count = robust_scm2int (me->get_property ("gap-count"), 0);
   Real gap_length = robust_scm2double (me->get_property ("gap"), 0.0);
 
@@ -370,13 +392,13 @@ Beam::get_beam_segments (Grob *me_grob, Grob **common)
              int beam_rank = scm_to_int (scm_car (s));
              ranks.add_point (beam_rank);
            }
-         
+
          for (SCM s = index_get_cell (beaming, d);
               scm_is_pair (s); s = scm_cdr (s))
            {
              if (!scm_is_integer (scm_car (s)))
                continue;
-         
+
              int beam_rank = scm_to_int (scm_car (s));
              Beam_stem_segment seg;
              seg.stem_ = stem;
@@ -386,9 +408,9 @@ Beam::get_beam_segments (Grob *me_grob, Grob **common)
              seg.stem_index_ = i;
              seg.dir_ = d;
              seg.max_connect_ = robust_scm2int (stem->get_property ("max-beam-connect"), 1000);
-             
+
              Direction stem_dir = get_grob_direction (stem);
-             
+
              seg.gapped_
                = (stem_dir * beam_rank < (stem_dir * ranks[-stem_dir] + gap_count));
              stem_segments[beam_rank].push_back (seg);
@@ -439,12 +461,12 @@ Beam::get_beam_segments (Grob *me_grob, Grob **common)
              bool inside_stem = (event_dir == LEFT)
                ? seg.stem_index_ > 0
                : seg.stem_index_ + 1 < stems.size () ;
-                     
+
              bool event = on_beam_bound
                || abs (seg.rank_ - neighbor_seg.rank_) > 1
                || (abs (vertical_count) >= seg.max_connect_
                    || abs (vertical_count) >= neighbor_seg.max_connect_);
-             
+
              if (!event)
                // Then this edge of the current segment is irrelevent because it will
                // be connected with the next segment in the event_dir direction.
@@ -520,7 +542,7 @@ Beam::get_beam_segments (Grob *me_grob, Grob **common)
            }
          while (flip (&event_dir) != LEFT);
        }
-      
+
     }
 
   return segments;
@@ -533,6 +555,8 @@ Beam::print (SCM grob)
   Spanner *me = unsmob_spanner (grob);
   Grob *commonx = 0;
   vector<Beam_segment> segments = get_beam_segments (me, &commonx);
+  if (!segments.size ())
+    return SCM_EOL;
 
   Interval span;
   if (normal_stem_count (me))
@@ -542,7 +566,7 @@ Beam::print (SCM grob)
     }
   else
     {
-      extract_grob_set (me, "stems", stems);      
+      extract_grob_set (me, "stems", stems);
       span[LEFT] = stems[0]->relative_coordinate (commonx, X_AXIS);
       span[RIGHT] = stems.back ()->relative_coordinate (commonx, X_AXIS);
     }
@@ -564,43 +588,84 @@ Beam::print (SCM grob)
   Real dy = pos[RIGHT] - pos[LEFT];
   Real slope = (dy && span.length ()) ? dy / span.length ()  : 0;
 
-  Real thick = get_thickness (me);
+  Real beam_thickness = get_beam_thickness (me);
   Real beam_dy = get_beam_translation (me);
 
   Direction feather_dir = to_dir (me->get_property ("grow-direction"));
-  
+
+  Interval placements = robust_scm2interval (me->get_property ("normalized-endpoints"), Interval (0.0, 0.0));
+
   Stencil the_beam;
+
+  int extreme = (segments[0].vertical_count_ == 0
+                 ? segments[0].vertical_count_
+                 : segments.back ().vertical_count_);
+
   for (vsize i = 0; i < segments.size (); i ++)
     {
       Real local_slope = slope;
+      /*
+        Makes local slope proportional to the ratio of the length of this beam
+        to the total length.
+      */
       if (feather_dir)
-       {
-         local_slope += feather_dir * segments[i].vertical_count_ * beam_dy / span.length ();
-       }
-      
-      Stencil b = Lookup::beam (local_slope, segments[i].horizontal_.length (), thick, blot);
+        local_slope += (feather_dir * segments[i].vertical_count_
+                                    * beam_dy
+                                    * placements.length ()
+                        / span.length ());
+
+      Stencil b = Lookup::beam (local_slope, segments[i].horizontal_.length (), beam_thickness, blot);
 
       b.translate_axis (segments[i].horizontal_[LEFT], X_AXIS);
-      
-      b.translate_axis (local_slope
-                       * (segments[i].horizontal_[LEFT] - span.linear_combination (feather_dir))
-                       + pos.linear_combination (feather_dir)
-                       + beam_dy * segments[i].vertical_count_, Y_AXIS);
-      the_beam.add_stencil (b);      
+      Real multiplier = feather_dir ? placements[LEFT] : 1.0;
+
+      Interval weights (1 - multiplier, multiplier);
+
+      if (feather_dir != LEFT)
+        weights.swap ();
+
+      // we need two translations: the normal one and
+      // the one of the lowest segment
+      int idx[] = {i, extreme};
+      Real translations[2];
+
+      for (int j = 0; j < 2; j++)
+        translations[j] = slope
+                          * (segments[idx[j]].horizontal_[LEFT] - span.linear_combination (CENTER))
+                          + pos.linear_combination (CENTER)
+                          + beam_dy * segments[idx[j]].vertical_count_;
+
+      Real weighted_average = translations[0] * weights[LEFT] + translations[1] * weights[RIGHT];
+
+      /*
+        Tricky.  The manipulation of the variable `weighted_average' below ensures
+        that beams with a RIGHT grow direction will start from the position of the
+        lowest segment at 0, and this error will decrease and decrease over the
+        course of the beam.  Something with a LEFT grow direction, on the other
+        hand, will always start in the correct place but progressively accrue
+        error at broken places.  This code shifts beams up given where they are
+        in the total span length (controlled by the variable `multiplier').  To
+        better understand what it does, try commenting it out: you'll see that
+        all of the RIGHT growing beams immediately start too low and get better
+        over line breaks, whereas all of the LEFT growing beams start just right
+        and get worse over line breaks.
+      */
+      Real factor = Interval (multiplier, 1 - multiplier).linear_combination (feather_dir);
+
+      if (segments[0].vertical_count_ < 0 && feather_dir)
+        weighted_average += beam_dy * (segments.size () - 1) * factor;
+
+      b.translate_axis (weighted_average, Y_AXIS);
+
+      the_beam.add_stencil (b);
+
     }
-        
+
 #if (DEBUG_BEAM_SCORING)
   SCM annotation = me->get_property ("annotation");
-  if (!scm_is_string (annotation))
-    {
-      SCM debug = me->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring"));
-      if (to_boolean (debug))
-       annotation = me->get_property ("quant-score");
-    }
-  
   if (scm_is_string (annotation))
     {
-      extract_grob_set (me, "stems", stems);      
+      extract_grob_set (me, "stems", stems);
 
       /*
        This code prints the demerits for each beam. Perhaps this
@@ -610,10 +675,13 @@ Beam::print (SCM grob)
       string str;
       SCM properties = Font_interface::text_font_alist_chain (me);
 
+      properties = scm_cons(scm_acons (ly_symbol2scm ("font-size"), scm_from_int (-5), SCM_EOL),
+                            properties);
+
       Direction stem_dir = stems.size () ? to_dir (stems[0]->get_property ("direction")) : UP;
 
       Stencil score = *unsmob_stencil (Text_interface::interpret_markup
-                                   (me->layout ()->self_scm (), properties, annotation));
+                                       (me->layout ()->self_scm (), properties, annotation));
 
       if (!score.is_empty ())
        {
@@ -626,7 +694,7 @@ Beam::print (SCM grob)
   the_beam.translate_axis (-me->relative_coordinate (commonx, X_AXIS), X_AXIS);
   return the_beam.smobbed_copy ();
 }
+
 Direction
 Beam::get_default_dir (Grob *me)
 {
@@ -680,7 +748,7 @@ Beam::get_default_dir (Grob *me)
       else if (extremes[UP] < -extremes[DOWN])
        return UP;
     }
-  
+
   Direction dir = CENTER;
   Direction d = CENTER;
   if ((d = (Direction) sign (count[UP] - count[DOWN])))
@@ -693,7 +761,7 @@ Beam::get_default_dir (Grob *me)
     dir = d;
   else
     dir = to_dir (me->get_property ("neutral-direction"));
-  
+
   return dir;
 }
 
@@ -794,7 +862,7 @@ Beam::consider_auto_knees (Grob *me)
     }
 
   Real beam_translation = get_beam_translation (me);
-  Real beam_thickness = Beam::get_thickness (me);
+  Real beam_thickness = Beam::get_beam_thickness (me);
   int beam_count = Beam::get_beam_count (me);
   Real height_of_beams = beam_thickness / 2
     + (beam_count - 1) * beam_translation;
@@ -842,25 +910,25 @@ set_minimum_dy (Grob *me, Real *dy)
       */
 
       Real ss = Staff_symbol_referencer::staff_space (me);
-      Real thickness = Beam::get_thickness (me) / ss;
+      Real beam_thickness = Beam::get_beam_thickness (me) / ss;
       Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
-      Real sit = (thickness - slt) / 2;
+      Real sit = (beam_thickness - slt) / 2;
       Real inter = 0.5;
-      Real hang = 1.0 - (thickness - slt) / 2;
+      Real hang = 1.0 - (beam_thickness - slt) / 2;
 
       *dy = sign (*dy) * max (fabs (*dy),
                              min (min (sit, inter), hang));
     }
 }
 
-  
+
 
 MAKE_SCHEME_CALLBACK (Beam, calc_stem_shorten, 1)
 SCM
 Beam::calc_stem_shorten (SCM smob)
 {
   Grob *me = unsmob_grob (smob);
-  
+
   /*
     shortening looks silly for x staff beams
   */
@@ -884,7 +952,7 @@ Beam::calc_stem_shorten (SCM smob)
 
   shorten *= forced_fraction;
 
-  
+
   if (shorten)
     return scm_from_double (shorten);
 
@@ -898,7 +966,7 @@ Beam::no_visible_stem_positions (Grob *me, Interval default_value)
   extract_grob_set (me, "stems", stems);
   if (stems.empty ())
     return default_value;
-  
+
   Interval head_positions;
   Slice multiplicity;
   for (vsize i = 0; i < stems.size(); i++)
@@ -908,7 +976,11 @@ Beam::no_visible_stem_positions (Grob *me, Interval default_value)
     }
 
   Direction dir = get_grob_direction (me);
-  Real y = head_positions[dir]
+
+  if (!dir)
+    programming_error ("The beam should have a direction by now.");
+
+  Real y = head_positions.linear_combination (dir)
     * 0.5 * Staff_symbol_referencer::staff_space (me)
     + dir * get_beam_translation (me) * (multiplicity.length () + 1);
 
@@ -976,7 +1048,7 @@ Beam::calc_least_squares_positions (SCM smob, SCM /* posns */)
        {
          /* FIXME. -> UP */
          Direction d = (Direction) (sign (chord.delta ()) * UP);
-         pos[d] = get_thickness (me) / 2;
+         pos[d] = get_beam_thickness (me) / 2;
          pos[-d] = -pos[d];
        }
       else
@@ -1020,6 +1092,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.
@@ -1032,41 +1117,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
@@ -1074,6 +1161,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];
@@ -1081,7 +1169,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];
@@ -1091,8 +1178,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 ();
@@ -1101,20 +1188,180 @@ 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))
+  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;
+
+  // A list of intervals into which beams may not fall
+  vector<Interval> forbidden_intervals;
+
+  for (vsize i = 0; i < covered.size(); i++)
+    {
+      if (!covered[i]->is_live())
+        continue;
+
+      if (Beam::has_interface (covered[i]) && is_cross_staff (covered[i]))
+        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;
+          Interval disallowed;
+          do
+            {
+              Real left_y = b[Y_AXIS][yd];
+
+              left_y -= dy;
+
+              // Translate back to beam as ref point.
+              left_y -= me->relative_coordinate (common[Y_AXIS], Y_AXIS);
+
+              disallowed[yd] = left_y;
+            }
+          while (flip (&yd) != DOWN);
+
+          forbidden_intervals.push_back (disallowed);
+        }
+      while (flip (&d) != LEFT);
+    }
+
+  Grob_array *arr =
+    Pointer_group_interface::get_grob_array (me,
+                                             ly_symbol2scm ("covered-grobs"));
+  arr->set_array (filtered);
+
+  vector_sort (forbidden_intervals, Interval::left_less);
+  Real epsilon = 1.0e-10;
+  Interval feasible_beam_placements (beam_left_y, beam_left_y);
+
+  /*
+    forbidden_intervals contains a vector of intervals in which
+    the beam cannot start.  it iterates through these intervals,
+    pushing feasible_beam_placements epsilon over or epsilon under a
+    collision.  when this type of change happens, the loop is marked
+    as "dirty" and re-iterated.
+
+    TODO: figure out a faster ways that this loop can happen via
+    a better search algorithm and/or OOP.
+  */
+
+  bool dirty = false;
+  do
+    {
+      dirty = false;
+      for (vsize i = 0; i < forbidden_intervals.size (); i++)
+        {
+          Direction d = DOWN;
+          do
+            {
+              if (forbidden_intervals[i][d] == d * infinity_f)
+                feasible_beam_placements[d] = d * infinity_f;
+              else if (forbidden_intervals[i].contains (feasible_beam_placements[d]))
+                {
+                  feasible_beam_placements[d] = d * epsilon + forbidden_intervals[i][d];
+                  dirty = true;
+                }
+            }
+          while (flip (&d) != DOWN);
+        }
+    }
+  while (dirty);
+
+  // if the beam placement falls out of the feasible region, we push it
+  // to infinity so that it can never be a feasible candidate below
+  Direction d = DOWN;
+  do
+    {
+      if (!feasible_left_point.contains (feasible_beam_placements[d]))
+        feasible_beam_placements[d] = d*infinity_f;
+    }
+  while (flip (&d) != DOWN);
+
+  if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
     {
-      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;
+      // 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 if (!feasible_left_point.is_empty ())
+    {
+      // Only one of them offers is feasible solution. Pick that one.
+      if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
+        beam_left_y = feasible_beam_placements[UP];
       else
-       y = feasible_left_point.center ();
+        beam_left_y = feasible_beam_placements[DOWN];
+    }
+  else
+    {
+      // We are completely screwed.
+      warning (_ ("no viable initial configuration found: may not find good beam slope"));
     }
 
-  pos = Drul_array<Real> (y, (y + dy));
+  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);
@@ -1133,7 +1380,6 @@ Beam::slope_damping (SCM smob, SCM posns)
   if (normal_stem_count (me) <= 1)
     return posns;
 
-  
   SCM s = me->get_property ("damping");
   Real damping = scm_to_double (s);
   Real concaveness = robust_scm2double (me->get_property ("concaveness"), 0.0);
@@ -1143,7 +1389,7 @@ Beam::slope_damping (SCM smob, SCM posns)
       me->set_property ("least-squares-dy", scm_from_double (0));
       damping = 0;
     }
-  
+
   if (damping)
     {
       scale_drul (&pos, Staff_symbol_referencer::staff_space (me));
@@ -1175,6 +1421,21 @@ Beam::slope_damping (SCM smob, SCM posns)
   return ly_interval2scm (pos);
 }
 
+
+MAKE_SCHEME_CALLBACK (Beam, quanting, 2);
+SCM
+Beam::quanting (SCM smob, SCM posns)
+{
+  Grob *me = unsmob_grob (smob);
+  Drul_array<Real> ys(0, 0);
+  ys = robust_scm2drul (posns, ys);
+  Beam_scoring_problem problem (me, ys);
+
+  ys = problem.solve ();
+  return ly_interval2scm (ys);
+}
+
+
 /*
   Report slice containing the numbers that are both in (car BEAMING)
   and (cdr BEAMING)
@@ -1198,7 +1459,7 @@ where_are_the_whole_beams (SCM beaming)
    in POS for stem S.  This Y position is relative to S. */
 Real
 Beam::calc_stem_y (Grob *me, Grob *stem, Grob **common,
-                  Real xl, Real xr, Direction feather_dir, 
+                  Real xl, Real xr, Direction feather_dir,
                   Drul_array<Real> pos, bool french)
 {
   Real beam_translation = get_beam_translation (me);
@@ -1222,15 +1483,15 @@ Beam::calc_stem_y (Grob *me, Grob *stem, Grob **common,
 
   /*
     feather dir = 1 , relx 0->1 : factor 0 -> 1
-    feather dir = 0 , relx 0->1 : factor 1 -> 1    
-    feather dir = -1, relx 0->1 : factor 1 -> 0    
+    feather dir = 0 , relx 0->1 : factor 1 -> 1
+    feather dir = -1, relx 0->1 : factor 1 -> 0
    */
   Real feather_factor = 1;
   if (feather_dir > 0)
     feather_factor = relx;
   else if (feather_dir < 0)
     feather_factor = 1 - relx;
-  
+
   stem_y += feather_factor * beam_translation
     * beam_multiplicity[Direction(((french) ? DOWN : UP)*stem_dir)];
   Real id = me->relative_coordinate (common[Y_AXIS], Y_AXIS)
@@ -1243,7 +1504,7 @@ Beam::calc_stem_y (Grob *me, Grob *stem, Grob **common,
   Hmm.  At this time, beam position and slope are determined.  Maybe,
   stem directions and length should set to relative to the chord's
   position of the beam.  */
-MAKE_SCHEME_CALLBACK (Beam, set_stem_lengths, 1); 
+MAKE_SCHEME_CALLBACK (Beam, set_stem_lengths, 1);
 SCM
 Beam::set_stem_lengths (SCM smob)
 {
@@ -1254,7 +1515,7 @@ Beam::set_stem_lengths (SCM smob)
   (void) me->get_property ("beaming");
 
   SCM posns = me->get_property ("positions");
-  
+
   extract_grob_set (me, "stems", stems);
   if (!stems.size ())
     return posns;
@@ -1272,7 +1533,7 @@ Beam::set_stem_lengths (SCM smob)
   if (robust_scm2int (me->get_property ("gap-count"), 0))
     {
       gap = true;
-      thick = get_thickness (me);
+      thick = get_beam_thickness (me);
     }
 
   Grob *fvs = first_normal_stem (me);
@@ -1359,7 +1620,7 @@ Beam::forced_stem_count (Grob *me)
       /* I can imagine counting those boundaries as a half forced stem,
         but let's count them full for now. */
       Direction defdir = to_dir (s->get_property ("default-direction"));
-      
+
       if (abs (Stem::chord_start_y (s)) > 0.1
          && defdir
          && get_grob_direction (s) != defdir)
@@ -1408,7 +1669,7 @@ Beam::rest_collision_callback (SCM smob, SCM prev_offset)
     return scm_from_int (0);
 
   Real offset = robust_scm2double (prev_offset, 0.0);
-  
+
   Grob *st = unsmob_grob (rest->get_object ("stem"));
   Grob *stem = st;
   if (!stem)
@@ -1431,9 +1692,9 @@ Beam::rest_collision_callback (SCM smob, SCM prev_offset)
   Drul_array<Grob*> visible_stems (first_normal_stem (beam),
                                   last_normal_stem (beam));
   extract_grob_set (beam, "stems", stems);
-  
+
   Grob *common = common_refpoint_of_array (stems, beam, X_AXIS);
-  
+
   Real x0 = visible_stems[LEFT]->relative_coordinate (common, X_AXIS);
   Real dx = visible_stems[RIGHT]->relative_coordinate (common, X_AXIS) - x0;
   Real slope = dy && dx ? dy / dx : 0;
@@ -1443,7 +1704,7 @@ Beam::rest_collision_callback (SCM smob, SCM prev_offset)
     + (stem->relative_coordinate (common, X_AXIS) - x0) * slope;
 
   Real beam_translation = get_beam_translation (beam);
-  Real beam_thickness = Beam::get_thickness (beam);
+  Real beam_thickness = Beam::get_beam_thickness (beam);
 
   /*
     TODO: this is not strictly correct for 16th knee beams.
@@ -1457,13 +1718,9 @@ Beam::rest_collision_callback (SCM smob, SCM prev_offset)
 
   Grob *common_y = rest->common_refpoint (beam, Y_AXIS);
 
-  /*
-    TODO: this is dubious, because this call needs the info we're
-    computing right now.
-   */
-  Interval rest_extent = rest->extent (common_y, Y_AXIS);
-  rest_extent.translate (offset);
-  
+  Interval rest_extent = rest->extent (rest, Y_AXIS);
+  rest_extent.translate (offset + rest->get_parent (Y_AXIS)->relative_coordinate (common_y, Y_AXIS));
+
   Real rest_dim = rest_extent[d];
   Real minimum_distance
     = staff_space * (robust_scm2double (stem->get_property ("stemlet-length"), 0.0)
@@ -1552,19 +1809,57 @@ Beam::get_direction_beam_count (Grob *me, Direction d)
 ADD_INTERFACE (Beam,
               "A beam.\n"
               "\n"
-              "The @code{thickness} property is the weight of beams,"
+              "The @code{beam-thickness} property is the weight of beams,"
               " measured in staffspace.  The @code{direction} property is"
               " not user-serviceable.  Use the @code{direction} property"
-              " of @code{Stem} instead.",
-              
+              " of @code{Stem} instead.\n"
+               "\n"
+               "The following properties may be set in the @code{details}"
+               " list.\n"
+               "\n"
+               "@table @code\n"
+               "@item stem-length-demerit-factor\n"
+               "Demerit factor used for inappropriate stem lengths.\n"
+               "@item secondary-beam-demerit\n"
+               "Demerit used in quanting calculations for multiple"
+               " beams.\n"
+               "@item region-size\n"
+               "Size of region for checking quant scores.\n"
+               "@item beam-eps\n"
+               "Epsilon for beam quant code to check for presence"
+               " in gap.\n"
+               "@item stem-length-limit-penalty\n"
+               "Penalty for differences in stem lengths on a beam.\n"
+               "@item damping-direction-penalty\n"
+               "Demerit penalty applied when beam direction is different"
+               " from damping direction.\n"
+               "@item hint-direction-penalty\n"
+               "Demerit penalty applied when beam direction is different"
+               " from damping direction, but damping slope is"
+               " <= @code{round-to-zero-slope}.\n"
+               "@item musical-direction-factor\n"
+               "Demerit scaling factor for difference between"
+               " beam slope and music slope.\n"
+               "@item ideal-slope-factor\n"
+               "Demerit scaling factor for difference between"
+               " beam slope and damping slope.\n"
+               "@item round-to-zero-slope\n"
+               "Damping slope which is considered zero for purposes of"
+               " calculating direction penalties.\n"
+               "@end table\n",
+
               /* properties */
               "annotation "
               "auto-knee-gap "
               "beamed-stem-shorten "
               "beaming "
+              "beam-thickness "
               "break-overshoot "
               "clip-edges "
               "concaveness "
+              "collision-interfaces "
+              "collision-voice-only "
+              "covered-grobs "
               "damping "
               "details "
               "direction "
@@ -1578,9 +1873,7 @@ ADD_INTERFACE (Beam,
               "neutral-direction "
               "normal-stems "
               "positions "
-              "quant-score "
               "quantized-positions "
               "shorten "
               "stems "
-              "thickness "
               );