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