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