diff --git a/lily/accidental-placement.cc b/lily/accidental-placement.cc index 02f0c52..c943c9c 100644 --- a/lily/accidental-placement.cc +++ b/lily/accidental-placement.cc @@ -110,8 +110,8 @@ Accidental_placement::get_relevant_accid struct Accidental_placement_entry { - vector left_skyline_; - vector right_skyline_; + Skyline left_skyline_; + Skyline right_skyline_; Interval vertical_extent_; vector extents_; vector grobs_; @@ -307,22 +307,16 @@ Accidental_placement::calc_positioning_d for (vsize i = apes.size (); i--;) { Accidental_placement_entry *ape = apes[i]; - ape->left_skyline_ = empty_skyline (LEFT); - ape->right_skyline_ = empty_skyline (RIGHT); for (vsize j = apes[i]->grobs_.size (); j--;) { Grob *a = apes[i]->grobs_[j]; - vector boxes = Accidental_interface::accurate_boxes (a, common); ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ()); - for (vsize j = boxes.size (); j--;) - { - insert_extent_into_skyline (&ape->left_skyline_, boxes[j], Y_AXIS, LEFT); - insert_extent_into_skyline (&ape->right_skyline_, boxes[j], Y_AXIS, RIGHT); - } } + ape->left_skyline_ = Skyline (ape->extents_, Y_AXIS, LEFT); + ape->right_skyline_ = Skyline (ape->extents_, Y_AXIS, RIGHT); } Interval total; @@ -340,16 +334,11 @@ Accidental_placement::calc_positioning_d Accidental_placement_entry *head_ape = new Accidental_placement_entry; common[X_AXIS] = common_refpoint_of_array (heads, common[X_AXIS], X_AXIS); - vector head_skyline (empty_skyline (LEFT)); vector head_extents; for (vsize i = heads.size (); i--;) - { - Box b (heads[i]->extent (common[X_AXIS], X_AXIS), - heads[i]->extent (common[Y_AXIS], Y_AXIS)); - - insert_extent_into_skyline (&head_skyline, b, Y_AXIS, LEFT); - } + head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS), + heads[i]->extent (common[Y_AXIS], Y_AXIS))); vector stems; for (vsize i = 0; i < heads.size (); i++) @@ -364,27 +353,24 @@ Accidental_placement::calc_positioning_d { int very_large = INT_MAX; - Box b (heads[i]->extent (common[X_AXIS], X_AXIS), - heads[i]->pure_height (common[Y_AXIS], 0, very_large)); - - insert_extent_into_skyline (&head_skyline, b, Y_AXIS, LEFT); + head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS), + heads[i]->pure_height (common[Y_AXIS], 0, very_large))); } - - head_ape->left_skyline_ = head_skyline; + + head_ape->left_skyline_ = Skyline (head_extents, Y_AXIS, LEFT); head_ape->offset_ = 0.0; Real padding = robust_scm2double (me->get_property ("padding"), 0.2); - vector left_skyline = head_ape->left_skyline_; - heighten_skyline (&left_skyline, - -robust_scm2double (me->get_property ("right-padding"), 0)); + Skyline left_skyline = head_ape->left_skyline_; + left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0)) +; /* Add accs entries right-to-left. */ for (vsize i = apes.size (); i-- > 0;) { - Real offset - = -skyline_meshing_distance (apes[i]->right_skyline_, left_skyline); + Real offset = -apes[i]->right_skyline_.distance (left_skyline); if (isinf (offset)) offset = (i < apes.size () - 1) ? apes[i + 1]->offset_ : 0.0; else @@ -392,9 +378,9 @@ Accidental_placement::calc_positioning_d apes[i]->offset_ = offset; - vector new_left_skyline = apes[i]->left_skyline_; - heighten_skyline (&new_left_skyline, apes[i]->offset_); - merge_skyline (&new_left_skyline, left_skyline, LEFT); + Skyline new_left_skyline = apes[i]->left_skyline_; + new_left_skyline.raise (apes[i]->offset_); + new_left_skyline.merge (left_skyline); left_skyline = new_left_skyline; } diff --git a/lily/include/skyline.hh b/lily/include/skyline.hh index fc8d3ac..f086969 100644 --- a/lily/include/skyline.hh +++ b/lily/include/skyline.hh @@ -1,41 +1,63 @@ /* - skyline.hh -- declare Skyline_entry and funcbs. + skyline.hh -- declare Skyline class. source file of the GNU LilyPond music typesetter - (c) 2002--2006 Han-Wen Nienhuys + (c) 2006 Joe Neeman */ #ifndef SKYLINE_HH #define SKYLINE_HH -#include "std-vector.hh" +#include +#include "axis.hh" #include "box.hh" +#include "interval.hh" +#include "direction.hh" +#include "std-vector.hh" -struct Skyline_entry +struct Building { - Interval width_; - Real height_; - Skyline_entry (); - Skyline_entry (Interval, Real); + Interval iv_; + Real start_height_; + Real end_height_; + Real m_; + Real b_; + + Building (Real start, Real start_height, Real end_height, Real end); + + Real height (Real x) const; + Real intersection (Building const &other) const; + void leading_part (Real chop); + bool obstructs (Building const &other) const; }; -void -merge_skyline (vector *a1, vector const &a2, - Direction); -void insert_extent_into_skyline (vector *line, Box b, Axis line_axis, - Direction d); -vector -extents_to_skyline (vector const &extents, Axis a, Direction d); -vector empty_skyline (Direction d); -void heighten_skyline (vector *buildings, Real ground); -Real -skyline_meshing_distance (vector const &buildings, - vector const &clouds); - -Real -skyline_height (vector const &buildings, - Real airplane, Direction sky_dir); +class Skyline +{ +public: +private: + list buildings_; + Direction sky_; + Real last_visible_point (Building const &b, list *const sky); + void internal_merge_skyline (list*, list*, + list *const result); + void internal_build_skyline (list*, + list *const result); + bool is_legal_skyline () const; + +public: + Skyline (); + Skyline (Direction sky); + Skyline (vector const &bldgs, Axis a, Direction sky); + + void merge (Skyline const &); + void insert (Box const &, Axis); + void raise (Real); + Real distance (Skyline const &) const; + Real height (Real airplane) const; + Real max_height () const; + void set_minimum_height (Real height); +}; #endif /* SKYLINE_HH */ diff --git a/lily/include/system.hh b/lily/include/system.hh index 2fe740f..f10b9b7 100644 --- a/lily/include/system.hh +++ b/lily/include/system.hh @@ -11,6 +11,7 @@ #define SYSTEM_HH #include "column-x-positions.hh" #include "spanner.hh" #include "grob-array.hh" +#include "skyline.hh" /* If you keep following offset reference points, you will always end @@ -21,6 +22,8 @@ class System : public Spanner { int rank_; Grob_array *all_elements_; + Drul_array skylines_; + void build_skylines (); void init_elements (); friend class Paper_score; // ugh. Paper_score *pscore_; // ugh. diff --git a/lily/include/tie-column-format.hh b/lily/include/tie-column-format.hh index 1c82c42..3206e32 100644 --- a/lily/include/tie-column-format.hh +++ b/lily/include/tie-column-format.hh @@ -13,7 +13,7 @@ #define TIE_COLUMN_FORMAT_HH #include "lily-proto.hh" #include "tie-configuration.hh" -void set_chord_outline (vector *skyline, +void set_chord_outline (Skyline *skyline, vector bounds, Grob *common, Direction d); @@ -25,7 +25,7 @@ void final_shape_adjustment (Tie_configu Tie_formatting_problem const&, Grob *staff_referencer); void -set_chord_outlines (Drul_array< vector > *skyline_drul, +set_chord_outlines (Drul_array *skyline_drul, vector ties, Grob *common); diff --git a/lily/include/tie-formatting-problem.hh b/lily/include/tie-formatting-problem.hh index 5d46129..7d48995 100644 --- a/lily/include/tie-formatting-problem.hh +++ b/lily/include/tie-formatting-problem.hh @@ -47,7 +47,7 @@ struct Tie_configuration_variation Tie_configuration_variation (); }; -typedef map < Tuple, vector > Chord_outline_map; +typedef map < Tuple, Skyline> Chord_outline_map; typedef map < Tuple, Box> Column_extent_map; class Tie_formatting_problem { diff --git a/lily/skyline.cc b/lily/skyline.cc index f72ea5b..d508450 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -1,202 +1,385 @@ -/* - skyline.cc -- implement Skyline_entry and funcs. +/* skyline.cc -- implement the Skyline class - source file of the GNU LilyPond music typesetter - - (c) 2002--2006 Han-Wen Nienhuys + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman */ #include "skyline.hh" -/* - A skyline is a shape of the form: +/* A skyline is a sequence of non-overlapping buildings: something like + this: + _________ + | | ________ + | | _________| | + /| | \ | | + / |------- \ | | + / \ | | + / --------------- ------- + -- + Each building has a starting position, and ending position, a starting + height and an ending height. + + The following invariants are observed: + - the start of the first building is at -infinity + - the end of the last building is at infinity + - if a building has infinite length (ie. the first and last buildings), + then its starting height and ending height are equal + - the end of one building is the same as the beginning of the next + building + + We also allow skylines to point down (the structure is exactly the same, + but we think of the part above the line as being filled with mass and the + part below as being empty). ::distance finds the minimum distance between + an UP skyline and a DOWN skyline. + + Note that we store DOWN skylines upside-down. That is, in order to compare + a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first. + This means that the merging routine doesn't need to be aware of direction, + but the distance routine does. +*/ +#define EPS 1e-10 - * ---- - * | | - * ---------| | - * | | - * | | - * | |______ - * --------| |___ - * +static inline bool +equal (Real x, Real y) +{ + return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0))); +} - This file deals with building such skyline structure, and computing - the minimum distance between two opposing skylines. +bool +Skyline::is_legal_skyline () const +{ + list::const_iterator i; + Real last_x = -infinity_f; + for (i = buildings_.begin (); i != buildings_.end (); i++) + { + if (isinf (i->start_height_) != isinf (i->end_height_)) + return false; + if (i->iv_[LEFT] != last_x) + return false; + if (isinf (i->iv_.length ()) && i->start_height_ != i->end_height_) + return false; + last_x = i->iv_[RIGHT]; + } + return last_x == infinity_f; +} - Invariants for a skyline: +Building::Building (Real start, Real start_height, Real end_height, Real end) + : iv_ (start, end) +{ + start_height_ = start_height; + end_height_ = end_height; - skyline[...].width_ forms a partition of the real interval, where - the segments are adjacent, and ascending. Hence we have + if (isinf (start_height) || isinf (start) || isinf (end)) + end_height_ = start_height; + else if (isinf (end_height)) + start_height_ = end_height; - skyline.back ().width_[RIGHT] = inf - skyline[0].width_[LEFT] = -inf -*/ + m_ = (end_height - start_height) / (end - start); + b_ = start_height - m_*start; -const Real EPS = 1e-12; + if (isinf (start_height) || isinf (start) || isinf (end)) + { + m_ = 0; + b_ = start_height; + } +} -/* - TODO: avoid unnecessary fragmentation. +Real +Building::height (Real x) const +{ + if (isinf (x)) + return start_height_; + return m_*x + b_; +} + +Real +Building::intersection (Building const &other) const +{ + return (b_ - other.b_) / (other.m_ - m_); +} - This is O (n^2), searching and insertion. Could be O (n log n) with - binsearch. -*/ void -insert_extent_into_skyline (vector *line, Box b, Axis line_axis, - Direction d) +Building::leading_part (Real chop) { - Interval extent = b[line_axis]; - if (extent.is_empty ()) - return; + assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT])); + iv_[RIGHT] = chop; + end_height_ = height (chop); +} - Real stick_out = b[other_axis (line_axis)][d]; +static void +skyline_trailing_part (list *sky, Real x) +{ + if (equal (x, sky->front ().iv_[RIGHT])) + sky->pop_front (); + else + assert (x < sky->front ().iv_[RIGHT]); - /* - Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments. - */ - for (vsize i = line->size (); i--;) + if (!sky->empty ()) { - Interval w = line->at (i).width_; - w.intersect (extent); + sky->front ().iv_[LEFT] = x; + sky->front ().start_height_ = sky->front ().height (x); + } +} + +bool +Building::obstructs (Building const &other) const +{ + if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_)) + return m_ > other.m_; + return start_height_ > other.start_height_; +} - if (extent[LEFT] >= w[RIGHT]) - break; - Real my_height = line->at (i).height_; +/* precondition: the building should be visible above the first + building in skyline. The building and the skyline should + start at the same point. - if (!w.is_empty () - && w.length () > EPS - && d * (my_height - stick_out) < 0) - { - Interval e1 (line->at (i).width_[LEFT], extent[LEFT]); - Interval e3 (extent[RIGHT], line->at (i).width_[RIGHT]); + return the point at which the building b is no longer visible, + either because it has ended or because the skyline has risen + above it. Truncate the skyline at that point. +*/ +Real +Skyline::last_visible_point (Building const &b, list *const skyline) +{ + assert (!skyline->front ().obstructs (b)); + while (1) + { + Building other = skyline->front (); - if (!e3.is_empty () && e3.length () > EPS) - line->insert (line->begin () + i + 1, Skyline_entry (e3, my_height)); + /* there are 3 interesting cases: + 1) the roofs intersect within the spans of the buildings */ + Real intersect = b.intersection (other); + if (intersection (b.iv_, other.iv_).contains (intersect)) + { + if (equal (intersect, b.iv_[LEFT])) + { + /* if the buildings have almost the same starting height, we can find + that their intersection "equals" the start point. In this case, we + just skip the intersection. + */ + assert (b.m_ >= other.m_); + } + else + { + skyline_trailing_part (skyline, intersect); + return intersect; + } + } - line->at (i).height_ = stick_out; - line->at (i).width_ = w; - if (!e1.is_empty () && e1.length () > EPS) - line->insert (line->begin () + i, Skyline_entry (e1, my_height)); + /* 2) the first building ends. This is guaranteed to happen before + the skyline becomes empty because it has to end at infinity */ + if (skyline->empty () && !other.iv_.contains (b.iv_[RIGHT])) + assert (0); + if (other.iv_.contains (b.iv_[RIGHT])) + { + skyline_trailing_part (skyline, b.iv_[RIGHT]); + return b.iv_[RIGHT]; } + + assert (!skyline->empty ()); + skyline->pop_front (); + other = skyline->front (); + + /* 3) the next building in the skyline starts above b */ + if (other.start_height_ > b.height (other.iv_[LEFT])) + return other.iv_[LEFT]; } } void -merge_skyline (vector *a1, - vector const &a2, - Direction dir) +Skyline::internal_merge_skyline (list *s1, list *s2, + list *const result) { - for (vsize i = 0; i < a2.size (); i++) + while (!s1->empty ()) { - Box b; - b[X_AXIS] = a2[i].width_; - b[Y_AXIS][dir] = a2[i].height_; - b[Y_AXIS][-dir] = dir * infinity_f; + if (s2->front ().obstructs (s1->front ())) + swap (s1, s2); + + Building b = s1->front (); + Real end = last_visible_point (b, s2); + + b.leading_part (end); + result->push_front (b); - insert_extent_into_skyline (a1, b, X_AXIS, dir); + skyline_trailing_part (s1, end); } + result->reverse (); } -vector -empty_skyline (Direction d) +static void +empty_skyline (list *const ret) { - vector skyline; + ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)); +} - Interval i; - i.set_empty (); - i.swap (); - Skyline_entry e; - e.width_ = i; - e.height_ = -d * infinity_f; - skyline.push_back (e); - return skyline; +static void +single_skyline (Building const &b, list *const ret) +{ + if (!isinf (b.iv_[RIGHT])) + ret->push_front (Building (b.iv_[RIGHT], -infinity_f, -infinity_f, infinity_f)); + ret->push_front (b); + if (!isinf (b.iv_[LEFT])) + ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, b.iv_[LEFT])); } -vector -extents_to_skyline (vector const &extents, Axis a, Direction d) +void +Skyline::internal_build_skyline (list *buildings, list *const result) { + vsize size = buildings->size (); - vector skyline = empty_skyline (d); + if (size == 0) + { + empty_skyline (result); + return; + } + else if (size == 1) + { + single_skyline (buildings->front (), result); + return; + } - /* - This makes a cubic algorithm (array insertion is O (n), - searching the array dumbly is O (n), and for n items, we get O (n^3).) + list right_half; + list::iterator i = buildings->begin (); - We could do a lot better (n log (n), using a balanced tree) but - that seems overkill for now. - */ - for (vsize j = extents.size (); j--;) - insert_extent_into_skyline (&skyline, extents[j], a, d); + for (vsize s = 0; s < size/2; s++) + i++; + right_half.splice (right_half.end (), *buildings, i, buildings->end ()); - return skyline; + list right; + list left; + internal_build_skyline (&right_half, &right); + internal_build_skyline (buildings, &left); + internal_merge_skyline (&right, &left, result); } -/* - minimum distance that can be achieved between baselines. "Clouds" is - a skyline pointing down. +Skyline::Skyline () +{ + sky_ = UP; + empty_skyline (&buildings_); +} - This is an O (n) algorithm. -*/ -Real -skyline_meshing_distance (vector const &buildings, - vector const &clouds) +Skyline::Skyline (Direction sky) { - int i = buildings.size () -1; - int j = clouds.size () -1; + sky_ = sky; + empty_skyline (&buildings_); +} - Real distance = -infinity_f; +Skyline::Skyline (vector const &boxes, Axis a, Direction sky) +{ + list bldgs; + sky_ = sky; - while (i > 0 || j > 0) + for (vsize i = 0; i < boxes.size (); i++) { - Interval w = buildings[i].width_; - w.intersect (clouds[j].width_); - - if (!w.is_empty ()) - distance = max (distance, (buildings[i].height_ - clouds[j].height_)); - - if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT]) - i--; - else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT]) - j--; + Interval iv = boxes[i][a]; + Real height = sky * boxes[i][other_axis (a)][sky]; + if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT])) + bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT])); } - - return distance; + internal_build_skyline (&bldgs, &buildings_); + assert (is_legal_skyline ()); } -Skyline_entry::Skyline_entry () +void +Skyline::merge (Skyline const &other) { - height_ = 0.0; + assert (sky_ == other.sky_); + + list other_bld (other.buildings_); + list my_bld; + my_bld.splice (my_bld.begin (), buildings_); + internal_merge_skyline (&other_bld, &my_bld, &buildings_); + assert (is_legal_skyline ()); } -Skyline_entry::Skyline_entry (Interval i, Real r) +void +Skyline::insert (Box const &b, Axis a) { - width_ = i; - height_ = r; + list other_bld; + list my_bld (buildings_); + Interval iv = b[a]; + Real height = sky_ * b[other_axis (a)][sky_]; + + single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld); + internal_merge_skyline (&other_bld, &my_bld, &buildings_); + assert (is_legal_skyline ()); } void -heighten_skyline (vector *buildings, Real ground) +Skyline::raise (Real r) +{ + list::iterator end = buildings_.end (); + for (list::iterator i = buildings_.begin (); i != end; i++) + { + i->start_height_ += sky_ * r; + i->end_height_ += sky_ * r; + i->b_ += sky_ * r; + } + assert (is_legal_skyline ()); +} + +Real +Skyline::distance (Skyline const &other) const { - for (vsize i = 0; i < buildings->size (); i++) - buildings->at (i).height_ += ground; + assert (sky_ == -other.sky_); + list::const_iterator i = buildings_.begin (); + list::const_iterator j = other.buildings_.begin (); + + Real dist = -infinity_f; + for (; i != buildings_.end () && j != other.buildings_.end (); i++) + { + while (j->iv_[RIGHT] < i->iv_[LEFT]) + j++; + + list::const_iterator k; + for (k = j; k->iv_[LEFT] <= i->iv_[RIGHT] && k != other.buildings_.end (); k++) + { + Interval iv = intersection (i->iv_, k->iv_); + dist = max (dist, max (i->height (iv[LEFT]) + k->height (iv[LEFT]), + i->height (iv[RIGHT]) + k->height (iv[RIGHT]))); + } + } + return dist; } Real -skyline_height (vector const &buildings, - Real airplane, - Direction sky_dir) +Skyline::height (Real airplane) const { - Real h = - sky_dir * infinity_f; + assert (!isinf (airplane)); + + list::const_iterator i; + for (i = buildings_.begin (); i != buildings_.end (); i++) + { + if (i->iv_[RIGHT] > airplane) + return sky_ * i->height (airplane); + if (i->iv_[RIGHT] == airplane) + { + assert (i != buildings_.end ()); + list::const_iterator j = i; + j++; + return sky_ * (max (i->end_height_, j->start_height_)); + } + } + assert (0); + return 0; +} - /* - Ugh! linear, should be O(log n). - */ - for (vsize i = 0; i < buildings.size (); i++) - if (buildings[i].width_.contains (airplane)) - h = sky_dir * max (sky_dir * h, - sky_dir * buildings[i].height_); - - return h; +Real +Skyline::max_height () const +{ + Skyline s (-sky_); + s.set_minimum_height (0); + return sky_ * distance (s); } +void +Skyline::set_minimum_height (Real h) +{ + Skyline s (sky_); + s.buildings_.front ().start_height_ = h*sky_; + s.buildings_.front ().end_height_ = h*sky_; + s.buildings_.front ().b_ = h*sky_; + merge (s); +} diff --git a/lily/system.cc b/lily/system.cc index 0649849..3337a77 100644 --- a/lily/system.cc +++ b/lily/system.cc @@ -186,6 +186,13 @@ System::get_paper_systems () System *system = dynamic_cast (broken_intos_[i]); system->post_processing (); + system->build_skylines (); + if (i > 0) + { + System *prev = dynamic_cast (broken_intos_[i-1]); + Real r = prev->skylines_[DOWN].distance (system->skylines_[UP]); + system->set_property ("skyline-distance", scm_from_double (r)); + } scm_vector_set_x (lines, scm_from_int (i), system->get_paper_system ()); @@ -399,6 +406,7 @@ System::get_paper_system () /* information that the page breaker might need */ Grob *right_bound = this->get_bound (RIGHT); + pl->set_property ("skyline-distance", get_property ("skyline-distance")); pl->set_property ("page-break-permission", right_bound->get_property ("page-break-permission")); pl->set_property ("page-turn-permission", right_bound->get_property ("page-turn-permission")); pl->set_property ("page-break-penalty", right_bound->get_property ("page-break-penalty")); @@ -499,6 +507,25 @@ get_root_system (Grob *me) return dynamic_cast (system_grob); } +void +System::build_skylines () +{ + vector boxes; + for (vsize i = 0; i < all_elements_->size (); i++) + { + Grob *g = all_elements_->grob (i); + if (!unsmob_stencil (g->get_property ("stencil"))) + continue; + + Interval xiv = g->extent (this, X_AXIS); + Interval yiv = g->extent (this, Y_AXIS); + if (!xiv.is_empty () && !yiv.is_empty ()) + boxes.push_back (Box (xiv, yiv)); + } + + skylines_[UP] = Skyline (boxes, X_AXIS, UP); + skylines_[DOWN] = Skyline (boxes, X_AXIS, DOWN); +} ADD_INTERFACE (System, "system-interface", @@ -510,4 +537,5 @@ ADD_INTERFACE (System, "system-interface "columns " "pure-Y-extent " "spaceable-staves " + "skyline-distance " ) diff --git a/lily/tie-formatting-problem.cc b/lily/tie-formatting-problem.cc index d22d54b..bb314a6 100644 --- a/lily/tie-formatting-problem.cc +++ b/lily/tie-formatting-problem.cc @@ -51,7 +51,7 @@ Tie_formatting_problem::get_attachment ( if (i == chord_outlines_.end ()) programming_error ("Can't find chord outline"); else - attachments[d] = skyline_height ((*i).second, y, -d); + attachments[d] = i->second.height (y); } while (flip (&d) != LEFT); @@ -115,28 +115,6 @@ Tie_formatting_problem::set_column_chord } Tuple2 key (column_rank, int (dir)); - - chord_outlines_[key] = empty_skyline (-dir); - - if (bounds[0]->break_status_dir ()) - { - Real x = robust_relative_extent (bounds[0], x_refpoint_, X_AXIS)[-dir]; - chord_outlines_[key].at (0).height_ = x; - } - else - { - Interval x; - for (vsize j = 0; j < head_boxes.size (); j++) - { - x.unite (head_boxes[j][X_AXIS]); - } - - chord_outlines_[key].at (0).height_ = x[dir]; - } - - for (vsize i = 0; i < boxes.size (); i++) - insert_extent_into_skyline (&chord_outlines_[key] , - boxes[i], Y_AXIS, -dir); if (stem && !Stem::is_invisible (stem)) @@ -150,8 +128,8 @@ Tie_formatting_problem::set_column_chord Direction stemdir = get_grob_direction (stem); y.add_point (Stem::head_positions (stem)[-stemdir] * staff_space * .5); - - insert_extent_into_skyline (&chord_outlines_[key], Box (x,y), Y_AXIS, -dir); + + boxes.push_back (Box (x, y)); stem_extents_[key].unite (Box (x,y)); @@ -159,8 +137,7 @@ Tie_formatting_problem::set_column_chord { Box flag_box = Stem::get_translated_flag (stem).extent_box (); flag_box.translate( Offset (x[RIGHT], X_AXIS)); - insert_extent_into_skyline (&chord_outlines_[key], flag_box, - Y_AXIS, -dir); + boxes.push_back (flag_box); } } else if (stem) @@ -176,10 +153,8 @@ Tie_formatting_problem::set_column_chord Interval y_ext; for (vsize j = 0; j < head_boxes.size (); j++) y_ext.unite (head_boxes[j][Y_AXIS]); - - insert_extent_into_skyline (&chord_outlines_[key], - Box (x_ext, y_ext), - Y_AXIS, -dir); + + boxes.push_back (Box (x_ext, y_ext)); } Direction updowndir = DOWN; @@ -197,12 +172,27 @@ Tie_formatting_problem::set_column_chord } if (!x.is_empty ()) - insert_extent_into_skyline (&chord_outlines_[key], - Box (x,y), - Y_AXIS, -dir); + boxes.push_back (Box (x, y)); } while (flip (&updowndir) != DOWN); + chord_outlines_[key] = Skyline (boxes, Y_AXIS, -dir); + if (bounds[0]->break_status_dir ()) + { + Real x = robust_relative_extent (bounds[0], x_refpoint_, X_AXIS)[-dir]; + chord_outlines_[key].set_minimum_height (x); + } + else + { + Interval x; + for (vsize j = 0; j < head_boxes.size (); j++) + { + x.unite (head_boxes[j][X_AXIS]); + } + + chord_outlines_[key].set_minimum_height (x[dir]); + } + head_extents_[key].set_empty (); for (vsize i = 0; i < head_boxes.size (); i++) { @@ -344,22 +334,12 @@ Tie_formatting_problem::from_semi_ties ( set_chord_outline (heads, head_dir); - Real extremal = head_dir * infinity_f; - Tuple2 head_key (column_rank, head_dir); Tuple2 open_key (column_rank, -head_dir); - - for (vsize i = 0; i < chord_outlines_[head_key].size (); i++) - { - extremal = head_dir * min (head_dir * extremal, - head_dir * chord_outlines_[head_key][i].height_); - } + Real extremal = chord_outlines_[head_key].max_height (); - Skyline_entry right_entry; - right_entry.width_.set_full (); - right_entry.height_ = extremal - head_dir * 1.5; - - chord_outlines_[open_key].push_back (right_entry); + chord_outlines_[open_key] = Skyline (head_dir); + chord_outlines_[open_key].set_minimum_height (extremal - head_dir * 1.5); } diff --git a/scm/define-grob-properties.scm b/scm/define-grob-properties.scm index dddcef9..47f0b8c 100644 --- a/scm/define-grob-properties.scm +++ b/scm/define-grob-properties.scm @@ -549,7 +549,7 @@ 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.") ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ancient notation diff --git a/scm/layout-page-layout.scm b/scm/layout-page-layout.scm index e370a17..090ad06 100644 --- a/scm/layout-page-layout.scm +++ b/scm/layout-page-layout.scm @@ -73,9 +73,10 @@ (define (line-minimum-distance line next "Minimum distance between `line' reference position and `next-line' reference position. If next-line is #f, return #f." (and next-line - (max 0 (- (+ (interval-end (paper-system-extent next-line Y)) - (if ignore-padding 0 (line-next-padding line next-line layout))) - (interval-start (paper-system-extent line Y)))))) + (let ((non-skyline-distance (- (interval-end (paper-system-extent next-line Y)) + (interval-start (paper-system-extent line Y))))) + (max 0 (+ (ly:prob-property next-line 'skyline-distance non-skyline-distance) + (if ignore-padding 0 (line-next-padding line next-line layout))))))) (define (line-ideal-distance line next-line layout ignore-padding) "Ideal distance between `line' reference position and `next-line'