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 void
 115 Building::precompute ()
 116 {
 117   slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
 118   if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
 119     slope_ = 0;
 120
 121   assert (!isinf (slope_) && !isnan (slope_));
 122
 123   if (isinf (iv_[START]))
 124     {
 125       assert (slope_ == 0);
 126       y_intercept_ = height_[LEFT];
 127     }
 128   else
 129     y_intercept_ = height_[LEFT] - slope_ * iv_[START];
 130 }
 131
 132 Real
 133 Building::height (Real x) const
 134 {
 135   if (isinf (x))
 136     return (x > 0) ? height_[RIGHT] : height_[LEFT];
 137   return slope_*x + y_intercept_;
 138 }
 139
 140 void
 141 Building::print () const
 142 {
 143   printf ("X[%f,%f] -> Y[%f,%f]\n",
 144           iv_[LEFT], iv_[RIGHT],
 145           height_[LEFT], height_[RIGHT]);
 146 }
 147
 148 Real
 149 Building::intersection (Building const &other) const
 150 {
 151   return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
 152 }
 153
 154 void
 155 Building::leading_part (Real chop)
 156 {
 157   assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
 158   iv_[RIGHT] = chop;
 159   height_[RIGHT] = height (chop);
 160 }
 161
 162 Building
 163 Building::sloped_neighbour (Real horizon_padding, Direction d) const
 164 {
 165   Real left = iv_[d];
 166   Real right = iv_[d] + d * horizon_padding;
 167   Real left_height = height_[d];
 168   Real right_height = height_[d] - horizon_padding;
 169   if (d == LEFT)
 170     {
 171       swap (left, right);
 172       swap (left_height, right_height);
 173     }
 174   return Building (left, left_height, right_height, right);
 175 }
 176
 177 static void
 178 skyline_trailing_part (list<Building> *sky, Real x)
 179 {
 180   if (approx_equal (x, sky->front ().iv_[RIGHT]))
 181     sky->pop_front ();
 182   else
 183     assert (x < sky->front ().iv_[RIGHT]);
 184
 185   if (!sky->empty ())
 186     {
 187       sky->front ().iv_[LEFT] = x;
 188       sky->front ().height_[LEFT] = sky->front ().height (x);
 189     }
 190 }
 191
 192 bool
 193 Building::conceals_beginning (Building const &other) const
 194 {
 195   if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT]))
 196     return slope_ > other.slope_;
 197   return height_[LEFT] > other.height_[LEFT];
 198 }
 199
 200 bool
 201 Building::conceals (Building const &other) const
 202 {
 203   assert (iv_[LEFT] <= other.iv_[LEFT]);
 204   return (iv_[RIGHT] >= other.iv_[RIGHT])
 205     && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
 206     && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
 207 }
 208
 209 void
 210 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 211                                  list<Building> *const result)
 212 {
 213   while (!s1->empty ())
 214     {
 215       if (s2->front ().conceals_beginning (s1->front ()))
 216         swap (s1, s2);
 217
 218       Building b = s1->front ();
 219       while (!s2->empty () && b.conceals (s2->front ()))
 220         s2->pop_front ();
 221       if (s2->empty ())
 222         {
 223           result->push_front (b);
 224           break;
 225         }
 226
 227       /* s2 either intersects with b or it ends after b */
 228       Real end = infinity_f;
 229       Real s2_start_height = s2->front ().height_[LEFT];
 230       Real s2_end_height = s2->front ().height_[RIGHT];
 231       Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
 232       Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
 233       if (approx_greater_than (s2_start_height, s1_start_height))
 234         end = s2->front ().iv_[LEFT];
 235       else if (approx_greater_than (s2_end_height, s1_end_height))
 236         end = b.intersection (s2->front ());
 237       end = min (end, b.iv_[RIGHT]);
 238
 239       b.leading_part (end);
 240       result->push_front (b);
 241
 242       skyline_trailing_part (s1, end);
 243       skyline_trailing_part (s2, end);
 244     }
 245   result->reverse ();
 246 }
 247
 248 static void
 249 empty_skyline (list<Building> *const ret)
 250 {
 251   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
 252 }
 253
 254 static void
 255 single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
 256 {
 257   b.iv_.widen (horizon_padding);
 258
 259   if (!isinf (b.iv_[RIGHT]))
 260     ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
 261                                -infinity_f, infinity_f));
 262   if (horizon_padding > 0 && !isinf (b.iv_.length ()))
 263     ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
 264
 265   if (b.iv_[RIGHT] > b.iv_[LEFT])
 266     ret->push_front (b);
 267
 268   if (horizon_padding > 0 && !isinf (b.iv_.length ()))
 269     ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
 270   if (!isinf (b.iv_[LEFT]))
 271     ret->push_front (Building (-infinity_f, -infinity_f,
 272                                -infinity_f, b.iv_[LEFT]));
 273 }
 274
 275 void
 276 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
 277 {
 278   vsize size = buildings->size ();
 279
 280   if (size == 0)
 281     {
 282       empty_skyline (result);
 283       return;
 284     }
 285   else if (size == 1)
 286     {
 287       single_skyline (buildings->front (), 0, result);
 288       return;
 289     }
 290
 291   list<Building> right_half;
 292   list<Building>::iterator i = buildings->begin ();
 293
 294   for (vsize s = 0; s < size/2; s++)
 295     i++;
 296   right_half.splice (right_half.end (), *buildings, i, buildings->end ());
 297
 298   list<Building> right;
 299   list<Building> left;
 300   internal_build_skyline (&right_half, &right);
 301   internal_build_skyline (buildings, &left);
 302   internal_merge_skyline (&right, &left, result);
 303 }
 304
 305 Skyline::Skyline ()
 306 {
 307   sky_ = UP;
 308   empty_skyline (&buildings_);
 309 }
 310
 311 Skyline::Skyline (Skyline const &src)
 312 {
 313   sky_ = src.sky_;
 314
 315   for (list<Building>::const_iterator i = src.buildings_.begin ();
 316        i != src.buildings_.end (); i++)
 317     {
 318       buildings_.push_back (Building ((*i)));
 319     }
 320 }
 321
 322 Skyline::Skyline (Direction sky)
 323 {
 324   sky_ = sky;
 325   empty_skyline (&buildings_);
 326 }
 327
 328 /*
 329   build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
 330   by that amount and add 45-degree sloped boxes to the edges of each box (of
 331   width horizon_padding). That is, the total amount of horizontal expansion is
 332   horizon_padding*4, half of which is sloped and half of which is flat.
 333
 334   Boxes should have fatness in the horizon_axis (after they are expanded by
 335   horizon_padding), otherwise they are ignored.
 336  */
 337 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
 338 {
 339   list<Building> bldgs;
 340   sky_ = sky;
 341
 342   for (vsize i = 0; i < boxes.size (); i++)
 343     {
 344       Interval iv = boxes[i][horizon_axis];
 345       Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
 346
 347       iv.widen (horizon_padding);
 348       if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT]))
 349         {
 350           iv.widen (EPS);
 351           Building front = Building (iv[LEFT], height, height, iv[RIGHT]);
 352           bldgs.push_front (front);
 353           if (horizon_padding > 0 && !isinf (front.iv_.length ()))
 354             {
 355               bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT));
 356               bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT));
 357             }
 358         }
 359     }
 360
 361   internal_build_skyline (&bldgs, &buildings_);
 362   assert (is_legal_skyline ());
 363 }
 364
 365 void
 366 Skyline::merge (Skyline const &other)
 367 {
 368   assert (sky_ == other.sky_);
 369
 370   list<Building> other_bld (other.buildings_);
 371   list<Building> my_bld;
 372   my_bld.splice (my_bld.begin (), buildings_);
 373   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 374   assert (is_legal_skyline ());
 375 }
 376
 377 void
 378 Skyline::insert (Box const &b, Real horizon_padding, Axis a)
 379 {
 380   list<Building> other_bld;
 381   list<Building> my_bld;
 382   Interval iv = b[a];
 383   Real height = sky_ * b[other_axis (a)][sky_];
 384
 385   assert (!iv.is_empty ());
 386   iv.widen (EPS);
 387
 388   my_bld.splice (my_bld.begin (), buildings_);
 389   single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), horizon_padding, &other_bld);
 390   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 391   assert (is_legal_skyline ());
 392 }
 393
 394 void
 395 Skyline::raise (Real r)
 396 {
 397   list<Building>::iterator end = buildings_.end ();
 398   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 399     {
 400       i->height_[LEFT] += sky_ * r;
 401       i->height_[RIGHT] += sky_ * r;
 402       i->y_intercept_ += sky_ * r;
 403     }
 404   assert (is_legal_skyline ());
 405 }
 406
 407 Real
 408 Skyline::distance (Skyline const &other) const
 409 {
 410   assert (sky_ == -other.sky_);
 411   list<Building>::const_iterator i = buildings_.begin ();
 412   list<Building>::const_iterator j = other.buildings_.begin ();
 413
 414   Real dist = -infinity_f;
 415   while (i != buildings_.end () && j != other.buildings_.end ())
 416     {
 417       Interval iv = intersection (i->iv_, j->iv_);
 418       dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
 419                              i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
 420       if (i->iv_[RIGHT] <= j->iv_[RIGHT])
 421         i++;
 422       else
 423         j++;
 424     }
 425   return dist;
 426 }
 427
 428 Real
 429 Skyline::height (Real airplane) const
 430 {
 431   assert (!isinf (airplane));
 432
 433   list<Building>::const_iterator i;
 434   for (i = buildings_.begin (); i != buildings_.end (); i++)
 435     {
 436       if (i->iv_[RIGHT] >= airplane)
 437         return sky_ * i->height (airplane);
 438     }
 439
 440   assert (0);
 441   return 0;
 442 }
 443
 444 Real
 445 Skyline::max_height () const
 446 {
 447   Skyline s (-sky_);
 448   s.set_minimum_height (0);
 449   return sky_ * distance (s);
 450 }
 451
 452 void
 453 Skyline::set_minimum_height (Real h)
 454 {
 455   Skyline s (sky_);
 456   s.buildings_.front ().height_[LEFT] = h * sky_;
 457   s.buildings_.front ().height_[RIGHT] = h * sky_;
 458   s.buildings_.front ().y_intercept_ = h * sky_;
 459   merge (s);
 460 }
 461
 462
 463 vector<Offset>
 464 Skyline::to_points () const
 465 {
 466   vector<Offset> out;
 467
 468   for (list<Building>::const_iterator i (buildings_.begin ());
 469        i != buildings_.end (); i++)
 470     {
 471       if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT]))
 472         out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT]));
 473       if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT]))
 474         out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT]));
 475     }
 476   return out;
 477 }
 478
 479 /****************************************************************/
 480
 481
 482 IMPLEMENT_SIMPLE_SMOBS (Skyline);
 483 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
 484 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
 485
 486 SCM
 487 Skyline::mark_smob (SCM)
 488 {
 489   return SCM_EOL;
 490 }
 491
 492 int
 493 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
 494 {
 495   Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
 496   (void) r;
 497
 498   scm_puts ("#<Skyline>", port);
 499
 500   return 1;
 501 }