1 /*
2 This file is part of LilyPond, the GNU music typesetter.
3
4 Copyright (C) 2004--2021 Han-Wen Nienhuys <hanwen@xs4all.nl>
5
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "config.hh"
21
22 #include "slur-configuration.hh"
23
24 #include "item.hh"
25 #include "libc-extension.hh"
26 #include "misc.hh"
27 #include "pointer-group-interface.hh"
28 #include "slur-scoring.hh"
29 #include "slur.hh"
30 #include "spanner.hh"
31 #include "staff-symbol-referencer.hh"
32 #include "stem.hh"
33 #include "tie.hh"
34 #include "warn.hh"
35
36 #include <cmath>
37 #include <memory>
38 #include <string>
39 #include <vector>
40
41 using std::string;
42 using std::unique_ptr;
43 using std::vector;
44
45 Bezier
avoid_staff_line(Slur_score_state const & state,Bezier bez)46 avoid_staff_line (Slur_score_state const &state,
47 Bezier bez)
48 {
49 Offset horiz (1, 0);
50 vector<Real> ts = bez.solve_derivative (horiz);
51
52 /* TODO: handle case of broken slur. */
53 if (!ts.empty ()
54 && (state.extremes_[LEFT].staff_ == state.extremes_[RIGHT].staff_)
55 && state.extremes_[LEFT].staff_ && state.extremes_[RIGHT].staff_)
56 {
57 Real t = ts[0]; //the first (usually only) point where slur is horizontal
58 Real y = bez.curve_point (t)[Y_AXIS];
59 // A Bezier curve at t moves 3t-3t² as far as the middle control points
60 Real factor = 3.0 * t * (1.0 - t);
61
62 Grob *staff = state.extremes_[LEFT].staff_;
63
64 Real p = 2 * (y - staff->relative_coordinate (state.common_[Y_AXIS], Y_AXIS))
65 / state.staff_space_;
66
67 auto round_p = static_cast<int> (round_halfway_up (p));
68 if (!Staff_symbol_referencer::on_staff_line (staff, round_p))
69 round_p += (p > round_p) ? 1 : -1;
70 if (!Staff_symbol_referencer::on_staff_line (staff, round_p))
71 return bez;
72
73 Real const distance = (p - round_p) * state.staff_space_ / 2.0;
74 // Allow half the thickness of the slur at the point t, plus one basic
75 // blot-diameter (half for the slur outline, half for the staff line)
76 Real const min_distance = 0.5 * state.thickness_ * factor
77 + state.line_thickness_
78 + ((state.dir_ * distance > 0.0)
79 ? state.parameters_.gap_to_staffline_inside_
80 : state.parameters_.gap_to_staffline_outside_);
81 if (fabs (distance) < min_distance)
82 {
83 Direction resolution_dir = (distance > 0.0) ? UP : DOWN;
84
85 Real dy = resolution_dir * (min_distance - fabs (distance));
86
87 // Shape the curve, moving the horizontal point by factor * dy
88 bez.control_[1][Y_AXIS] += dy;
89 bez.control_[2][Y_AXIS] += dy;
90 // Move the entire curve by the remaining amount
91 bez.translate (Offset (0.0, dy - factor * dy));
92 }
93 }
94 return bez;
95 }
96
97 Real
fit_factor(Offset dz_unit,Offset dz_perp,Real close_to_edge_length,Bezier curve,Direction d,vector<Offset> const & avoid)98 fit_factor (Offset dz_unit, Offset dz_perp, Real close_to_edge_length,
99 Bezier curve, Direction d, vector<Offset> const &avoid)
100 {
101 Real fit_factor = 0.0;
102 Offset x0 = curve.control_[0];
103 curve.translate (-x0);
104 curve.rotate (-dz_unit.angle_degrees ());
105 curve.scale (1, d);
106
107 Interval curve_xext;
108 curve_xext.add_point (curve.control_[0][X_AXIS]);
109 curve_xext.add_point (curve.control_[3][X_AXIS]);
110
111 for (vsize i = 0; i < avoid.size (); i++)
112 {
113 Offset z = (avoid[i] - x0);
114 Offset p (dot_product (z, dz_unit),
115 d * dot_product (z, dz_perp));
116
117 bool close_to_edge = false;
118 for (const auto d : {LEFT, RIGHT})
119 close_to_edge = close_to_edge || -d * (p[X_AXIS] - curve_xext[d]) < close_to_edge_length;
120
121 if (close_to_edge)
122 continue;
123
124 Real eps = 0.01;
125 Interval pext = eps * Interval (-1, 1) + p[X_AXIS];
126 pext.intersect (curve_xext);
127
128 if (pext.is_empty () || pext.length () <= 1.999 * eps)
129 continue;
130
131 Real y = curve.get_other_coordinate (X_AXIS, p[X_AXIS]);
132 if (y)
133 fit_factor = std::max (fit_factor, (p[Y_AXIS] / y));
134 }
135 return fit_factor;
136 }
137
138 void
generate_curve(Slur_score_state const & state,Real r_0,Real h_inf,vector<Offset> const & avoid)139 Slur_configuration::generate_curve (Slur_score_state const &state,
140 Real r_0, Real h_inf,
141 vector<Offset> const &avoid)
142 {
143 Offset dz = attachment_[RIGHT] - attachment_[LEFT];;
144 Offset dz_unit = dz;
145 dz_unit *= 1 / dz.length ();
146 Offset dz_perp = dz_unit * Offset (0, 1);
147
148 Real indent, height;
149 get_slur_indent_height (&indent, &height, dz.length (), h_inf, r_0);
150
151 Real len = dz.length ();
152
153 /* This condition,
154
155 len^2 > 4h^2 + 3 (i + 1/3len)^2 - 1/3 len^2
156
157 is equivalent to:
158
159 |bez' (0)| < | bez' (.5)|
160
161 when (control2 - control1) has the same direction as
162 (control3 - control0). */
163
164 Real max_indent = len / 3.1;
165 indent = std::min (indent, max_indent);
166
167 Real a1 = sqr (len) / 3.0;
168 Real a2 = 0.75 * sqr (indent + len / 3.0);
169 Real max_h = a1 - a2;
170
171 if (max_h < 0)
172 {
173 programming_error ("slur indent too small");
174 max_h = len / 3.0;
175 }
176 else
177 max_h = sqrt (max_h);
178
179 Real eccentricity = from_scm<double> (get_property (state.slur_, "eccentricity"), 0);
180
181 Real x1 = (eccentricity + indent);
182 Real x2 = (eccentricity - indent);
183
184 Bezier curve;
185 curve.control_[0] = attachment_[LEFT];
186 curve.control_[1] = attachment_[LEFT] + dz_perp * height * state.dir_
187 + dz_unit * x1;
188 curve.control_[2] = attachment_[RIGHT] + dz_perp * height * state.dir_
189 + dz_unit * x2;
190 curve.control_[3] = attachment_[RIGHT];
191
192 Real ff = fit_factor (dz_unit, dz_perp, state.parameters_.close_to_edge_length_,
193 curve, state.dir_, avoid);
194
195 height = std::max (height, std::min (height * ff, max_h));
196
197 curve.control_[0] = attachment_[LEFT];
198 curve.control_[1] = attachment_[LEFT] + dz_perp * height * state.dir_
199 + dz_unit * x1;
200 curve.control_[2] = attachment_[RIGHT] + dz_perp * height * state.dir_
201 + dz_unit * x2;
202 curve.control_[3] = attachment_[RIGHT];
203
204 curve_ = avoid_staff_line (state, curve);
205 height_ = height;
206 }
207
Slur_configuration()208 Slur_configuration::Slur_configuration ()
209 {
210 score_ = 0.0;
211 index_ = -1;
212 };
213
214 void
add_score(Real s,const string & desc)215 Slur_configuration::add_score (Real s, const string &desc)
216 {
217 if (s < 0)
218 {
219 programming_error ("Negative demerits found for slur. Ignoring");
220 s = 0.0;
221 }
222
223 if (s)
224 {
225 if (score_card_.length () > 0)
226 score_card_ += ", ";
227 score_card_ += to_string ("%s=%.2f", desc.c_str (), s);
228 score_ += s;
229 }
230 }
231
232 void
score_encompass(Slur_score_state const & state)233 Slur_configuration::score_encompass (Slur_score_state const &state)
234 {
235 Bezier const &bez (curve_);
236 Real demerit = 0.0;
237
238 /*
239 Distances for heads that are between slur and line between
240 attachment points.
241 */
242 vector<Real> convex_head_distances;
243 for (vsize j = 0; j < state.encompass_infos_.size (); j++)
244 {
245 Real x = state.encompass_infos_[j].x_;
246
247 bool l_edge = j == 0;
248 bool r_edge = j == state.encompass_infos_.size () - 1;
249 bool edge = l_edge || r_edge;
250
251 if (! (x < attachment_[RIGHT][X_AXIS]
252 && x > attachment_[LEFT][X_AXIS]))
253 continue;
254
255 Real y = bez.get_other_coordinate (X_AXIS, x);
256 if (!edge)
257 {
258 Real head_dy = (y - state.encompass_infos_[j].head_);
259 if (state.dir_ * head_dy < 0)
260 {
261 demerit += state.parameters_.head_encompass_penalty_;
262 convex_head_distances.push_back (0.0);
263 }
264 else
265 {
266 Real hd = (head_dy)
267 ? (1 / fabs (head_dy) - 1 / state.parameters_.free_head_distance_)
268 : state.parameters_.head_encompass_penalty_;
269 hd = std::min (std::max (hd, 0.0), state.parameters_.head_encompass_penalty_);
270
271 demerit += hd;
272 }
273
274 Real line_y = linear_interpolate (x,
275 attachment_[RIGHT][X_AXIS],
276 attachment_[LEFT][X_AXIS],
277 attachment_[RIGHT][Y_AXIS],
278 attachment_[LEFT][Y_AXIS]);
279
280 if (1) // state.dir_ * state.encompass_infos_[j].get_point (state.dir_) > state.dir_ *line_y )
281 {
282
283 Real closest
284 = state.dir_ * std::max (state.dir_ * state.encompass_infos_[j].get_point (state.dir_), state.dir_ * line_y);
285 Real d = fabs (closest - y);
286
287 convex_head_distances.push_back (d);
288 }
289 }
290
291 if (state.dir_ * (y - state.encompass_infos_[j].stem_) < 0)
292 {
293 Real stem_dem = state.parameters_.stem_encompass_penalty_;
294 if ((l_edge && state.dir_ == UP)
295 || (r_edge && state.dir_ == DOWN))
296 stem_dem /= 5;
297
298 demerit += stem_dem;
299 }
300 }
301 add_score (demerit, "encompass");
302
303 if (vsize n = convex_head_distances.size ())
304 {
305 Real avg_distance = 0.0;
306 Real min_dist = infinity_f;
307
308 for (vsize j = 0; j < n; j++)
309 {
310 min_dist = std::min (min_dist, convex_head_distances[j]);
311 avg_distance += convex_head_distances[j];
312 }
313
314 /*
315 For slurs over 3 or 4 heads, the average distance is not a
316 good normalizer.
317 */
318 if (n <= 2)
319 {
320 Real fact = 1.0;
321 avg_distance += height_ * fact;
322 ++n;
323 }
324
325 /*
326 TODO: maybe it's better to use (avgdist - mindist)*factor
327 as penalty.
328 */
329 avg_distance /= static_cast<Real> (n);
330 Real variance_penalty = state.parameters_.head_slur_distance_max_ratio_;
331 if (min_dist > 0.0)
332 variance_penalty
333 = std::min ((avg_distance / (min_dist + state.parameters_.absolute_closeness_measure_) - 1.0), variance_penalty);
334
335 variance_penalty = std::max (variance_penalty, 0.0);
336 variance_penalty *= state.parameters_.head_slur_distance_factor_;
337
338 add_score (variance_penalty, "variance");
339 }
340 }
341
342 void
score_extra_encompass(Slur_score_state const & state)343 Slur_configuration::score_extra_encompass (Slur_score_state const &state)
344 {
345 // we find forbidden attachments
346 vector<Offset> forbidden_attachments;
347 for (vsize i = 0; i < state.extra_encompass_infos_.size (); i++)
348 if (has_interface<Tie> (state.extra_encompass_infos_[i].grob_))
349 {
350 Grob *t = state.extra_encompass_infos_[i].grob_;
351 Grob *common_x = Grob::get_vertical_axis_group (t);
352 Real rp = t->relative_coordinate (common_x, X_AXIS);
353 SCM cp = get_property (t, "control-points");
354
355 Bezier b;
356 for (int j = 0; j < b.CONTROL_COUNT; ++j)
357 {
358 if (scm_is_pair (cp))
359 {
360 b.control_[j] = from_scm<Offset> (scm_car (cp));
361 cp = scm_cdr (cp);
362 }
363 else
364 b.control_[j] = Offset (0.0, 0.0);
365 }
366 forbidden_attachments.push_back (b.control_[0] + Offset (rp, 0));
367 forbidden_attachments.push_back (b.control_[3] + Offset (rp, 0));
368 }
369
370 bool too_close = false;
371 for (vsize k = 0; k < forbidden_attachments.size (); k++)
372 for (const auto side : {LEFT, RIGHT})
373 if ((forbidden_attachments[k] - attachment_[side]).length () < state.parameters_.slur_tie_extrema_min_distance_)
374 {
375 too_close = true;
376 break;
377 }
378
379 if (too_close)
380 add_score (state.parameters_.slur_tie_extrema_min_distance_penalty_, "extra");
381
382 for (vsize j = 0; j < state.extra_encompass_infos_.size (); j++)
383 {
384 Drul_array<Offset> attachment = attachment_;
385 Extra_collision_info const &info (state.extra_encompass_infos_[j]);
386
387 Interval slur_wid (attachment[LEFT][X_AXIS], attachment[RIGHT][X_AXIS]);
388
389 /*
390 to prevent numerical inaccuracies in
391 Bezier::get_other_coordinate ().
392 */
393
394 bool found = false;
395 Real y = 0.0;
396
397 for (const auto d : {LEFT, RIGHT})
398 {
399 /*
400 We need to check for the bound explicitly, since the
401 slur-ending can be almost vertical, making the Y
402 coordinate a bad approximation of the object-slur
403 distance.
404 */
405 Item *as_item = dynamic_cast<Item *> (state.extra_encompass_infos_[j].grob_);
406 if (!as_item)
407 continue;
408
409 Interval item_x = as_item->extent (state.common_[X_AXIS], X_AXIS);
410 item_x.intersect (state.extremes_[d].slur_head_x_extent_);
411 if (!item_x.is_empty ())
412 {
413 y = attachment[d][Y_AXIS];
414 found = true;
415 }
416
417 }
418
419 if (!found)
420 {
421 Real x = info.extents_[X_AXIS].linear_combination (info.idx_);
422
423 if (!slur_wid.contains (x))
424 continue;
425
426 y = curve_.get_other_coordinate (X_AXIS, x);
427 }
428
429 Real dist = 0.0;
430 if (scm_is_eq (info.type_, ly_symbol2scm ("around")))
431 dist = info.extents_[Y_AXIS].distance (y);
432
433 /*
434 Have to score too: the curve enumeration is limited in its
435 shape, and may produce curves which collide anyway.
436 */
437 else if (scm_is_eq (info.type_, ly_symbol2scm ("inside")))
438 dist = state.dir_ * (y - info.extents_[Y_AXIS][state.dir_]);
439 else
440 programming_error ("unknown avoidance type");
441
442 dist = std::max (dist, 0.0);
443
444 Real penalty = info.penalty_ * peak_around (0.1 * state.parameters_.extra_encompass_free_distance_,
445 state.parameters_.extra_encompass_free_distance_,
446 dist);
447
448 add_score (penalty, "extra");
449 }
450 }
451
452 void
score_edges(Slur_score_state const & state)453 Slur_configuration::score_edges (Slur_score_state const &state)
454 {
455
456 Offset dz = attachment_[RIGHT]
457 - attachment_[LEFT];
458 Real slope = dz[Y_AXIS] / dz[X_AXIS];
459 for (const auto d : {LEFT, RIGHT})
460 {
461 Real y = attachment_[d][Y_AXIS];
462 Real dy = fabs (y - state.base_attachments_[d][Y_AXIS]);
463
464 Real factor = state.parameters_.edge_attraction_factor_;
465 Real demerit = factor * dy;
466 if (state.extremes_[d].stem_
467 && state.extremes_[d].stem_dir_ == state.dir_
468 // TODO - Stem::get_beaming() should be precomputed.
469 && !Stem::get_beaming (state.extremes_[d].stem_, -d))
470 demerit /= 5;
471
472 demerit *= exp (state.dir_ * d * slope
473 * state.parameters_.edge_slope_exponent_);
474
475 string dir_str = d == LEFT ? "L" : "R";
476 add_score (demerit, dir_str + " edge");
477 }
478 }
479
480 void
score_slopes(Slur_score_state const & state)481 Slur_configuration::score_slopes (Slur_score_state const &state)
482 {
483 Real dy = state.musical_dy_;
484 Offset slur_dz = attachment_[RIGHT] - attachment_[LEFT];
485 Real slur_dy = slur_dz[Y_AXIS];
486 Real demerit = 0.0;
487
488 demerit += std::max ((fabs (slur_dy / slur_dz[X_AXIS])
489 - state.parameters_.max_slope_), 0.0)
490 * state.parameters_.max_slope_factor_;
491
492 /* 0.2: account for staffline offset. */
493 Real max_dy = (fabs (dy) + 0.2);
494 if (state.edge_has_beams_)
495 max_dy += 1.0;
496
497 if (!state.is_broken_)
498 demerit += state.parameters_.steeper_slope_factor_
499 * (std::max (fabs (slur_dy) - max_dy, 0.0));
500
501 demerit += std::max ((fabs (slur_dy / slur_dz[X_AXIS])
502 - state.parameters_.max_slope_), 0.0)
503 * state.parameters_.max_slope_factor_;
504
505 if (sign (dy) == 0
506 && sign (slur_dy) != 0
507 && !state.is_broken_)
508 demerit += state.parameters_.non_horizontal_penalty_;
509
510 if (sign (dy)
511 && !state.is_broken_
512 && sign (slur_dy)
513 && sign (slur_dy) != sign (dy))
514 demerit += state.edge_has_beams_
515 ? state.parameters_.same_slope_penalty_ / 10
516 : state.parameters_.same_slope_penalty_;
517
518 add_score (demerit, "slope");
519 }
520
521 void
run_next_scorer(Slur_score_state const & state)522 Slur_configuration::run_next_scorer (Slur_score_state const &state)
523 {
524 switch (next_scorer_todo)
525 {
526 case EXTRA_ENCOMPASS:
527 score_extra_encompass (state);
528 break;
529 case SLOPE:
530 score_slopes (state);
531 break;
532 case EDGES:
533 score_edges (state);
534 break;
535 case ENCOMPASS:
536 score_encompass (state);
537 break;
538 default:
539 assert (false);
540 }
541 next_scorer_todo++;
542 }
543
544 bool
done() const545 Slur_configuration::done () const
546 {
547 return next_scorer_todo >= NUM_SCORERS;
548 }
549
550 unique_ptr<Slur_configuration>
new_config(Drul_array<Offset> const & offs,size_t idx)551 Slur_configuration::new_config (Drul_array<Offset> const &offs, size_t idx)
552 {
553 unique_ptr<Slur_configuration> conf (new Slur_configuration);
554 conf->attachment_ = offs;
555 conf->index_ = idx;
556 conf->next_scorer_todo = INITIAL_SCORE + 1;
557 return conf;
558 }
559