Improvements in vertical skyline approximations (issue 2148).

The file stencil-integral.cc provides a suite of functions that
traverse a stencil and do linear approximations of its components.
These are then turned into boxes that are passed to the Skyline
constructor. This approximation is used for several vertical skylines
including those of VerticalAxisGroup and System. As a result of these
more accurate approximations, vertical spacing is more snug between
grobs.

Additionally, in axis-group-interface.cc, skylines of grobs are no
longer compared to a monolithic axis-group skyline but rather all
of the component skylines of the axis-group, allowing grobs to
be fit under other ones if there is space instead of always shifted over.

Two new python scripts allow to visualize the position of skylines.

All other changes provide functions that allow for better debugging
of Skylines, better approximations of grobs via skylines, and changes
to the measurement of distance between grobs via the new Skyline API.

This results in a significant time increase in score compilation for
objects with complex skylines such as all text grobs.  For orchestral
scores, the increase is not as steep.

13 files changed, 82 insertions, 19 deletions

diff --git a/lily/include/axis-group-interface.hh b/lily/include/axis-group-interface.hh
index 19bdc1e2ee..4098a19514 100644
--- a/lily/include/axis-group-interface.hh
+++ b/lily/include/axis-group-interface.hh
@@ -25,9 +25,13 @@
 #include "grob-interface.hh"
 #include "skyline.hh"
 
-struct Axis_group_interface
+class Axis_group_interface
 {
+  static Real default_outside_staff_padding_;
+  public
+:
   static SCM generic_group_extent (Grob *me, Axis a);
+  static Real get_default_outside_staff_padding ();
   static Interval generic_bound_extent (Grob *me, Grob *common, Axis a);
   static Interval pure_group_height (Grob *me, int start, int end);
   DECLARE_SCHEME_CALLBACK (width, (SCM smob));
@@ -57,7 +61,7 @@ struct Axis_group_interface
   static Interval rest_of_line_pure_height (Grob *me, int, int);
   static Interval part_of_line_pure_height (Grob *me, bool begin, int, int);
 
-  static bool has_outside_staff_parent (Grob *me);
+  static Grob *outside_staff_ancestor (Grob *me);
   static Skyline_pair skyline_spacing (Grob *me, vector<Grob *> elements);
   static void add_element (Grob *me, Grob *);
   static void set_axes (Grob *, Axis, Axis);
diff --git a/lily/include/bezier.hh b/lily/include/bezier.hh
index 1e88dbb764..d09c0ac8be 100644
--- a/lily/include/bezier.hh
+++ b/lily/include/bezier.hh
@@ -48,6 +48,7 @@ public:
 
   Polynomial polynomial (Axis)const;
   Offset curve_point (Real t) const;
+  Real slope_at_point (Real t) const;
   Real curve_coordinate (Real t, Axis) const;
 
   static const int CONTROL_COUNT = 4;
diff --git a/lily/include/box.hh b/lily/include/box.hh
index af5695b3bc..ab0d3f5300 100644
--- a/lily/include/box.hh
+++ b/lily/include/box.hh
@@ -20,6 +20,7 @@ public:
   Interval y () const {return interval_a_[Y_AXIS]; }
   Interval operator [] (Axis a) const;
   Interval &operator [] (Axis a);
+  Real area () const;
 
   Offset center () const;
 
@@ -36,4 +37,6 @@ public:
   Box (Interval ix, Interval iy);
 };
 
+DECLARE_UNSMOB (Box, box);
+
 #endif
diff --git a/lily/include/freetype.hh b/lily/include/freetype.hh
index 3ddc07e67f..14f14d92c0 100644
--- a/lily/include/freetype.hh
+++ b/lily/include/freetype.hh
@@ -24,10 +24,16 @@
 #include FT_FREETYPE_H
 
 #include "std-string.hh"
+#include "box.hh"
 
 void init_freetype ();
 extern FT_Library freetype2_library;
 
 string freetype_error_string (FT_Error code);
 
+SCM box_to_scheme_lines (Box b);
+Box ly_FT_get_unscaled_indexed_char_dimensions (FT_Face const &face, size_t signed_idx);
+Box ly_FT_get_glyph_outline_bbox (FT_Face const &face, size_t signed_idx);
+SCM ly_FT_get_glyph_outline (FT_Face const &face, size_t signed_idx);
+
 #endif /* FREETYPE_HH */
diff --git a/lily/include/grob.hh b/lily/include/grob.hh
index fd55dbf209..14a7b47925 100644
--- a/lily/include/grob.hh
+++ b/lily/include/grob.hh
@@ -69,6 +69,12 @@ public:
   DECLARE_SCHEME_CALLBACK (y_parent_positioning, (SCM));
   DECLARE_SCHEME_CALLBACK (stencil_height, (SCM smob));
   DECLARE_SCHEME_CALLBACK (stencil_width, (SCM smob));
+  DECLARE_SCHEME_CALLBACK (simple_vertical_skylines_from_stencil, (SCM smob));
+  DECLARE_SCHEME_CALLBACK (vertical_skylines_from_stencil, (SCM smob));
+  DECLARE_SCHEME_CALLBACK (vertical_skylines_from_element_stencils, (SCM smob));
+  DECLARE_SCHEME_CALLBACK (simple_horizontal_skylines_from_stencil, (SCM smob));
+  DECLARE_SCHEME_CALLBACK (horizontal_skylines_from_stencil, (SCM smob));
+  DECLARE_SCHEME_CALLBACK (horizontal_skylines_from_element_stencils, (SCM smob));
 
   /* R/O access */
   Output_def *layout () const { return layout_; }
@@ -141,17 +147,20 @@ public:
   void fixup_refpoint ();
 
   /* vertical ordering */
+  static bool internal_vertical_less (Grob *g1, Grob *g2, bool pure);
   static Grob *get_root_vertical_alignment (Grob *g);
   static Grob *get_vertical_axis_group (Grob *g);
   static bool vertical_less (Grob *g1, Grob *g2);
   static bool pure_vertical_less (Grob *g1, Grob *g2);
-  static bool internal_vertical_less (Grob *g1, Grob *g2, bool pure);
   static int get_vertical_axis_group_index (Grob *g);
 
+  /* skylines */
   virtual Interval_t<int> spanned_rank_interval () const;
   virtual bool pure_is_visible (int start, int end) const;
   bool check_cross_staff (Grob *common);
   static bool less (Grob *g1, Grob *g2);
+  static SCM internal_simple_skylines_from_stencil (SCM, Axis);
+  static SCM internal_skylines_from_element_stencils (SCM, Axis);
 };
 
 /* smob utilities */
diff --git a/lily/include/misc.hh b/lily/include/misc.hh
index b70d2c2ce2..511fc0545f 100644
--- a/lily/include/misc.hh
+++ b/lily/include/misc.hh
@@ -61,6 +61,7 @@ normalize (Real x, Real x1, Real x2)
 
 Real directed_round (Real f, Direction d);
 
+Offset get_point_in_y_direction (Offset orig, Real slope, Real dist, Direction dir);
 Real peak_around (Real epsilon, Real threshold, Real x);
 Real convex_amplifier (Real standard_x, Real increase_factor, Real x);
 string camel_case_to_lisp_identifier (string in);
diff --git a/lily/include/modified-font-metric.hh b/lily/include/modified-font-metric.hh
index cd5cd6116f..6bf2d8d6d0 100644
--- a/lily/include/modified-font-metric.hh
+++ b/lily/include/modified-font-metric.hh
@@ -27,6 +27,7 @@ struct Modified_font_metric : public Font_metric
 {
 public:
   Stencil text_stencil (Output_def *output_state, string, bool) const;
+  Real get_magnification () const;
 
   static SCM make_scaled_font_metric (Font_metric *fm, Real magnification);
   size_t count () const;
diff --git a/lily/include/open-type-font.hh b/lily/include/open-type-font.hh
index 6ee62823ec..e3789d0685 100644
--- a/lily/include/open-type-font.hh
+++ b/lily/include/open-type-font.hh
@@ -41,11 +41,13 @@ class Open_type_font : public Font_metric
 
   DECLARE_CLASSNAME (Open_type_font);
 public:
+  Real get_units_per_EM () const;
   SCM get_subfonts () const;
   SCM get_global_table () const;
   SCM get_char_table () const;
   SCM glyph_list () const;
-
+  SCM get_glyph_outline (size_t signed_idx) const;
+  Box get_glyph_outline_bbox (size_t signed_idx) const;
   string get_otf_table (string tag) const;
   static SCM make_otf (string);
   string font_name () const;
@@ -53,6 +55,7 @@ public:
   Offset attachment_point (string) const;
   size_t count () const;
   Box get_indexed_char_dimensions (size_t) const;
+  Box get_unscaled_indexed_char_dimensions (size_t) const;
   size_t name_to_index (string) const;
   //size_t glyph_name_to_charcode (string) const;
   size_t index_to_charcode (size_t) const;
diff --git a/lily/include/pango-font.hh b/lily/include/pango-font.hh
index 6b4ad4b68f..f57b5d5b76 100644
--- a/lily/include/pango-font.hh
+++ b/lily/include/pango-font.hh
@@ -50,6 +50,12 @@ public:
   SCM font_file_name () const;
   void register_font_file (string, string, int);
 
+  size_t name_to_index (string) const;
+  SCM get_glyph_outline (size_t signed_idx) const;
+  Box get_glyph_outline_bbox (size_t signed_idx) const;
+  Box get_unscaled_indexed_char_dimensions (size_t) const;
+  Box get_scaled_indexed_char_dimensions (size_t) const;
+
   Stencil pango_item_string_stencil (PangoGlyphItem const *) const;
 
   virtual Stencil text_stencil (Output_def *output_state,
diff --git a/lily/include/skyline-pair.hh b/lily/include/skyline-pair.hh
index 22dd639332..604d2fb4df 100644
--- a/lily/include/skyline-pair.hh
+++ b/lily/include/skyline-pair.hh
@@ -30,14 +30,25 @@ private:
   DECLARE_SIMPLE_SMOBS (Skyline_pair);
 public:
   Skyline_pair ();
-  Skyline_pair (vector<Box> const &boxes, Real horizon_padding, Axis a);
-  Skyline_pair (Box const &, Real horizon_padding, Axis a);
+  Skyline_pair (vector<Box> const &boxes, Axis a);
+  Skyline_pair (vector<Drul_array<Offset> > const &buildings, Axis a);
+  Skyline_pair (vector<Skyline_pair> const &skypairs);
+  Skyline_pair (Box const &, Axis a);
+
   void raise (Real);
+  void grow (Real);
   void shift (Real);
-  void insert (Box const &, Real horizon_padding, Axis);
+  void deholify ();
+  Real smallest_shift (Skyline_pair const &other, Direction d,
+                       Real h_padding = 0, Real v_padding = 0);
+  Real left () const;
+  Real right () const;
+  bool intersects (Skyline_pair const &other) const;
+  void insert (Box const &, Axis);
   void merge (Skyline_pair const &other);
   Skyline &operator [] (Direction d);
   Skyline const &operator [] (Direction d) const;
+  bool is_singleton () const;
   bool is_empty () const;
   void print () const;
   void print_points () const;
diff --git a/lily/include/skyline.hh b/lily/include/skyline.hh
index ceedf24007..a93316d935 100644
--- a/lily/include/skyline.hh
+++ b/lily/include/skyline.hh
@@ -32,20 +32,22 @@
 
 struct Building
 {
+  Real start_;
   Real end_;
   Real y_intercept_;
   Real slope_;
 
   void precompute (Real start, Real start_height, Real end_height, Real end);
   Building (Real start, Real start_height, Real end_height, Real end);
-  Building (Box const &b, Real horizon_padding, Axis a, Direction d);
+  Building (Box const &b, Axis a, Direction d);
   void print () const;
 
   Real height (Real x) const;
   Real intersection_x (Building const &other) const;
   void leading_part (Real chop);
   bool conceals (Building const &other, Real x) const;
-  Building sloped_neighbour (Real start, Real horizon_padding, Direction d) const;
+  Real shift_to_intersect (Real x, Real y) const;
+  Interval overlapping_shift_interval (Building const &other) const;
 };
 
 class Skyline
@@ -55,43 +57,57 @@ private:
   Direction sky_;
 
   void internal_merge_skyline (list<Building> *, list<Building> *,
-                               list<Building> *const result);
-  list<Building> internal_build_skyline (list<Box> *, Real, Axis, Direction);
+                               list<Building> *const result) const;
+  list<Building> internal_build_skyline (list<Building> *) const;
+  Real internal_distance (Skyline const &, Real horizon_padding, Real *touch_point) const;
+  Real internal_distance (Skyline const &, Real *touch_point) const;
+  void normalize ();
 
   DECLARE_SIMPLE_SMOBS (Skyline);
 
 public:
   Skyline ();
   Skyline (Skyline const &src);
-  Skyline (Skyline const &src, Real horizon_padding, Axis a);
   Skyline (Direction sky);
-  Skyline (vector<Box> const &bldgs, Real horizon_padding, Axis a, Direction sky);
-  Skyline (Box const &b, Real horizon_padding, Axis a, Direction sky);
+  Skyline (vector<Box> const &bldgs, Axis a, Direction sky);
+  Skyline (vector<Drul_array<Offset> > const &bldgs, Axis a, Direction sky);
+  Skyline (vector<Skyline_pair> const &skypairs, Direction sky);
+  Skyline (Box const &b, Axis a, Direction sky);
 
   vector<Offset> to_points (Axis) const;
+  void deholify ();
   void merge (Skyline const &);
-  void insert (Box const &, Real horizon_padding, Axis);
+  void insert (Box const &, Axis);
   void print () const;
   void print_points () const;
   void raise (Real);
   void shift (Real);
+  void invert ();
   Real distance (Skyline const &, Real horizon_padding = 0) const;
+  Real smallest_shift (Skyline const &, Direction d,
+                       Real horizon_padding = 0,
+                       Real vertical_padding = 0) const;
   Real touching_point (Skyline const &, Real horizon_padding = 0) const;
+  Real shift_to_avoid (Skyline const &other, Real, Direction d, Real horizon_padding = 0);
+  Real raise_to_avoid (Skyline const &other, Real, Direction d, Real horizon_padding = 0);
+  Drul_array<Real> shifts_to_avoid_intersection (Skyline const &, Real horizon_padding = 0) const;
+  Interval raises_to_avoid_intersection (Skyline const &, Real horizon_padding = 0) const;
   Real height (Real airplane) const;
   Real max_height () const;
   Real max_height_position () const;
   void set_minimum_height (Real height);
   void clear ();
   bool is_empty () const;
+  bool is_singleton () const;
+  Real left () const;
+  Real right () const;
+  Skyline padded (Real horizon_padding) const;
 
   DECLARE_SCHEME_CALLBACK (get_touching_point, (SCM, SCM, SCM));
   DECLARE_SCHEME_CALLBACK (get_distance, (SCM, SCM, SCM));
   DECLARE_SCHEME_CALLBACK (get_max_height, (SCM));
   DECLARE_SCHEME_CALLBACK (get_max_height_position, (SCM));
   DECLARE_SCHEME_CALLBACK (get_height, (SCM, SCM));
-
-protected:
-  Real internal_distance (Skyline const &, Real horizon_padding, Real *touch_point) const;
 };
 
 extern bool debug_skylines;
diff --git a/lily/include/stencil.hh b/lily/include/stencil.hh
index 00c295316c..65c0b7a0f1 100644
--- a/lily/include/stencil.hh
+++ b/lily/include/stencil.hh
@@ -85,6 +85,7 @@ public:
   Box extent_box () const;
   bool is_empty () const;
   Stencil in_color (Real r, Real g, Real b) const;
+  static SCM skylines_from_stencil (SCM, Real, Axis);
 };
 
 DECLARE_UNSMOB (Stencil, stencil);
diff --git a/lily/include/system.hh b/lily/include/system.hh
index 453e48234d..a5efe750ad 100644
--- a/lily/include/system.hh
+++ b/lily/include/system.hh
@@ -39,7 +39,6 @@ class System : public Spanner
 
 public:
   Paper_score *paper_score () const;
-  Grob *get_vertical_alignment ();
   Grob *get_extremal_staff (Direction dir, Interval const &);
   Grob *get_neighboring_staff (Direction dir, Grob *vertical_axis_group, Interval_t<int> bounds);
   Grob *get_pure_bound (Direction dir, int start, int end);
@@ -59,12 +58,14 @@ public:
 
   DECLARE_SCHEME_CALLBACK (footnotes_before_line_breaking, (SCM));
   DECLARE_SCHEME_CALLBACK (footnotes_after_line_breaking, (SCM));
+  DECLARE_SCHEME_CALLBACK (vertical_skyline_elements, (SCM));
   DECLARE_SCHEME_CALLBACK (calc_pure_relevant_grobs, (SCM));
   DECLARE_SCHEME_CALLBACK (height, (SCM));
   DECLARE_SCHEME_CALLBACK (calc_pure_height, (SCM, SCM, SCM));
   DECLARE_SCHEME_CALLBACK (get_staves, (SCM));
   DECLARE_SCHEME_CALLBACK (get_spaceable_staves, (SCM));
   DECLARE_SCHEME_CALLBACK (get_nonspaceable_staves, (SCM));
+  DECLARE_SCHEME_CALLBACK (get_vertical_alignment, (SCM));
 
   System (SCM);
   System (System const &);