]> git.donarmstrong.com Git - lilypond.git/blobdiff - lily/skyline.cc
Issue 5167/6: Changes: show \markup xxx = ... \etc assignments
[lilypond.git] / lily / skyline.cc
index 3f52d82e9040fd65b104bd98593c034265fbd19d..6ef2069c39b50b0acb7273c06928c3e509cf4729 100644 (file)
@@ -1,7 +1,7 @@
 /*
   This file is part of LilyPond, the GNU music typesetter.
 
 /*
   This file is part of LilyPond, the GNU music typesetter.
 
-  Copyright (C) 2006--2012 Joe Neeman <joeneeman@gmail.com>
+  Copyright (C) 2006--2015 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
 
   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 <deque>
 #include <cstdio>
 
 #include <deque>
 #include <cstdio>
 
-#include "ly-smobs.icc"
-
 /* A skyline is a sequence of non-overlapping buildings: something like
    this:
                    _______
 /* 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.
 
    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
 */
 
 static void
@@ -133,6 +123,12 @@ Building::precompute (Real start, Real start_height, Real end_height, Real end)
       assert (start_height == end_height);
       y_intercept_ = start_height;
     }
       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;
 }
   else
     y_intercept_ = start_height - slope_ * start;
 }
@@ -156,13 +152,6 @@ Building::intersection_x (Building const &other) const
   return isnan (ret) ? -infinity_f : ret;
 }
 
   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
 // Returns a shift s such that (x + s, y) intersects the roof of
 // this building.  If no such shift exists, returns infinity_f.
 Real
@@ -176,48 +165,12 @@ Building::shift_to_intersect (Real x, Real y) const
   return infinity_f;
 }
 
   return infinity_f;
 }
 
-static Real
-first_intersection (Building const &b, list<Building> *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
 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.
 }
 
 // Remove redundant empty buildings from the skyline.
@@ -247,88 +200,80 @@ Skyline::normalize ()
 }
 
 void
 }
 
 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<Building>::iterator left = buildings_.begin ();
-  list<Building>::iterator center = buildings_.begin ();
-  list<Building>::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<Building> *s1, list<Building> *s2,
+Skyline::internal_merge_skyline (list<Building> *sb, list<Building> *sc,
                                  list<Building> *const result) const
 {
                                  list<Building> *const result) const
 {
-  if (s1->empty () || s2->empty ())
+  if (sb->empty () || sc->empty ())
     {
       programming_error ("tried to merge an empty skyline");
       return;
     }
 
     {
       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<Building>::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
 }
 
 static void
@@ -386,7 +331,8 @@ non_overlapping_skyline (list<Building> *const buildings)
           continue;
         }
 
           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);
         result.push_back (Building (last_end, -infinity_f, -infinity_f, x1));
 
       result.push_back (*i);
@@ -464,18 +410,6 @@ Skyline::Skyline ()
   empty_skyline (&buildings_);
 }
 
   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;
 Skyline::Skyline (Direction sky)
 {
   sky_ = sky;
@@ -493,7 +427,8 @@ Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
   sky_ = sky;
 
   for (vsize i = 0; i < boxes.size (); i++)
   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);
       buildings.push_front (Building (boxes[i], horizon_axis, sky));
 
   buildings_ = internal_build_skyline (&buildings);
@@ -560,9 +495,12 @@ Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky)
 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky)
 {
   sky_ = 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
 }
 
 void
@@ -600,7 +538,7 @@ Skyline::insert (Box const &b, Axis a)
     }
 
   /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
     }
 
   /* 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_);
     return;
 
   my_bld.splice (my_bld.begin (), buildings_);
@@ -864,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 ("#<Skyline>", port);
-
-  return 1;
-}
+const char * const Skyline::type_p_name_ = "ly:skyline?";
 
 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
 SCM
 
 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
 SCM
@@ -893,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;
   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);
     }
 
     {
       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> (skyline_scm);
+  Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 }
 
   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 }
 
@@ -911,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;
   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);
     }
 
     {
       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> (skyline_scm);
+  Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 }
 
   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 }
 
@@ -926,14 +844,14 @@ MAKE_SCHEME_CALLBACK (Skyline, get_max_height, 1)
 SCM
 Skyline::get_max_height (SCM skyline_scm)
 {
 SCM
 Skyline::get_max_height (SCM skyline_scm)
 {
-  return scm_from_double (Skyline::unsmob (skyline_scm)->max_height ());
+  return scm_from_double (unsmob<Skyline> (skyline_scm)->max_height ());
 }
 
 MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1)
 SCM
 Skyline::get_max_height_position (SCM skyline_scm)
 {
 }
 
 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> (skyline_scm)->max_height_position ());
 }
 
 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
 }
 
 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
@@ -941,14 +859,14 @@ SCM
 Skyline::get_height (SCM skyline_scm, SCM x_scm)
 {
   Real x = robust_scm2double (x_scm, 0.0);
 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> (skyline_scm)->height (x));
 }
 
 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
            1, 0, 0, (SCM sky),
            "Return whether @var{sky} is empty.")
 {
 }
 
 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<Skyline> (sky);
   LY_ASSERT_SMOB (Skyline, sky, 1);
   return scm_from_bool (s->is_empty ());
 }
   LY_ASSERT_SMOB (Skyline, sky, 1);
   return scm_from_bool (s->is_empty ());
 }