X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=ed5f390a017bbfdf59ad773c61d7f77fa0570c1b;hb=a713d376200adcb6eda27c8667eceb52116de341;hp=d65e48b573e7eeb4a2be65bc23c946e168ca6ec3;hpb=3ef893f1fe182e9f6cf5841cbff0706789bd3361;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index d65e48b573..ed5f390a01 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -1,7 +1,7 @@ /* This file is part of LilyPond, the GNU music typesetter. - Copyright (C) 2006--2011 Joe Neeman + Copyright (C) 2006--2012 Joe Neeman LilyPond is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -18,6 +18,7 @@ */ #include "skyline.hh" +#include "skyline-pair.hh" #include #include @@ -87,16 +88,18 @@ Building::Building (Real start, Real start_height, Real end_height, Real end) if (isinf (start) || isinf (end)) assert (start_height == end_height); + start_ = start; end_ = end; precompute (start, start_height, end_height, end); } -Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky) +Building::Building (Box const &b, Axis horizon_axis, Direction sky) { - Real start = b[horizon_axis][LEFT] - horizon_padding; - Real end = b[horizon_axis][RIGHT] + horizon_padding; + Real start = b[horizon_axis][LEFT]; + Real end = b[horizon_axis][RIGHT]; Real height = sky * b[other_axis (horizon_axis)][sky]; + start_ = start; end_ = end; precompute (start, height, height, end); } @@ -104,9 +107,9 @@ Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direc void Building::precompute (Real start, Real start_height, Real end_height, Real end) { - slope_ = (end_height - start_height) / (end - start); - if (start_height == end_height) /* if they were both infinite, we would get nan, not 0, from the prev line */ - slope_ = 0; + slope_ = 0.0; /* if they were both infinite, we would get nan, not 0, from the prev line */ + if (start_height != end_height) + slope_ = (end_height - start_height) / (end - start); assert (!isinf (slope_) && !isnan (slope_)); @@ -119,7 +122,7 @@ Building::precompute (Real start, Real start_height, Real end_height, Real end) y_intercept_ = start_height - slope_ * start; } -Real +inline Real Building::height (Real x) const { return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_; @@ -128,10 +131,10 @@ Building::height (Real x) const void Building::print () const { - printf ("%f x + %f ends at %f\n", slope_, y_intercept_, end_); + printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_); } -Real +inline Real Building::intersection_x (Building const &other) const { Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); @@ -145,20 +148,17 @@ Building::leading_part (Real chop) end_ = chop; } -Building -Building::sloped_neighbour (Real start, Real horizon_padding, Direction d) const +// Returns a shift s such that (x + s, y) intersects the roof of +// this building. If no such shift exists, returns infinity_f. +Real +Building::shift_to_intersect (Real x, Real y) const { - Real x = (d == LEFT) ? start : end_; - Real left = x; - Real right = x + d * horizon_padding; - Real left_height = height (x); - Real right_height = left_height - horizon_padding; - if (d == LEFT) - { - swap (left, right); - swap (left_height, right_height); - } - return Building (left, left_height, right_height, right); + // Solve for s: y = (x + s)*m + b + Real ret = (y - y_intercept_ - slope_ * x) / slope_; + + if (ret >= start_ && ret <= end_ && !isinf (ret)) + return ret; + return infinity_f; } static Real @@ -167,6 +167,18 @@ first_intersection (Building const &b, list *const s, Real start_x) while (!s->empty () && start_x < b.end_) { Building c = s->front (); + + // conceals and intersection_x involve multiplication and + // division. Avoid that, if we can. + if (c.y_intercept_ == -infinity_f) + { + if (c.end_ > b.end_) + return b.end_; + start_x = c.end_; + s->pop_front (); + continue; + } + if (c.conceals (b, start_x)) return start_x; @@ -193,9 +205,59 @@ Building::conceals (Building const &other, Real x) const || (i > x && slope_ < other.slope_); } +// Remove redundant empty buildings from the skyline. +// If there are two adjacent empty buildings, they can be +// turned into one. +void +Skyline::normalize () +{ + bool last_empty = false; + list::iterator i; + + for (i = buildings_.begin (); i != buildings_.end (); i++) + { + if (last_empty && i->y_intercept_ == -infinity_f) + { + list::iterator last = i; + last--; + last->end_ = i->end_; + buildings_.erase (i); + i = last; + } + last_empty = (i->y_intercept_ == -infinity_f); + } + + assert (buildings_.front ().start_ == -infinity_f); + assert (buildings_.back ().end_ == infinity_f); +} + +void +Skyline::deholify () +{ + // Since a skyline should always be normalized, we can + // assume that there are never two adjacent empty buildings. + // That is, if center is empty then left and right are not. + list::iterator left = buildings_.begin (); + list::iterator center = buildings_.begin (); + list::iterator right; + + for (right = buildings_.begin (); right != buildings_.end (); right++) + { + if (center != buildings_.begin () && center->y_intercept_ == -infinity_f) + { + Real p1 = left->height (left->end_); + Real p2 = right->height (right->start_); + *center = Building (center->start_, p1, p2, center->end_); + + left = center; + center = right; + } + } +} + void Skyline::internal_merge_skyline (list *s1, list *s2, - list *const result) + list *const result) const { if (s1->empty () || s2->empty ()) { @@ -204,17 +266,38 @@ Skyline::internal_merge_skyline (list *s1, list *s2, } Real x = -infinity_f; + Real last_end = -infinity_f; while (!s1->empty ()) { if (s2->front ().conceals (s1->front (), x)) swap (s1, s2); Building b = s1->front (); - Real end = first_intersection (b, s2, x); + Building c = s2->front (); + // Optimization: if the other skyline is empty at this point, + // we can avoid testing some intersections. Just grab as many + // buildings from s1 as we can, and shove them onto the output. + if (c.y_intercept_ == -infinity_f + && c.end_ >= b.end_) + { + list::iterator i = s1->begin (); + i++; + while (i != s1->end () && i->end_ <= c.end_) + i++; + + s1->front ().start_ = x; + result->splice (result->end (), *s1, s1->begin (), i); + x = result->back ().end_; + last_end = x; + continue; + } + + Real end = first_intersection (b, s2, x); if (s2->empty ()) { - result->push_front (b); + b.start_ = last_end; + result->push_back (b); break; } @@ -222,7 +305,9 @@ Skyline::internal_merge_skyline (list *s1, list *s2, if (end > x + EPS) { b.leading_part (end); - result->push_front (b); + b.start_ = last_end; + last_end = b.end_; + result->push_back (b); } if (end >= s1->front ().end_) @@ -230,7 +315,6 @@ Skyline::internal_merge_skyline (list *s1, list *s2, x = end; } - result->reverse (); } static void @@ -240,89 +324,93 @@ empty_skyline (list *const ret) } /* - Given Building 'b' with starting wall location 'start', extend each side - with a sloped roofline of width 'horizon_padding'; put the skyline in 'ret' + Given Building 'b', build a skyline containing only that building. */ static void -single_skyline (Building b, Real start, Real horizon_padding, list *const ret) +single_skyline (Building b, list *const ret) { - bool sloped_neighbours = horizon_padding > 0 && !isinf (start) && !isinf (b.end_); - if (!isinf (b.end_)) - ret->push_front (Building (b.end_ + horizon_padding, -infinity_f, - -infinity_f, infinity_f)); - if (sloped_neighbours) - ret->push_front (b.sloped_neighbour (start, horizon_padding, RIGHT)); - - if (b.end_ > start + EPS) - ret->push_front (b); - - if (sloped_neighbours) - ret->push_front (b.sloped_neighbour (start, horizon_padding, LEFT)); - - if (!isinf (start)) - ret->push_front (Building (-infinity_f, -infinity_f, - -infinity_f, start - horizon_padding)); + if (b.end_ > b.start_ + EPS) + { + if (b.start_ != -infinity_f) + ret->push_back (Building (-infinity_f, -infinity_f, + -infinity_f, b.start_)); + ret->push_back (b); + if (b.end_ != infinity_f) + ret->push_back (Building (b.end_, -infinity_f, + -infinity_f, infinity_f)); + } + else + { + empty_skyline (ret); + } } /* remove a non-overlapping set of boxes from BOXES and build a skyline out of them */ static list -non_overlapping_skyline (list *const boxes, Real horizon_padding, Axis horizon_axis, Direction sky) +non_overlapping_skyline (list *const buildings) { list result; Real last_end = -infinity_f; - list::iterator i = boxes->begin (); - while (i != boxes->end ()) + Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f); + list::iterator i = buildings->begin (); + while (i != buildings->end ()) { - Interval iv = (*i)[horizon_axis]; + Real x1 = i->start_; + Real y1 = i->height (i->start_); + Real x2 = i->end_; + Real y2 = i->height (i->end_); + + // Drop buildings that will obviously have no effect. + if (last_building.height (x1) >= y1 + && last_building.end_ >= x2 + && last_building.height (x2) >= y2) + { + list::iterator j = i++; + buildings->erase (j); + continue; + } - if (iv[LEFT] - horizon_padding < last_end) + if (x1 < last_end) { i++; continue; } - if (iv[LEFT] - horizon_padding > last_end + EPS) - result.push_front (Building (last_end, -infinity_f, -infinity_f, iv[LEFT] - 2 * horizon_padding)); + if (x1 > last_end + EPS) + result.push_back (Building (last_end, -infinity_f, -infinity_f, x1)); - Building b (*i, horizon_padding, horizon_axis, sky); - bool sloped_neighbours = horizon_padding > 0 && !isinf (iv.length ()); - if (sloped_neighbours) - result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, LEFT)); - result.push_front (b); - if (sloped_neighbours) - result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, RIGHT)); + result.push_back (*i); + last_building = *i; + last_end = i->end_; - list::iterator j = i++; - boxes->erase (j); - last_end = result.front ().end_; + list::iterator j = i++; + buildings->erase (j); } + if (last_end < infinity_f) - result.push_front (Building (last_end, -infinity_f, -infinity_f, infinity_f)); - result.reverse (); + result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f)); return result; } -class LessThanBox +class LessThanBuilding { - Axis a_; - public: - LessThanBox (Axis a) + bool operator () (Building const &b1, Building const &b2) { - a_ = a; - } - - bool operator () (Box const &b1, Box const &b2) - { - return b1[a_][LEFT] < b2[a_][LEFT]; + return b1.start_ < b2.start_ + || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_)); } }; +/** + BUILDINGS is a list of buildings, but they could be overlapping + and in any order. The returned list of buildings is ordered and non-overlapping. +*/ list -Skyline::internal_build_skyline (list *boxes, Real horizon_padding, Axis horizon_axis, Direction sky) +Skyline::internal_build_skyline (list *buildings) const { - vsize size = boxes->size (); + vsize size = buildings->size (); if (size == 0) { @@ -333,16 +421,14 @@ Skyline::internal_build_skyline (list *boxes, Real horizon_padding, Axis ho else if (size == 1) { list result; - single_skyline (Building (boxes->front (), horizon_padding, horizon_axis, sky), - boxes->front ()[horizon_axis][LEFT] - horizon_padding, - horizon_padding, &result); + single_skyline (buildings->front (), &result); return result; } deque > partials; - boxes->sort (LessThanBox (horizon_axis)); - while (!boxes->empty ()) - partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon_axis, sky)); + buildings->sort (LessThanBuilding ()); + while (!buildings->empty ()) + partials.push_back (non_overlapping_skyline (buildings)); /* we'd like to say while (partials->size () > 1) but that's O (n). Instead, we exit in the middle of the loop */ @@ -388,68 +474,89 @@ Skyline::Skyline (Direction sky) } /* - build padded skyline from an existing skyline with padding - added to it. -*/ + Build skyline from a set of boxes. -Skyline::Skyline (Skyline const &src, Real horizon_padding, Axis /*a*/) + Boxes should have fatness in the horizon_axis, otherwise they are ignored. + */ +Skyline::Skyline (vector const &boxes, Axis horizon_axis, Direction sky) { - /* - We extract boxes from the skyline, then build a new skyline from - the boxes. - A box is created for every horizontal portion of the skyline - Because skylines are defined positive, and then inverted if they - are to be down-facing, we create the new skyline in the UP - direction, then give it the down direction if needed. - */ - Real start = -infinity_f; - list boxes; - - // establish a baseline box - // FIXME: This has hardcoded logic, assuming a == X_AXIS! - boxes.push_back (Box (Interval (-infinity_f, infinity_f), - Interval (0, 0))); - list::const_iterator end = src.buildings_.end (); - for (list::const_iterator i = src.buildings_.begin (); i != end; start = i->end_, i++) - if ((i->slope_ == 0) && !isinf (i->y_intercept_)) - boxes.push_back (Box (Interval (start, i->end_), - Interval (-infinity_f, i->y_intercept_))); - buildings_ = internal_build_skyline (&boxes, horizon_padding, X_AXIS, UP); - sky_ = src.sky_; + list buildings; + sky_ = sky; + + Axis vert_axis = other_axis (horizon_axis); + for (vsize i = 0; i < boxes.size (); i++) + { + Interval iv = boxes[i][horizon_axis]; + if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ()) + buildings.push_front (Building (boxes[i], horizon_axis, sky)); + } + + buildings_ = internal_build_skyline (&buildings); + normalize (); } /* - 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. + build skyline from a set of line segments. - Boxes should have fatness in the horizon_axis (after they are expanded by - horizon_padding), otherwise they are ignored. + Buildings should have fatness in the horizon_axis, otherwise they are ignored. */ -Skyline::Skyline (vector const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky) +Skyline::Skyline (vector > const &segments, Axis horizon_axis, Direction sky) { - list filtered_boxes; + list buildings; sky_ = sky; - Axis vert_axis = other_axis (horizon_axis); - for (vsize i = 0; i < boxes.size (); i++) + for (vsize i = 0; i < segments.size (); i++) { - Interval iv = boxes[i][horizon_axis]; - iv.widen (horizon_padding); - if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ()) - filtered_boxes.push_front (boxes[i]); + Drul_array const &seg = segments[i]; + Offset left = seg[LEFT]; + Offset right = seg[RIGHT]; + if (left[horizon_axis] > right[horizon_axis]) + swap (left, right); + + Real x1 = left[horizon_axis]; + Real x2 = right[horizon_axis]; + Real y1 = left[other_axis (horizon_axis)] * sky; + Real y2 = right[other_axis (horizon_axis)] * sky; + + if (x1 + EPS < x2) + buildings.push_back (Building (x1, y1, y2, x2)); + } + + buildings_ = internal_build_skyline (&buildings); + normalize (); +} + +Skyline::Skyline (vector const &skypairs, Direction sky) +{ + sky_ = sky; + + deque partials; + for (vsize i = 0; i < skypairs.size (); i++) + partials.push_back (Skyline ((skypairs[i])[sky])); + + while (partials.size () > 1) + { + Skyline one = partials.front (); + partials.pop_front (); + Skyline two = partials.front (); + partials.pop_front (); + + one.merge (two); + partials.push_back (one); } - buildings_ = internal_build_skyline (&filtered_boxes, horizon_padding, horizon_axis, sky); + if (partials.size ()) + buildings_.swap (partials.front ().buildings_); + else + buildings_.clear (); } -Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky) +Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) { sky_ = sky; - Building front (b, horizon_padding, horizon_axis, sky); - single_skyline (front, b[horizon_axis][LEFT] - horizon_padding, - horizon_padding, &buildings_); + Building front (b, horizon_axis, sky); + single_skyline (front, &buildings_); + normalize (); } void @@ -457,14 +564,24 @@ Skyline::merge (Skyline const &other) { assert (sky_ == other.sky_); + if (other.is_empty ()) + return; + + if (is_empty ()) + { + buildings_ = other.buildings_; + return; + } + list other_bld (other.buildings_); list my_bld; my_bld.splice (my_bld.begin (), buildings_); internal_merge_skyline (&other_bld, &my_bld, &buildings_); + normalize (); } void -Skyline::insert (Box const &b, Real horizon_padding, Axis a) +Skyline::insert (Box const &b, Axis a) { list other_bld; list my_bld; @@ -478,14 +595,13 @@ Skyline::insert (Box const &b, Real horizon_padding, Axis a) /* do the same filtering as in Skyline (vector const&, etc.) */ Interval iv = b[a]; - iv.widen (horizon_padding); if (iv.length () <= EPS || b[other_axis (a)].is_empty ()) return; my_bld.splice (my_bld.begin (), buildings_); - single_skyline (Building (b, horizon_padding, a, sky_), b[a][LEFT] - horizon_padding, - horizon_padding, &other_bld); + single_skyline (Building (b, a, sky_), &other_bld); internal_merge_skyline (&other_bld, &my_bld, &buildings_); + normalize (); } void @@ -502,6 +618,7 @@ Skyline::shift (Real s) list::iterator end = buildings_.end (); for (list::iterator i = buildings_.begin (); i != end; i++) { + i->start_ += s; i->end_ += s; i->y_intercept_ -= s * i->slope_; } @@ -525,32 +642,81 @@ Skyline::touching_point (Skyline const &other, Real horizon_padding) const Real Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *touch_point) const { - assert (sky_ == -other.sky_); + if (horizon_padding == 0.0) + return internal_distance (other, touch_point); + + // Note that it is not necessary to build a padded version of other, + // because the same effect can be achieved just by doubling horizon_padding. + Skyline padded_this = padded (horizon_padding); + return padded_this.internal_distance (other, touch_point); +} - Skyline const *padded_this = this; - Skyline const *padded_other = &other; - bool created_tmp_skylines = false; - - /* - For systems, padding is not added at creation time. Padding is - added to AxisGroup objects when outside-staff objects are added. - Thus, when we want to place systems with horizontal padding, - we do it at distance calculation time. - */ - if (horizon_padding != 0.0) +Skyline +Skyline::padded (Real horizon_padding) const +{ + list pad_buildings; + for (list::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i) { - padded_this = new Skyline (*padded_this, horizon_padding, X_AXIS); - padded_other = new Skyline (*padded_other, horizon_padding, X_AXIS); - created_tmp_skylines = true; + if (i->start_ > -infinity_f) + { + Real height = i->height (i->start_); + if (height > -infinity_f) + { + // Add the sloped building that pads the left side of the current building. + Real start = i->start_ - 2 * horizon_padding; + Real end = i->start_ - horizon_padding; + pad_buildings.push_back (Building (start, height - horizon_padding, height, end)); + + // Add the flat building that pads the left side of the current building. + start = i->start_ - horizon_padding; + end = i->start_; + pad_buildings.push_back (Building (start, height, height, end)); + } + } + + if (i->end_ < infinity_f) + { + Real height = i->height (i->end_); + if (height > -infinity_f) + { + // Add the flat building that pads the right side of the current building. + Real start = i->end_; + Real end = start + horizon_padding; + pad_buildings.push_back (Building (start, height, height, end)); + + // Add the sloped building that pads the right side of the current building. + start = end; + end += horizon_padding; + pad_buildings.push_back (Building (start, height, height - horizon_padding, end)); + } + } } - list::const_iterator i = padded_this->buildings_.begin (); - list::const_iterator j = padded_other->buildings_.begin (); + // The buildings may be overlapping, so resolve that. + list pad_skyline = internal_build_skyline (&pad_buildings); + + // Merge the padding with the original, to make a new skyline. + Skyline padded (sky_); + list my_buildings = buildings_; + padded.buildings_.clear (); + internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_); + padded.normalize (); + + return padded; +} + +Real +Skyline::internal_distance (Skyline const &other, Real *touch_point) const +{ + assert (sky_ == -other.sky_); + + list::const_iterator i = buildings_.begin (); + list::const_iterator j = other.buildings_.begin (); Real dist = -infinity_f; Real start = -infinity_f; Real touch = -infinity_f; - while (i != padded_this->buildings_.end () && j != padded_other->buildings_.end ()) + while (i != buildings_.end () && j != other.buildings_.end ()) { Real end = min (i->end_, j->end_); Real start_dist = i->height (start) + j->height (start); @@ -558,9 +724,9 @@ Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *to dist = max (dist, max (start_dist, end_dist)); if (end_dist == dist) - touch = end; + touch = end; else if (start_dist == dist) - touch = start; + touch = start; if (i->end_ <= j->end_) i++; @@ -569,12 +735,6 @@ Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *to start = end; } - if (created_tmp_skylines) - { - delete padded_this; - delete padded_other; - } - *touch_point = touch; return dist; } @@ -598,9 +758,44 @@ Skyline::height (Real airplane) const Real Skyline::max_height () const { - Skyline s (-sky_); - s.set_minimum_height (0); - return sky_ * distance (s); + Real ret = -infinity_f; + + list::const_iterator i; + for (i = buildings_.begin (); i != buildings_.end (); ++i) + { + ret = max (ret, i->height (i->start_)); + ret = max (ret, i->height (i->end_)); + } + + return sky_ * ret; +} + +Direction +Skyline::direction () const +{ + return sky_; +} + +Real +Skyline::left () const +{ + for (list::const_iterator i (buildings_.begin ()); + i != buildings_.end (); i++) + if (i->y_intercept_ > -infinity_f) + return i->start_; + + return infinity_f; +} + +Real +Skyline::right () const +{ + for (list::const_reverse_iterator i (buildings_.rbegin ()); + i != buildings_.rend (); ++i) + if (i->y_intercept_ > -infinity_f) + return i->end_; + + return -infinity_f; } Real @@ -643,6 +838,8 @@ Skyline::to_points (Axis horizon_axis) const bool Skyline::is_empty () const { + if (!buildings_.size ()) + return true; Building b = buildings_.front (); return b.end_ == infinity_f && b.y_intercept_ == -infinity_f; } @@ -661,9 +858,9 @@ IMPLEMENT_TYPE_P (Skyline, "ly:skyline?"); IMPLEMENT_DEFAULT_EQUAL_P (Skyline); SCM -Skyline::mark_smob (SCM) +Skyline::mark_smob (SCM s) { - ASSERT_LIVE_IS_ALLOWED (); + ASSERT_LIVE_IS_ALLOWED (s); return SCM_EOL; }