lily/bezier-bow.cc

   1 /*
   2   bezier.cc -- implement Bezier and Bezier_bow
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1998--2000 Jan Nieuwenhuizen <janneke@gnu.org>
   7 */
   8
   9 #include <math.h>
  10 #include "bezier-bow.hh"
  11 #include "misc.hh"
  12 #include "bezier.hh"
  13 #include "dimensions.hh"
  14 #include "direction.hh"
  15 #include "debug.hh"
  16 #include "main.hh"
  17 #include "lily-guile.hh"
  18
  19 void
  20 flipy (Array<Offset>  &c)
  21 {
  22   for (int i = c.size (); i--;)
  23     c[i][Y_AXIS] = - c[i][Y_AXIS];
  24 }
  25
  26 void
  27 rotate (Array<Offset> &c, Real phi)
  28 {
  29   Offset rot (complex_exp (Offset (0, phi)));
  30   for (int i = 0; i < c.size (); i++)
  31     c[i] = complex_multiply (rot, c[i]);
  32 }
  33
  34 void
  35 translate (Array<Offset> &c, Offset o)
  36 {
  37   for (int i = 0; i < c.size (); i++)
  38     c[i] += o;
  39 }
  40
  41
  42 Bezier_bow::Bezier_bow (Array<Offset> points, Direction dir)
  43 {
  44   dir_ = dir;
  45   encompass_ = points;
  46   to_canonic_form ();
  47
  48   rc_factor_ = 1.0;
  49   height_limit_ = 1.0;
  50   ratio_ = 1.0;
  51 }
  52
  53 static Real
  54 default_height (Real len)
  55 {
  56   // assume 20pt staff
  57   // see fonts.doc
  58   Real staff_space = 5.0;
  59   Real h_inf = 2.0* staff_space;
  60   Real r_0 = 0.33;
  61   return h_inf * 2.0 / M_PI * atan ( M_PI * r_0 / (2.0 * h_inf) * len);
  62 }
  63
  64 void
  65 Bezier_bow::blow_fit ()
  66 {
  67   Real len = curve_.control_[3][X_AXIS];
  68   Real h = curve_.control_[1][Y_AXIS] * fit_factor () / len;
  69   curve_.control_[1][Y_AXIS] = h * len;
  70   curve_.control_[2][Y_AXIS] = h * len;
  71   curve_.check_sanity ();
  72 }
  73
  74 void
  75 Bezier_bow::de_uglyfy ()
  76 {
  77   Real len = curve_.control_[3][X_AXIS] ;
  78   Real ff = fit_factor ();
  79   for (int i = 1; i < 3; i++)
  80     {
  81       Real ind = abs (curve_.control_[(i-1)*3][X_AXIS]
  82                       - curve_.control_[i][X_AXIS]) / len;
  83       Real h = curve_.control_[i][Y_AXIS] * ff / len;
  84
  85       // ugh. Unhardcode this
  86 #if 0
  87       // Too crude.
  88       if (h > 4 * ind)
  89         {
  90           h = 4* ind;
  91         }
  92 #else
  93       Real f = default_height (len) / len;
  94       if (h > 2.0 * f)
  95         {
  96           h = 2.0 * f;
  97         }
  98 #endif
  99
 100       if (h > 0.8 + -2 * ind)
 101         {
 102           h = 0.8 - 2  *ind;
 103         }
 104
 105       curve_.control_[i][Y_AXIS] = h * len;
 106     }
 107
 108   curve_.check_sanity ();
 109 }
 110
 111 Real
 112 Bezier_bow::calc_enclosed_area_f () const
 113 {
 114   Real a = 0;
 115   for (int i=0; i < encompass_.size (); i++)
 116     {
 117       Interval x;
 118       Interval y;
 119       if (i == 0)
 120         {
 121           x = Interval (0, encompass_[1][X_AXIS] / 2);
 122           y = Interval (0,
 123                         curve_.get_other_coordinate (X_AXIS,
 124                                                      encompass_[1][X_AXIS]
 125                                                      / 2));
 126         }
 127       else if (i == encompass_.size () - 1)
 128         {
 129           x = Interval ((encompass_[i-1][X_AXIS] + encompass_[i][X_AXIS])/2,
 130                         encompass_[i][X_AXIS]);
 131           y = Interval (0,
 132                         (curve_.get_other_coordinate (X_AXIS,
 133                                                       (x[MIN] + x[MAX]) / 2)));
 134         }
 135       else
 136         {
 137           x = Interval ((encompass_[i-1][X_AXIS] + encompass_[i][X_AXIS]) / 2,
 138                         (encompass_[i][X_AXIS] + encompass_[i+1][X_AXIS]) / 2);
 139           y = Interval (encompass_[i][Y_AXIS],
 140                         (curve_.get_other_coordinate (X_AXIS, x[MIN])
 141                          + curve_.get_other_coordinate (X_AXIS,
 142                                                         (x[MIN] + x[MAX]) / 2)
 143                          + curve_.get_other_coordinate (X_AXIS, x[MAX])) / 3);
 144         }
 145
 146       Real da = x.length () * y.length ();
 147       a += da;
 148     }
 149   return a;
 150 }
 151
 152 Array<Offset>
 153 Bezier_bow::area_gradient_offset_arr ()
 154 {
 155   Real len = curve_.control_[3][X_AXIS];
 156   Real area = calc_enclosed_area_f ();
 157
 158   Real grow = len / 10.0;
 159   Array<Offset> da (2);
 160   for (int i=1; i < 3; i++)
 161     {
 162       for (Axis a=X_AXIS; a < NO_AXES; incr (a))
 163         {
 164           Real r = curve_.control_[i][a];
 165           curve_.control_[i][a] += grow;
 166           da[i-1][a] = (calc_enclosed_area_f () - area) / grow;
 167
 168           curve_.control_[i][a] = r;
 169         }
 170     }
 171   return da;
 172 }
 173
 174 void
 175 Bezier_bow::minimise_enclosed_area ()
 176 {
 177   Real len = curve_.control_[3][X_AXIS];
 178   Real beautiful = len * default_height (len) / 2.0;
 179
 180   DEBUG_OUT << to_str ("Beautiful: %f\n", beautiful);
 181   DEBUG_OUT << to_str ("Length: %f\n", len);
 182   int steps=2;
 183   for (int i=0; i < steps; i++)
 184     {
 185       Real ff = fit_factor ();
 186       if (!ff)
 187         break;
 188
 189       DEBUG_OUT << to_str ("FitFac: %f\n", ff);
 190
 191       // slur must be higher at every point
 192       if (ff > 1.01)
 193         {
 194           blow_fit ();
 195           DEBUG_OUT << to_str ("Blown area: %f\n", calc_enclosed_area_f ());
 196         }
 197       else
 198           DEBUG_OUT << to_str ("Init area: %f\n", calc_enclosed_area_f ());
 199
 200       Real area = calc_enclosed_area_f ();
 201
 202
 203       if (area <= beautiful)
 204         break;
 205
 206       Array<Offset> da = area_gradient_offset_arr ();
 207
 208       /*
 209         Urg: empiric cs
 210              Small slurs are easily too asymmetric,
 211              while big slurs are too symmetric
 212
 213              This makes short slurs strictly x-bound,
 214              long slurs become y-bound.
 215        */
 216       Real ypct = 0.50;
 217       //Real xpct = (0.07 * len * len / 1000.0) <? 0.80;
 218       Real xpct = (0.1 * len * len * len / 100000.0) <? 0.80;
 219
 220       Real yu = (abs (curve_.control_[1][Y_AXIS] / da[0][Y_AXIS])
 221                  <? abs (curve_.control_[2][Y_AXIS] / da[1][Y_AXIS]))
 222         * ypct;
 223       Real xu = (abs (curve_.control_[1][X_AXIS] / da[0][X_AXIS])
 224                  <? abs ((curve_.control_[3][X_AXIS]
 225                              - curve_.control_[2][X_AXIS]) / da[1][X_AXIS]))
 226         * xpct;
 227       Real u = yu <? xu;
 228       DEBUG_OUT << to_str ("u (xu, yu): %f (%f, %f)\n", u, xu, yu);
 229       DEBUG_OUT << to_str ("pct (x, y): (%f, %f)\n", xpct, ypct);
 230
 231       DEBUG_OUT << to_str ("da1: (%f, %f)\n", da[0][X_AXIS], da[0][Y_AXIS]);
 232       DEBUG_OUT << to_str ("da2: (%f, %f)\n", da[1][X_AXIS], da[1][Y_AXIS]);
 233
 234       curve_.control_[1] -= da[0] * u;
 235       curve_.control_[2] -= da[1] * u;
 236     }
 237
 238
 239   if (fit_factor () > 1.5)
 240     blow_fit ();
 241
 242   DEBUG_OUT << to_str ("Exarea: %f\n", calc_enclosed_area_f ());
 243   Real area = calc_enclosed_area_f ();
 244   /*
 245     Slurs that fit beautifully are not ugly
 246    */
 247   if (area > beautiful)
 248     {
 249       DEBUG_OUT << "DE-UGLYFY\n";
 250       de_uglyfy ();
 251     }
 252
 253 }
 254
 255 void
 256 Bezier_bow::calculate ()
 257 {
 258   calc_default ();
 259   if (fit_factor () > 1.0)
 260     {
 261       //    calc_tangent_controls ();
 262       // blow_fit ();
 263       minimise_enclosed_area ();
 264     }
 265 }
 266
 267
 268
 269 Bezier
 270 Bezier_bow::get_curve ()const
 271 {
 272   Bezier rv = curve_;
 273   if (dir_ == DOWN)
 274     {
 275       rv.flip (Y_AXIS);
 276     }
 277
 278   rv.rotate (alpha_);
 279   rv.translate (origin_);
 280
 281   return rv;
 282 }
 283
 284 static Real const FUDGE = 1e-8;
 285
 286 /*
 287   This function calculates 2 center control points,
 288   based on lines through c_0 --> left disturbing
 289   and c_3--> right disturbing encompass points.
 290
 291   See Documentation/fonts.tex
 292  */
 293 void
 294 Bezier_bow::calc_tangent_controls ()
 295 {
 296   Real b = curve_.control_[3][X_AXIS];
 297   Real h = curve_.control_[1][Y_AXIS];
 298
 299
 300   Drul_array<Offset> disturb;
 301   Drul_array<Real> maxtan;
 302   maxtan[LEFT]  = maxtan[RIGHT] = h/(b/2);
 303   disturb[LEFT]  = disturb[RIGHT] =   Offset (b / 2, h);
 304
 305   for (int i = 1; i < encompass_.size () -1; i++)
 306     {
 307       Real y= encompass_[i][Y_AXIS];
 308       if (y> 0)
 309         {
 310           Real x = encompass_[i][X_AXIS];
 311
 312           Direction d = LEFT;
 313           do
 314             {
 315               // 1 if d == LEFT
 316               int k = (1 - d)/2;
 317               Real tan = y /  ((1-k)* b - d * x);
 318
 319               if (tan > maxtan[d])
 320                 {
 321                   maxtan[d] = tan;
 322                   disturb[d] = Offset (x,y);
 323                 }
 324             }
 325           while (flip (&d)!=LEFT);
 326         }
 327     }
 328
 329   for (int i = 0; i < encompass_.size (); i++ )
 330     h = h >? encompass_[i][Y_AXIS];
 331
 332   /*
 333     The curve will always be under line between curve_.control_0 -> curve_.control_1, so
 334     make it extra steep by slur_rc_factor
 335   */
 336
 337
 338   Drul_array<Real> angles;
 339   Direction d = LEFT;
 340   do
 341     {
 342       maxtan[d] *= -d * rc_factor_;
 343       angles[d] = atan (maxtan[d]);
 344     }
 345   while (flip(&d) != LEFT);
 346
 347   Real rc3 = 0.0;
 348
 349   /*
 350     if we have two disturbing points, have line through those...
 351     in order to get a sane line, make sure points are reasonably far apart
 352     X distance must be reasonably(!) big (division)
 353    */
 354   if (abs (disturb[LEFT][X_AXIS] - disturb[RIGHT][X_AXIS]) > FUDGE)
 355     rc3 = (disturb[RIGHT][Y_AXIS] - disturb[LEFT][Y_AXIS]) / (disturb[RIGHT][X_AXIS] - disturb[LEFT][X_AXIS]);
 356
 357   else
 358     rc3 = tan ((angles[LEFT] - angles[RIGHT]) / 2);
 359
 360
 361   // ugh: be less steep
 362   rc3 /= 2*rc_factor_;
 363
 364
 365   Real c2 = -maxtan[RIGHT] * curve_.control_[3][X_AXIS];
 366
 367   // use highest because rc3 is damped.
 368   Real maxy = disturb[LEFT][Y_AXIS] >? disturb[RIGHT][Y_AXIS];
 369   Real c3 = disturb[LEFT][Y_AXIS] > disturb[RIGHT][Y_AXIS] ?
 370     maxy - rc3 * disturb[LEFT][X_AXIS] :
 371     maxy - rc3 * disturb[RIGHT][X_AXIS];
 372
 373   curve_.control_[1][X_AXIS] = c3 / (maxtan[LEFT] - rc3);
 374   curve_.control_[1][Y_AXIS] = maxtan[LEFT] * curve_.control_[1][X_AXIS];
 375
 376   curve_.control_[2][X_AXIS] = (c3 - c2) / (maxtan[RIGHT] - rc3);
 377   curve_.control_[2][Y_AXIS] = maxtan[RIGHT] * curve_.control_[2][X_AXIS] + c2;
 378
 379
 380   curve_.check_sanity();
 381 }
 382
 383 /*
 384   max ( encompass.y / curve.y )
 385
 386  */
 387 Real
 388 Bezier_bow::fit_factor () const
 389 {
 390   Real x1 = encompass_[0][X_AXIS];
 391   Real x2 = encompass_.top ()[X_AXIS];
 392
 393   Real factor = 0.0;
 394   for (int i=1; i < encompass_.size ()-1; i++)
 395     {
 396       if (encompass_[i][X_AXIS] > x1 && encompass_[i][X_AXIS] < x2)
 397         {
 398          Real y = curve_.get_other_coordinate (X_AXIS, encompass_[i][X_AXIS]);
 399          if (y>0)
 400            {
 401              Real f = encompass_[i][Y_AXIS] / y;
 402              factor = factor >? f;
 403            }
 404         }
 405     }
 406
 407
 408   return factor;
 409 }
 410
 411
 412
 413
 414 void
 415 Bezier_bow::to_canonic_form ()
 416 {
 417   origin_ = encompass_[0];
 418   translate (encompass_,-origin_);
 419
 420   Offset delta = encompass_.top () - encompass_[0];
 421   alpha_ = delta.arg ();
 422
 423   rotate (encompass_, -alpha_);
 424   if (dir_ == DOWN)
 425     {
 426       flipy (encompass_);
 427     }
 428
 429   while (encompass_.size () > 1 && encompass_[1][X_AXIS] <= 0.0)
 430     {
 431       programming_error ("Degenerate slur: infinite steepness reqd");
 432       encompass_.del (1);
 433     }
 434
 435   Real l = encompass_.top ()[X_AXIS];
 436   while (encompass_.size () > 1 && encompass_.top (1)[X_AXIS] >= l)
 437     {
 438       programming_error ("Degenerate slur: infinite steepness reqd");
 439       encompass_.del (encompass_.size ()-2);
 440     }
 441 }
 442
 443
 444
 445 /*
 446  See Documentation/fonts.tex
 447  */
 448 void
 449 Bezier_bow::calc_default ()
 450 {
 451   Real pi = M_PI;
 452
 453   Real alpha = height_limit_ * 2.0 / pi;
 454   Real beta = pi * ratio_ / (2.0 * height_limit_);
 455
 456   Offset delta (encompass_.top ()[X_AXIS]
 457     - encompass_[0][X_AXIS], 0);
 458
 459   Real b = delta.length ();
 460   Real indent = alpha * atan (beta * b);
 461   Real height = indent;
 462
 463   curve_.control_ [0] = Offset (0, 0);
 464   curve_.control_ [1] = Offset (indent, height);
 465   curve_.control_ [2] = Offset (b - indent, height);
 466   curve_.control_ [3] = Offset (b, 0);
 467 }
 468
 469
 470
 471