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