X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=ab877f28ce605fcb4854984c049885007007c47d;hb=40468a49fc7c96b98f49fb307a6977d0485cf398;hp=36046f19a61061f58accd6c639ebc43d71634824;hpb=99bb6d948373592d482c1517a12f9fdcb74bffc4;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index 36046f19a6..ab877f28ce 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -1,202 +1,501 @@ -/* - skyline.cc -- implement Skyline_entry and funcs. - - source file of the GNU LilyPond music typesetter +/* skyline.cc -- implement the Skyline class - (c) 2002--2005 Han-Wen Nienhuys + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman */ #include "skyline.hh" -/* - A skyline is a shape of the form: +#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. +*/ +#define EPS 1e-10 - * ---- - * | | - * ---------| | - * | | - * | | - * | |______ - * --------| |___ - * +static inline bool +approx_equal (Real x, Real y) +{ + return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0))); +} - This file deals with building such skyline structure, and computing - the minimum distance between two opposing skylines. +static inline bool +approx_greater_than (Real x, Real y) +{ + return x > y + EPS; +} - Invariants for a skyline: +static inline bool +approx_less_than (Real x, Real y) +{ + return x < y - EPS; +} - skyline[...].width_ forms a partition of the real interval, where - the segments are adjacent, and ascending. Hence we have +static inline bool +approx_less_equal (Real x, Real y) +{ + return x <= y + EPS; +} - skyline.top ().width_[RIGHT] = inf - skyline[0].width_[LEFT] = -inf -*/ +static inline bool +approx_greater_equal (Real x, Real y) +{ + return x >= y - EPS; +} -const Real EPS = 1e-12; +void +Skyline::print () const +{ + for (list::const_iterator i = buildings_.begin (); + i != buildings_.end (); i++) + { + (*i).print (); + } +} -/* - TODO: avoid unnecessary fragmentation. +bool +Skyline::is_legal_skyline () const +{ + list::const_iterator i; + Real last_x = -infinity_f; + for (i = buildings_.begin (); i != buildings_.end (); i++) + { + 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; +} + +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) || isinf (end)) + assert (start_height == end_height); + + precompute (); +} - 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) +Building::precompute () { - Interval extent = b[line_axis]; - if (extent.is_empty ()) - return; + slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length()); + if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */ + slope_ = 0; - Real stick_out = b[other_axis (line_axis)][d]; + assert (!isinf (slope_) && !isnan (slope_)); - /* - Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments. - */ - for (int i = line->size (); i--;) + if (isinf (iv_[START])) { - Interval w = line->elem (i).width_; - w.intersect (extent); + assert (slope_ == 0); + y_intercept_ = height_[LEFT]; + } + else + y_intercept_ = height_[LEFT] - slope_ * iv_[START]; +} - if (extent[LEFT] >= w[RIGHT]) - break; +Real +Building::height (Real x) const +{ + if (isinf (x)) + return (x > 0) ? height_[RIGHT] : height_[LEFT]; + return slope_*x + y_intercept_; +} - Real my_height = line->elem (i).height_; +void +Building::print () const +{ + printf ("X[%f,%f] -> Y[%f,%f]\n", + iv_[LEFT], iv_[RIGHT], + height_[LEFT], height_[RIGHT]); +} - if (!w.is_empty () - && 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]); +Real +Building::intersection (Building const &other) const +{ + return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); +} - if (!e3.is_empty () && e3.length () > EPS) - line->insert (Skyline_entry (e3, my_height), i + 1); +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); +} - line->elem_ref (i).height_ = stick_out; - line->elem_ref (i).width_ = w; - if (!e1.is_empty () && e1.length () > EPS) - line->insert (Skyline_entry (e1, my_height), i); - } +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 (approx_equal (x, sky->front ().iv_[RIGHT])) + sky->pop_front (); + else + assert (x < sky->front ().iv_[RIGHT]); + + if (!sky->empty ()) + { + sky->front ().iv_[LEFT] = x; + sky->front ().height_[LEFT] = sky->front ().height (x); } } +bool +Building::conceals_beginning (Building const &other) const +{ + 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 -merge_skyline (Array *a1, - Array const &a2, - Direction dir) +Skyline::internal_merge_skyline (list *s1, list *s2, + list *const result) { - for (int i = 0; i < a2.size (); i++) + while (!s1->empty ()) { - Box b; - b[X_AXIS] = a2[i].width_; - b[Y_AXIS][dir] = a2[i].height_; - b[Y_AXIS][-dir] = dir * infinity_f; + if (s2->front ().conceals_beginning (s1->front ())) + swap (s1, s2); + + Building b = s1->front (); + while (!s2->empty () && b.conceals (s2->front ())) + s2->pop_front (); + if (s2->empty ()) + { + result->push_front (b); + break; + } - insert_extent_into_skyline (a1, b, X_AXIS, dir); + /* 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 (); } -Array -empty_skyline (Direction d) +static void +empty_skyline (list *const ret) { - Array skyline; + ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)); +} - Interval i; - i.set_empty (); - i.swap (); - Skyline_entry e; - e.width_ = i; - e.height_ = -d * infinity_f; - skyline.push (e); - return skyline; +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])); } -Array -extents_to_skyline (Array const &extents, Axis a, Direction d) +void +Skyline::internal_build_skyline (list *buildings, list *const result) { + vsize size = buildings->size (); - Array skyline = empty_skyline (d); + if (size == 0) + { + empty_skyline (result); + return; + } + else if (size == 1) + { + single_skyline (buildings->front (), 0, result); + return; + } - /* - 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).) + list right_half; + list::iterator i = buildings->begin (); - 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); + for (vsize s = 0; s < size/2; s++) + i++; + right_half.splice (right_half.end (), *buildings, i, buildings->end ()); - return skyline; + list right; + list left; + internal_build_skyline (&right_half, &right); + internal_build_skyline (buildings, &left); + internal_merge_skyline (&right, &left, result); } -/* - minimum distance that can be achieved between baselines. "Clouds" is - a skyline pointing down. +Skyline::Skyline () +{ + sky_ = UP; + empty_skyline (&buildings_); +} - This is an O (n) algorithm. -*/ -Real -skyline_meshing_distance (Array const &buildings, - Array const &clouds) +Skyline::Skyline (Skyline const &src) { - int i = buildings.size () -1; - int j = clouds.size () -1; + sky_ = src.sky_; + + for (list::const_iterator i = src.buildings_.begin (); + i != src.buildings_.end (); i++) + { + buildings_.push_back (Building ((*i))); + } +} - Real distance = -infinity_f; +Skyline::Skyline (Direction sky) +{ + sky_ = sky; + empty_skyline (&buildings_); +} - while (i > 0 || j > 0) +/* + 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 w = buildings[i].width_; - w.intersect (clouds[j].width_); + 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 && !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 ()); +} - if (!w.is_empty ()) - distance = max (distance, (buildings[i].height_ - clouds[j].height_)); +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 ()); +} + +void +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_]; + + 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 ()); +} - if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT]) - i--; - else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT]) - j--; +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 ()); +} - return distance; +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; } -Skyline_entry::Skyline_entry () +Real +Skyline::height (Real airplane) const { - height_ = 0.0; + 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; } -Skyline_entry::Skyline_entry (Interval i, Real r) +Real +Skyline::max_height () const { - width_ = i; - height_ = r; + Skyline s (-sky_); + s.set_minimum_height (0); + return sky_ * distance (s); } void -heighten_skyline (Array *buildings, Real ground) +Skyline::set_minimum_height (Real h) { - for (int i = 0; i < buildings->size (); i++) - buildings->elem_ref (i).height_ += ground; + 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); } -Real -skyline_height (Array const &buildings, - Real airplane, - Direction sky_dir) -{ - Real h = - sky_dir * infinity_f; - - /* - Ugh! linear, should be O(log n). - */ - for (int i = 0; i < buildings.size (); i++) - if (buildings[i].width_.contains (airplane)) - h = sky_dir * max (sky_dir * h, - sky_dir * buildings[i].height_); - - return h; + +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; +}