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