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 void
  53 Skyline::print () const
  54 {
  55   for (list<Building>::const_iterator i = buildings_.begin ();
  56        i != buildings_.end (); i++)
  57     {
  58       (*i).print ();
  59     }
  60 }
  61
  62 bool
  63 Skyline::is_legal_skyline () const
  64 {
  65   list<Building>::const_iterator i;
  66   Real last_x = -infinity_f;
  67   Real last_h = -infinity_f;
  68   for (i = buildings_.begin (); i != buildings_.end (); i++)
  69     {
  70       if (i->iv_[LEFT] != last_x)
  71         return false;
  72       if (i != buildings_.begin () && !equal (i->start_height_, last_h))
  73         return false;
  74       last_x = i->iv_[RIGHT];
  75       last_h = i->end_height_;
  76     }
  77   return last_x == infinity_f;
  78 }
  79
  80 Building::Building (Real start, Real start_height, Real end_height,
  81                     Real end, Real max_slope)
  82   : iv_ (start, end)
  83 {
  84   start_height_ = start_height;
  85   end_height_ = end_height;
  86
  87   if (isinf (start))
  88     assert (isinf (start_height) || start_height == end_height);
  89   if (isinf (end))
  90     assert (isinf (end_height) || start_height == end_height);
  91
  92   precompute (max_slope);
  93 }
  94
  95 void
  96 Building::precompute (Real max_slope)
  97 {
  98   slope_ = (end_height_ - start_height_) / (iv_.length());
  99   if (start_height_ == end_height_)
 100     slope_ = 0;
 101   if (isinf (slope_) || isnan (slope_))
 102     slope_ = max_slope * (start_height_ < end_height_ ? 1 : -1);
 103
 104 #if 0
 105   /*
 106     this check is sensitive to roundoff errors when converting to/from
 107     sequences of points.
 108    */
 109   assert (abs (slope_) <= max_slope + EPS);
 110 #endif
 111
 112   if (isinf (iv_[START]))
 113     {
 114       if (isinf (iv_[STOP]))
 115         zero_height_ = start_height_;
 116       else
 117         zero_height_ = end_height_ - slope_ * iv_[STOP];
 118     }
 119   else
 120     zero_height_ = start_height_ - slope_ * iv_[START];
 121 }
 122
 123 Real
 124 Building::height (Real x) const
 125 {
 126   if (isinf (x))
 127     return (x > 0) ? end_height_ : start_height_;
 128   return slope_*x + zero_height_;
 129 }
 130
 131 void
 132 Building::print () const
 133 {
 134   printf ("X[%f,%f] -> Y[%f,%f]\n",
 135           iv_[LEFT], iv_[RIGHT],
 136           start_height_, end_height_);
 137 }
 138
 139 Real
 140 Building::intersection (Building const &other) const
 141 {
 142   return (zero_height_ - other.zero_height_) / (other.slope_ - slope_);
 143 }
 144
 145 void
 146 Building::leading_part (Real chop, Real h)
 147 {
 148   assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
 149   assert (equal (h, height (chop)));
 150   iv_[RIGHT] = chop;
 151   end_height_ = h;
 152 }
 153
 154 static void
 155 skyline_trailing_part (list<Building> *sky, Real x)
 156 {
 157   if (equal (x, sky->front ().iv_[RIGHT]))
 158     sky->pop_front ();
 159   else
 160     assert (x < sky->front ().iv_[RIGHT]);
 161
 162   if (!sky->empty ())
 163     {
 164       sky->front ().iv_[LEFT] = x;
 165       sky->front ().start_height_ = sky->front ().height (x);
 166     }
 167 }
 168
 169 bool
 170 Building::obstructs (Building const &other) const
 171 {
 172   if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
 173     return slope_ > other.slope_ || (slope_ == other.slope_ && zero_height_ > other.zero_height_);
 174   return start_height_ > other.start_height_;
 175 }
 176
 177 void
 178 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 179                                  list<Building> *const result)
 180 {
 181   while (!s1->empty ())
 182     {
 183       if (s2->front ().obstructs (s1->front ()))
 184         swap (s1, s2);
 185
 186       Building b = s1->front ();
 187       while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
 188              && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]) + EPS)
 189         s2->pop_front ();
 190
 191       /* the front of s2 either intersects with b or it ends after b */
 192       Real end = infinity_f;
 193       Real s2_end_height = s2->front ().end_height_;
 194       Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
 195       if (s2_end_height > s1_end_height + EPS)
 196         end = b.intersection (s2->front ());
 197       end = min (end, b.iv_[RIGHT]);
 198       Real height = b.height (end);
 199
 200       b.leading_part (end, height);
 201       result->push_front (b);
 202
 203       skyline_trailing_part (s1, end);
 204       if (!s1->empty ())
 205         s1->front ().start_height_ = height;
 206       skyline_trailing_part (s2, 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, 0));
 215 }
 216
 217 static void
 218 single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
 219 {
 220   if (!isinf (b.iv_[RIGHT]))
 221     ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
 222   ret->push_front (b);
 223   if (!isinf (b.iv_[LEFT]))
 224     ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
 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, max_slope_);
 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   max_slope_ = 2;
 260   sky_ = UP;
 261   empty_skyline (&buildings_);
 262 }
 263
 264 Skyline::Skyline (Direction sky)
 265 {
 266   max_slope_ = 2;
 267   sky_ = sky;
 268   empty_skyline (&buildings_);
 269 }
 270
 271 /*
 272   build skyline from a set of boxes.
 273
 274   Boxes should have fatness in the horizon_axis, otherwise they are ignored.
 275  */
 276 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
 277 {
 278   list<Building> bldgs;
 279   sky_ = sky;
 280   max_slope_ = 2;
 281
 282   for (vsize i = 0; i < boxes.size (); i++)
 283     {
 284       Interval iv = boxes[i][horizon_axis];
 285       Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
 286       if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
 287         bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_));
 288     }
 289   internal_build_skyline (&bldgs, &buildings_);
 290   assert (is_legal_skyline ());
 291 }
 292
 293 Skyline::Skyline (vector<Offset> const &points, Real max_slope, Direction sky)
 294 {
 295   sky_ = sky;
 296   max_slope_ = max_slope;
 297
 298   for (vsize i = 1; i < points.size (); i++)
 299     {
 300       buildings_.push_back (Building (points[i-1][X_AXIS], sky * points[i-1][Y_AXIS],
 301                                       sky * points[i][Y_AXIS],
 302
 303                                       points[i][X_AXIS],
 304                                       max_slope));
 305
 306     }
 307
 308   assert (is_legal_skyline ());
 309 }
 310
 311 void
 312 Skyline::merge (Skyline const &other)
 313 {
 314   assert (sky_ == other.sky_);
 315
 316   list<Building> other_bld (other.buildings_);
 317   list<Building> my_bld;
 318   my_bld.splice (my_bld.begin (), buildings_);
 319   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 320   assert (is_legal_skyline ());
 321 }
 322
 323 void
 324 Skyline::insert (Box const &b, Axis a)
 325 {
 326   list<Building> other_bld;
 327   list<Building> my_bld;
 328   Interval iv = b[a];
 329   Real height = sky_ * b[other_axis (a)][sky_];
 330
 331   my_bld.splice (my_bld.begin (), buildings_);
 332   single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
 333   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 334   assert (is_legal_skyline ());
 335 }
 336
 337 void
 338 Skyline::raise (Real r)
 339 {
 340   list<Building>::iterator end = buildings_.end ();
 341   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 342     {
 343       i->start_height_ += sky_ * r;
 344       i->end_height_ += sky_ * r;
 345       i->zero_height_ += sky_ * r;
 346     }
 347   assert (is_legal_skyline ());
 348 }
 349
 350 Real
 351 Skyline::distance (Skyline const &other) const
 352 {
 353   assert (sky_ == -other.sky_);
 354   list<Building>::const_iterator i = buildings_.begin ();
 355   list<Building>::const_iterator j = other.buildings_.begin ();
 356
 357   Real dist = -infinity_f;
 358   while (i != buildings_.end () && j != other.buildings_.end ())
 359     {
 360       Interval iv = intersection (i->iv_, j->iv_);
 361       dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
 362                              i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
 363       if (i->iv_[RIGHT] <= j->iv_[RIGHT])
 364         i++;
 365       else
 366         j++;
 367     }
 368   return dist;
 369 }
 370
 371 Real
 372 Skyline::height (Real airplane) const
 373 {
 374   assert (!isinf (airplane));
 375
 376   list<Building>::const_iterator i;
 377   for (i = buildings_.begin (); i != buildings_.end (); i++)
 378     {
 379       if (i->iv_[RIGHT] >= airplane)
 380         return sky_ * i->height (airplane);
 381     }
 382
 383   assert (0);
 384   return 0;
 385 }
 386
 387 Real
 388 Skyline::max_height () const
 389 {
 390   Skyline s (-sky_);
 391   s.set_minimum_height (0);
 392   return sky_ * distance (s);
 393 }
 394
 395 void
 396 Skyline::set_minimum_height (Real h)
 397 {
 398   Skyline s (sky_);
 399   s.buildings_.front ().start_height_ = h * sky_;
 400   s.buildings_.front ().end_height_ = h * sky_;
 401   s.buildings_.front ().zero_height_ = h * sky_;
 402   merge (s);
 403 }
 404
 405 Stencil
 406 to_stencil (Skyline const &line)
 407 {
 408   vector<Offset> points (line.to_points ());
 409
 410   Stencil ret;
 411   for (vsize i = 1; i < points.size (); i++)
 412     {
 413       if (points[i-1].is_sane ()  && points[i].is_sane ())
 414         {
 415           Stencil line
 416             = Line_interface::make_line (0.1, points[i-1], points[i]);
 417           ret.add_stencil (line);
 418         }
 419     }
 420   return ret;
 421 }
 422
 423 vector<Offset>
 424 Skyline::to_points () const
 425 {
 426   vector<Offset> out;
 427
 428   bool first = true;
 429   for (list<Building>::const_iterator i (buildings_.begin ());
 430        i != buildings_.end (); i++)
 431     {
 432       if (first)
 433         out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).start_height_));
 434
 435       first = false;
 436       out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).end_height_));
 437     }
 438
 439   return out;
 440 }
 441