lily/bezier.cc

   1 /*
   2   bezier.cc -- implement Bezier and Bezier_bow
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1998--1999 Jan Nieuwenhuizen <janneke@gnu.org>
   7 */
   8
   9 #include <math.h>
  10 #include "bezier.hh"
  11 #include "misc.hh"
  12
  13 #ifndef STANDALONE
  14 #include "dimensions.hh"
  15 #include "direction.hh"
  16 #include "paper-def.hh"
  17 #include "debug.hh"
  18 #include "main.hh"
  19 #define BEZIER_BOW_DOUT if (check_debug && !monitor->silent_b ("Bezier_bow")) cout
  20 #else
  21 #define BEZIER_BOW_DOUT cerr
  22 #endif
  23
  24
  25 /*
  26   [TODO]
  27
  28   * better names, esp. for all calc_foo functions
  29   * blow_fit vs calc_default (Real) and calc_f (Real)
  30   * exact height / tangent calculation
  31
  32  */
  33
  34 void
  35 Curve::flipy ()
  36 {
  37   for (int i = 0; i < size (); i++)
  38     (*this)[i].mirror (Y_AXIS);
  39 }
  40
  41 int
  42 Curve::largest_disturbing ()
  43 {
  44   Real alpha = 0;
  45   int j = 0;
  46   for (int i = 1; i < size (); i++)
  47     {
  48       if ((*this)[i][Y_AXIS] > 0)
  49         {
  50           Real phi = (*this)[i][Y_AXIS] / (*this)[i][X_AXIS];
  51           if (phi > alpha)
  52             {
  53               alpha = phi;
  54               j = i;
  55             }
  56         }
  57     }
  58   return j;
  59 }
  60
  61 void
  62 Curve::rotate (Real phi)
  63 {
  64   Offset rot (complex_exp (Offset (0, phi)));
  65   for (int i = 0; i < size (); i++)
  66     (*this)[i] = complex_multiply (rot, (*this)[i]);
  67 }
  68
  69 void
  70 Curve::translate (Offset o)
  71 {
  72   for (int i = 0; i < size (); i++)
  73     (*this)[i] += o;
  74 }
  75
  76 Bezier::Bezier ()
  77 {
  78   control_.set_size (4);
  79 }
  80
  81 void
  82 Bezier::calc (int steps)
  83 {
  84   steps = steps >? 10;
  85   curve_.set_size (steps);
  86   Real dt = 1.0 / curve_.size ();
  87   Offset c = 3.0 * (control_[1] - control_[0]);
  88   Offset b = 3.0 * (control_[2] - control_[1]) - c;
  89   Offset a = control_[3] - (control_[0] + c + b);
  90   Real t = 0.0;
  91   for (int i = 0; i < curve_.size (); i++ )
  92     {
  93       curve_[i] = ((a * t + b) * t + c) * t + control_[0];
  94       t += dt;
  95     }
  96 }
  97
  98 void
  99 Bezier::print () const
 100 {
 101 #ifndef NPRINT
 102   if (check_debug && !monitor->silent_b ("Bezier_controls"))
 103     {
 104       if (control_[1].length ())
 105         {
 106           cout << "Bezier\n";
 107           cout << "Controls:  ";
 108           for (int i=0; i < control_.size (); i++)
 109             cout << control_[i].str () << ", ";
 110 //        cout << "\n";
 111         }
 112     }
 113 #endif
 114 }
 115
 116 void
 117 Bezier::set (Array<Offset> points)
 118 {
 119   assert (points.size () == 4);
 120   control_ = points;
 121 }
 122
 123 Real
 124 Bezier::y (Real x)
 125 {
 126   // ugh
 127   // bounds func should be templatised to take array of offsets too?
 128   Array<Real> positions;
 129   for (int i = 0; i < curve_.size (); i++)
 130     positions.push (curve_[i][X_AXIS]);
 131
 132   Slice slice = get_bounds_slice (positions, x);
 133   // ugh
 134   Offset z1 = curve_[0 >? slice[BIGGER] - 1];
 135   Offset z2 = curve_[1 >? slice[BIGGER]];
 136   Real multiplier = (x - z2[X_AXIS]) / (z1[X_AXIS] - z2[X_AXIS]);
 137   Real y = z1[Y_AXIS] * multiplier + (1.0 - multiplier) * z2[Y_AXIS];
 138
 139   return y;
 140 }
 141
 142
 143 Bezier_bow::Bezier_bow (Paper_def* paper_l)
 144 {
 145   paper_l_ = paper_l;
 146   return_.set_size (4);
 147 }
 148
 149 void
 150 Bezier_bow::blow_fit ()
 151 {
 152   Real dy1 = check_fit_f ();
 153   if (!dy1)
 154     return;
 155
 156   // be careful not to take too big step
 157   Real f = 0.3;
 158   Real h1 = dy1 * f;
 159   control_[1][Y_AXIS] += h1;
 160   control_[2][Y_AXIS] += h1;
 161   return_[1][Y_AXIS] += h1;
 162   return_[2][Y_AXIS] += h1;
 163
 164   calc_bezier ();
 165   Real dy2 = check_fit_f ();
 166   if (!dy2)
 167     return;
 168
 169 #ifndef STANDALONE
 170   Real internote_f = paper_l_->get_realvar (interline_scm_sym)/2.0;
 171 #else
 172   Real internote_f = STAFFHEIGHT / 8;
 173 #endif
 174
 175   Real epsilon = internote_f / 4;
 176   if (abs (dy2 - dy1) < epsilon)
 177     return;
 178
 179   /*
 180     Assume
 181       dy = B (h)
 182     with
 183       B (h) = a * h + b;
 184
 185     Then we get for h : B (h) = 0
 186
 187      B(0)  = dy1 = a * 0 + b   =>   b = dy1
 188      B(h1) = dy2 = a * h1 + b  =>   a * f * dy1 + b = dy2
 189
 190          =>
 191
 192      a * dy1 / 2 + dy1 = dy2  =>  a = (dy2 - dy1) / (f * dy1)
 193    */
 194
 195   Real a = (dy2 - dy1) / (f * dy1);
 196   Real b = dy1;
 197   Real h = -b / a;
 198
 199   if (sign (h) != sign (h1))
 200     return;
 201
 202   if (sign (h) != sign (h1))
 203     return;
 204
 205   control_[1][Y_AXIS] += -h1 +h;
 206   control_[2][Y_AXIS] += -h1 +h;
 207   return_[1][Y_AXIS] += -h1 +h;
 208   return_[2][Y_AXIS] += -h1 +h;
 209 }
 210
 211 void
 212 Bezier_bow::calc_bezier ()
 213 {
 214   Real s = sqrt (control_[3][X_AXIS] * control_[3][X_AXIS]
 215     + control_[1][Y_AXIS] * control_[2][Y_AXIS]);
 216 #ifndef STANDALONE
 217   Real internote = paper_l_->get_realvar (interline_scm_sym)/2.0;
 218 #else
 219   Real internote = STAFFHEIGHT / 8;
 220 #endif
 221   int steps = (int)rint (s / internote);
 222   Bezier::calc (steps);
 223 }
 224
 225 Real
 226 Bezier_bow::calc_f (Real height)
 227 {
 228   transform ();
 229   calc_default (height);
 230
 231   calc_bezier ();
 232
 233   Real dy = check_fit_f ();
 234   calc_return (0, 0);
 235
 236   transform_back ();
 237   return dy;
 238 }
 239
 240 void
 241 Bezier_bow::calc ()
 242 {
 243 #ifndef NPRINT
 244 //  if (check_debug && !monitor->silent_b ("Bezier_bow_controls"))
 245   if (check_debug && !(monitor->silent_b ("Bezier_controls")
 246     && monitor->silent_b ("Bezier_bow_controls")))
 247     {
 248       cout << "Before transform*********\n";
 249       print ();
 250       cout << "************************\n";
 251     }
 252 #endif
 253   transform ();
 254   print ();
 255
 256   calc_controls ();
 257
 258   /*
 259     duh, this is crude (control-points)
 260     perhaps it's even better to check the amount of blow_fit ()
 261    */
 262   for (int i=0; i < control_.size (); i++)
 263     {
 264       Real y = control_[i][Y_AXIS];
 265       curve_extent_drul_[Y].unite (Interval (y, y));
 266       Real x = control_[i][X_AXIS];
 267       curve_extent_drul_[X].unite (Interval (x, x));
 268     }
 269
 270   print ();
 271   transform_back ();
 272 #ifndef NPRINT
 273 //  if (check_debug && !monitor->silent_b ("Bezier_bow_controls"))
 274   if (check_debug && !(monitor->silent_b ("Bezier_controls")
 275     && monitor->silent_b ("Bezier_bow_controls")))
 276     {
 277       cout << "After transform*********\n";
 278       print ();
 279       cout << "************************\n";
 280     }
 281 #endif
 282 }
 283
 284 /*
 285   [TODO]
 286     * see if it works
 287     * document in Documentation/fonts.tex
 288  */
 289
 290 /*
 291   Clipping
 292
 293   This function tries to address two issues:
 294     * the tangents of the slur should always point inwards
 295       in the actual slur, i.e.  *after rotating back*.
 296
 297     * slurs shouldn't be too high
 298       let's try : h <= 1.2 b && h <= 3 staffheight?
 299
 300   We could calculate the tangent of the bezier curve from
 301   both ends going inward, and clip the slur at the point
 302   where the tangent (after rotation) points up (or inward
 303   with a certain maximum angle).
 304
 305   However, we assume that real clipping is not the best
 306   answer.  We expect that moving the outer control point up
 307   if the slur becomes too high will result in a nicer slur
 308   after recalculation.
 309
 310   Knowing that the tangent is the line through the first
 311   two control points, we'll clip (move the outer control
 312   point upwards) too if the tangent points outwards.
 313  */
 314
 315 bool
 316 Bezier_bow::calc_clipping ()
 317 {
 318 #ifndef STANDALONE
 319   Real clip_height = paper_l_->get_var ("slur_clip_height");
 320   Real clip_ratio = paper_l_->get_var ("slur_clip_ratio");
 321   Real clip_angle = paper_l_->get_var ("slur_clip_angle");
 322 #else
 323   Real staffsize_f = STAFFHEIGHT;
 324   Real clip_height = 3.0 * staffsize_f;
 325   Real clip_ratio = 1.2;
 326   Real clip_angle = 100;
 327 #endif
 328
 329   Real b = control_[3][X_AXIS] - control_[0][X_AXIS];
 330   Real clip_h = clip_ratio * b <? clip_height;
 331   Real begin_h = control_[1][Y_AXIS] - control_[0][Y_AXIS];
 332   Real end_h = control_[2][Y_AXIS] - control_[3][Y_AXIS];
 333   Real begin_dy = 0 >? begin_h - clip_h;
 334   Real end_dy = 0 >? end_h - clip_h;
 335
 336   Real pi = M_PI;
 337   Real begin_alpha = (control_[1] - control_[0]).arg () + dir_ * alpha_;
 338   Real end_alpha = pi -  (control_[2] - control_[3]).arg () - dir_ * alpha_;
 339
 340   Real max_alpha = clip_angle / 90 * pi / 2;
 341   if ((begin_dy < 0) && (end_dy < 0)
 342     && (begin_alpha < max_alpha) && (end_alpha < max_alpha))
 343     return false;
 344
 345   transform_back ();
 346
 347   bool again = true;
 348
 349   if ((begin_dy > 0) || (end_dy > 0))
 350     {
 351       Real dy = (begin_dy + end_dy) / 4;
 352       dy *= cos (alpha_);
 353       encompass_[0][Y_AXIS] += dir_ * dy;
 354       encompass_[encompass_.size () - 1][Y_AXIS] += dir_ * dy;
 355     }
 356   else
 357     {
 358       //ugh
 359       Real c = 0.4;
 360       if (begin_alpha >= max_alpha)
 361         begin_dy = 0 >? c * begin_alpha / max_alpha * begin_h;
 362       if (end_alpha >= max_alpha)
 363         end_dy = 0 >? c * end_alpha / max_alpha * end_h;
 364
 365       encompass_[0][Y_AXIS] += dir_ * begin_dy;
 366       encompass_[encompass_.size () - 1][Y_AXIS] += dir_ * end_dy;
 367
 368       Offset delta = encompass_[encompass_.size () - 1] - encompass_[0];
 369       alpha_ = delta.arg ();
 370     }
 371
 372   transform ();
 373
 374   return again;
 375 }
 376
 377 void
 378 Bezier_bow::calc_controls ()
 379 {
 380   for (int i = 0; i < 3; i++)
 381     {
 382       if (i && !calc_clipping ())
 383         return;
 384
 385       /*
 386         why do we always recalc from 0?
 387         shouldn't calc_f () be used (too), rather than blow_fit () (only)?
 388        */
 389       calc_default (0);
 390       calc_bezier ();
 391
 392       if (check_fit_bo ())
 393         {
 394           calc_return (0, 0);
 395           return;
 396         }
 397       calc_tangent_controls ();
 398
 399       blow_fit ();
 400       // ugh
 401       blow_fit ();
 402     }
 403 }
 404
 405 void
 406 Bezier_bow::calc_return (Real begin_alpha, Real end_alpha)
 407 {
 408 #ifndef STANDALONE
 409   Real thick = paper_l_->get_var ("slur_thickness");
 410 #else
 411   Real thick = 1.8 * 0.4 PT;
 412 #endif
 413
 414   return_[0] = control_[3];
 415   return_[3] = control_[0];
 416
 417   return_[1] = control_[2] - thick * complex_exp (Offset (0, 90 + end_alpha));
 418   return_[2] = control_[1]
 419     - thick * complex_exp (Offset (0, 90 - begin_alpha));
 420 }
 421
 422 /*
 423  See Documentation/fonts.tex
 424  */
 425 void
 426 Bezier_bow::calc_tangent_controls ()
 427 {
 428   Offset ijk_p (control_[3][X_AXIS] / 2, control_[1][Y_AXIS]);
 429   BEZIER_BOW_DOUT << "ijk: " << ijk_p[X_AXIS] << ", " << ijk_p[Y_AXIS] << endl;
 430
 431   Real default_rc = ijk_p[Y_AXIS] / ijk_p[X_AXIS];
 432
 433   int begin_disturb = encompass_.largest_disturbing ();
 434   Offset begin_p = begin_disturb ? Offset (encompass_[begin_disturb][X_AXIS],
 435     encompass_[begin_disturb][Y_AXIS]) : ijk_p;
 436   Real begin_rc = begin_p[Y_AXIS] / begin_p[X_AXIS];
 437   if (default_rc > begin_rc)
 438     {
 439       begin_p = ijk_p;
 440       begin_rc = default_rc;
 441     }
 442
 443   Curve reversed;
 444   reversed.set_size (encompass_.size ());
 445   Real b = control_[3][X_AXIS];
 446   for (int i = 0; i < encompass_.size (); i++ )
 447     {
 448       //       b     1  0
 449       // r  =     -        *  c
 450       //       0     0 -1
 451       reversed[i][X_AXIS] = b - encompass_[encompass_.size () - i - 1][X_AXIS];
 452       reversed[i][Y_AXIS] = encompass_[encompass_.size () - i - 1][Y_AXIS];
 453     }
 454
 455   int end_disturb = reversed.largest_disturbing ();
 456   end_disturb = end_disturb ? encompass_.size () - end_disturb - 1 : 0;
 457   Offset end_p = end_disturb ? Offset (encompass_[end_disturb][X_AXIS],
 458     encompass_[end_disturb][Y_AXIS]) : ijk_p;
 459   Real end_rc = end_p[Y_AXIS] / (control_[3][X_AXIS] - end_p[X_AXIS]);
 460   if (default_rc > end_rc)
 461     {
 462       end_p = ijk_p;
 463       end_rc = default_rc;
 464     }
 465   BEZIER_BOW_DOUT << "begin " << begin_p[X_AXIS] << ", " << begin_p[Y_AXIS] << endl;
 466   BEZIER_BOW_DOUT << "end " << end_p[X_AXIS] << ", " << end_p[Y_AXIS] << endl;
 467
 468   Real height =control_[1][Y_AXIS];
 469   for (int i = 0; i < encompass_.size (); i++ )
 470     height = height >? encompass_[i][Y_AXIS];
 471
 472   // emperic computer science:
 473   //   * tangents somewhat steeper than minimal line
 474 #ifndef STANDALONE
 475   Real internote = paper_l_->get_realvar (interline_scm_sym)/2.0;
 476   Real rc_correct = paper_l_->get_var ("slur_rc_factor");
 477 #else
 478   Real internote = STAFFHEIGHT / 8;
 479   Real rc_correct = 2.4;
 480 #endif
 481
 482   begin_rc *= rc_correct;
 483   end_rc *= rc_correct;
 484   Real rc1 = begin_rc;
 485   Real rc2 = -end_rc;
 486
 487   Real begin_alpha = atan (begin_rc);
 488   Real end_alpha = atan (-end_rc);
 489   Real theta = (begin_alpha - end_alpha) / 2;
 490
 491   Real epsilon = internote / 5;
 492
 493   // if we have two disturbing points, have height line through those...
 494   if (!((abs (begin_p[X_AXIS] - end_p[X_AXIS]) < epsilon)
 495     && (abs (begin_p[Y_AXIS] - end_p[Y_AXIS]) < epsilon)))
 496       theta = atan (end_p[Y_AXIS] - begin_p[Y_AXIS]) / (end_p[X_AXIS] - begin_p[X_AXIS]);
 497
 498   Real rc3 = tan (theta);
 499   // ugh: be less steep
 500   rc3 /= 2*rc_correct;
 501
 502   Real c2 = -rc2 * control_[3][X_AXIS];
 503   Real c3 = begin_p[Y_AXIS] > end_p[Y_AXIS] ? begin_p[Y_AXIS]
 504     - rc3 * begin_p[X_AXIS] : end_p[Y_AXIS] - rc3 * end_p[X_AXIS];
 505
 506   BEZIER_BOW_DOUT << "y1 = " << rc1 << " x + 0" << endl;
 507   BEZIER_BOW_DOUT << "y2 = " << rc2 << " x + " << c2 << endl;
 508   BEZIER_BOW_DOUT << "y3 = " << rc3 << " x + " << c3 << endl;
 509   control_[1][X_AXIS] = c3 / (rc1 - rc3);
 510   control_[1][Y_AXIS] = rc1 * control_[1][X_AXIS];
 511   control_[2][X_AXIS] = (c3 - c2) / (rc2 - rc3);
 512   BEZIER_BOW_DOUT << "c2[X_AXIS] = " << control_[2][X_AXIS] << endl;
 513   BEZIER_BOW_DOUT << "(c3 - c2) = " << (c3 - c2) << endl;
 514   BEZIER_BOW_DOUT << "(rc2 - rc3) = " << (rc2 - rc3) << endl;
 515   control_[2][Y_AXIS] = rc2 * control_[2][X_AXIS] + c2;
 516   BEZIER_BOW_DOUT << "c2[Y_AXIS]" << control_[2][Y_AXIS] << endl;
 517
 518   calc_return (begin_alpha, end_alpha);
 519 }
 520
 521 bool
 522 Bezier_bow::check_fit_bo ()
 523 {
 524   for (int i = 1; i < encompass_.size () - 1; i++)
 525     if ((encompass_[i][X_AXIS] > encompass_[0][X_AXIS])
 526       && (encompass_[i][X_AXIS] < encompass_[encompass_.size () -1][X_AXIS]))
 527       if (encompass_[i][Y_AXIS] > y (encompass_[i][X_AXIS]))
 528         return false;
 529   return true;
 530 }
 531
 532 Real
 533 Bezier_bow::check_fit_f ()
 534 {
 535   Real dy = 0;
 536   for (int i = 1; i < encompass_.size () - 1; i++)
 537     if ((encompass_[i][X_AXIS] > encompass_[0][X_AXIS])
 538       && (encompass_[i][X_AXIS] < encompass_[encompass_.size () -1][X_AXIS]))
 539       dy = dy >? (encompass_[i][Y_AXIS] - y (encompass_[i][X_AXIS]));
 540   return dy;
 541 }
 542
 543 void
 544 Bezier_bow::print () const
 545 {
 546 #ifndef NPRINT
 547   Bezier::print ();
 548   if (check_debug && !monitor->silent_b ("Bezier_bow_controls"))
 549     {
 550       cout << "Bezier_bow\n";
 551       cout << "Encompass: ";
 552       for (int i=0; i < encompass_.size (); i++)
 553         cout << encompass_[i].str () << ", ";
 554 //      cout << "\n";
 555     }
 556 #endif
 557 }
 558
 559 void
 560 Bezier_bow::set (Array<Offset> points, int dir)
 561 {
 562   dir_ = dir;
 563   encompass_ = points;
 564 }
 565
 566 void
 567 Bezier_bow::transform ()
 568 {
 569   origin_ = encompass_[0];
 570   encompass_.translate (-origin_);
 571
 572   Offset delta = encompass_[encompass_.size () - 1] - encompass_[0];
 573   alpha_ = delta.arg ();
 574
 575   encompass_.rotate (-alpha_);
 576
 577   if (dir_ == DOWN)
 578     encompass_.flipy ();
 579 }
 580
 581 void
 582 Bezier_bow::transform_back ()
 583 {
 584   if (dir_ == DOWN)
 585     {
 586       control_.flipy ();
 587       return_.flipy ();
 588       encompass_.flipy ();
 589     }
 590
 591   control_.rotate (alpha_);
 592   control_.translate (origin_);
 593
 594   return_.rotate (alpha_);
 595   return_.translate (origin_);
 596
 597   encompass_.rotate (alpha_);
 598   encompass_.translate (origin_);
 599 }
 600
 601 /*
 602  See Documentation/fonts.tex
 603  */
 604 void
 605 Bezier_bow::calc_default (Real h)
 606 {
 607   Real pi = M_PI;
 608 #ifndef STANDALONE
 609   Real height_limit = paper_l_->get_var ("slur_height_limit");
 610   Real ratio = paper_l_->get_var ("slur_ratio");
 611 #else
 612   Real staffsize_f = STAFFHEIGHT;
 613   Real height_limit = staffsize_f;
 614   Real ratio = 1.0/3.0;
 615 #endif
 616
 617   Real alpha = height_limit * 2.0 / pi;
 618   Real beta = pi * ratio / (2.0 * height_limit);
 619
 620   Offset delta (encompass_[encompass_.size () - 1][X_AXIS]
 621     - encompass_[0][X_AXIS], 0);
 622   Real b = delta.length ();
 623   Real indent = alpha * atan (beta * b);
 624   Real height = indent + h;
 625
 626   Array<Offset> control;
 627   control.push (Offset (0, 0));
 628   control.push (Offset (indent, height));
 629   control.push (Offset (b - indent, height));
 630   control.push (Offset (b, 0));
 631   Bezier::set (control);
 632 }
 633