X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=5eedbe25373f39f53da02f671c7b00f6826c5074;hb=1f3b8cf85db24896d7021f8babda94bd48a48ebe;hp=65f267aa176b9e9529e1c49d1549c6dddfa959b9;hpb=7aabfb20c46e0a1de41698ddc6859ccd3a6dea85;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index 65f267aa17..5eedbe2537 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -1,174 +1,696 @@ -/* - skyline.cc -- implement Skyline_entry and funcs. +/* skyline.cc -- implement the Skyline class - source file of the GNU LilyPond music typesetter - - (c) 2002--2003 Han-Wen Nienhuys + source file of the GNU LilyPond music typesetter + + (c) 2006--2007 Joe Neeman */ -#include "skyline.hh" - +#include "skyline.hh" +#include + +#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. + + 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. +*/ /* - A skyline is a shape of the form: + 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. - This file deals with building such skyline structure, and computing - the minimum distance between two opposing skylines. - - - Invariants for a skyline: - skyline[...].width_ forms a partition of the real interval, where - the segments are adjacent, and ascending. Hence we have + * All the messing around with EPS is very fishy. There are no + complicated numerical algorithms involved, so EPS should not be + necessary. + + --hwn - skyline.top().width_[RIGHT] = inf - skyline[0].width_[LEFT] = -inf */ +#define EPS 1e-10 -const Real EPS = 1e-12; +static inline bool +approx_equal (Real x, Real y) +{ + return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0))); +} -/* - TODO: avoid unnecessary fragmentation. +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; +} - This is O(n^2), searching and insertion. Could be O(n log n) with - binsearch. -*/ void -insert_extent_into_skyline (Array *line, Box b, Axis line_axis, - Direction d) +Skyline::print () const { - Interval extent = b[line_axis]; - if (extent.empty_b()) - return; - - Real stick_out = b[other_axis (line_axis)][d]; + for (list::const_iterator i = buildings_.begin (); + i != buildings_.end (); i++) + { + (*i).print (); + } +} - /* - Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments. - */ - for (int i = line->size(); i--;) +bool +is_legal_skyline (list const &buildings) +{ + list::const_iterator i; + Real last_x = -infinity_f; + for (i = buildings.begin (); i != buildings.end (); i++) { - Interval w = line->elem(i).width_; - w.intersect (extent); + if (i->iv_[LEFT] != last_x) + 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; +} - if (extent[LEFT] >= w[RIGHT]) - break; - - Real my_height = line->elem(i).height_; +Building::Building (Real start, Real start_height, Real end_height, Real end) + : iv_ (start, end) +{ + height_[LEFT] = start_height; + height_[RIGHT] = end_height; - if (!w.empty_b () && - w.length() > EPS - && d* (my_height - stick_out) < 0) - { - Interval e1 (line->elem(i).width_[LEFT], extent[LEFT]); - Interval e3 (extent[RIGHT], line->elem(i).width_[RIGHT]); + if (isinf (start) || isinf (end)) + assert (start_height == end_height); - if (!e3.empty_b () && e3.length() > EPS) - line->insert (Skyline_entry (e3, my_height), i+1); + precompute (); +} - line->elem_ref(i).height_ = stick_out; - line->elem_ref(i).width_ = w; - if (!e1.empty_b () && e1.length() > EPS) - line->insert (Skyline_entry (e1, my_height), i ); - } +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 (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; + assert (!isinf (slope_) && !isnan (slope_)); + if (isinf (iv_[START])) + { + 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 (x > 0) ? height_[RIGHT] : height_[LEFT]; + return slope_*x + y_intercept_; +} -Array -empty_skyline (Direction d) +void +Building::print () const { - Array skyline; + printf ("X[%f,%f] -> Y[%f,%f]\n", + iv_[LEFT], iv_[RIGHT], + height_[LEFT], height_[RIGHT]); +} - Interval i; - i.set_empty(); - i.swap(); - Skyline_entry e; - e.width_ = i; - e.height_ = -d * infinity_f; - skyline.push (e); - return skyline; +Real +Building::intersection_x (Building const &other) const +{ + return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); } -Array -extents_to_skyline (Array const &extents, Axis a, Direction d) +void +Building::leading_part (Real chop) { + assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT])); + iv_[RIGHT] = chop; + height_[RIGHT] = height (chop); +} - Array skyline = empty_skyline(d); +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); +} - /* - 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).) +bool +Building::sane () const +{ + return approx_less_than (iv_[LEFT], iv_[RIGHT]) + && !isinf (height_[RIGHT]) + && !isinf (height_[LEFT]); +} - We could do a lot better (n log (n), using a balanced tree) but - that seems overkill for now. - */ - for (int j = extents.size(); j--; ) - insert_extent_into_skyline (&skyline, extents[j], a, d); +static void +skyline_trailing_part (list *sky, Real x) +{ + if (approx_equal (x, sky->front ().iv_[RIGHT])) + sky->pop_front (); + else + assert (x < sky->front ().iv_[RIGHT]); - return skyline; + if (!sky->empty ()) + { + sky->front ().iv_[LEFT] = x; + sky->front ().height_[LEFT] = sky->front ().height (x); + } } +bool +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; +} -/* - minimum distance that can be achieved between baselines. "Clouds" is - a skyline pointing down. - - This is an O(n) algorithm. - */ -Real -skyline_meshing_distance (Array const &buildings, - Array const &clouds) +bool +Building::conceals (Building const &other) const { - int i = buildings.size () -1; - int j = clouds.size() -1; + 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]); +} - Real distance = - infinity_f; - - while (i > 0 || j > 0) +void +Skyline::internal_merge_skyline (list *s1, list *s2, + list *const result) +{ + while (!s1->empty ()) { - Interval w = buildings[i].width_; - w.intersect(clouds[j].width_); - - if (!w.empty_b()) - distance = distance >? (buildings[i].height_ - clouds[j].height_); + if (s2->front ().conceals_beginning (s1->front ())) + swap (s1, s2); - if (i>0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT]) + Building b = s1->front (); + while (!s2->empty () && b.conceals (s2->front ())) + s2->pop_front (); + if (s2->empty ()) { - i--; + result->push_front (b); + break; } - else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT]) + + /* 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_x (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 (); +} + +static void +empty_skyline (list *const ret) +{ + ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)); +} + +static void +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)); + 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, + -infinity_f, b.iv_[LEFT])); +} + +/* 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)) { - j--; - } + 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) + { + list result; + empty_skyline (&result); + return result; + } + else if (size == 1) + { + list result; + single_skyline (buildings->front (), 0, &result); + return result; + } + + deque > partials; + buildings->sort (); + while (!buildings->empty ()) + partials.push_back (non_overlapping_skyline (buildings)); - return distance; + /* 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_entry::Skyline_entry() +Skyline::Skyline () { - height_ = 0.0; + sky_ = UP; + empty_skyline (&buildings_); } -Skyline_entry::Skyline_entry (Interval i, Real r) +Skyline::Skyline (Skyline const &src) { - width_ = i; - height_ = r; + 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) +{ + sky_ = sky; + empty_skyline (&buildings_); +} + +/* + 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++) + { + 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)); + } + } + } + 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 +Skyline::merge (Skyline const &other) +{ + 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 (buildings_)); +} + +void +Skyline::insert (Box const &b, Real horizon_padding, Axis a) +{ + list other_bld; + list my_bld; + + my_bld.splice (my_bld.begin (), buildings_); + single_skyline (Building (b, 0, a, sky_), horizon_padding, &other_bld); + internal_merge_skyline (&other_bld, &my_bld, &buildings_); + assert (is_legal_skyline (buildings_)); +} + +void +Skyline::raise (Real r) +{ + list::iterator end = buildings_.end (); + for (list::iterator i = buildings_.begin (); i != end; i++) + { + 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; + } +} + +Real +Skyline::distance (Skyline const &other) const +{ + assert (sky_ == -other.sky_); + list::const_iterator i = buildings_.begin (); + list::const_iterator j = other.buildings_.begin (); + + Real dist = -infinity_f; + while (i != buildings_.end () && j != other.buildings_.end ()) + { + 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++; + } + return dist; +} + +Real +Skyline::height (Real airplane) const +{ + 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); + } + + assert (0); + return 0; +} + +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 ().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; +} + +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; }