X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=99452189c65f7784678e82c71c7e94ec3fbd9a60;hb=3f8485925e8c879fe4c9ae86acef9804126c3b91;hp=e52a6277d50adfeeb44b6f9369944f8c4a900909;hpb=9115b5f48f2f52110585d575af777f75e86ce64c;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index e52a6277d5..99452189c6 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -2,22 +2,23 @@ source file of the GNU LilyPond music typesetter - (c) 2006 Joe Neeman + (c) 2006--2007 Joe Neeman */ #include "skyline.hh" +#include -#include "line-interface.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. @@ -41,88 +42,189 @@ but the distance routine does. */ +/* + FIXME: + + * Consider to use + + typedef list Skyline; + struct Skyline_point + { + Real x; + Drul_array ys; + }; + + this is a cleaner representation, as it doesn't duplicate the X, and + doesn't need bogus buildings at infinity --hwn. + + + * All the messing around with EPS is very fishy. There are no + complicated numerical algorithms involved, so EPS should not be + necessary. + + --hwn + + + */ + #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 +is_legal_skyline (list const &buildings) { list::const_iterator i; Real last_x = -infinity_f; - Real last_h = -infinity_f; - for (i = buildings_.begin (); i != buildings_.end (); i++) + for (i = buildings.begin (); i != buildings.end (); i++) { if (i->iv_[LEFT] != last_x) return false; - if (i != buildings_.begin () && !equal (i->start_height_, last_h)) - return false; last_x = i->iv_[RIGHT]; - last_h = i->end_height_; + 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) { - start_height_ = start_height; - end_height_ = end_height; + height_[LEFT] = start_height; + height_[RIGHT] = end_height; + + if (isinf (start) || isinf (end)) + assert (start_height == end_height); + + 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 (isinf (start)) - assert (isinf (start_height) || start_height == end_height); - if (isinf (end)) - assert (isinf (end_height) || start_height == end_height); + if (sane ()) + precompute (); +} + +void +Building::precompute () +{ + slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length ()); + if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */ + slope_ = 0; - m_ = (end_height - start_height) / (end - start); - if (start_height == end_height) - m_ = 0; - if (isinf (m_) || isnan (m_)) - m_ = max_slope * (start_height < end_height ? 1 : -1); - assert (abs (m_) <= max_slope); + assert (!isinf (slope_) && !isnan (slope_)); - if (isinf (start)) + if (isinf (iv_[START])) { - if (isinf (end)) - b_ = start_height; - else - b_ = end_height - m_*end; + assert (slope_ == 0); + y_intercept_ = height_[LEFT]; } else - b_ = start_height - m_*start; + y_intercept_ = height_[LEFT] - slope_ * iv_[START]; } Real Building::height (Real x) const { if (isinf (x)) - return (x > 0) ? end_height_ : 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 +Building::intersection_x (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, 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; - end_height_ = 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); +} + +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) { - 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]); @@ -130,16 +232,32 @@ 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 +{ + bool w = false; + Real h = other.height (iv_[LEFT]); + if (approx_equal (height_[LEFT], h)) + w = slope_ > other.slope_; + else if (height_[LEFT] > h) + w = true; + else + w = false; + + return w; +} + +bool +Building::conceals (Building const &other) const { - if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_)) - return m_ > other.m_ || (m_ == other.m_ && b_ > other.b_); - return start_height_ > other.start_height_; + 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 @@ -148,29 +266,34 @@ 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 (); - while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT] - && s2->front ().end_height_ <= 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_end_height = s2->front ().end_height_; + 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) - end = b.intersection (s2->front ()); + 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_x (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 ().start_height_ = height; skyline_trailing_part (s2, end); } result->reverse (); @@ -179,78 +302,164 @@ 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.end_height_, -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.start_height_, b.iv_[LEFT], max_slope)); + ret->push_front (Building (-infinity_f, -infinity_f, + -infinity_f, b.iv_[LEFT])); } -void -Skyline::internal_build_skyline (list *buildings, list *const result) +/* remove a non-overlapping set of buildings from BUILDINGS and build a skyline + out of them */ +static list +non_overlapping_skyline (list *const buildings) +{ + list result; + Real last_end = -infinity_f; + list::iterator i = buildings->begin (); + while (i != buildings->end ()) + { + if (approx_less_than (i->iv_[LEFT], last_end)) + { + i++; + continue; + } + + if (approx_greater_than (i->iv_[LEFT], last_end)) + result.push_back (Building (last_end, -infinity_f, -infinity_f, i->iv_[LEFT])); + else + i->iv_[LEFT] = last_end; + + last_end = i->iv_[RIGHT]; + list::iterator j = i; + i++; + result.splice (result.end (), *buildings, j); + } + if (last_end < infinity_f) + result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f)); + assert (is_legal_skyline (result)); + return result; +} + +list +Skyline::internal_build_skyline (list *buildings) { vsize size = buildings->size (); if (size == 0) { - empty_skyline (result); - return; + list result; + empty_skyline (&result); + return result; } else if (size == 1) { - single_skyline (buildings->front (), result, max_slope_); - return; + list result; + single_skyline (buildings->front (), 0, &result); + return result; } - list right_half; - list::iterator i = buildings->begin (); + deque > partials; + buildings->sort (); + while (!buildings->empty ()) + partials.push_back (non_overlapping_skyline (buildings)); - for (vsize s = 0; s < size/2; s++) - i++; - right_half.splice (right_half.end (), *buildings, i, buildings->end ()); - - list right; - list left; - internal_build_skyline (&right_half, &right); - internal_build_skyline (buildings, &left); - internal_merge_skyline (&right, &left, result); + /* we'd like to say while (partials->size () > 1) but that's O (n). + Instead, we exit in the middle of the loop */ + while (!partials.empty ()) + { + list merged; + list one = partials.front (); + partials.pop_front (); + if (partials.empty ()) + return one; + + list two = partials.front (); + partials.pop_front (); + internal_merge_skyline (&one, &two, &merged); + partials.push_back (merged); + } + assert (0); + return list (); } Skyline::Skyline () { - max_slope_ = 2; 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) { - max_slope_ = 2; sky_ = 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; - max_slope_ = 2; 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], max_slope_)); + Building front (boxes[i], horizon_padding, horizon_axis, sky); + if (front.sane ()) + { + 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 ()); + + buildings_ = internal_build_skyline (&bldgs); + assert (is_legal_skyline (buildings_)); +} + +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 @@ -262,21 +471,19 @@ Skyline::merge (Skyline const &other) list my_bld; my_bld.splice (my_bld.begin (), buildings_); internal_merge_skyline (&other_bld, &my_bld, &buildings_); - assert (is_legal_skyline ()); + assert (is_legal_skyline (buildings_)); } void -Skyline::insert (Box const &b, Axis a) +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_]; 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 (b, 0, a, sky_), horizon_padding, &other_bld); internal_merge_skyline (&other_bld, &my_bld, &buildings_); - assert (is_legal_skyline ()); + assert (is_legal_skyline (buildings_)); } void @@ -285,11 +492,22 @@ 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 (buildings_)); +} + +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; } - assert (is_legal_skyline ()); } Real @@ -324,6 +542,7 @@ Skyline::height (Real airplane) const if (i->iv_[RIGHT] >= airplane) return sky_ * i->height (airplane); } + assert (0); return 0; } @@ -340,25 +559,138 @@ 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); } -Stencil -Skyline::stencil () + +vector +Skyline::to_points () const { - Stencil ret; - for (list::iterator i = buildings_.begin (); i != buildings_.end (); i++) + vector out; + + for (list::const_iterator i (buildings_.begin ()); + i != buildings_.end (); i++) { - if (!isinf (i->iv_.length ())) - { - Stencil line = Line_interface::make_line (0.1, - Offset (i->iv_[LEFT], sky_*i->start_height_), - Offset (i->iv_[RIGHT], sky_*i->end_height_)); - ret.add_stencil (line); - } + 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 ret; + return out; +} + +bool +Skyline::is_empty () const +{ + return buildings_.empty (); +} + +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]); +} + +bool +Skyline_pair::is_empty () const +{ + return skylines_[UP].is_empty () + && skylines_[DOWN].is_empty (); +} + +Skyline& +Skyline_pair::operator [] (Direction d) +{ + return skylines_[d]; +} + +Skyline const& +Skyline_pair::operator [] (Direction d) const +{ + return skylines_[d]; +} + +/****************************************************************/ + + +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) +{ + ASSERT_LIVE_IS_ALLOWED (); + 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; +} + +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; }