X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=66cca3fd53a044c96b3b82d85ab42d7a57847ece;hb=47db9a3883d726ca53e2133a3b2298f78dd6a32e;hp=33d2823d47e0d752934558f75ea74e90e85ead41;hpb=0b544cfb7332615ef809b71b57ab656741311ae1;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index 33d2823d47..66cca3fd53 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--2014 Joe Neeman + Copyright (C) 2006--2015 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 @@ -22,8 +22,6 @@ #include #include -#include "ly-smobs.icc" - /* A skyline is a sequence of non-overlapping buildings: something like this: _______ @@ -125,11 +123,11 @@ Building::precompute (Real start, Real start_height, Real end_height, Real end) assert (start_height == end_height); y_intercept_ = start_height; } - else if (fabs(slope_) > 1e6) + else if (fabs (slope_) > 1e6) // too steep to be stored in slope-intercept form, given round-off error { slope_ = 0.0; - y_intercept_ = max(start_height, end_height); + y_intercept_ = max (start_height, end_height); } else y_intercept_ = start_height - slope_ * start; @@ -154,13 +152,6 @@ Building::intersection_x (Building const &other) const return isnan (ret) ? -infinity_f : ret; } -void -Building::leading_part (Real chop) -{ - assert (chop <= end_); - end_ = chop; -} - // Returns a shift s such that (x + s, y) intersects the roof of // this building. If no such shift exists, returns infinity_f. Real @@ -174,50 +165,12 @@ Building::shift_to_intersect (Real x, Real y) const return infinity_f; } -static Real -first_intersection (Building const &b, list *s, Real start_x) -/* Return the first x >= start_x where skyline s above Building b. - * Removes buildings from s that are concealed by b. */ -{ - 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; - - Real i = b.intersection_x (c); - if (i > start_x && i <= b.end_ && i <= c.end_) - return i; - - start_x = c.end_; - if (b.end_ > c.end_) - s->pop_front (); - } - return b.end_; -} - bool -Building::conceals (Building const &other, Real x) const +Building::above (Building const &other, Real x) const { - if (slope_ == other.slope_) - return y_intercept_ > other.y_intercept_; - - /* their slopes were not equal, so there is an intersection point */ - Real i = intersection_x (other); - return (i <= x && slope_ > other.slope_) - || (i > x && slope_ < other.slope_); + return (isinf (y_intercept_) || isinf (other.y_intercept_) || isinf (x)) + ? y_intercept_ > other.y_intercept_ + : (slope_ - other.slope_) * x + y_intercept_ > other.y_intercept_; } // Remove redundant empty buildings from the skyline. @@ -247,93 +200,80 @@ Skyline::normalize () } 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, +Skyline::internal_merge_skyline (list *sb, list *sc, list *const result) const { - if (s1->empty () || s2->empty ()) + if (sb->empty () || sc->empty ()) { programming_error ("tried to merge an empty skyline"); return; } - Real x = -infinity_f; - Real last_end = -infinity_f; - while (!s1->empty ()) + Building b = sb->front (); + for (; !sc->empty (); sc->pop_front ()) { - if (s2->front ().conceals (s1->front (), x)) - swap (s1, s2); - - Building b = s1->front (); - 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; - } - // first_intersection() removes buildings from s2 if b hides them - Real end = first_intersection (b, s2, x); - if (s2->empty ()) + /* Building b is continuing from the previous pass through the loop. + Building c is newly-considered, and starts no earlier than b started. + The comments draw b as if its roof had zero slope ----. + with dashes where b lies above c. + The roof of c could rise / or fall \ through the roof of b, + or the vertical sides | of c could intersect the roof of b. */ + Building c = sc->front (); + if (b.end_ < c.end_) /* finish with b */ { - b.start_ = last_end; - result->push_back (b); - break; + if (b.end_ <= b.start_) /* we are already finished with b */ + ; + else if (c.above (b, c.start_)) /* -| . | */ + { + Building m (b); + m.end_ = c.start_; + if (m.end_ > m.start_) + result->push_back (m); + if (b.above (c, b.end_)) /* -|\--. */ + { + Building n (c); + n.end_ = b.start_ = b.intersection_x (c); + result->push_back (n); + result->push_back (b); + } + } + else + { + if (c.above (b, b.end_)) /* ---/ . | */ + b.end_ = b.intersection_x (c); + else /* -----. */ + c.start_ = b.end_; + result->push_back (b); + } + /* 'c' continues further, so move it into 'b' for the next pass. */ + b = c; + swap (sb, sc); } - - // Should be (end > x), during ver2.19. end == x happens fairly often, - // and we do not need to keep vertical segments within a skyline. - if (end >= x) + else /* b.end_ > c.end_ so finish with c */ { - b.leading_part (end); - b.start_ = last_end; - last_end = b.end_; - result->push_back (b); + if (c.above (b, c.start_)) /* -| |---. */ + { + Building m (b); + m.end_ = c.start_; + if (m.end_ > m.start_) + result->push_back (m); + if (b.above (c, c.end_)) /* -| \---. */ + c.end_ = b.intersection_x (c); + } + else if (c.above (b, c.end_)) /* ---/|--. */ + { + Building m (b); + c.start_ = m.end_ = b.intersection_x (c); + result->push_back (m); + } + else /* c is completely hidden by b */ + continue; + result->push_back (c); + b.start_ = c.end_; } - - if (end >= s1->front ().end_) - s1->pop_front (); - // Should add during ver2.19 (to avoid an endless loop - // when merging identical skylines with a vertical segment) - // if (end >= s2->front().end_) s2->pop_front(); - - x = end; } + if (b.end_ > b.start_) + result->push_back (b); } static void @@ -862,27 +802,7 @@ Skyline::clear () /****************************************************************/ -IMPLEMENT_SIMPLE_SMOBS (Skyline); -IMPLEMENT_TYPE_P (Skyline, "ly:skyline?"); -IMPLEMENT_DEFAULT_EQUAL_P (Skyline); - -SCM -Skyline::mark_smob (SCM s) -{ - ASSERT_LIVE_IS_ALLOWED (s); - 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; -} +const char Skyline::type_p_name_[] = "ly:skyline?"; MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "") SCM