X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=b729e5312b15a56471f9f7b58ca542e0db947281;hb=33aea9c0d161f3ed0166bef403b6daf52d74847a;hp=fa028562aabbf2939ea91345fd3082dd533cea8a;hpb=8dfabc02615ad25d5450cb5f42e194ce50a7be18;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index fa028562aa..b729e5312b 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 "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,6 +42,31 @@ 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 @@ -84,11 +110,11 @@ Skyline::print () const } bool -Skyline::is_legal_skyline () const +is_legal_skyline (list const &buildings) { list::const_iterator i; Real last_x = -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; @@ -111,6 +137,19 @@ Building::Building (Real start, Real start_height, Real end_height, Real end) 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 (sane ()) + precompute (); +} + void Building::precompute () { @@ -146,7 +185,7 @@ Building::print () const } Real -Building::intersection (Building const &other) const +Building::intersection_x (Building const &other) const { return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); } @@ -159,6 +198,29 @@ Building::leading_part (Real 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); +} + +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) { @@ -177,9 +239,16 @@ skyline_trailing_part (list *sky, Real 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 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 @@ -218,7 +287,7 @@ Skyline::internal_merge_skyline (list *s1, list *s2, 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 = b.intersection_x (s2->front ()); end = min (end, b.iv_[RIGHT]); b.leading_part (end); @@ -237,46 +306,98 @@ 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)); + 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])); } -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); - return; + list result; + single_skyline (buildings->front (), 0, &result); + return result; } - list right_half; - list::iterator i = buildings->begin (); - - for (vsize s = 0; s < size/2; s++) - i++; - right_half.splice (right_half.end (), *buildings, i, buildings->end ()); + deque > partials; + buildings->sort (); + while (!buildings->empty ()) + partials.push_back (non_overlapping_skyline (buildings)); - 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 () @@ -303,44 +424,42 @@ Skyline::Skyline (Direction sky) } /* - 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; 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) && !approx_equal (iv[LEFT], iv[RIGHT])) + Building front (boxes[i], horizon_padding, horizon_axis, sky); + if (front.sane ()) { - iv.widen (EPS); - bldgs.push_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 ()); + buildings_ = internal_build_skyline (&bldgs); + assert (is_legal_skyline (buildings_)); } -Skyline::Skyline (vector const &points, Direction sky) +Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky) { sky_ = sky; - - 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])); - - } - - assert (is_legal_skyline ()); + Building front (b, 0, horizon_axis, sky); + single_skyline (front, horizon_padding, &buildings_); } void @@ -352,24 +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_]; - - assert (!iv.is_empty ()); - iv.widen (EPS); my_bld.splice (my_bld.begin (), buildings_); - single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld); + 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 @@ -382,7 +496,18 @@ Skyline::raise (Real r) i->height_[RIGHT] += sky_ * r; i->y_intercept_ += sky_ * r; } - assert (is_legal_skyline ()); + 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 @@ -446,20 +571,72 @@ 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; } +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]); +} + +Skyline& +Skyline_pair::operator [] (Direction d) +{ + return skylines_[d]; +} + +Skyline const& +Skyline_pair::operator [] (Direction d) const +{ + return skylines_[d]; +} + /****************************************************************/ @@ -467,9 +644,14 @@ 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; } @@ -483,3 +665,19 @@ Skyline::print_smob (SCM s, SCM port, scm_print_state *) 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; +}