From a7fe7834a16062ca5f7c55d9af811c2e2a925320 Mon Sep 17 00:00:00 2001 From: Joe Neeman Date: Fri, 15 Dec 2006 17:21:57 +0200 Subject: [PATCH] use skylines in VerticalAlignment. add the Skyline_pair class. remove self-alignment support from align-interface. --- lily/align-interface.cc | 154 +++++++++++++-------------- lily/axis-group-interface.cc | 57 ++++++++-- lily/include/axis-group-interface.hh | 5 +- lily/include/skyline.hh | 22 ++++ lily/separation-item.cc | 27 +---- lily/skyline.cc | 130 +++++++++++++++++++--- scm/define-grob-properties.scm | 4 +- scm/define-grobs.scm | 7 +- 8 files changed, 280 insertions(+), 126 deletions(-) diff --git a/lily/align-interface.cc b/lily/align-interface.cc index f2eacf7608..2f23220c5a 100644 --- a/lily/align-interface.cc +++ b/lily/align-interface.cc @@ -123,28 +123,71 @@ Align_interface::align_to_fixed_distance (Grob *me, Axis a) v.unite (Interval (where, where)); } - /* - TODO: support self-alignment-{Y, X} - */ for (vsize i = 0; i < translates.size (); i++) elems[i]->translate_axis (translates[i] - v.center (), a); } -/* - Hairy function to put elements where they should be. Can be tweaked - from the outside by setting extra-space in its - children - - We assume that the children the refpoints of the children are still - found at 0.0 -- we will fuck up with thresholds if children's - extents are already moved to locations such as (-16, -8), since the - dy needed to put things in a row doesn't relate to the distances - between original refpoints. - - TODO: maybe we should rethink and throw out thresholding altogether. - The original function has been taken over by - align_to_fixed_distance (). -*/ +/* for each grob, find its upper and lower skylines. If the grob has + an empty extent, delete it from the list instead. If the extent is + non-empty but there is no skyline available (or pure is true), just + create a flat skyline from the bounding box */ +static void +get_skylines (Grob *me, + vector *const elements, + Axis a, + bool pure, int start, int end, + vector *const ret) +{ + Grob *other_axis_common = common_refpoint_of_array (*elements, me, other_axis (a)); + for (vsize i = elements->size (); i--;) + { + Grob *g = (*elements)[i]; + Interval extent = g->maybe_pure_extent (g, a, pure, start, end); + Interval other_extent = pure ? Interval (-infinity_f, infinity_f) + : g->extent (other_axis_common, other_axis (a)); + Box b = (a == X_AXIS) ? Box (extent, other_extent) : Box (other_extent, extent); + + if (extent.is_empty ()) + { + elements->erase (elements->begin () + i); + continue; + } + + Skyline_pair skylines; + if (!pure + && Skyline_pair::unsmob (g->get_property ("skylines"))) + skylines = *Skyline_pair::unsmob (g->get_property ("skylines")); + else + { + if (!pure) + programming_error ("no skylines for alignment-child\n"); + + skylines = Skyline_pair (b, 0, other_axis (a)); + } + + /* each skyline is calculated relative to (potentially) a different other_axis + coordinate. In order to compare the skylines effectively, we need to shift them + to some absolute reference point */ + if (!pure) + { + /* this is perhaps an abuse of minimum-?-extent: maybe we should create + another property? But it seems that the only (current) use of + minimum-Y-extent is to separate vertically-aligned elements */ + SCM min_extent = g->get_property (a == X_AXIS ? "minimum-X-extent" : "minimum-Y-extent"); + if (is_number_pair (min_extent)) + { + b[a] = ly_scm2interval (min_extent); + skylines.insert (b, 0, other_axis (a)); + } + Real offset = g->relative_coordinate (other_axis_common, other_axis (a)); + skylines.shift (-offset); + } + + + ret->push_back (skylines); + } + reverse (*ret); +} vector Align_interface::get_extents_aligned_translates (Grob *me, @@ -169,63 +212,29 @@ Align_interface::get_extents_aligned_translates (Grob *me, Direction stacking_dir = robust_scm2dir (me->get_property ("stacking-dir"), DOWN); - Interval threshold = robust_scm2interval (me->get_property ("threshold"), - Interval (0, Interval::infinity ())); + vector elems (all_grobs); // writable copy + vector skylines; - vector dims; - vector elems; + get_skylines (me, &elems, a, pure, start, end, &skylines); - for (vsize i = 0; i < all_grobs.size (); i++) - { - Interval y = all_grobs[i]->maybe_pure_extent (all_grobs[i], a, pure, start, end); - if (!y.is_empty ()) - { - Grob *e = dynamic_cast (all_grobs[i]); - - elems.push_back (e); - dims.push_back (y); - } - } - - /* - Read self-alignment-X and self-alignment-Y. This may seem like - code duplication. (and really: it is), but this is necessary to - prevent ugly cyclic dependencies that arise when you combine - self-alignment on a child with alignment of children. - */ - SCM align ((a == X_AXIS) - ? me->get_property ("self-alignment-X") - : me->get_property ("self-alignment-Y")); - - Interval total; Real where = 0; - Real extra_space = 0.0; SCM extra_space_handle = scm_assq (ly_symbol2scm ("alignment-extra-space"), line_break_details); + Real extra_space = robust_scm2double (scm_is_pair (extra_space_handle) + ? scm_cdr (extra_space_handle) + : SCM_EOL, + 0.0); - extra_space = robust_scm2double (scm_is_pair (extra_space_handle) - ? scm_cdr (extra_space_handle) - : SCM_EOL, - extra_space); - - Real padding = robust_scm2double (me->get_property ("padding"), - 0.0); + Real padding = robust_scm2double (me->get_property ("padding"), 0.0); vector translates; for (vsize j = 0; j < elems.size (); j++) { - Real dy = -dims[j][-stacking_dir]; - if (j) - dy += dims[j - 1][stacking_dir]; - - /* - we want dy to be > 0 - */ - dy *= stacking_dir; - if (j) - dy = min (max (dy, threshold[SMALLER]), threshold[BIGGER]); - + Real dy = 0; + if (j == 0) + dy = skylines[j][-stacking_dir].max_height (); + else + dy = skylines[j-1][stacking_dir].distance (skylines[j][-stacking_dir]); where += stacking_dir * (dy + padding + extra_space / elems.size ()); - total.unite (dims[j] + where); translates.push_back (where); } @@ -243,25 +252,16 @@ Align_interface::get_extents_aligned_translates (Grob *me, } } - - Real center_offset = 0.0; - - /* - also move the grobs that were empty, to maintain spatial order. - */ vector all_translates; - if (translates.size ()) + + if (!translates.empty ()) { Real w = translates[0]; - - if (scm_is_number (align)) - center_offset = total.linear_combination (scm_to_double (align)); - for (vsize i = 0, j = 0; j < all_grobs.size (); j++) { if (i < elems.size () && all_grobs[j] == elems[i]) w = translates[i++]; - all_translates.push_back (w - center_offset); + all_translates.push_back (w); } } return all_translates; diff --git a/lily/axis-group-interface.cc b/lily/axis-group-interface.cc index 9149f667bc..0020865621 100644 --- a/lily/axis-group-interface.cc +++ b/lily/axis-group-interface.cc @@ -179,13 +179,54 @@ Axis_group_interface::pure_height (SCM smob, SCM start_scm, SCM end_scm) return pure_group_height (me, start, end); } + +MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_skylines, 1); +SCM +Axis_group_interface::calc_skylines (SCM smob) +{ + Grob *me = unsmob_grob (smob); + extract_grob_set (me, "elements", elts); + return skyline_spacing (me, elts).smobbed_copy (); +} + +/* whereas calc_skylines calculates skylines for axis-groups with a lot of + visible children, combine_skylines is designed for axis-groups whose only + children are other axis-groups (ie. VerticalAlignment). Rather than + calculating all the skylines from scratch, we just merge the skylines + of the children. +*/ +MAKE_SCHEME_CALLBACK (Axis_group_interface, combine_skylines, 1); +SCM +Axis_group_interface::combine_skylines (SCM smob) +{ + Grob *me = unsmob_grob (smob); + extract_grob_set (me, "elements", elements); + Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS); + + assert (y_common == me); + + Skyline_pair ret; + for (vsize i = 0; i < elements.size (); i++) + { + SCM skyline_scm = elements[i]->get_property ("skylines"); + if (Skyline_pair::unsmob (skyline_scm)) + { + Real offset = elements[i]->relative_coordinate (y_common, Y_AXIS); + Skyline_pair other = *Skyline_pair::unsmob (skyline_scm); + other.raise (offset); + ret.merge (other); + } + } + return ret.smobbed_copy (); +} SCM Axis_group_interface::generic_group_extent (Grob *me, Axis a) { + /* trigger the callback to do skyline-spacing on the children */ + (void) me->get_property ("skylines"); + extract_grob_set (me, "elements", elts); - if (a == Y_AXIS && to_boolean (me->get_property ("skyline-spacing"))) - skyline_spacing (me, elts); Grob *common = common_refpoint_of_array (elts, me, a); Real my_coord = me->relative_coordinate (common, a); @@ -307,7 +348,7 @@ add_boxes (Grob *me, Grob *x_common, Grob *y_common, vector *const boxes) edge of the just-placed grob). Otherwise, we skip it until the next pass. */ static void -add_grobs_of_one_priority (Drul_array *const skylines, +add_grobs_of_one_priority (Skyline_pair *const skylines, vector elements, Grob *x_common, Grob *y_common) @@ -362,13 +403,15 @@ add_grobs_of_one_priority (Drul_array *const skylines, } } -void +Skyline_pair Axis_group_interface::skyline_spacing (Grob *me, vector elements) { vector_sort (elements, staff_priority_less); Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS); Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS); + assert (y_common == me); + vsize i = 0; vector boxes; @@ -376,8 +419,7 @@ Axis_group_interface::skyline_spacing (Grob *me, vector elements) && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++) add_boxes (elements[i], x_common, y_common, &boxes); - Drul_array skylines (Skyline (boxes, 0, X_AXIS, DOWN), - Skyline (boxes, 0, X_AXIS, UP)); + Skyline_pair skylines (boxes, 0, X_AXIS); for (; i < elements.size (); i++) { SCM priority = elements[i]->get_property ("outside-staff-priority"); @@ -389,6 +431,7 @@ Axis_group_interface::skyline_spacing (Grob *me, vector elements) add_grobs_of_one_priority (&skylines, current_elts, x_common, y_common); } + return skylines; } ADD_INTERFACE (Axis_group_interface, @@ -400,6 +443,6 @@ ADD_INTERFACE (Axis_group_interface, "elements " "common-refpoint-of-elements " "pure-relevant-elements " - "skyline-spacing " + "skylines " "cached-pure-extents " ); diff --git a/lily/include/axis-group-interface.hh b/lily/include/axis-group-interface.hh index b38537c661..4272b1a890 100644 --- a/lily/include/axis-group-interface.hh +++ b/lily/include/axis-group-interface.hh @@ -12,6 +12,7 @@ #include "std-vector.hh" #include "lily-proto.hh" #include "grob-interface.hh" +#include "skyline.hh" struct Axis_group_interface { @@ -20,6 +21,8 @@ struct Axis_group_interface DECLARE_SCHEME_CALLBACK (width, (SCM smob)); DECLARE_SCHEME_CALLBACK (height, (SCM smob)); DECLARE_SCHEME_CALLBACK (pure_height, (SCM smob, SCM start, SCM end)); + DECLARE_SCHEME_CALLBACK (calc_skylines, (SCM smob)); + DECLARE_SCHEME_CALLBACK (combine_skylines, (SCM smob)); static Interval relative_group_extent (vector const &list, Grob *common, Axis); static Interval relative_pure_height (Grob *me, vector const &list, @@ -28,7 +31,7 @@ struct Axis_group_interface static Interval cached_pure_height (Grob *me, vector const &list, Grob *common, int, int); - static void skyline_spacing (Grob *me, vector elements); + static Skyline_pair skyline_spacing (Grob *me, vector elements); static void add_element (Grob *me, Grob *); static void set_axes (Grob *, Axis, Axis); static bool has_axis (Grob *, Axis); diff --git a/lily/include/skyline.hh b/lily/include/skyline.hh index 7f3130ecab..36fd9d23e4 100644 --- a/lily/include/skyline.hh +++ b/lily/include/skyline.hh @@ -28,6 +28,7 @@ struct Building void precompute (); Building (Real start, Real start_height, Real end_height, Real end); + Building (Box const &b, Real horizon_padding, Axis a, Direction d); void print () const; Real height (Real x) const; @@ -35,6 +36,7 @@ struct Building void leading_part (Real chop); bool conceals_beginning (Building const &other) const; bool conceals (Building const &other) const; + bool sane () const; Building sloped_neighbour (Real horizon_padding, Direction d) const; }; @@ -55,16 +57,36 @@ public: Skyline (Skyline const &src); Skyline (Direction sky); Skyline (vector const &bldgs, Real horizon_padding, Axis a, Direction sky); + Skyline (Box const &b, Real horizon_padding, Axis a, Direction sky); vector to_points () const; void merge (Skyline const &); void insert (Box const &, Real horizon_padding, Axis); void print () const; void raise (Real); + void shift (Real); Real distance (Skyline const &) const; Real height (Real airplane) const; Real max_height () const; void set_minimum_height (Real height); }; +class Skyline_pair +{ +private: + Drul_array skylines_; + + DECLARE_SIMPLE_SMOBS(Skyline_pair); +public: + Skyline_pair (); + Skyline_pair (vector const &boxes, Real horizon_padding, Axis a); + Skyline_pair (Box const &, Real horizon_padding, Axis a); + void raise (Real); + void shift (Real); + void insert (Box const &, Real horizon_padding, Axis); + void merge (Skyline_pair const &other); + Skyline &operator [] (Direction d); + Skyline const &operator [] (Direction d) const; +}; + #endif /* SKYLINE_HH */ diff --git a/lily/separation-item.cc b/lily/separation-item.cc index 20de8fbbd5..ecb4e5d71f 100644 --- a/lily/separation-item.cc +++ b/lily/separation-item.cc @@ -31,17 +31,10 @@ void Separation_item::set_skyline_distance (Drul_array items, Real padding) { - Drul_array lines; - Direction d = LEFT; + Drul_array lines (Skyline_pair::unsmob (items[LEFT]->get_property ("skylines")), + Skyline_pair::unsmob (items[RIGHT]->get_property ("skylines"))); - do - { - SCM prop = items[d]->get_property ("skylines"); - lines[d] = Skyline::unsmob (index_get_cell (prop, -d)); - } - while (flip (&d) != LEFT); - - Real dist = padding + lines[LEFT]->distance (*lines[RIGHT]); + Real dist = padding + (*lines[LEFT])[RIGHT].distance ((*lines[RIGHT])[LEFT]); if (dist > 0) { Rod rod; @@ -122,19 +115,9 @@ SCM Separation_item::calc_skylines (SCM smob) { Item *me = unsmob_item (smob); - SCM lines = scm_cons (SCM_BOOL_F,SCM_BOOL_F); - - Direction d = LEFT; vector bs = boxes (me); - do - { - /* todo: the horizon_padding is somewhat arbitrary */ - Skyline l (bs, 0.1, Y_AXIS, d); - index_set_cell (lines, d, l.smobbed_copy ()); - } - while (flip (&d) != LEFT); - - return lines; + /* todo: the horizon_padding is somewhat arbitrary */ + return Skyline_pair (bs, 0.1, Y_AXIS).smobbed_copy (); } diff --git a/lily/skyline.cc b/lily/skyline.cc index ab877f28ce..6b53a62ef8 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -111,6 +111,19 @@ Building::Building (Real start, Real start_height, Real end_height, Real end) precompute (); } +Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky) +{ + Real height = sky * b[other_axis (horizon_axis)][sky]; + + iv_ = b[horizon_axis]; + iv_.widen (horizon_padding + EPS); + height_[LEFT] = height; + height_[RIGHT] = height; + + if (sane ()) + precompute (); +} + void Building::precompute () { @@ -174,6 +187,14 @@ Building::sloped_neighbour (Real horizon_padding, Direction d) const return Building (left, left_height, right_height, right); } +bool +Building::sane () const +{ + return approx_less_than (iv_[LEFT], iv_[RIGHT]) + && !isinf (height_[RIGHT]) + && !isinf (height_[LEFT]); +} + static void skyline_trailing_part (list *sky, Real x) { @@ -341,14 +362,9 @@ Skyline::Skyline (vector const &boxes, Real horizon_padding, Axis horizon_a for (vsize i = 0; i < boxes.size (); i++) { - Interval iv = boxes[i][horizon_axis]; - Real height = sky * boxes[i][other_axis (horizon_axis)][sky]; - - iv.widen (horizon_padding); - if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT])) + Building front (boxes[i], horizon_padding, horizon_axis, sky); + if (front.sane ()) { - iv.widen (EPS); - Building front = Building (iv[LEFT], height, height, iv[RIGHT]); bldgs.push_front (front); if (horizon_padding > 0 && !isinf (front.iv_.length ())) { @@ -362,6 +378,13 @@ Skyline::Skyline (vector const &boxes, Real horizon_padding, Axis horizon_a assert (is_legal_skyline ()); } +Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky) +{ + sky_ = sky; + Building front (b, 0, horizon_axis, sky); + single_skyline (front, horizon_padding, &buildings_); +} + void Skyline::merge (Skyline const &other) { @@ -379,14 +402,9 @@ Skyline::insert (Box const &b, Real horizon_padding, Axis a) { list other_bld; list my_bld; - Interval iv = b[a]; - Real height = sky_ * b[other_axis (a)][sky_]; - - assert (!iv.is_empty ()); - iv.widen (EPS); my_bld.splice (my_bld.begin (), buildings_); - single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), horizon_padding, &other_bld); + single_skyline (Building (b, 0, a, sky_), horizon_padding, &other_bld); internal_merge_skyline (&other_bld, &my_bld, &buildings_); assert (is_legal_skyline ()); } @@ -404,6 +422,17 @@ Skyline::raise (Real r) assert (is_legal_skyline ()); } +void +Skyline::shift (Real r) +{ + list::iterator end = buildings_.end (); + for (list::iterator i = buildings_.begin (); i != end; i++) + { + i->iv_[LEFT] += r; + i->iv_[RIGHT] += r; + } +} + Real Skyline::distance (Skyline const &other) const { @@ -476,6 +505,61 @@ Skyline::to_points () const return out; } +Skyline_pair::Skyline_pair () + : skylines_ (Skyline (DOWN), Skyline (UP)) +{ +} + +Skyline_pair::Skyline_pair (vector const &boxes, Real padding, Axis a) + : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP)) +{ +} + +Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a) + : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP)) +{ +} + +void +Skyline_pair::raise (Real r) +{ + skylines_[UP].raise (r); + skylines_[DOWN].raise (r); +} + +void +Skyline_pair::shift (Real r) +{ + skylines_[UP].shift (r); + skylines_[DOWN].shift (r); +} + +void +Skyline_pair::insert (Box const &b, Real padding, Axis a) +{ + skylines_[UP].insert (b, padding, a); + skylines_[DOWN].insert (b, padding, a); +} + +void +Skyline_pair::merge (Skyline_pair const &other) +{ + skylines_[UP].merge (other[UP]); + skylines_[DOWN].merge (other[DOWN]); +} + +Skyline& +Skyline_pair::operator [] (Direction d) +{ + return skylines_[d]; +} + +Skyline const& +Skyline_pair::operator [] (Direction d) const +{ + return skylines_[d]; +} + /****************************************************************/ @@ -483,6 +567,10 @@ IMPLEMENT_SIMPLE_SMOBS (Skyline); IMPLEMENT_TYPE_P (Skyline, "ly:skyline?"); IMPLEMENT_DEFAULT_EQUAL_P (Skyline); +IMPLEMENT_SIMPLE_SMOBS (Skyline_pair); +IMPLEMENT_TYPE_P (Skyline_pair, "ly:skyline-pair?"); +IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair); + SCM Skyline::mark_smob (SCM) { @@ -499,3 +587,19 @@ Skyline::print_smob (SCM s, SCM port, scm_print_state *) return 1; } + +SCM +Skyline_pair::mark_smob (SCM) +{ + return SCM_EOL; +} + +int +Skyline_pair::print_smob (SCM s, SCM port, scm_print_state *) +{ + Skyline_pair *r = (Skyline_pair *) SCM_CELL_WORD_1 (s); + (void) r; + + scm_puts ("#", port); + return 1; +} diff --git a/scm/define-grob-properties.scm b/scm/define-grob-properties.scm index d0364bf495..140cf382b7 100644 --- a/scm/define-grob-properties.scm +++ b/scm/define-grob-properties.scm @@ -348,7 +348,7 @@ note that starts here.") object.") (side-axis ,number? "If the value is #X (or equivalently 1), the object is placed horizontally next to the other object. If the value is #Y or 0, it is placed vertically.") (size ,number? "Size of object, relative to standard size.") - (skylines ,pair? "A pair of lists of (x height) pairs.") + (skylines ,ly:skyline-pair? "Two skylines, one above and one below this grob (or, for some grobs, to the left and to the right).") (slope ,number? "The slope of this object.") (slur-padding ,number? "Extra distance between slur and script.") (space-alist ,list? "A table that specifies distances between @@ -562,8 +562,6 @@ than a whole rest.") (spaceable-staves ,ly:grob-array? "Objects to be spaced during page layout.") (skyline-distance ,number? "The distance between this staff and the next one, as determined by a skyline algorithm.") (skyline-horizontal-padding ,number? "For determining the vertical distance between 2 staves, it is possible to have a configuration which would result in a tight interleaving of grobs from the top staff and the bottom staff. The larger this parameter is, the farther apart the staves will be placed in such a configuration.") - (skyline-spacing ,boolean? "When true, this axis-group will vertically space its children -using a skyline algorithm.") ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; diff --git a/scm/define-grobs.scm b/scm/define-grobs.scm index 8b5f3ac5f6..ca3bcd130d 100644 --- a/scm/define-grobs.scm +++ b/scm/define-grobs.scm @@ -1653,7 +1653,7 @@ (axes . (0 1)) (X-extent . ,ly:axis-group-interface::width) (Y-extent . ,ly:axis-group-interface::height) - (skyline-spacing . #t) + (skylines . ,ly:axis-group-interface::calc-skylines) (skyline-horizontal-padding . 1.0) (meta . ((class . System) (interfaces . (system-interface @@ -1974,7 +1974,8 @@ (Y-extent . ,ly:axis-group-interface::height) (X-extent . ,ly:axis-group-interface::width) (stacking-dir . -1) - (padding . 0.1) + (padding . 0.1) + (skylines . ,ly:axis-group-interface::combine-skylines) (meta . ((class . Spanner) (interfaces . (align-interface axis-group-interface)))))) @@ -1984,7 +1985,7 @@ (Y-offset . ,ly:hara-kiri-group-spanner::force-hara-kiri-callback) (Y-extent . ,ly:hara-kiri-group-spanner::y-extent) (X-extent . ,ly:axis-group-interface::width) - (skyline-spacing . #t) + (skylines . ,ly:axis-group-interface::calc-skylines); (meta . ((class . Spanner) (interfaces . (axis-group-interface hara-kiri-group-spanner-interface -- 2.39.5