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