X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=6c3caab69ebe05b3c223050277576a85e46cae9f;hb=31eac32495c21fc614bdd883dbcc2729de03027f;hp=d508450cba3c80e3b94e361ee06a91628e2f3689;hpb=fb2c53d8b1c06d8b20e92024ed6f9c34a7e11a33;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index d508450cba..6c3caab69e 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -7,15 +7,17 @@ #include "skyline.hh" +#include "ly-smobs.icc" + /* 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. @@ -42,11 +44,45 @@ #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 +{ + for (list::const_iterator i = buildings_.begin (); + i != buildings_.end (); i++) + { + (*i).print (); + } +} + bool Skyline::is_legal_skyline () const { @@ -54,13 +90,11 @@ Skyline::is_legal_skyline () const 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]; + if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT]) + return false; } return last_x == infinity_f; } @@ -68,50 +102,82 @@ Skyline::is_legal_skyline () const Building::Building (Real start, Real start_height, Real end_height, Real end) : iv_ (start, end) { - start_height_ = start_height; - end_height_ = end_height; + height_[LEFT] = start_height; + height_[RIGHT] = end_height; - if (isinf (start_height) || isinf (start) || isinf (end)) - end_height_ = start_height; - else if (isinf (end_height)) - start_height_ = end_height; + if (isinf (start) || isinf (end)) + assert (start_height == end_height); - m_ = (end_height - start_height) / (end - start); - b_ = start_height - m_*start; + precompute (); +} + +void +Building::precompute () +{ + slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length()); + if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */ + slope_ = 0; - if (isinf (start_height) || isinf (start) || isinf (end)) + assert (!isinf (slope_) && !isnan (slope_)); + + if (isinf (iv_[START])) { - m_ = 0; - b_ = start_height; + assert (slope_ == 0); + y_intercept_ = height_[LEFT]; } + else + y_intercept_ = height_[LEFT] - slope_ * iv_[START]; } Real Building::height (Real x) const { if (isinf (x)) - return start_height_; - return m_*x + b_; + return (x > 0) ? height_[RIGHT] : height_[LEFT]; + return slope_*x + y_intercept_; +} + +void +Building::print () const +{ + printf ("X[%f,%f] -> Y[%f,%f]\n", + iv_[LEFT], iv_[RIGHT], + height_[LEFT], height_[RIGHT]); } Real Building::intersection (Building const &other) const { - return (b_ - other.b_) / (other.m_ - m_); + return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); } void Building::leading_part (Real chop) { - assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT])); + assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT])); iv_[RIGHT] = chop; - end_height_ = height (chop); + 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]); @@ -119,73 +185,25 @@ skyline_trailing_part (list *sky, Real x) if (!sky->empty ()) { sky->front ().iv_[LEFT] = x; - sky->front ().start_height_ = sky->front ().height (x); + sky->front ().height_[LEFT] = sky->front ().height (x); } } bool -Building::obstructs (Building const &other) const +Building::conceals_beginning (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 (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT])) + return slope_ > other.slope_; + return height_[LEFT] > other.height_[LEFT]; } - -/* precondition: the building should be visible above the first - building in skyline. The building and the skyline should - start at the same point. - - 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) +bool +Building::conceals (Building const &other) const { - assert (!skyline->front ().obstructs (b)); - while (1) - { - Building other = skyline->front (); - - /* 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; - } - } - - /* 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]; - } + 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 @@ -194,16 +212,35 @@ Skyline::internal_merge_skyline (list *s1, list *s2, { while (!s1->empty ()) { - if (s2->front ().obstructs (s1->front ())) + if (s2->front ().conceals_beginning (s1->front ())) swap (s1, s2); Building b = s1->front (); - Real end = last_visible_point (b, s2); + while (!s2->empty () && b.conceals (s2->front ())) + s2->pop_front (); + if (s2->empty ()) + { + result->push_front (b); + break; + } + + /* 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 (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]); b.leading_part (end); result->push_front (b); skyline_trailing_part (s1, end); + skyline_trailing_part (s2, end); } result->reverse (); } @@ -215,13 +252,24 @@ empty_skyline (list *const ret) } static void -single_skyline (Building const &b, list *const ret) +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], -infinity_f, -infinity_f, infinity_f)); - ret->push_front (b); + ret->push_front (Building (b.iv_[RIGHT], -infinity_f, + -infinity_f, infinity_f)); + if (horizon_padding > 0) + ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT)); + + if (b.iv_[RIGHT] > b.iv_[LEFT]) + ret->push_front (b); + + if (horizon_padding > 0) + ret->push_front (b.sloped_neighbour (horizon_padding, LEFT)); if (!isinf (b.iv_[LEFT])) - ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, b.iv_[LEFT])); + ret->push_front (Building (-infinity_f, -infinity_f, + -infinity_f, b.iv_[LEFT])); } void @@ -236,7 +284,7 @@ Skyline::internal_build_skyline (list *buildings, list *cons } else if (size == 1) { - single_skyline (buildings->front (), result); + single_skyline (buildings->front (), 0, result); return; } @@ -257,7 +305,18 @@ Skyline::internal_build_skyline (list *buildings, list *cons Skyline::Skyline () { sky_ = UP; - empty_skyline (&buildings_); + empty_skyline (&buildings_); +} + +Skyline::Skyline (Skyline const &src) +{ + sky_ = src.sky_; + + for (list::const_iterator i = src.buildings_.begin (); + i != src.buildings_.end (); i++) + { + buildings_.push_back (Building ((*i))); + } } Skyline::Skyline (Direction sky) @@ -266,18 +325,39 @@ Skyline::Skyline (Direction sky) empty_skyline (&buildings_); } -Skyline::Skyline (vector const &boxes, Axis a, Direction sky) +/* + 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 (after they are expanded by + horizon_padding), otherwise they are ignored. + */ +Skyline::Skyline (vector const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky) { list bldgs; sky_ = sky; for (vsize i = 0; i < boxes.size (); i++) { - 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])); + 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])) + { + iv.widen (EPS); + Building front = Building (iv[LEFT], height, height, iv[RIGHT]); + bldgs.push_front (front); + if (horizon_padding > 0) + { + 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 ()); } @@ -295,14 +375,18 @@ 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 (buildings_); + list my_bld; Interval iv = b[a]; Real height = sky_ * b[other_axis (a)][sky_]; - single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld); + 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); internal_merge_skyline (&other_bld, &my_bld, &buildings_); assert (is_legal_skyline ()); } @@ -313,9 +397,9 @@ 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; + i->height_[LEFT] += sky_ * r; + i->height_[RIGHT] += sky_ * r; + i->y_intercept_ += sky_ * r; } assert (is_legal_skyline ()); } @@ -328,18 +412,15 @@ Skyline::distance (Skyline const &other) const list::const_iterator j = other.buildings_.begin (); Real dist = -infinity_f; - for (; i != buildings_.end () && j != other.buildings_.end (); i++) + while (i != buildings_.end () && j != other.buildings_.end ()) { - while (j->iv_[RIGHT] < i->iv_[LEFT]) + Interval iv = intersection (i->iv_, j->iv_); + dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]), + i->height (iv[RIGHT]) + j->height (iv[RIGHT]))); + if (i->iv_[RIGHT] <= j->iv_[RIGHT]) + i++; + else 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; } @@ -352,16 +433,10 @@ Skyline::height (Real airplane) const list::const_iterator i; for (i = buildings_.begin (); i != buildings_.end (); i++) { - if (i->iv_[RIGHT] > airplane) + 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; } @@ -378,8 +453,49 @@ 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_; + s.buildings_.front ().height_[LEFT] = h * sky_; + s.buildings_.front ().height_[RIGHT] = h * sky_; + s.buildings_.front ().y_intercept_ = h * sky_; merge (s); } + + +vector +Skyline::to_points () const +{ + vector out; + + for (list::const_iterator i (buildings_.begin ()); + i != buildings_.end (); i++) + { + 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; +} + +/****************************************************************/ + + +IMPLEMENT_SIMPLE_SMOBS (Skyline); +IMPLEMENT_TYPE_P (Skyline, "ly:skyline?"); +IMPLEMENT_DEFAULT_EQUAL_P (Skyline); + +SCM +Skyline::mark_smob (SCM) +{ + return SCM_EOL; +} + +int +Skyline::print_smob (SCM s, SCM port, scm_print_state *) +{ + Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s); + (void) r; + + scm_puts ("#", port); + + return 1; +}