X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=6ef2069c39b50b0acb7273c06928c3e509cf4729;hb=97a0169312a260933246ab224e4f8b0969871dd5;hp=c8c6d347f8574351991a13b1d974513133257574;hpb=4c792504d7780b2da43434a9c29d1ec74ea7c6db;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index c8c6d347f8..6ef2069c39 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 @@ -152,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 @@ -172,38 +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 <= x <= b.end) - * where skyline s is clear of Building b. - * Removes buildings from s that are fully concealed by b. */ +bool +Building::above (Building const &other, Real x) const { - for ( ; !s->empty (); s->pop_front ()) - { - Building c = s->front (); - - start_x = max (start_x, c.start_); - if (start_x >= b.end_) - return b.end_; - - // height and intersection_x involve multiplication and - // division. Avoid that, if we can. - if (c.y_intercept_ != -infinity_f) - { - if (c.height (start_x) > b.height (start_x)) - return start_x; - - if (c.height (b.end_) > b.height (b.end_)) - { - Real i = b.intersection_x (c); - if (i <= b.end_ && i <= c.end_) - return max (start_x, i); - } - } - if (c.end_ >= b.end_) - return b.end_; // leave this c on the list s - } - return b.end_; + 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. @@ -233,86 +200,80 @@ Skyline::normalize () } 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 ()) - programming_error ("tried to merge two empty skylines"); - - bool s2_pending = false; - Real last_end = -infinity_f; - while (!s1->empty () && !s2->empty ()) + if (sb->empty () || sc->empty ()) { - Building b = s1->front (); - Building c = s2->front (); - if (s2_pending // the head of s2 starts before the head of s1 - || c.height (last_end) > b.height (last_end)) - { - swap (s1, s2); - swap (b, c); - } - // Now b, the head of s1, starts earlier or lies above s2. - - // 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_ = last_end; - result->splice (result->end (), *s1, s1->begin (), i); - last_end = result->back ().end_; - continue; - } - // first_intersection() removes buildings from s2 if b hides them - Real x = first_intersection (b, s2, last_end); - if (s2->empty ()) - break; - - if (x > last_end) - { - b.leading_part (x); // chops b, leaving the part up to x - b.start_ = last_end; - last_end = b.end_; - result->push_back (b); - } - - b = s1->front (); - c = s2->front (); - if (b.end_ <= c.end_) - { - // Any trailing part of b is concealed by c - s1->pop_front (); - // Consider c next for inclusion in the merged skyline - s2_pending = true; - } - else - { - // the trailing part of c is fully exposed, goes directly to merged - s2->pop_front (); - c.start_ = last_end; - last_end = c.end_; - result->push_back (c); - } + programming_error ("tried to merge an empty skyline"); + return; } - if (last_end < infinity_f) + + Building b = sb->front (); + for (; !sc->empty (); sc->pop_front ()) { - if (!s1->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 */ { - s1->front ().start_ = last_end; - result->splice (result->end (), *s1); + 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); } - else if (!s2->empty ()) + else /* b.end_ > c.end_ so finish with c */ { - s2->front ().start_ = last_end; - result->splice (result->end (), *s2); + 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 (b.end_ > b.start_) + result->push_back (b); } static void @@ -841,7 +802,7 @@ Skyline::clear () /****************************************************************/ -const char Skyline::type_p_name_[] = "ly:skyline?"; +const char * const Skyline::type_p_name_ = "ly:skyline?"; MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "") SCM @@ -850,14 +811,14 @@ Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1); Real horizon_padding = 0; - if (horizon_padding_scm != SCM_UNDEFINED) + if (!SCM_UNBNDP (horizon_padding_scm)) { LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3); horizon_padding = scm_to_double (horizon_padding_scm); } - Skyline *skyline = Skyline::unsmob (skyline_scm); - Skyline *other_skyline = Skyline::unsmob (other_skyline_scm); + Skyline *skyline = unsmob (skyline_scm); + Skyline *other_skyline = unsmob (other_skyline_scm); return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding)); } @@ -868,14 +829,14 @@ Skyline::get_distance (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_paddi LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1); Real horizon_padding = 0; - if (horizon_padding_scm != SCM_UNDEFINED) + if (!SCM_UNBNDP (horizon_padding_scm)) { LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3); horizon_padding = scm_to_double (horizon_padding_scm); } - Skyline *skyline = Skyline::unsmob (skyline_scm); - Skyline *other_skyline = Skyline::unsmob (other_skyline_scm); + Skyline *skyline = unsmob (skyline_scm); + Skyline *other_skyline = unsmob (other_skyline_scm); return scm_from_double (skyline->distance (*other_skyline, horizon_padding)); } @@ -883,14 +844,14 @@ MAKE_SCHEME_CALLBACK (Skyline, get_max_height, 1) SCM Skyline::get_max_height (SCM skyline_scm) { - return scm_from_double (Skyline::unsmob (skyline_scm)->max_height ()); + return scm_from_double (unsmob (skyline_scm)->max_height ()); } MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1) SCM Skyline::get_max_height_position (SCM skyline_scm) { - return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ()); + return scm_from_double (unsmob (skyline_scm)->max_height_position ()); } MAKE_SCHEME_CALLBACK (Skyline, get_height, 2) @@ -898,14 +859,14 @@ SCM Skyline::get_height (SCM skyline_scm, SCM x_scm) { Real x = robust_scm2double (x_scm, 0.0); - return scm_from_double (Skyline::unsmob (skyline_scm)->height (x)); + return scm_from_double (unsmob (skyline_scm)->height (x)); } LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?", 1, 0, 0, (SCM sky), "Return whether @var{sky} is empty.") { - Skyline *s = Skyline::unsmob (sky); + Skyline *s = unsmob (sky); LY_ASSERT_SMOB (Skyline, sky, 1); return scm_from_bool (s->is_empty ()); }