lily/skyline.cc

   1 /* skyline.cc -- implement the Skyline class
   2
   3    source file of the GNU LilyPond music typesetter
   4
   5    (c) 2006 Joe Neeman <joeneeman@gmail.com>
   6 */
   7
   8 #include "skyline.hh"
   9
  10 #include "line-interface.hh"
  11
  12 /* A skyline is a sequence of non-overlapping buildings: something like
  13    this:
  14                    _______
  15                   /       \                                ________
  16                  /         \                      ________/        \
  17         /\      /           \                    /                  \
  18        /  -----/              \                 /                    \
  19       /                         \              /                      \
  20      /                            ------------/                        ----
  21    --
  22    Each building has a starting position, and ending position, a starting
  23    height and an ending height.
  24
  25    The following invariants are observed:
  26     - the start of the first building is at -infinity
  27     - the end of the last building is at infinity
  28     - if a building has infinite length (ie. the first and last buildings),
  29       then its starting height and ending height are equal
  30     - the end of one building is the same as the beginning of the next
  31       building
  32
  33    We also allow skylines to point down (the structure is exactly the same,
  34    but we think of the part above the line as being filled with mass and the
  35    part below as being empty). ::distance finds the minimum distance between
  36    an UP skyline and a DOWN skyline.
  37
  38    Note that we store DOWN skylines upside-down. That is, in order to compare
  39    a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
  40    This means that the merging routine doesn't need to be aware of direction,
  41    but the distance routine does.
  42 */
  43
  44 #define EPS 1e-10
  45
  46 static inline bool
  47 equal (Real x, Real y)
  48 {
  49   return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
  50 }
  51
  52 bool
  53 Skyline::is_legal_skyline () const
  54 {
  55   list<Building>::const_iterator i;
  56   Real last_x = -infinity_f;
  57   Real last_h = -infinity_f;
  58   for (i = buildings_.begin (); i != buildings_.end (); i++)
  59     {
  60       if (i->iv_[LEFT] != last_x)
  61         return false;
  62       if (i != buildings_.begin () && !equal (i->start_height_, last_h))
  63         return false;
  64       last_x = i->iv_[RIGHT];
  65       last_h = i->end_height_;
  66     }
  67   return last_x == infinity_f;
  68 }
  69
  70 Building::Building (Real start, Real start_height, Real end_height, Real end, Real max_slope)
  71   : iv_ (start, end)
  72 {
  73   start_height_ = start_height;
  74   end_height_ = end_height;
  75
  76   if (isinf (start))
  77     assert (isinf (start_height) || start_height == end_height);
  78   if (isinf (end))
  79     assert (isinf (end_height) || start_height == end_height);
  80
  81   m_ = (end_height - start_height) / (end - start);
  82   if (start_height == end_height)
  83     m_ = 0;
  84   if (isinf (m_) || isnan (m_))
  85     m_ = max_slope * (start_height < end_height ? 1 : -1);
  86   assert (abs (m_) <= max_slope);
  87
  88   if (isinf (start))
  89     {
  90       if (isinf (end))
  91         b_ = start_height;
  92       else
  93         b_ = end_height - m_*end;
  94     }
  95   else
  96     b_ = start_height - m_*start;
  97 }
  98
  99 Real
 100 Building::height (Real x) const
 101 {
 102   if (isinf (x))
 103     return (x > 0) ? end_height_ : start_height_;
 104   return m_*x + b_;
 105 }
 106
 107 Real
 108 Building::intersection (Building const &other) const
 109 {
 110   return (b_ - other.b_) / (other.m_ - m_);
 111 }
 112
 113 void
 114 Building::leading_part (Real chop, Real h)
 115 {
 116   assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
 117   assert (equal (h, height (chop)));
 118   iv_[RIGHT] = chop;
 119   end_height_ = h;
 120 }
 121
 122 static void
 123 skyline_trailing_part (list<Building> *sky, Real x)
 124 {
 125   if (equal (x, sky->front ().iv_[RIGHT]))
 126     sky->pop_front ();
 127   else
 128     assert (x < sky->front ().iv_[RIGHT]);
 129
 130   if (!sky->empty ())
 131     {
 132       sky->front ().iv_[LEFT] = x;
 133       sky->front ().start_height_ = sky->front ().height (x);
 134     }
 135 }
 136
 137 bool
 138 Building::obstructs (Building const &other) const
 139 {
 140   if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
 141     return m_ > other.m_ || (m_ == other.m_ && b_ > other.b_);
 142   return start_height_ > other.start_height_;
 143 }
 144
 145 void
 146 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 147                                  list<Building> *const result)
 148 {
 149   while (!s1->empty ())
 150     {
 151       if (s2->front ().obstructs (s1->front ()))
 152         swap (s1, s2);
 153
 154       Building b = s1->front ();
 155       while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
 156              && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]))
 157         s2->pop_front ();
 158
 159       /* the front of s2 either intersects with b or it ends after b */
 160       Real end = infinity_f;
 161       if (s2->front ().end_height_ > b.height (s2->front ().iv_[RIGHT]))
 162         end = b.intersection (s2->front ());
 163       end = min (end, b.iv_[RIGHT]);
 164       Real height = b.height (end);
 165
 166       b.leading_part (end, height);
 167       result->push_front (b);
 168
 169       skyline_trailing_part (s1, end);
 170       if (!s1->empty ())
 171         s1->front ().start_height_ = height;
 172       skyline_trailing_part (s2, end);
 173     }
 174   result->reverse ();
 175 }
 176
 177 static void
 178 empty_skyline (list<Building> *const ret)
 179 {
 180   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
 181 }
 182
 183 static void
 184 single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
 185 {
 186   if (!isinf (b.iv_[RIGHT]))
 187     ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
 188   ret->push_front (b);
 189   if (!isinf (b.iv_[LEFT]))
 190     ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
 191 }
 192
 193 void
 194 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
 195 {
 196   vsize size = buildings->size ();
 197
 198   if (size == 0)
 199     {
 200       empty_skyline (result);
 201       return;
 202     }
 203   else if (size == 1)
 204     {
 205       single_skyline (buildings->front (), result, max_slope_);
 206       return;
 207     }
 208
 209   list<Building> right_half;
 210   list<Building>::iterator i = buildings->begin ();
 211
 212   for (vsize s = 0; s < size/2; s++)
 213     i++;
 214   right_half.splice (right_half.end (), *buildings, i, buildings->end ());
 215
 216   list<Building> right;
 217   list<Building> left;
 218   internal_build_skyline (&right_half, &right);
 219   internal_build_skyline (buildings, &left);
 220   internal_merge_skyline (&right, &left, result);
 221 }
 222
 223 Skyline::Skyline ()
 224 {
 225   max_slope_ = 2;
 226   sky_ = UP;
 227   empty_skyline (&buildings_);
 228 }
 229
 230 Skyline::Skyline (Direction sky)
 231 {
 232   max_slope_ = 2;
 233   sky_ = sky;
 234   empty_skyline (&buildings_);
 235 }
 236
 237 Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
 238 {
 239   list<Building> bldgs;
 240   sky_ = sky;
 241   max_slope_ = 2;
 242
 243   for (vsize i = 0; i < boxes.size (); i++)
 244     {
 245       Interval iv = boxes[i][a];
 246       Real height = sky * boxes[i][other_axis (a)][sky];
 247       if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
 248         bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_));
 249     }
 250   internal_build_skyline (&bldgs, &buildings_);
 251   assert (is_legal_skyline ());
 252 }
 253
 254 void
 255 Skyline::merge (Skyline const &other)
 256 {
 257   assert (sky_ == other.sky_);
 258
 259   list<Building> other_bld (other.buildings_);
 260   list<Building> my_bld;
 261   my_bld.splice (my_bld.begin (), buildings_);
 262   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 263   assert (is_legal_skyline ());
 264 }
 265
 266 void
 267 Skyline::insert (Box const &b, Axis a)
 268 {
 269   list<Building> other_bld;
 270   list<Building> my_bld (buildings_);
 271   Interval iv = b[a];
 272   Real height = sky_ * b[other_axis (a)][sky_];
 273
 274   single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
 275   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 276   assert (is_legal_skyline ());
 277 }
 278
 279 void
 280 Skyline::raise (Real r)
 281 {
 282   list<Building>::iterator end = buildings_.end ();
 283   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 284     {
 285       i->start_height_ += sky_ * r;
 286       i->end_height_ += sky_ * r;
 287       i->b_ += sky_ * r;
 288     }
 289   assert (is_legal_skyline ());
 290 }
 291
 292 Real
 293 Skyline::distance (Skyline const &other) const
 294 {
 295   assert (sky_ == -other.sky_);
 296   list<Building>::const_iterator i = buildings_.begin ();
 297   list<Building>::const_iterator j = other.buildings_.begin ();
 298
 299   Real dist = -infinity_f;
 300   for (; i != buildings_.end () && j != other.buildings_.end (); i++)
 301     {
 302       while (j->iv_[RIGHT] < i->iv_[LEFT])
 303         j++;
 304
 305       Interval iv = intersection (i->iv_, j->iv_);
 306       dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
 307                              i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
 308     }
 309   return dist;
 310 }
 311
 312 Real
 313 Skyline::height (Real airplane) const
 314 {
 315   assert (!isinf (airplane));
 316
 317   list<Building>::const_iterator i;
 318   for (i = buildings_.begin (); i != buildings_.end (); i++)
 319     {
 320       if (i->iv_[RIGHT] >= airplane)
 321         return sky_ * i->height (airplane);
 322     }
 323   assert (0);
 324   return 0;
 325 }
 326
 327 Real
 328 Skyline::max_height () const
 329 {
 330   Skyline s (-sky_);
 331   s.set_minimum_height (0);
 332   return sky_ * distance (s);
 333 }
 334
 335 void
 336 Skyline::set_minimum_height (Real h)
 337 {
 338   Skyline s (sky_);
 339   s.buildings_.front ().start_height_ = h*sky_;
 340   s.buildings_.front ().end_height_ = h*sky_;
 341   s.buildings_.front ().b_ = h*sky_;
 342   merge (s);
 343 }
 344
 345 Stencil
 346 Skyline::stencil ()
 347 {
 348   Stencil ret;
 349   for (list<Building>::iterator i = buildings_.begin (); i != buildings_.end (); i++)
 350     {
 351       if (!isinf (i->iv_.length ()))
 352         {
 353           Stencil line = Line_interface::make_line (0.1,
 354                                                     Offset (i->iv_[LEFT], sky_*i->start_height_),
 355                                                     Offset (i->iv_[RIGHT], sky_*i->end_height_));
 356           ret.add_stencil (line);
 357         }
 358     }
 359   return ret;
 360 }