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 SLUR_DOUT if (check_debug && !monitor->silent_b ("Slur")) cout
  19 #else
  20 #define SLUR_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 = 1; 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 = 1; 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 //  if (x <= curve_[0].x ())
  98 //    return curve_[0].y ();
  99   for (int i = 1; i < curve_.size (); i++ )
 100     {
 101       if (x < curve_[i].x () || (i == curve_.size () - 1))
 102         {
 103           Offset z1 = curve_[i-1];
 104           Offset z2 = curve_[i];
 105           Real multiplier = (x - z2.x ()) / (z1.x () - z2.x ());
 106           Real y = z1.y () * multiplier + (1.0 - multiplier) z2.y();
 107
 108           return y;
 109         }
 110     }
 111   assert (false);
 112   // silly c++
 113   return 0;
 114 }
 115
 116
 117 Bezier_bow::Bezier_bow (Paper_def* paper_l)
 118 {
 119   paper_l_ = paper_l;
 120   return_.set_size (4);
 121 }
 122
 123 void
 124 Bezier_bow::blow_fit ()
 125 {
 126   Real dy1 = check_fit_f ();
 127   if (!dy1)
 128     return;
 129
 130   // be careful not to take too big step
 131   Real f = 0.3;
 132   Real h1 = dy1 * f;
 133   control_[1].y () += h1;
 134   control_[2].y () += h1;
 135   return_[1].y () += h1;
 136   return_[2].y () += h1;
 137
 138   calc_bezier ();
 139   Real dy2 = check_fit_f ();
 140   if (!dy2)
 141     return;
 142
 143 #ifndef STANDALONE
 144   Real epsilon = paper_l_->rule_thickness ();
 145 #else
 146   Real epsilon = 1.5 * 0.4 PT;
 147 #endif
 148   if (abs (dy2 - dy1) < epsilon)
 149     return;
 150
 151   /*
 152     Assume
 153       dy = B (h)
 154     with
 155       B (h) = a * h + b;
 156
 157     Then we get for h : B (h) = 0
 158
 159      B(0)  = dy1 = a * 0 + b   =>   b = dy1
 160      B(h1) = dy2 = a * h1 + b  =>   a * f * dy1 + b = dy2
 161
 162          =>
 163
 164      a * dy1 / 2 + dy1 = dy2  =>  a = (dy2 - dy1) / (f * dy1)
 165    */
 166
 167   Real a = (dy2 - dy1) / (f * dy1);
 168   Real b = dy1;
 169   Real h = -b / a;
 170
 171   control_[1].y () += -h1 +h;
 172   control_[2].y () += -h1 +h;
 173   return_[1].y () += -h1 +h;
 174   return_[2].y () += -h1 +h;
 175 }
 176
 177 void
 178 Bezier_bow::calc_bezier ()
 179 {
 180   Real s = sqrt (control_[3].x () * control_[3].x ()
 181     + control_[1].y () * control_[2].y ());
 182 #ifndef STANDALONE
 183   Real internote = paper_l_->internote_f ();
 184 #else
 185   Real internote = STAFFHEIGHT / 8;
 186 #endif
 187   int steps = (int)rint (s / internote);
 188   Bezier::calc (steps);
 189 }
 190
 191 Real
 192 Bezier_bow::calc_f (Real height)
 193 {
 194   transform ();
 195   calc_default (height);
 196
 197   calc_bezier ();
 198
 199   Real dy = check_fit_f ();
 200   calc_return (0, 0);
 201
 202   transform_controls_back ();
 203   return dy;
 204 }
 205
 206 void
 207 Bezier_bow::calc ()
 208 {
 209   transform ();
 210   calc_default (0);
 211   calc_bezier ();
 212
 213   if (check_fit_bo ())
 214     calc_return (0, 0);
 215   else
 216     {
 217       calc_controls ();
 218       blow_fit ();
 219     }
 220
 221   transform_controls_back ();
 222 }
 223
 224 void
 225 Bezier_bow::calc_return (Real begin_alpha, Real end_alpha)
 226 {
 227 #ifndef STANDALONE
 228   Real thick = 1.8 * paper_l_->rule_thickness ();
 229 #else
 230   Real thick = 1.8 * 0.4 PT;
 231 #endif
 232
 233   return_[0] = control_[3];
 234   return_[3] = control_[0];
 235
 236   return_[1] = control_[2] - thick * complex_exp (Offset (0, 90 + end_alpha));
 237   return_[2] = control_[1]
 238     - thick * complex_exp (Offset (0, 90 - begin_alpha));
 239 }
 240
 241 /*
 242  [TODO]
 243  Document algorithm in:
 244  See Documentation/fonts.tex
 245  */
 246 void
 247 Bezier_bow::calc_controls ()
 248 {
 249   Offset ijk_p (control_[3].x () / 2, control_[1].y ());
 250   SLUR_DOUT << "ijk: " << ijk_p.x () << ", " << ijk_p.y () << endl;
 251
 252   Real default_rc = ijk_p.y () / ijk_p.x ();
 253
 254   int begin_disturb = encompass_.largest_disturbing ();
 255   Offset begin_p = begin_disturb ? Offset (encompass_[begin_disturb].x (),
 256     encompass_[begin_disturb].y ()) : ijk_p;
 257   Real begin_rc = begin_p.y () / begin_p.x ();
 258   if (default_rc > begin_rc)
 259     {
 260       begin_p = ijk_p;
 261       begin_rc = default_rc;
 262     }
 263
 264   Curve reversed;
 265   reversed.set_size (encompass_.size ());
 266   Real b = control_[3].x ();
 267   for (int i = 0; i < encompass_.size (); i++ )
 268     {
 269       //       b     1  0
 270       // r  =     -        *  c
 271       //       0     0 -1
 272       reversed[i].x () = b - encompass_[encompass_.size () - i - 1].x ();
 273       reversed[i].y () = encompass_[encompass_.size () - i - 1].y ();
 274     }
 275
 276   int end_disturb = reversed.largest_disturbing ();
 277   end_disturb = end_disturb ? encompass_.size () - end_disturb - 1 : 0;
 278   Offset end_p = end_disturb ? Offset (encompass_[end_disturb].x (),
 279     encompass_[end_disturb].y ()) : ijk_p;
 280   Real end_rc = end_p.y () / (control_[3].x () - end_p.x ());
 281   if (default_rc > end_rc)
 282     {
 283       end_p = ijk_p;
 284       end_rc = default_rc;
 285     }
 286   SLUR_DOUT << "begin " << begin_p.x () << ", " << begin_p.y () << endl;
 287   SLUR_DOUT << "end " << end_p.x () << ", " << end_p.y () << endl;
 288
 289   Real height =control_[1].y ();
 290   for (int i = 0; i < encompass_.size (); i++ )
 291     height = height >? encompass_[i].y ();
 292
 293   // emperic computer science:
 294   //   * tangents somewhat steeper than minimal line
 295   Real rc_correct = 2.4;
 296
 297   begin_rc *= rc_correct;
 298   end_rc *= rc_correct;
 299   Real rc1 = begin_rc;
 300   Real rc2 = -end_rc;
 301
 302   Real begin_alpha = atan (begin_rc);
 303   Real end_alpha = atan (-end_rc);
 304   Real theta = (begin_alpha - end_alpha) / 2;
 305
 306 #ifndef STANDALONE
 307   Real internote = paper_l_->internote_f ();
 308 #else
 309   Real internote = STAFFHEIGHT / 8;
 310 #endif
 311   Real epsilon = internote / 5;
 312
 313   // if we have two disturbing points, have height line through those...
 314   if (!((abs (begin_p.x () - end_p.x ()) < epsilon)
 315     && (abs (begin_p.y () - end_p.y ()) < epsilon)))
 316       theta = atan (end_p.y () - begin_p.y ()) / (end_p.x () - begin_p.x ());
 317
 318   Real rc3 = tan (theta);
 319   // ugh: be less steep
 320   rc3 /= 2*rc_correct;
 321
 322   Real c2 = -rc2 * control_[3].x ();
 323   Real c3 = begin_p.y () > end_p.y () ? begin_p.y ()
 324     - rc3 * begin_p.x () : end_p.y () - rc3 * end_p.x ();
 325
 326   SLUR_DOUT << "y1 = " << rc1 << " x + 0" << endl;
 327   SLUR_DOUT << "y2 = " << rc2 << " x + " << c2 << endl;
 328   SLUR_DOUT << "y3 = " << rc3 << " x + " << c3 << endl;
 329   control_[1].x () = c3 / (rc1 - rc3);
 330   control_[1].y () = rc1 * control_[1].x ();
 331   control_[2].x () = (c3 - c2) / (rc2 - rc3);
 332   SLUR_DOUT << "c2.x () = " << control_[2].x () << endl;
 333   SLUR_DOUT << "(c3 - c2) = " << (c3 - c2) << endl;
 334   SLUR_DOUT << "(rc2 - rc3) = " << (rc2 - rc3) << endl;
 335   control_[2].y () = rc2 * control_[2].x () + c2;
 336   SLUR_DOUT << "c2.y ()" << control_[2].y () << endl;
 337
 338   calc_return (begin_alpha, end_alpha);
 339 }
 340
 341 bool
 342 Bezier_bow::check_fit_bo ()
 343 {
 344   for (int i = 1; i < encompass_.size () - 1; i++)
 345     if (encompass_[i].y () > y (encompass_[i].x ()))
 346       return false;
 347   return true;
 348 }
 349
 350 Real
 351 Bezier_bow::check_fit_f ()
 352 {
 353   Real dy = 0;
 354   for (int i = 1; i < encompass_.size () - 1; i++)
 355     dy = dy >? (encompass_[i].y () - y (encompass_[i].x ()));
 356   return dy;
 357 }
 358
 359 void
 360 Bezier_bow::set (Array<Offset> points, int dir)
 361 {
 362   dir_ = dir;
 363   encompass_ = points;
 364 }
 365
 366 void
 367 Bezier_bow::transform ()
 368 {
 369   origin_ = encompass_[0];
 370   encompass_.translate (-origin_);
 371
 372   Offset delta = encompass_[encompass_.size () - 1] - encompass_[0];
 373
 374   alpha_ = delta.arg ();
 375   encompass_.rotate (-alpha_);
 376
 377   if (dir_ == DOWN)
 378     encompass_.flipy ();
 379 }
 380
 381 void
 382 Bezier_bow::transform_controls_back ()
 383 {
 384   // silly name; let's transform encompass back too
 385   // to allow recalculation without re-set()ting encompass array
 386   if (dir_ == DOWN)
 387     {
 388       control_.flipy ();
 389       return_.flipy ();
 390       encompass_.flipy ();
 391     }
 392
 393   control_.rotate (alpha_);
 394   control_.translate (origin_);
 395
 396   return_.rotate (alpha_);
 397   return_.translate (origin_);
 398
 399   encompass_.rotate (alpha_);
 400   encompass_.translate (origin_);
 401 }
 402
 403 /*
 404  See Documentation/fonts.tex
 405  */
 406 void
 407 Bezier_bow::calc_default (Real h)
 408 {
 409   Real pi = M_PI;
 410 #ifndef STANDALONE
 411   Real staffsize_f = paper_l_->get_var ("barsize");
 412 #else
 413   Real staffsize_f = STAFFHEIGHT;
 414 #endif
 415
 416   Real height_limit = staffsize_f;
 417   Real ratio = 1.0/3.0;
 418
 419   Real alpha = height_limit * 2.0 / pi;
 420   Real beta = pi * ratio / (2.0 * height_limit);
 421
 422   Offset delta (encompass_[encompass_.size () - 1].x ()
 423     - encompass_[0].x (), 0);
 424   Real b = delta.length ();
 425   Real indent = alpha * atan (beta * b);
 426   Real height = indent + h;
 427
 428   Array<Offset> control;
 429   control.push (Offset (0, 0));
 430   control.push (Offset (indent, height));
 431   control.push (Offset (b - indent, height));
 432   control.push (Offset (b, 0));
 433   Bezier::set (control);
 434 }
 435