X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=6ef2069c39b50b0acb7273c06928c3e509cf4729;hb=97a0169312a260933246ab224e4f8b0969871dd5;hp=9908c611d59efaea501e94e30c414a7c23ebc705;hpb=6f13ef4a292625c1a9d528ac88aec98071ba6388;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index 9908c611d5..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: _______ @@ -54,6 +52,17 @@ a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first. This means that the merging routine doesn't need to be aware of direction, but the distance routine does. + + From 2007 through 2012, buildings of width less than EPS were discarded, + citing numerical accuracy concerns. We remember that floating point + comparisons of nearly-equal values can be affected by rounding error. + Also, some target machines use the x87 floating point unit, which provides + extended precision for intermediate results held in registers. On this type + of hardware comparisons such as + double c = 1.0/3.0; boolean compare = (c == 1.0/3.0) + could go either way because the 1.0/3.0 is allowed to be kept + higher precision than the variable 'c'. + Alert to these considerations, we now accept buildings of zero-width. */ static void @@ -114,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; } @@ -137,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 @@ -157,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. @@ -228,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; + 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); } - - Real end = first_intersection (b, s2, x); - if (s2->empty ()) + else /* b.end_ > c.end_ so finish with c */ { - b.start_ = last_end; - result->push_back (b); - break; - } - - if (end >= x) - { - 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 @@ -367,7 +331,8 @@ non_overlapping_skyline (list *const buildings) continue; } - if (x1 >= last_end) + // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH) + if (x1 > last_end) result.push_back (Building (last_end, -infinity_f, -infinity_f, x1)); result.push_back (*i); @@ -445,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; @@ -474,7 +427,8 @@ Skyline::Skyline (vector const &boxes, Axis horizon_axis, Direction sky) sky_ = sky; for (vsize i = 0; i < boxes.size (); i++) - if (!boxes[i].is_empty ()) + if (!boxes[i].is_empty (X_AXIS) + && !boxes[i].is_empty (Y_AXIS)) buildings.push_front (Building (boxes[i], horizon_axis, sky)); buildings_ = internal_build_skyline (&buildings); @@ -541,9 +495,12 @@ Skyline::Skyline (vector const &skypairs, Direction sky) Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) { sky_ = sky; - Building front (b, horizon_axis, sky); - single_skyline (front, &buildings_); - normalize (); + if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS)) + { + Building front (b, horizon_axis, sky); + single_skyline (front, &buildings_); + normalize (); + } } void @@ -581,7 +538,7 @@ Skyline::insert (Box const &b, Axis a) } /* do the same filtering as in Skyline (vector const&, etc.) */ - if (b.is_empty ()) + if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS)) return; my_bld.splice (my_bld.begin (), buildings_); @@ -845,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 @@ -874,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)); } @@ -892,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)); } @@ -907,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) @@ -922,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 ()); }