Build: Fix dependencies for ly-grammar.txt (issue 3577).

[lilypond.git] / lily / skyline.cc

diff --git a/lily/skyline.cc b/lily/skyline.cc
index 3f52d82e9040fd65b104bd98593c034265fbd19d..a4620158661686c997ae058498152ccab811398f 100644 (file)
--- a/lily/skyline.cc
+++ b/lily/skyline.cc
@@ -55,24 +55,16 @@
    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
@@ -133,6 +125,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;
 }
@@ -177,7 +175,9 @@ Building::shift_to_intersect (Real x, Real y) const
 }
 
 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_)
     {
@@ -307,7 +307,7 @@ Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
           last_end = x;
           continue;
         }
-
+      // first_intersection() removes buildings from s2 if b hides them
       Real end = first_intersection (b, s2, x);
       if (s2->empty ())
         {
@@ -316,6 +316,8 @@ Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
           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);
@@ -326,6 +328,9 @@ Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 
       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;
     }
@@ -386,7 +391,8 @@ non_overlapping_skyline (list<Building> *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);
@@ -464,18 +470,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<Building>::const_iterator i = src.buildings_.begin ();
-       i != src.buildings_.end (); i++)
-    {
-      buildings_.push_back (Building ((*i)));
-    }
-}
-
 Skyline::Skyline (Direction sky)
 {
   sky_ = sky;
@@ -493,7 +487,8 @@ Skyline::Skyline (vector<Box> 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);
@@ -560,9 +555,12 @@ Skyline::Skyline (vector<Skyline_pair> 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
@@ -600,7 +598,7 @@ Skyline::insert (Box const &b, Axis a)
     }
 
   /* 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_);