X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=ab877f28ce605fcb4854984c049885007007c47d;hb=c60d8fc4b3f31ddb520522ac911359ff1b82138b;hp=ebdc891cdc2c705585944ff372d5717feb8ad696;hpb=c4fd8507a0fe7b527fab21a772ba78194d030624;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index ebdc891cdc..ab877f28ce 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -12,12 +12,12 @@ /* 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. @@ -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,36 @@ 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); +} + +Building +Building::sloped_neighbour (Real horizon_padding, Direction d) const +{ + Real left = iv_[d]; + Real right = iv_[d] + d * horizon_padding; + Real left_height = height_[d]; + Real right_height = height_[d] - horizon_padding; + if (d == LEFT) + { + swap (left, right); + swap (left_height, right_height); + } + return Building (left, left_height, right_height, right); } 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 +190,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,19 +248,28 @@ 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 b, Real horizon_padding, list *const ret) { + b.iv_.widen (horizon_padding); + if (!isinf (b.iv_[RIGHT])) - ret->push_front (Building (b.iv_[RIGHT], b.height_[RIGHT], - -infinity_f, infinity_f, max_slope)); - ret->push_front (b); + ret->push_front (Building (b.iv_[RIGHT], -infinity_f, + -infinity_f, infinity_f)); + if (horizon_padding > 0 && !isinf (b.iv_.length ())) + ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT)); + + if (b.iv_[RIGHT] > b.iv_[LEFT]) + ret->push_front (b); + + if (horizon_padding > 0 && !isinf (b.iv_.length ())) + ret->push_front (b.sloped_neighbour (horizon_padding, LEFT)); 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 @@ -238,7 +284,7 @@ Skyline::internal_build_skyline (list *buildings, list *cons } else if (size == 1) { - single_skyline (buildings->front (), result, max_slope_); + single_skyline (buildings->front (), 0, result); return; } @@ -258,16 +304,12 @@ Skyline::internal_build_skyline (list *buildings, list *cons Skyline::Skyline () { - max_slope_ = 2; sky_ = UP; - empty_skyline (&buildings_); - - + empty_skyline (&buildings_); } Skyline::Skyline (Skyline const &src) { - max_slope_ = src.max_slope_; sky_ = src.sky_; for (list::const_iterator i = src.buildings_.begin (); @@ -279,53 +321,47 @@ Skyline::Skyline (Skyline const &src) Skyline::Skyline (Direction sky) { - max_slope_ = 2; sky_ = sky; empty_skyline (&buildings_); } /* - build skyline from a set of boxes. + build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes + by that amount and add 45-degree sloped boxes to the edges of each box (of + width horizon_padding). That is, the total amount of horizontal expansion is + horizon_padding*4, half of which is sloped and half of which is flat. - Boxes should have fatness in the horizon_axis, otherwise they are ignored. + Boxes should have fatness in the horizon_axis (after they are expanded by + horizon_padding), otherwise they are ignored. */ -Skyline::Skyline (vector const &boxes, Axis horizon_axis, Direction sky) +Skyline::Skyline (vector const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky) { list bldgs; sky_ = sky; - max_slope_ = 2; for (vsize i = 0; i < boxes.size (); i++) { 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_)); + + iv.widen (horizon_padding); + if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT])) + { + iv.widen (EPS); + Building front = Building (iv[LEFT], height, height, iv[RIGHT]); + bldgs.push_front (front); + if (horizon_padding > 0 && !isinf (front.iv_.length ())) + { + bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT)); + bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT)); + } + } } internal_build_skyline (&bldgs, &buildings_); assert (is_legal_skyline ()); } -Skyline::Skyline (vector const &points, Real max_slope, Direction sky) -{ - sky_ = sky; - max_slope_ = max_slope; - - for (vsize i = 1; i < points.size (); i++) - { - 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)); - - } - - assert (is_legal_skyline ()); -} - void Skyline::merge (Skyline const &other) { @@ -339,7 +375,7 @@ Skyline::merge (Skyline const &other) } void -Skyline::insert (Box const &b, Axis a) +Skyline::insert (Box const &b, Real horizon_padding, Axis a) { list other_bld; list my_bld; @@ -347,9 +383,10 @@ Skyline::insert (Box const &b, 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]), horizon_padding, &other_bld); internal_merge_skyline (&other_bld, &my_bld, &buildings_); assert (is_legal_skyline ()); } @@ -362,7 +399,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 ()); } @@ -418,7 +455,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); } @@ -428,17 +465,14 @@ Skyline::to_points () const { vector out; - bool first = true; for (list::const_iterator i (buildings_.begin ()); i != buildings_.end (); i++) { - if (first) - out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).height_[LEFT])); - - first = false; - out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).height_[RIGHT])); + if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT])) + out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT])); + if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT])) + out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT])); } - return out; }