/*
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
#include <deque>
#include <cstdio>
-#include "ly-smobs.icc"
/* A skyline is a sequence of non-overlapping buildings: something like
this:
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_);
/****************************************************************/
-IMPLEMENT_SIMPLE_SMOBS (Skyline);
-IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
-IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
+const char Skyline::type_p_name_[] = "ly:skyline?";
SCM
Skyline::mark_smob (SCM s)
projects / lilypond.git / blobdiff