X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=6ef2069c39b50b0acb7273c06928c3e509cf4729;hb=90e4d7057f3857da049dfda3d130017d4719bd6b;hp=5073e69e14b3eaccb805a712e8979be7d9b8856f;hpb=8a1caa214f1d2b517a418fc59fa82a0f3bbe0f19;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index 5073e69e14..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--2012 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,6 +123,12 @@ 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) + // too steep to be stored in slope-intercept form, given round-off error + { + slope_ = 0.0; + y_intercept_ = max (start_height, end_height); + } else y_intercept_ = start_height - slope_ * start; } @@ -148,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 @@ -168,48 +165,12 @@ Building::shift_to_intersect (Real x, Real y) const return infinity_f; } -static Real -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; - - 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. @@ -239,88 +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_) + /* 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 */ { - 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 ()) - { - 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); } - - 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 (); - - x = end; } + if (b.end_ > b.start_) + result->push_back (b); } static void @@ -457,18 +410,6 @@ Skyline::Skyline () empty_skyline (&buildings_); } -Skyline::Skyline (Skyline const &src) -{ - sky_ = src.sky_; - - /* doesn't a list's copy constructor do this? -- jneem */ - for (list::const_iterator i = src.buildings_.begin (); - i != src.buildings_.end (); i++) - { - buildings_.push_back (Building ((*i))); - } -} - Skyline::Skyline (Direction sky) { sky_ = sky; @@ -861,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 * const Skyline::type_p_name_ = "ly:skyline?"; MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "") SCM @@ -890,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)); } @@ -908,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)); } @@ -923,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) @@ -938,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 ()); }