From 8d95c70b50afc86c06096797b444c2be4a78b0f5 Mon Sep 17 00:00:00 2001 From: Mike Solomon Date: Thu, 25 Aug 2011 09:16:51 +0200 Subject: [PATCH] Fixes issue 1328. Finds the local minimum or maximum of a Bezier curve along the X axis in the range of an intersection and shifts intersecting curves up over this range plus slur padding. Adds default slur padding to all scripts, as this algorithm makes them almost just touch with the slur whereas the previous one already had a bit of padding built into it because it was a generous approximation. --- flower/include/polynomial.hh | 1 + flower/polynomial.cc | 26 ++++++++++++++ input/regression/slur-avoid.ly | 11 ++++++ lily/bezier.cc | 56 ++++++++++++++++++++++++++++++ lily/include/bezier.hh | 3 ++ lily/slur.cc | 63 ++++++++++++++++++---------------- scm/define-grobs.scm | 1 + scm/script.scm | 2 -- 8 files changed, 132 insertions(+), 31 deletions(-) create mode 100644 input/regression/slur-avoid.ly diff --git a/flower/include/polynomial.hh b/flower/include/polynomial.hh index f575be35fd..c58cb93500 100644 --- a/flower/include/polynomial.hh +++ b/flower/include/polynomial.hh @@ -44,6 +44,7 @@ struct Polynomial Real lc () const; void print () const; Real eval (Real) const; + Real minmax (Real, Real, bool) const; void print_sols (vector) const; void check_sols (vector) const; void check_sol (Real x) const; diff --git a/flower/polynomial.cc b/flower/polynomial.cc index 2cd0eaf2e0..05faf42097 100644 --- a/flower/polynomial.cc +++ b/flower/polynomial.cc @@ -61,6 +61,32 @@ Polynomial::multiply (const Polynomial &p1, const Polynomial &p2) return dest; } +Real +Polynomial::minmax (Real l, Real r, bool ret_max) const +{ + vector sols; + if (l > r) + { + programming_error ("left bound greater than right bound for polynomial minmax. flipping bounds."); + l = l + r; + r = l - r; + l = l - r; + } + + sols.push_back (eval (l)); + sols.push_back (eval (r)); + + Polynomial deriv (*this); + deriv.differentiate (); + vector maxmins = deriv.solve (); + for (vsize i = 0; i < maxmins.size (); i++) + if (maxmins[i] >= l && maxmins[i] <= r) + sols.push_back (eval (maxmins[i])); + vector_sort (sols, less ()); + + return ret_max ? sols.back () : sols[0]; +} + void Polynomial::differentiate () { diff --git a/input/regression/slur-avoid.ly b/input/regression/slur-avoid.ly new file mode 100644 index 0000000000..372b8c8fc7 --- /dev/null +++ b/input/regression/slur-avoid.ly @@ -0,0 +1,11 @@ + +\version "2.15.9" + +\header { + texidoc = "Slurs handle avoid objects better. +" +} + +{ + a'8 ( b''4 \fermata ) +} diff --git a/lily/bezier.cc b/lily/bezier.cc index f230d1057d..ce84ce8da8 100644 --- a/lily/bezier.cc +++ b/lily/bezier.cc @@ -81,6 +81,17 @@ Bezier::get_other_coordinate (Axis a, Real x) const return curve_coordinate (ts[0], other); } +vector +Bezier::get_other_coordinates (Axis a, Real x) const +{ + Axis other = other_axis (a); + vector ts = solve_point (a, x); + vector sols; + for (vsize i = 0; i < ts.size (); i++) + sols.push_back (curve_coordinate (ts[i], other)); + return sols; +} + Real Bezier::curve_coordinate (Real t, Axis a) const { @@ -202,6 +213,51 @@ Bezier::solve_point (Axis ax, Real coordinate) const return filter_solutions (sol); } +Real +Bezier::minmax (Axis ax, Real l, Real r, Direction d) const +{ + return minmax (ax, l, r, d, 0, 0); +} + +Real +Bezier::minmax (Axis axis, Real l, Real r, Direction d, vsize left_index, vsize right_index) const +{ + Axis other = other_axis (axis); + Interval lr (l, r); + Drul_array > sol; + Direction dir = LEFT; + do + { + Polynomial p (polynomial (axis)); + p.coefs_[0] -= lr[dir]; + + sol[dir] = filter_solutions (p.solve ()); + } + while (flip (&dir) != LEFT); + + if (!sol[LEFT].size () || !sol[RIGHT].size ()) + { + programming_error ("no solution found for Bezier intersection"); + return 0.0; + } + + Polynomial p (polynomial (other)); + + Drul_array indices(left_index, right_index); + do + { + vector_sort (sol[dir], less ()); + if (!Interval (0, sol[LEFT].size () - 1).contains (indices[dir])) + { + programming_error ("requested bezier solution outside range of solutions. defaulting to lowest solution."); + indices[dir] = 0; + } + } + while (flip (&dir) != LEFT); + + return p.minmax (sol[LEFT][indices[LEFT]], sol[RIGHT][indices[RIGHT]], d != LEFT); +} + /** Compute the bounding box dimensions in direction of A. */ diff --git a/lily/include/bezier.hh b/lily/include/bezier.hh index a144e4a755..839c8ddc8f 100644 --- a/lily/include/bezier.hh +++ b/lily/include/bezier.hh @@ -39,7 +39,10 @@ public: Bezier extract (Real, Real) const; Real get_other_coordinate (Axis a, Real x) const; + vector get_other_coordinates (Axis a, Real x) const; vector solve_point (Axis, Real coordinate) const; + Real minmax (Axis, Real, Real, Direction) const; + Real minmax (Axis, Real, Real, Direction, vsize, vsize) const; vector solve_derivative (Offset) const; Interval extent (Axis) const; Interval control_point_extent (Axis) const; diff --git a/lily/slur.cc b/lily/slur.cc index 32149e8412..964a4d091b 100644 --- a/lily/slur.cc +++ b/lily/slur.cc @@ -279,42 +279,47 @@ Slur::outside_slur_callback (SCM grob, SCM offset_scm) 0.0); yext.widen (slur_padding); - const Real EPS = 1e-3; - Interval bezext (curve.control_[0][X_AXIS], curve.control_[3][X_AXIS]); - bool consider[] = {false, false, false}; - Real ys[] = {0, 0, 0}; + Interval exts[] = {xext, yext}; bool do_shift = false; - - for (int d = LEFT, k = 0; d <= RIGHT; d++, k++) + Real EPS = 1.0e-5; + if (avoid == ly_symbol2scm ("outside")) { - Real x = xext.linear_combination ((Direction) d); - consider[k] = bezext.contains (x); - - if (consider[k]) + Direction d = LEFT; + do { - ys[k] - = (fabs (bezext[LEFT] - x) < EPS) - ? curve.control_[0][Y_AXIS] - : ((fabs (bezext[RIGHT] - x) < EPS) - ? curve.control_[3][Y_AXIS] - : curve.get_other_coordinate (X_AXIS, x)); - - /* Request shift if slur is contained script's Y, or if - script is inside slur and avoid == outside. */ - if (yext.contains (ys[k]) - || (dir * ys[k] > dir * yext[-dir] && avoid == ly_symbol2scm ("outside"))) - do_shift = true; + Real x = minmax (-d, xext[d], curve.control_[d == LEFT ? 0 : 3][X_AXIS] + -d * EPS); + Real y = curve.get_other_coordinate (X_AXIS, x); + do_shift = y == minmax (dir, yext[-dir], y); + if (do_shift) + break; } + while (flip (&d) != LEFT); } - - Real avoidance_offset = 0.0; - if (do_shift) + else { - for (int d = LEFT, k = 0; d <= RIGHT; d++, k++) - if (consider[k]) - avoidance_offset = dir * (max (dir * avoidance_offset, - dir * (ys[k] - yext[-dir] + dir * slur_padding))); + for (int a = X_AXIS; a < NO_AXES; a++) + { + Direction d = LEFT; + do + { + vector coords = curve.get_other_coordinates (Axis (a), exts[a][d]); + for (vsize i = 0; i < coords.size (); i++) + { + do_shift = exts[(a + 1) % NO_AXES].contains (coords[i]); + if (do_shift) + break; + } + if (do_shift) + break; + } + while (flip (&d) != LEFT); + if (do_shift) + break; + } } + + Real avoidance_offset = do_shift ? curve.minmax (X_AXIS, max (xext[LEFT], curve.control_[0][X_AXIS] + EPS), min (xext[RIGHT], curve.control_[3][X_AXIS] - EPS), dir) - yext[-dir] : 0.0; + return scm_from_double (offset + avoidance_offset); } diff --git a/scm/define-grobs.scm b/scm/define-grobs.scm index e1d076c296..3055af219b 100644 --- a/scm/define-grobs.scm +++ b/scm/define-grobs.scm @@ -1716,6 +1716,7 @@ (side-axis . ,Y) ;; padding set in script definitions. + (slur-padding . 0.2) (staff-padding . 0.25) (stencil . ,ly:script-interface::print) diff --git a/scm/script.scm b/scm/script.scm index 417df4cbee..4d6dc05a8e 100644 --- a/scm/script.scm +++ b/scm/script.scm @@ -175,7 +175,6 @@ . ( (script-stencil . (feta . ("uportato" . "dportato"))) (avoid-slur . around) - (slur-padding . 0.3) (padding . 0.45) (side-relative-direction . ,DOWN))) ("prall" @@ -300,7 +299,6 @@ (avoid-slur . around) (padding . 0.50) (direction . ,UP) - (slur-padding . 0.2) (staff-padding . 0.5))) ("trill" . ( -- 2.39.2