From 768509751fd13f169829b61f022cc578609a7add Mon Sep 17 00:00:00 2001 From: Joe Neeman Date: Tue, 12 Dec 2006 10:27:04 +0200 Subject: [PATCH] remove skyline max-slope --- lily/accidental-placement.cc | 6 +- lily/axis-group-interface.cc | 10 +- lily/include/skyline.hh | 20 ++-- lily/separation-item.cc | 5 +- lily/skyline.cc | 164 +++++++++++++++++++-------------- lily/system.cc | 5 +- lily/tie-formatting-problem.cc | 2 +- scm/define-grob-properties.scm | 1 - 8 files changed, 116 insertions(+), 97 deletions(-) diff --git a/lily/accidental-placement.cc b/lily/accidental-placement.cc index bc091cb6af..f8245b0cbf 100644 --- a/lily/accidental-placement.cc +++ b/lily/accidental-placement.cc @@ -340,8 +340,8 @@ Accidental_placement::calc_positioning_done (SCM smob) ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ()); } - ape->left_skyline_ = Skyline (ape->extents_, 4, Y_AXIS, LEFT); - ape->right_skyline_ = Skyline (ape->extents_, 4, Y_AXIS, RIGHT); + ape->left_skyline_ = Skyline (ape->extents_, Y_AXIS, LEFT); + ape->right_skyline_ = Skyline (ape->extents_, Y_AXIS, RIGHT); } Interval total; @@ -373,7 +373,7 @@ Accidental_placement::calc_positioning_done (SCM smob) stems[i]->pure_height (common[Y_AXIS], 0, very_large))); } - head_ape->left_skyline_ = Skyline (head_extents, 4, Y_AXIS, LEFT); + 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); diff --git a/lily/axis-group-interface.cc b/lily/axis-group-interface.cc index 6d7074fe98..7edb236e5e 100644 --- a/lily/axis-group-interface.cc +++ b/lily/axis-group-interface.cc @@ -293,7 +293,6 @@ 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); - Real max_slope = robust_scm2double (me->get_property ("skyline-max-slope"), 4); vsize i = 0; vector boxes; @@ -302,8 +301,8 @@ 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, max_slope, X_AXIS, DOWN), - Skyline (boxes, max_slope, X_AXIS, UP)); + Drul_array skylines (Skyline (boxes, X_AXIS, DOWN), + Skyline (boxes, X_AXIS, UP)); for (; i < elements.size (); i++) { Direction dir = get_grob_direction (elements[i]); @@ -323,7 +322,7 @@ Axis_group_interface::skyline_spacing (Grob *me, vector elements) boxes.clear (); boxes.push_back (b); - Skyline other = Skyline (boxes, max_slope, X_AXIS, -dir); + Skyline other = Skyline (boxes, X_AXIS, -dir); Real padding = robust_scm2double (elements[i]->get_property ("outside-staff-padding"), 0.5); Real dist = skylines[dir].distance (other) + padding; @@ -332,7 +331,7 @@ Axis_group_interface::skyline_spacing (Grob *me, vector elements) b.translate (Offset (0, dir*dist)); elements[i]->translate_axis (dir*dist, Y_AXIS); } - skylines[dir].insert (b, max_slope, X_AXIS); + skylines[dir].insert (b, X_AXIS); } } @@ -345,7 +344,6 @@ ADD_INTERFACE (Axis_group_interface, "elements " "common-refpoint-of-elements " "pure-relevant-elements " - "skyline-max-slope " "skyline-spacing " "cached-pure-extents " ); diff --git a/lily/include/skyline.hh b/lily/include/skyline.hh index de38eae318..464bd58004 100644 --- a/lily/include/skyline.hh +++ b/lily/include/skyline.hh @@ -23,17 +23,18 @@ struct Building Interval iv_; Drul_array height_; - Real zero_height_; + Real y_intercept_; Real slope_; - void precompute (Real max_slope); - Building (Real start, Real start_height, Real end_height, Real end, Real max_slope); + void precompute (); + Building (Real start, Real start_height, Real end_height, Real end); void print () const; Real height (Real x) const; Real intersection (Building const &other) const; - void leading_part (Real chop, Real h); - bool obstructs (Building const &other) const; + void leading_part (Real chop); + bool conceals_beginning (Building const &other) const; + bool conceals (Building const &other) const; }; class Skyline @@ -44,8 +45,7 @@ private: void internal_merge_skyline (list*, list*, list *const result); - void internal_build_skyline (list*, Real max_slope, - list *const result); + void internal_build_skyline (list*, list *const result); bool is_legal_skyline () const; DECLARE_SIMPLE_SMOBS(Skyline); @@ -53,11 +53,11 @@ public: Skyline (); Skyline (Skyline const &src); Skyline (Direction sky); - Skyline (vector const &bldgs, Real max_slope, Axis a, Direction sky); - Skyline (vector const &points, Real max_slope, Direction sky); + Skyline (vector const &bldgs, Axis a, Direction sky); + Skyline (vector const &points, Direction sky); vector to_points () const; void merge (Skyline const &); - void insert (Box const &, Real max_slope, Axis); + void insert (Box const &, Axis); void print () const; void raise (Real); Real distance (Skyline const &) const; diff --git a/lily/separation-item.cc b/lily/separation-item.cc index 03996bae89..a53917f8b2 100644 --- a/lily/separation-item.cc +++ b/lily/separation-item.cc @@ -128,8 +128,7 @@ Separation_item::calc_skylines (SCM smob) vector bs = boxes (me); do { - /* todo: make skyline max-slope configurable? */ - Skyline l (bs, 2, Y_AXIS, d); + Skyline l (bs, Y_AXIS, d); index_set_cell (lines, d, l.smobbed_copy ()); } while (flip (&d) != LEFT); @@ -162,7 +161,7 @@ Separation_item::boxes (Grob *me) continue; Interval y (il->pure_height (ycommon, 0, very_large)); - y.widen (0.01); // fixme + y.widen (0.1); // fixme Box b (il->extent (pc, X_AXIS), y); out.push_back (b); diff --git a/lily/skyline.cc b/lily/skyline.cc index fd8c1357ef..fa028562aa 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -44,11 +44,35 @@ #define EPS 1e-10 static inline bool -equal (Real x, Real y) +approx_equal (Real x, Real y) { return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0))); } +static inline bool +approx_greater_than (Real x, Real y) +{ + return x > y + EPS; +} + +static inline bool +approx_less_than (Real x, Real y) +{ + return x < y - EPS; +} + +static inline bool +approx_less_equal (Real x, Real y) +{ + return x <= y + EPS; +} + +static inline bool +approx_greater_equal (Real x, Real y) +{ + return x >= y - EPS; +} + void Skyline::print () const { @@ -64,60 +88,45 @@ Skyline::is_legal_skyline () const { list::const_iterator i; Real last_x = -infinity_f; - Real last_h = -infinity_f; for (i = buildings_.begin (); i != buildings_.end (); i++) { if (i->iv_[LEFT] != last_x) return false; - if (i != buildings_.begin () && !equal (i->height_[LEFT], last_h)) - return false; last_x = i->iv_[RIGHT]; - last_h = i->height_[RIGHT]; + if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT]) + return false; } return last_x == infinity_f; } -Building::Building (Real start, Real start_height, Real end_height, - Real end, Real max_slope) +Building::Building (Real start, Real start_height, Real end_height, Real end) : iv_ (start, end) { height_[LEFT] = start_height; height_[RIGHT] = end_height; - if (isinf (start)) - assert (isinf (start_height) || start_height == end_height); - if (isinf (end)) - assert (isinf (end_height) || start_height == end_height); + if (isinf (start) || isinf (end)) + assert (start_height == end_height); - precompute (max_slope); + precompute (); } void -Building::precompute (Real max_slope) +Building::precompute () { slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length()); - if (height_[LEFT] == height_[RIGHT]) + if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */ slope_ = 0; - if (isinf (slope_) || isnan (slope_)) - slope_ = max_slope * (height_[LEFT] < height_[RIGHT] ? 1 : -1); - -#if 0 - /* - this check is sensitive to roundoff errors when converting to/from - sequences of points. - */ - assert (abs (slope_) <= max_slope + EPS); -#endif - + + assert (!isinf (slope_) && !isnan (slope_)); + if (isinf (iv_[START])) { - if (isinf (iv_[STOP])) - zero_height_ = height_[LEFT]; - else - zero_height_ = height_[RIGHT] - slope_ * iv_[STOP]; + assert (slope_ == 0); + y_intercept_ = height_[LEFT]; } else - zero_height_ = height_[LEFT] - slope_ * iv_[START]; + y_intercept_ = height_[LEFT] - slope_ * iv_[START]; } Real @@ -125,7 +134,7 @@ Building::height (Real x) const { if (isinf (x)) return (x > 0) ? height_[RIGHT] : height_[LEFT]; - return slope_*x + zero_height_; + return slope_*x + y_intercept_; } void @@ -139,22 +148,21 @@ Building::print () const Real Building::intersection (Building const &other) const { - return (zero_height_ - other.zero_height_) / (other.slope_ - slope_); + return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); } void -Building::leading_part (Real chop, Real h) +Building::leading_part (Real chop) { - assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT])); - assert (equal (h, height (chop))); + assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT])); iv_[RIGHT] = chop; - height_[RIGHT] = h; + height_[RIGHT] = height (chop); } static void skyline_trailing_part (list *sky, Real x) { - if (equal (x, sky->front ().iv_[RIGHT])) + if (approx_equal (x, sky->front ().iv_[RIGHT])) sky->pop_front (); else assert (x < sky->front ().iv_[RIGHT]); @@ -167,42 +175,56 @@ skyline_trailing_part (list *sky, Real x) } bool -Building::obstructs (Building const &other) const +Building::conceals_beginning (Building const &other) const { - if (equal (intersection (other), iv_[LEFT]) || equal (height_[LEFT], other.height_[LEFT])) - return slope_ > other.slope_ || (slope_ == other.slope_ && zero_height_ > other.zero_height_); + if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT])) + return slope_ > other.slope_; return height_[LEFT] > other.height_[LEFT]; } +bool +Building::conceals (Building const &other) const +{ + assert (iv_[LEFT] <= other.iv_[LEFT]); + return (iv_[RIGHT] >= other.iv_[RIGHT]) + && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT]) + && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]); +} + void Skyline::internal_merge_skyline (list *s1, list *s2, list *const result) { while (!s1->empty ()) { - if (s2->front ().obstructs (s1->front ())) + if (s2->front ().conceals_beginning (s1->front ())) swap (s1, s2); Building b = s1->front (); - while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT] - && s2->front ().height_[RIGHT] <= b.height (s2->front ().iv_[RIGHT]) + EPS) + while (!s2->empty () && b.conceals (s2->front ())) s2->pop_front (); + if (s2->empty ()) + { + result->push_front (b); + break; + } - /* the front of s2 either intersects with b or it ends after b */ + /* s2 either intersects with b or it ends after b */ Real end = infinity_f; + Real s2_start_height = s2->front ().height_[LEFT]; Real s2_end_height = s2->front ().height_[RIGHT]; + Real s1_start_height = b.height (s2->front ().iv_[LEFT]); Real s1_end_height = b.height (s2->front ().iv_[RIGHT]); - if (s2_end_height > s1_end_height + EPS) + if (approx_greater_than (s2_start_height, s1_start_height)) + end = s2->front ().iv_[LEFT]; + else if (approx_greater_than (s2_end_height, s1_end_height)) end = b.intersection (s2->front ()); end = min (end, b.iv_[RIGHT]); - Real height = b.height (end); - b.leading_part (end, height); + b.leading_part (end); result->push_front (b); skyline_trailing_part (s1, end); - if (!s1->empty ()) - s1->front ().height_[LEFT] = height; skyline_trailing_part (s2, end); } result->reverse (); @@ -211,24 +233,24 @@ Skyline::internal_merge_skyline (list *s1, list *s2, static void empty_skyline (list *const ret) { - ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0)); + ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)); } static void -single_skyline (Building const &b, list *const ret, Real max_slope) +single_skyline (Building const &b, list *const ret) { if (!isinf (b.iv_[RIGHT])) - ret->push_front (Building (b.iv_[RIGHT], b.height_[RIGHT], - -infinity_f, infinity_f, max_slope)); + ret->push_front (Building (b.iv_[RIGHT], -infinity_f, + -infinity_f, infinity_f)); if (b.iv_[RIGHT] > b.iv_[LEFT]) ret->push_front (b); if (!isinf (b.iv_[LEFT])) ret->push_front (Building (-infinity_f, -infinity_f, - b.height_[LEFT], b.iv_[LEFT], max_slope)); + -infinity_f, b.iv_[LEFT])); } void -Skyline::internal_build_skyline (list *buildings, Real max_slope, list *const result) +Skyline::internal_build_skyline (list *buildings, list *const result) { vsize size = buildings->size (); @@ -239,7 +261,7 @@ Skyline::internal_build_skyline (list *buildings, Real max_slope, list } else if (size == 1) { - single_skyline (buildings->front (), result, max_slope); + single_skyline (buildings->front (), result); return; } @@ -252,8 +274,8 @@ Skyline::internal_build_skyline (list *buildings, Real max_slope, list list right; list left; - internal_build_skyline (&right_half, max_slope, &right); - internal_build_skyline (buildings, max_slope, &left); + internal_build_skyline (&right_half, &right); + internal_build_skyline (buildings, &left); internal_merge_skyline (&right, &left, result); } @@ -285,7 +307,7 @@ Skyline::Skyline (Direction sky) Boxes should have fatness in the horizon_axis, otherwise they are ignored. */ -Skyline::Skyline (vector const &boxes, Real max_slope, Axis horizon_axis, Direction sky) +Skyline::Skyline (vector const &boxes, Axis horizon_axis, Direction sky) { list bldgs; sky_ = sky; @@ -294,16 +316,18 @@ Skyline::Skyline (vector const &boxes, Real max_slope, Axis horizon_axis, D { Interval iv = boxes[i][horizon_axis]; Real height = sky * boxes[i][other_axis (horizon_axis)][sky]; - if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT])) - bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], - max_slope)); + if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT])) + { + iv.widen (EPS); + bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT])); + } } - internal_build_skyline (&bldgs, max_slope, &buildings_); + internal_build_skyline (&bldgs, &buildings_); assert (is_legal_skyline ()); } -Skyline::Skyline (vector const &points, Real max_slope, Direction sky) +Skyline::Skyline (vector const &points, Direction sky) { sky_ = sky; @@ -312,8 +336,7 @@ Skyline::Skyline (vector const &points, Real max_slope, Direction sky) buildings_.push_back (Building (points[i-1][X_AXIS], sky * points[i-1][Y_AXIS], sky * points[i][Y_AXIS], - points[i][X_AXIS], - max_slope)); + points[i][X_AXIS])); } @@ -333,7 +356,7 @@ Skyline::merge (Skyline const &other) } void -Skyline::insert (Box const &b, Real max_slope, Axis a) +Skyline::insert (Box const &b, Axis a) { list other_bld; list my_bld; @@ -341,9 +364,10 @@ Skyline::insert (Box const &b, Real max_slope, Axis 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], max_slope), &other_bld, max_slope); + single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld); internal_merge_skyline (&other_bld, &my_bld, &buildings_); assert (is_legal_skyline ()); } @@ -356,7 +380,7 @@ Skyline::raise (Real r) { i->height_[LEFT] += sky_ * r; i->height_[RIGHT] += sky_ * r; - i->zero_height_ += sky_ * r; + i->y_intercept_ += sky_ * r; } assert (is_legal_skyline ()); } @@ -412,7 +436,7 @@ Skyline::set_minimum_height (Real h) Skyline s (sky_); s.buildings_.front ().height_[LEFT] = h * sky_; s.buildings_.front ().height_[RIGHT] = h * sky_; - s.buildings_.front ().zero_height_ = h * sky_; + s.buildings_.front ().y_intercept_ = h * sky_; merge (s); } diff --git a/lily/system.cc b/lily/system.cc index 4d42bdb171..c4aaca306a 100644 --- a/lily/system.cc +++ b/lily/system.cc @@ -532,9 +532,8 @@ System::build_skylines () boxes.push_back (Box (xiv, yiv)); } - /* todo: make skyline slope configurable? */ - skylines_[UP] = Skyline (boxes, 2, X_AXIS, UP); - skylines_[DOWN] = Skyline (boxes, 2, X_AXIS, DOWN); + skylines_[UP] = Skyline (boxes, X_AXIS, UP); + skylines_[DOWN] = Skyline (boxes, X_AXIS, DOWN); } diff --git a/lily/tie-formatting-problem.cc b/lily/tie-formatting-problem.cc index 60d9e1bc11..9f05c5b807 100644 --- a/lily/tie-formatting-problem.cc +++ b/lily/tie-formatting-problem.cc @@ -175,7 +175,7 @@ Tie_formatting_problem::set_column_chord_outline (vector bounds, } while (flip (&updowndir) != DOWN); - chord_outlines_[key] = Skyline (boxes, 4, Y_AXIS, -dir); + 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]; diff --git a/scm/define-grob-properties.scm b/scm/define-grob-properties.scm index 8184b16f6a..9d0d665b88 100644 --- a/scm/define-grob-properties.scm +++ b/scm/define-grob-properties.scm @@ -557,7 +557,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-max-slope ,number? "The maximum slope of buildings in the skyline used in skyline-spacing. If this is small, grobs will be placed away from the staff is there is another grob within a short horizontal distance (even if there would be no collision). If this is large (100, say), grobs will be placed close to the staff even if it means packing them in tightly horizontally.") (skyline-spacing ,boolean? "When true, this axis-group will vertically space its children using a skyline algorithm.") -- 2.39.5