/*
This file is part of LilyPond, the GNU music typesetter.
- Copyright (C) 2006--2012 Joe Neeman <joeneeman@gmail.com>
+ Copyright (C) 2006--2014 Joe Neeman <joeneeman@gmail.com>
LilyPond is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
This means that the merging routine doesn't need to be aware of direction,
but the distance routine does.
- Be careful about numerical accuracy. When dealing with extremely small values,
- computation errors may arise due to the use of floating point arithmetic.
- For example, if left and right have equal values to start with, in C++
- they may not receive the same value after
-
- left = left*factor + offset;
- right = right*factor + offset;
-
- Which is very unfortunate. Maybe using GCC compiler options to disallow
- extended precision for intermediate results and/or the choice to store
- intermediates with less than full precision would retain some kind of
- deterministic behavior that way.
-
- Anyway, it seems that accepting extremely narrow building in skylines
- doesn't cause accuracy problems to us, so we allow arbitrarily small buildings.
- However, as Keith pointed out, problems may appear if more than one operation
- is done before storing the result, and/or there are different code paths
- for doing the operations to the different ends of an interval.
+ 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
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;
}
}
static Real
-first_intersection (Building const &b, list<Building> *const s, Real start_x)
+first_intersection (Building const &b, list<Building> *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_)
{
last_end = x;
continue;
}
-
+ // first_intersection() removes buildings from s2 if b hides them
Real end = first_intersection (b, s2, x);
if (s2->empty ())
{
break;
}
+ // 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)
{
b.leading_part (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;
}
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);
empty_skyline (&buildings_);
}
-Skyline::Skyline (Skyline const &src)
-{
- sky_ = src.sky_;
-
- /* doesn't a list's copy constructor do this? -- jneem */
- for (list<Building>::const_iterator i = src.buildings_.begin ();
- i != src.buildings_.end (); i++)
- {
- buildings_.push_back (Building ((*i)));
- }
-}
-
Skyline::Skyline (Direction sky)
{
sky_ = 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);
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
}
/* do the same filtering as in Skyline (vector<Box> 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_);
projects / lilypond.git / blobdiff