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,
  71                     Real end, Real max_slope)
  72   : iv_ (start, end)
  73 {
  74   start_height_ = start_height;
  75   end_height_ = end_height;
  76
  77   if (isinf (start))
  78     assert (isinf (start_height) || start_height == end_height);
  79   if (isinf (end))
  80     assert (isinf (end_height) || start_height == end_height);
  81
  82   precompute (max_slope);
  83 }
  84
  85 void
  86 Building::precompute (Real max_slope)
  87 {
  88   slope_ = (end_height_ - start_height_) / (iv_.length());
  89   if (start_height_ == end_height_)
  90     slope_ = 0;
  91   if (isinf (slope_) || isnan (slope_))
  92     slope_ = max_slope * (start_height_ < end_height_ ? 1 : -1);
  93   assert (abs (slope_) <= max_slope);
  94
  95   if (isinf (iv_[START]))
  96     {
  97       if (isinf (iv_[STOP]))
  98         zero_height_ = start_height_;
  99       else
 100         zero_height_ = end_height_ - slope_ * iv_[STOP];
 101     }
 102   else
 103     zero_height_ = start_height_ - slope_ * iv_[START];
 104 }
 105
 106 Real
 107 Building::height (Real x) const
 108 {
 109   if (isinf (x))
 110     return (x > 0) ? end_height_ : start_height_;
 111   return slope_*x + zero_height_;
 112 }
 113
 114 Real
 115 Building::intersection (Building const &other) const
 116 {
 117   return (zero_height_ - other.zero_height_) / (other.slope_ - slope_);
 118 }
 119
 120 void
 121 Building::leading_part (Real chop, Real h)
 122 {
 123   assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
 124   assert (equal (h, height (chop)));
 125   iv_[RIGHT] = chop;
 126   end_height_ = h;
 127 }
 128
 129 static void
 130 skyline_trailing_part (list<Building> *sky, Real x)
 131 {
 132   if (equal (x, sky->front ().iv_[RIGHT]))
 133     sky->pop_front ();
 134   else
 135     assert (x < sky->front ().iv_[RIGHT]);
 136
 137   if (!sky->empty ())
 138     {
 139       sky->front ().iv_[LEFT] = x;
 140       sky->front ().start_height_ = sky->front ().height (x);
 141     }
 142 }
 143
 144 bool
 145 Building::obstructs (Building const &other) const
 146 {
 147   if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
 148     return slope_ > other.slope_ || (slope_ == other.slope_ && zero_height_ > other.zero_height_);
 149   return start_height_ > other.start_height_;
 150 }
 151
 152 void
 153 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 154                                  list<Building> *const result)
 155 {
 156   while (!s1->empty ())
 157     {
 158       if (s2->front ().obstructs (s1->front ()))
 159         swap (s1, s2);
 160
 161       Building b = s1->front ();
 162       while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
 163              && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]) + EPS)
 164         s2->pop_front ();
 165
 166       /* the front of s2 either intersects with b or it ends after b */
 167       Real end = infinity_f;
 168       Real s2_end_height = s2->front ().end_height_;
 169       Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
 170       if (s2_end_height > s1_end_height + EPS)
 171         end = b.intersection (s2->front ());
 172       end = min (end, b.iv_[RIGHT]);
 173       Real height = b.height (end);
 174
 175       b.leading_part (end, height);
 176       result->push_front (b);
 177
 178       skyline_trailing_part (s1, end);
 179       if (!s1->empty ())
 180         s1->front ().start_height_ = height;
 181       skyline_trailing_part (s2, end);
 182     }
 183   result->reverse ();
 184 }
 185
 186 static void
 187 empty_skyline (list<Building> *const ret)
 188 {
 189   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
 190 }
 191
 192 static void
 193 single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
 194 {
 195   if (!isinf (b.iv_[RIGHT]))
 196     ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
 197   ret->push_front (b);
 198   if (!isinf (b.iv_[LEFT]))
 199     ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
 200 }
 201
 202 void
 203 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
 204 {
 205   vsize size = buildings->size ();
 206
 207   if (size == 0)
 208     {
 209       empty_skyline (result);
 210       return;
 211     }
 212   else if (size == 1)
 213     {
 214       single_skyline (buildings->front (), result, max_slope_);
 215       return;
 216     }
 217
 218   list<Building> right_half;
 219   list<Building>::iterator i = buildings->begin ();
 220
 221   for (vsize s = 0; s < size/2; s++)
 222     i++;
 223   right_half.splice (right_half.end (), *buildings, i, buildings->end ());
 224
 225   list<Building> right;
 226   list<Building> left;
 227   internal_build_skyline (&right_half, &right);
 228   internal_build_skyline (buildings, &left);
 229   internal_merge_skyline (&right, &left, result);
 230 }
 231
 232 Skyline::Skyline ()
 233 {
 234   max_slope_ = 2;
 235   sky_ = UP;
 236   empty_skyline (&buildings_);
 237 }
 238
 239 Skyline::Skyline (Direction sky)
 240 {
 241   max_slope_ = 2;
 242   sky_ = sky;
 243   empty_skyline (&buildings_);
 244 }
 245
 246
 247 Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
 248 {
 249   list<Building> bldgs;
 250   sky_ = sky;
 251   max_slope_ = 2;
 252
 253   for (vsize i = 0; i < boxes.size (); i++)
 254     {
 255       Interval iv = boxes[i][a];
 256       Real height = sky * boxes[i][other_axis (a)][sky];
 257       if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
 258         bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_));
 259     }
 260   internal_build_skyline (&bldgs, &buildings_);
 261   assert (is_legal_skyline ());
 262 }
 263
 264 Skyline::Skyline (vector<Offset> const &points, Real max_slope, Direction sky)
 265 {
 266   sky_ = sky;
 267   max_slope_ = max_slope;
 268
 269   for (vsize i = 1; i < points.size (); i++)
 270     {
 271       buildings_.push_back (Building (points[i-1][X_AXIS], sky * points[i-1][Y_AXIS],
 272                                       points[i][X_AXIS], sky * points[i][Y_AXIS],
 273                                       max_slope));
 274
 275     }
 276
 277   assert (is_legal_skyline ());
 278 }
 279
 280 void
 281 Skyline::merge (Skyline const &other)
 282 {
 283   assert (sky_ == other.sky_);
 284
 285   list<Building> other_bld (other.buildings_);
 286   list<Building> my_bld;
 287   my_bld.splice (my_bld.begin (), buildings_);
 288   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 289   assert (is_legal_skyline ());
 290 }
 291
 292 void
 293 Skyline::insert (Box const &b, Axis a)
 294 {
 295   list<Building> other_bld;
 296   list<Building> my_bld;
 297   Interval iv = b[a];
 298   Real height = sky_ * b[other_axis (a)][sky_];
 299
 300   my_bld.splice (my_bld.begin (), buildings_);
 301   single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
 302   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 303   assert (is_legal_skyline ());
 304 }
 305
 306 void
 307 Skyline::raise (Real r)
 308 {
 309   list<Building>::iterator end = buildings_.end ();
 310   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 311     {
 312       i->start_height_ += sky_ * r;
 313       i->end_height_ += sky_ * r;
 314       i->zero_height_ += sky_ * r;
 315     }
 316   assert (is_legal_skyline ());
 317 }
 318
 319 Real
 320 Skyline::distance (Skyline const &other) const
 321 {
 322   assert (sky_ == -other.sky_);
 323   list<Building>::const_iterator i = buildings_.begin ();
 324   list<Building>::const_iterator j = other.buildings_.begin ();
 325
 326   Real dist = -infinity_f;
 327   while (i != buildings_.end () && j != other.buildings_.end ())
 328     {
 329       Interval iv = intersection (i->iv_, j->iv_);
 330       dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
 331                              i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
 332       if (i->iv_[RIGHT] <= j->iv_[RIGHT])
 333         i++;
 334       else
 335         j++;
 336     }
 337   return dist;
 338 }
 339
 340 Real
 341 Skyline::height (Real airplane) const
 342 {
 343   assert (!isinf (airplane));
 344
 345   list<Building>::const_iterator i;
 346   for (i = buildings_.begin (); i != buildings_.end (); i++)
 347     {
 348       if (i->iv_[RIGHT] >= airplane)
 349         return sky_ * i->height (airplane);
 350     }
 351
 352   assert (0);
 353   return 0;
 354 }
 355
 356 Real
 357 Skyline::max_height () const
 358 {
 359   Skyline s (-sky_);
 360   s.set_minimum_height (0);
 361   return sky_ * distance (s);
 362 }
 363
 364 void
 365 Skyline::set_minimum_height (Real h)
 366 {
 367   Skyline s (sky_);
 368   s.buildings_.front ().start_height_ = h * sky_;
 369   s.buildings_.front ().end_height_ = h * sky_;
 370   s.buildings_.front ().zero_height_ = h * sky_;
 371   merge (s);
 372 }
 373
 374 Stencil
 375 to_stencil (Skyline const &line)
 376 {
 377   vector<Offset> points (line.to_points ());
 378
 379   Stencil ret;
 380   for (vsize i = 1; i < points.size (); i++)
 381     {
 382       if (points[i-1].is_sane ()  && points[i].is_sane ())
 383         {
 384           Stencil line
 385             = Line_interface::make_line (0.1, points[i-1], points[i]);
 386           ret.add_stencil (line);
 387         }
 388     }
 389   return ret;
 390 }
 391
 392 vector<Offset>
 393 Skyline::to_points () const
 394 {
 395   vector<Offset> out;
 396
 397   bool first = true;
 398   for (list<Building>::const_iterator i (buildings_.begin ());
 399        i != buildings_.end (); i++)
 400     {
 401       if (first)
 402         out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).start_height_));
 403       first = false;
 404       out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).end_height_));
 405     }
 406
 407   return out;
 408 }
 409