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 "ly-smobs.icc"
  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 approx_equal (Real x, Real y)
  48 {
  49   return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
  50 }
  51
  52 static inline bool
  53 approx_greater_than (Real x, Real y)
  54 {
  55   return x > y + EPS;
  56 }
  57
  58 static inline bool
  59 approx_less_than (Real x, Real y)
  60 {
  61   return x < y - EPS;
  62 }
  63
  64 static inline bool
  65 approx_less_equal (Real x, Real y)
  66 {
  67   return x <= y + EPS;
  68 }
  69
  70 static inline bool
  71 approx_greater_equal (Real x, Real y)
  72 {
  73   return x >= y - EPS;
  74 }
  75
  76 void
  77 Skyline::print () const
  78 {
  79   for (list<Building>::const_iterator i = buildings_.begin ();
  80        i != buildings_.end (); i++)
  81     {
  82       (*i).print ();
  83     }
  84 }
  85
  86 bool
  87 Skyline::is_legal_skyline () const
  88 {
  89   list<Building>::const_iterator i;
  90   Real last_x = -infinity_f;
  91   for (i = buildings_.begin (); i != buildings_.end (); i++)
  92     {
  93       if (i->iv_[LEFT] != last_x)
  94         return false;
  95       last_x = i->iv_[RIGHT];
  96       if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT])
  97         return false;
  98     }
  99   return last_x == infinity_f;
 100 }
 101
 102 Building::Building (Real start, Real start_height, Real end_height, Real end)
 103   : iv_ (start, end)
 104 {
 105   height_[LEFT] = start_height;
 106   height_[RIGHT] = end_height;
 107
 108   if (isinf (start) || isinf (end))
 109     assert (start_height == end_height);
 110
 111   precompute ();
 112 }
 113
 114 Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
 115 {
 116   Real height = sky * b[other_axis (horizon_axis)][sky];
 117
 118   iv_ = b[horizon_axis];
 119   iv_.widen (horizon_padding + EPS);
 120   height_[LEFT] = height;
 121   height_[RIGHT] = height;
 122
 123   if (sane ())
 124     precompute ();
 125 }
 126
 127 void
 128 Building::precompute ()
 129 {
 130   slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
 131   if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
 132     slope_ = 0;
 133
 134   assert (!isinf (slope_) && !isnan (slope_));
 135
 136   if (isinf (iv_[START]))
 137     {
 138       assert (slope_ == 0);
 139       y_intercept_ = height_[LEFT];
 140     }
 141   else
 142     y_intercept_ = height_[LEFT] - slope_ * iv_[START];
 143 }
 144
 145 Real
 146 Building::height (Real x) const
 147 {
 148   if (isinf (x))
 149     return (x > 0) ? height_[RIGHT] : height_[LEFT];
 150   return slope_*x + y_intercept_;
 151 }
 152
 153 void
 154 Building::print () const
 155 {
 156   printf ("X[%f,%f] -> Y[%f,%f]\n",
 157           iv_[LEFT], iv_[RIGHT],
 158           height_[LEFT], height_[RIGHT]);
 159 }
 160
 161 Real
 162 Building::intersection (Building const &other) const
 163 {
 164   return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
 165 }
 166
 167 void
 168 Building::leading_part (Real chop)
 169 {
 170   assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
 171   iv_[RIGHT] = chop;
 172   height_[RIGHT] = height (chop);
 173 }
 174
 175 Building
 176 Building::sloped_neighbour (Real horizon_padding, Direction d) const
 177 {
 178   Real left = iv_[d];
 179   Real right = iv_[d] + d * horizon_padding;
 180   Real left_height = height_[d];
 181   Real right_height = height_[d] - horizon_padding;
 182   if (d == LEFT)
 183     {
 184       swap (left, right);
 185       swap (left_height, right_height);
 186     }
 187   return Building (left, left_height, right_height, right);
 188 }
 189
 190 bool
 191 Building::sane () const
 192 {
 193   return approx_less_than (iv_[LEFT], iv_[RIGHT])
 194     && !isinf (height_[RIGHT])
 195     && !isinf (height_[LEFT]);
 196 }
 197
 198 static void
 199 skyline_trailing_part (list<Building> *sky, Real x)
 200 {
 201   if (approx_equal (x, sky->front ().iv_[RIGHT]))
 202     sky->pop_front ();
 203   else
 204     assert (x < sky->front ().iv_[RIGHT]);
 205
 206   if (!sky->empty ())
 207     {
 208       sky->front ().iv_[LEFT] = x;
 209       sky->front ().height_[LEFT] = sky->front ().height (x);
 210     }
 211 }
 212
 213 bool
 214 Building::conceals_beginning (Building const &other) const
 215 {
 216   if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT]))
 217     return slope_ > other.slope_;
 218   return height_[LEFT] > other.height_[LEFT];
 219 }
 220
 221 bool
 222 Building::conceals (Building const &other) const
 223 {
 224   assert (iv_[LEFT] <= other.iv_[LEFT]);
 225   return (iv_[RIGHT] >= other.iv_[RIGHT])
 226     && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
 227     && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
 228 }
 229
 230 void
 231 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 232                                  list<Building> *const result)
 233 {
 234   while (!s1->empty ())
 235     {
 236       if (s2->front ().conceals_beginning (s1->front ()))
 237         swap (s1, s2);
 238
 239       Building b = s1->front ();
 240       while (!s2->empty () && b.conceals (s2->front ()))
 241         s2->pop_front ();
 242       if (s2->empty ())
 243         {
 244           result->push_front (b);
 245           break;
 246         }
 247
 248       /* s2 either intersects with b or it ends after b */
 249       Real end = infinity_f;
 250       Real s2_start_height = s2->front ().height_[LEFT];
 251       Real s2_end_height = s2->front ().height_[RIGHT];
 252       Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
 253       Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
 254       if (approx_greater_than (s2_start_height, s1_start_height))
 255         end = s2->front ().iv_[LEFT];
 256       else if (approx_greater_than (s2_end_height, s1_end_height))
 257         end = b.intersection (s2->front ());
 258       end = min (end, b.iv_[RIGHT]);
 259
 260       b.leading_part (end);
 261       result->push_front (b);
 262
 263       skyline_trailing_part (s1, end);
 264       skyline_trailing_part (s2, end);
 265     }
 266   result->reverse ();
 267 }
 268
 269 static void
 270 empty_skyline (list<Building> *const ret)
 271 {
 272   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
 273 }
 274
 275 static void
 276 single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
 277 {
 278   b.iv_.widen (horizon_padding);
 279
 280   if (!isinf (b.iv_[RIGHT]))
 281     ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
 282                                -infinity_f, infinity_f));
 283   if (horizon_padding > 0 && !isinf (b.iv_.length ()))
 284     ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
 285
 286   if (b.iv_[RIGHT] > b.iv_[LEFT])
 287     ret->push_front (b);
 288
 289   if (horizon_padding > 0 && !isinf (b.iv_.length ()))
 290     ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
 291   if (!isinf (b.iv_[LEFT]))
 292     ret->push_front (Building (-infinity_f, -infinity_f,
 293                                -infinity_f, b.iv_[LEFT]));
 294 }
 295
 296 void
 297 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
 298 {
 299   vsize size = buildings->size ();
 300
 301   if (size == 0)
 302     {
 303       empty_skyline (result);
 304       return;
 305     }
 306   else if (size == 1)
 307     {
 308       single_skyline (buildings->front (), 0, result);
 309       return;
 310     }
 311
 312   list<Building> right_half;
 313   list<Building>::iterator i = buildings->begin ();
 314
 315   for (vsize s = 0; s < size/2; s++)
 316     i++;
 317   right_half.splice (right_half.end (), *buildings, i, buildings->end ());
 318
 319   list<Building> right;
 320   list<Building> left;
 321   internal_build_skyline (&right_half, &right);
 322   internal_build_skyline (buildings, &left);
 323   internal_merge_skyline (&right, &left, result);
 324 }
 325
 326 Skyline::Skyline ()
 327 {
 328   sky_ = UP;
 329   empty_skyline (&buildings_);
 330 }
 331
 332 Skyline::Skyline (Skyline const &src)
 333 {
 334   sky_ = src.sky_;
 335
 336   for (list<Building>::const_iterator i = src.buildings_.begin ();
 337        i != src.buildings_.end (); i++)
 338     {
 339       buildings_.push_back (Building ((*i)));
 340     }
 341 }
 342
 343 Skyline::Skyline (Direction sky)
 344 {
 345   sky_ = sky;
 346   empty_skyline (&buildings_);
 347 }
 348
 349 /*
 350   build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
 351   by that amount and add 45-degree sloped boxes to the edges of each box (of
 352   width horizon_padding). That is, the total amount of horizontal expansion is
 353   horizon_padding*4, half of which is sloped and half of which is flat.
 354
 355   Boxes should have fatness in the horizon_axis (after they are expanded by
 356   horizon_padding), otherwise they are ignored.
 357  */
 358 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
 359 {
 360   list<Building> bldgs;
 361   sky_ = sky;
 362
 363   for (vsize i = 0; i < boxes.size (); i++)
 364     {
 365       Building front (boxes[i], horizon_padding, horizon_axis, sky);
 366       if (front.sane ())
 367         {
 368           bldgs.push_front (front);
 369           if (horizon_padding > 0 && !isinf (front.iv_.length ()))
 370             {
 371               bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT));
 372               bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT));
 373             }
 374         }
 375     }
 376
 377   internal_build_skyline (&bldgs, &buildings_);
 378   assert (is_legal_skyline ());
 379 }
 380
 381 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
 382 {
 383   sky_ = sky;
 384   Building front (b, 0, horizon_axis, sky);
 385   single_skyline (front, horizon_padding, &buildings_);
 386 }
 387
 388 void
 389 Skyline::merge (Skyline const &other)
 390 {
 391   assert (sky_ == other.sky_);
 392
 393   list<Building> other_bld (other.buildings_);
 394   list<Building> my_bld;
 395   my_bld.splice (my_bld.begin (), buildings_);
 396   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 397   assert (is_legal_skyline ());
 398 }
 399
 400 void
 401 Skyline::insert (Box const &b, Real horizon_padding, Axis a)
 402 {
 403   list<Building> other_bld;
 404   list<Building> my_bld;
 405
 406   my_bld.splice (my_bld.begin (), buildings_);
 407   single_skyline (Building (b, 0, a, sky_), horizon_padding, &other_bld);
 408   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 409   assert (is_legal_skyline ());
 410 }
 411
 412 void
 413 Skyline::raise (Real r)
 414 {
 415   list<Building>::iterator end = buildings_.end ();
 416   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 417     {
 418       i->height_[LEFT] += sky_ * r;
 419       i->height_[RIGHT] += sky_ * r;
 420       i->y_intercept_ += sky_ * r;
 421     }
 422   assert (is_legal_skyline ());
 423 }
 424
 425 void
 426 Skyline::shift (Real r)
 427 {
 428   list<Building>::iterator end = buildings_.end ();
 429   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 430     {
 431       i->iv_[LEFT] += r;
 432       i->iv_[RIGHT] += r;
 433     }
 434 }
 435
 436 Real
 437 Skyline::distance (Skyline const &other) const
 438 {
 439   assert (sky_ == -other.sky_);
 440   list<Building>::const_iterator i = buildings_.begin ();
 441   list<Building>::const_iterator j = other.buildings_.begin ();
 442
 443   Real dist = -infinity_f;
 444   while (i != buildings_.end () && j != other.buildings_.end ())
 445     {
 446       Interval iv = intersection (i->iv_, j->iv_);
 447       dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
 448                              i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
 449       if (i->iv_[RIGHT] <= j->iv_[RIGHT])
 450         i++;
 451       else
 452         j++;
 453     }
 454   return dist;
 455 }
 456
 457 Real
 458 Skyline::height (Real airplane) const
 459 {
 460   assert (!isinf (airplane));
 461
 462   list<Building>::const_iterator i;
 463   for (i = buildings_.begin (); i != buildings_.end (); i++)
 464     {
 465       if (i->iv_[RIGHT] >= airplane)
 466         return sky_ * i->height (airplane);
 467     }
 468
 469   assert (0);
 470   return 0;
 471 }
 472
 473 Real
 474 Skyline::max_height () const
 475 {
 476   Skyline s (-sky_);
 477   s.set_minimum_height (0);
 478   return sky_ * distance (s);
 479 }
 480
 481 void
 482 Skyline::set_minimum_height (Real h)
 483 {
 484   Skyline s (sky_);
 485   s.buildings_.front ().height_[LEFT] = h * sky_;
 486   s.buildings_.front ().height_[RIGHT] = h * sky_;
 487   s.buildings_.front ().y_intercept_ = h * sky_;
 488   merge (s);
 489 }
 490
 491
 492 vector<Offset>
 493 Skyline::to_points () const
 494 {
 495   vector<Offset> out;
 496
 497   for (list<Building>::const_iterator i (buildings_.begin ());
 498        i != buildings_.end (); i++)
 499     {
 500       if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT]))
 501         out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT]));
 502       if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT]))
 503         out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT]));
 504     }
 505   return out;
 506 }
 507
 508 Skyline_pair::Skyline_pair ()
 509   : skylines_ (Skyline (DOWN), Skyline (UP))
 510 {
 511 }
 512
 513 Skyline_pair::Skyline_pair (vector<Box> const &boxes, Real padding, Axis a)
 514   : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP))
 515 {
 516 }
 517
 518 Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a)
 519   : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP))
 520 {
 521 }
 522
 523 void
 524 Skyline_pair::raise (Real r)
 525 {
 526   skylines_[UP].raise (r);
 527   skylines_[DOWN].raise (r);
 528 }
 529
 530 void
 531 Skyline_pair::shift (Real r)
 532 {
 533   skylines_[UP].shift (r);
 534   skylines_[DOWN].shift (r);
 535 }
 536
 537 void
 538 Skyline_pair::insert (Box const &b, Real padding, Axis a)
 539 {
 540   skylines_[UP].insert (b, padding, a);
 541   skylines_[DOWN].insert (b, padding, a);
 542 }
 543
 544 void
 545 Skyline_pair::merge (Skyline_pair const &other)
 546 {
 547   skylines_[UP].merge (other[UP]);
 548   skylines_[DOWN].merge (other[DOWN]);
 549 }
 550
 551 Skyline&
 552 Skyline_pair::operator [] (Direction d)
 553 {
 554   return skylines_[d];
 555 }
 556
 557 Skyline const&
 558 Skyline_pair::operator [] (Direction d) const
 559 {
 560   return skylines_[d];
 561 }
 562
 563 /****************************************************************/
 564
 565
 566 IMPLEMENT_SIMPLE_SMOBS (Skyline);
 567 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
 568 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
 569
 570 IMPLEMENT_SIMPLE_SMOBS (Skyline_pair);
 571 IMPLEMENT_TYPE_P (Skyline_pair, "ly:skyline-pair?");
 572 IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair);
 573
 574 SCM
 575 Skyline::mark_smob (SCM)
 576 {
 577   return SCM_EOL;
 578 }
 579
 580 int
 581 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
 582 {
 583   Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
 584   (void) r;
 585
 586   scm_puts ("#<Skyline>", port);
 587
 588   return 1;
 589 }
 590
 591 SCM
 592 Skyline_pair::mark_smob (SCM)
 593 {
 594   return SCM_EOL;
 595 }
 596
 597 int
 598 Skyline_pair::print_smob (SCM s, SCM port, scm_print_state *)
 599 {
 600   Skyline_pair *r = (Skyline_pair *) SCM_CELL_WORD_1 (s);
 601   (void) r;
 602
 603   scm_puts ("#<Skyline-pair>", port);
 604   return 1;
 605 }