]> git.donarmstrong.com Git - lilypond.git/blobdiff - lily/skyline.cc
Release: bump Welcome versions.
[lilypond.git] / lily / skyline.cc
index 624334ab7964f695ee0233a3e3832f753589fb38..6ef2069c39b50b0acb7273c06928c3e509cf4729 100644 (file)
@@ -1,7 +1,7 @@
 /*
   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
@@ -22,8 +22,6 @@
 #include <deque>
 #include <cstdio>
 
-#include "ly-smobs.icc"
-
 /* A skyline is a sequence of non-overlapping buildings: something like
    this:
                    _______
@@ -121,90 +119,58 @@ Building::precompute (Real start, Real start_height, Real end_height, Real end)
   assert (!isinf (slope_) && !isnan (slope_));
 
   if (isinf (start))
-    assert (start_height == end_height);
-
-  start_height_ = 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;
 }
 
-// Because of the way slope is calculated as a ratio of usually small
-// differences, its precision is not sufficient for extrapolating
-// significantly from the original interval.  For that reason, we
-// don't store the y0 value that would allow more precalculation by using
-// y = x * slope + y0 
-// rather than
-// y = (x - xstart) * slope + ystart
-
 inline Real
 Building::height (Real x) const
 {
-  return (isinf (x) || isinf (start_)) ? start_height_
-    : slope_ * (x - start_) + start_height_;
+  return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_;
 }
 
 void
 Building::print () const
 {
-  printf ("%f (x - x0) + %f from %f to %f\n", slope_, start_height_, start_, end_);
+  printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_);
 }
 
 inline Real
 Building::intersection_x (Building const &other) const
 {
-  Real ret = start_
-    - (other.start_height_ - start_height_
-       - other.slope_ * (other.start_ - start_))
-    /(other.slope_ - slope_);
-  /* A numerically symmetric version would be
-     x = (x1+x0)/2 - (y1-y0 - (s1+s0)(x1-x0)/2)/(s1-s0)
-   */
+  Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
   return isnan (ret) ? -infinity_f : ret;
 }
 
-void
-Building::leading_part (Real chop)
-{
-  assert (chop <= end_);
-  end_ = chop;
-}
-
-static Real
-first_intersection (Building const &b, list<Building> *const s, Real start_x)
+// Returns a shift s such that (x + s, y) intersects the roof of
+// this building.  If no such shift exists, returns infinity_f.
+Real
+Building::shift_to_intersect (Real x, Real y) const
 {
-  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.start_height_ == -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;
+  // Solve for s: y = (x + s)*m + b
+  Real ret = (y - y_intercept_ - slope_ * x) / slope_;
 
-      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_;
+  if (ret >= start_ && ret <= end_ && !isinf (ret))
+    return ret;
+  return infinity_f;
 }
 
-// conceals returns true if *this is strictly above other at x
-
 bool
-Building::conceals (Building const &other, Real x) const
+Building::above (Building const &other, Real x) const
 {
-  return height (x) > other.height (x);
+  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.
@@ -218,7 +184,7 @@ Skyline::normalize ()
 
   for (i = buildings_.begin (); i != buildings_.end (); i++)
     {
-      if (last_empty && i->start_height_ == -infinity_f)
+      if (last_empty && i->y_intercept_ == -infinity_f)
         {
           list<Building>::iterator last = i;
           last--;
@@ -226,7 +192,7 @@ Skyline::normalize ()
           buildings_.erase (i);
           i = last;
         }
-      last_empty = (i->start_height_ == -infinity_f);
+      last_empty = (i->y_intercept_ == -infinity_f);
     }
 
   assert (buildings_.front ().start_ == -infinity_f);
@@ -234,91 +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<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->start_height_ == -infinity_f)
-        {
-          Real p1 = left->height (left->end_);
-          Real p2 = right->start_height_;
-          *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
 {
-  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.start_height_ == -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_height_ = s1->front ().height (x);
-          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_height_ = b.height (last_end);
-          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_height_ = b.height (last_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
@@ -356,7 +311,7 @@ non_overlapping_skyline (list<Building> *const buildings)
   while (i != buildings->end ())
     {
       Real x1 = i->start_;
-      Real y1 = i->start_height_;
+      Real y1 = i->height (i->start_);
       Real x2 = i->end_;
       Real y2 = i->height (i->end_);
 
@@ -399,7 +354,7 @@ public:
   bool operator () (Building const &b1, Building const &b2)
   {
     return b1.start_ < b2.start_
-           || (b1.start_ == b2.start_ && b1.start_height_ > b2.start_height_);
+           || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_));
   }
 };
 
@@ -455,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<Building>::const_iterator i = src.buildings_.begin ();
-       i != src.buildings_.end (); i++)
-    {
-      buildings_.push_back (Building ((*i)));
-    }
-}
-
 Skyline::Skyline (Direction sky)
 {
   sky_ = sky;
@@ -609,7 +552,7 @@ Skyline::raise (Real r)
 {
   list<Building>::iterator end = buildings_.end ();
   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
-    i->start_height_ += sky_ * r;
+    i->y_intercept_ += sky_ * r;
 }
 
 void
@@ -620,6 +563,7 @@ Skyline::shift (Real s)
     {
       i->start_ += s;
       i->end_ += s;
+      i->y_intercept_ -= s * i->slope_;
     }
 }
 
@@ -664,7 +608,7 @@ Skyline::padded (Real horizon_padding) const
     {
       if (i->start_ > -infinity_f)
         {
-          Real height = i->start_height_;
+          Real height = i->height (i->start_);
           if (height > -infinity_f)
             {
               // Add the sloped building that pads the left side of the current building.
@@ -768,7 +712,7 @@ Skyline::max_height () const
   list<Building>::const_iterator i;
   for (i = buildings_.begin (); i != buildings_.end (); ++i)
     {
-      ret = max (ret, i->start_height_);
+      ret = max (ret, i->height (i->start_));
       ret = max (ret, i->height (i->end_));
     }
 
@@ -786,7 +730,7 @@ Skyline::left () const
 {
   for (list<Building>::const_iterator i (buildings_.begin ());
        i != buildings_.end (); i++)
-    if (i->start_height_ > -infinity_f)
+    if (i->y_intercept_ > -infinity_f)
       return i->start_;
 
   return infinity_f;
@@ -797,7 +741,7 @@ Skyline::right () const
 {
   for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
        i != buildings_.rend (); ++i)
-    if (i->start_height_ > -infinity_f)
+    if (i->y_intercept_ > -infinity_f)
       return i->end_;
 
   return -infinity_f;
@@ -815,7 +759,7 @@ void
 Skyline::set_minimum_height (Real h)
 {
   Skyline s (sky_);
-  s.buildings_.front ().start_height_ = h * sky_;
+  s.buildings_.front ().y_intercept_ = h * sky_;
   merge (s);
 }
 
@@ -846,7 +790,7 @@ Skyline::is_empty () const
   if (!buildings_.size ())
     return true;
   Building b = buildings_.front ();
-  return b.end_ == infinity_f && b.start_height_ == -infinity_f;
+  return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
 }
 
 void
@@ -858,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
@@ -887,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> (skyline_scm);
+  Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 }
 
@@ -905,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> (skyline_scm);
+  Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 }
 
@@ -920,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> (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> (skyline_scm)->max_height_position ());
 }
 
 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
@@ -935,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> (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<Skyline> (sky);
   LY_ASSERT_SMOB (Skyline, sky, 1);
   return scm_from_bool (s->is_empty ());
 }