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