1 /*
2 This file is part of LilyPond, the GNU music typesetter.
3
4 Copyright (C) 1997--2020 Han-Wen Nienhuys <hanwen@xs4all.nl>
5 Jan Nieuwenhuizen <janneke@gnu.org>
6
7 LilyPond is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 LilyPond is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include "config.hh"
22
23 #include "beam-scoring-problem.hh"
24
25 #include "align-interface.hh"
26 #include "beam.hh"
27 #include "direction.hh"
28 #include "directional-element-interface.hh"
29 #include "grob.hh"
30 #include "grob-array.hh"
31 #include "item.hh"
32 #include "international.hh"
33 #include "interval-minefield.hh"
34 #include "least-squares.hh"
35 #include "libc-extension.hh"
36 #include "main.hh"
37 #include "note-head.hh"
38 #include "output-def.hh"
39 #include "pointer-group-interface.hh"
40 #include "spanner.hh"
41 #include "staff-symbol-referencer.hh"
42 #include "stencil.hh"
43 #include "stem.hh"
44 #include "warn.hh"
45 #include "string-convert.hh"
46
47 #include <algorithm>
48 #include <cmath>
49 #include <memory>
50 #include <queue>
51 #include <set>
52
53 using std::set;
54 using std::string;
55 using std::unique_ptr;
56 using std::vector;
57
58 Real
get_detail(SCM alist,SCM sym,Real def)59 get_detail (SCM alist, SCM sym, Real def)
60 {
61 SCM entry = scm_assq (sym, alist);
62
63 if (scm_is_pair (entry))
64 return from_scm<double> (scm_cdr (entry), def);
65 return def;
66 }
67
68 void
fill(Grob * him)69 Beam_quant_parameters::fill (Grob *him)
70 {
71 SCM details = get_property (him, "details");
72
73 // General
74 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
75 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
76
77 // forbidden quants
78 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0)
79 // For stems that are non-standard, the forbidden beam quanting
80 // doesn't really work, so decrease their importance.
81 * exp (- 8 * fabs (1.0 - from_scm<double> (get_property (him, "length-fraction"), 1.0)));
82 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
83 HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
84
85 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
86 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
87 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
88 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
89 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
90 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
91
92 // Collisions
93 COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
94
95 /* For grace notes, beams get scaled down to 80%, but glyphs go down
96 to 63% (magstep -4 for accidentals). To make the padding
97 commensurate with glyph size for grace notes, we take the square
98 of the length fraction, yielding a 64% decrease.
99 */
100 COLLISION_PADDING = get_detail (details, ly_symbol2scm ("collision-padding"), 0.5)
101 * sqr (from_scm<double> (get_property (him, "length-fraction"), 1.0));
102 STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
103 }
104
105 // Add x if x is positive, add |x|*fac if x is negative.
106 static Real
shrink_extra_weight(Real x,Real fac)107 shrink_extra_weight (Real x, Real fac)
108 {
109 return fabs (x) * ((x < 0) ? fac : 1.0);
110 }
111
112 /****************************************************************/
113
Beam_configuration()114 Beam_configuration::Beam_configuration ()
115 {
116 y = Drul_array<Real> (0.0, 0.0);
117 demerits = 0.0;
118 next_scorer_todo = ORIGINAL_DISTANCE;
119 }
120
done() const121 bool Beam_configuration::done () const
122 {
123 return next_scorer_todo >= NUM_SCORERS;
124 }
125
add(Real demerit,const string & reason)126 void Beam_configuration::add (Real demerit, const string &reason)
127 {
128 demerits += demerit;
129
130 #if DEBUG_BEAM_SCORING
131 if (demerit)
132 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
133 #endif
134 }
135
136 unique_ptr<Beam_configuration>
new_config(Drul_array<Real> start,Drul_array<Real> offset)137 Beam_configuration::new_config (Drul_array<Real> start,
138 Drul_array<Real> offset)
139 {
140 unique_ptr<Beam_configuration> qs (new Beam_configuration);
141 qs->y = Drul_array<Real> (int (start[LEFT]) + offset[LEFT],
142 int (start[RIGHT]) + offset[RIGHT]);
143
144 // This orders the sequence so we try combinations closest to the
145 // the ideal offset first.
146 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
147 qs->demerits = start_score / 1000.0;
148 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
149
150 return qs;
151 }
152
153 Real
y_at(Real x,Beam_configuration const * p) const154 Beam_scoring_problem::y_at (Real x, Beam_configuration const *p) const
155 {
156 return p->y[LEFT] + x * p->y.delta () / x_span_;
157 }
158
159 /****************************************************************/
160
161 /*
162 TODO:
163
164 - Make all demerits customisable
165
166 - Add demerits for quants per se, as to forbid a specific quant
167 entirely
168 */
169
170 // This is a temporary hack to see how much we can gain by using a
171 // priority queue on the beams to score.
172 static int score_count = 0;
173 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
174 (),
175 "count number of beam scores.")
176 {
177 return to_scm (score_count);
178 }
179
add_collision(Real x,Interval y,Real score_factor)180 void Beam_scoring_problem::add_collision (Real x, Interval y,
181 Real score_factor)
182 {
183 // We used to screen for quant range, but no more.
184
185 Beam_collision c;
186 c.beam_y_.set_empty ();
187
188 for (vsize j = 0; j < segments_.size (); j++)
189 {
190 if (segments_[j].horizontal_.contains (x))
191 c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation_);
192 if (segments_[j].horizontal_[LEFT] > x)
193 break;
194 }
195 c.beam_y_.widen (0.5 * beam_thickness_);
196
197 c.x_ = x;
198
199 y *= 1 / staff_space_;
200 c.y_ = y;
201 c.base_penalty_ = score_factor;
202 collisions_.push_back (c);
203 }
204
init_instance_variables(Grob * me,Drul_array<Real> ys,bool align_broken_intos)205 void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
206 {
207 beam_ = dynamic_cast<Spanner *> (me);
208 unquanted_y_ = ys;
209
210 /*
211 If 'ys' are finite, use them as starting points for y-positions of the
212 ends of the beam, instead of the best-fit through the natural ends of
213 the stems. Otherwise, we want to do initial slope calculations.
214 */
215 do_initial_slope_calculations_ = false;
216 for (LEFT_and_RIGHT (d))
217 do_initial_slope_calculations_ |= !std::isfinite (unquanted_y_[d]);
218
219 /*
220 Calculations are relative to a unit-scaled staff, i.e. the quants are
221 divided by the current staff_space_.
222 */
223 staff_space_ = Staff_symbol_referencer::staff_space (beam_);
224 beam_thickness_ = Beam::get_beam_thickness (beam_) / staff_space_;
225 line_thickness_ = Staff_symbol_referencer::line_thickness (beam_) / staff_space_;
226 max_beam_count_ = Beam::get_beam_count (beam_);
227 length_fraction_
228 = from_scm<double> (get_property (beam_, "length-fraction"), 1.0);
229 // This is the least-squares DY, corrected for concave beams.
230 musical_dy_ = from_scm<double> (get_property (beam_, "least-squares-dy"), 0);
231
232 vector<Spanner *> beams;
233 align_broken_intos_ = align_broken_intos;
234 if (align_broken_intos_)
235 {
236 Spanner *orig = beam_->original ();
237 if (!orig)
238 align_broken_intos_ = false;
239 else if (!orig->broken_intos_.size ())
240 align_broken_intos_ = false;
241 else
242 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
243 }
244 if (!align_broken_intos_)
245 beams.push_back (beam_);
246
247 /*
248 x_span_ is a single scalar, cumulatively summing the length of all the
249 segments the parent beam was broken-into.
250 */
251 x_span_ = 0.0;
252 is_knee_ = false;
253 normal_stem_count_ = 0;
254 for (vsize i = 0; i < beams.size (); i++)
255 {
256 extract_grob_set (beams[i], "stems", stems);
257 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
258 vector<Grob *> collisions;
259
260 for (vsize j = 0; j < fake_collisions.size (); j++)
261 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
262 collisions.push_back (fake_collisions[j]);
263
264 Grob *common[2];
265 for (int a = 2; a--;)
266 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
267
268 for (LEFT_and_RIGHT (d))
269 common[X_AXIS] = beams[i]->get_bound (d)->common_refpoint (common[X_AXIS], X_AXIS);
270
271 // positions of the endpoints of this beam segment, including any overhangs
272 const Interval x_pos = from_scm (get_property (beams[i], "X-positions"),
273 Interval (0.0, 0.0));
274
275 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
276 Beam::last_normal_stem (beams[i]));
277
278 Drul_array<bool> dirs_found (0, 0);
279
280 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
281
282 Interval beam_width (-1.0, -1.0);
283 for (vsize j = 0; j < stems.size (); j++)
284 {
285 Grob *s = stems[j];
286 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
287 head_positions_.push_back (Stem::head_positions (stems[j]));
288 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
289
290 Stem_info si (Stem::get_stem_info (s));
291 si.scale (1 / staff_space_);
292 stem_infos_.push_back (si);
293 chord_start_y_.push_back (Stem::chord_start_y (s));
294 dirs_found[si.dir_] = true;
295
296 Beam_stem_end stem_end
297 = Beam::calc_stem_y (beams[i], s, common,
298 x_pos[LEFT], x_pos[RIGHT], CENTER,
299 Drul_array<Real> (0.0, 0.0), 0);
300 Real y = stem_end.stem_y_;
301 /* Remark: French Beaming is irrelevant for beam quanting */
302 base_lengths_.push_back (y / staff_space_);
303 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
304 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
305
306 if (is_normal_.back ())
307 {
308 if (beam_width[LEFT] == -1.0)
309 beam_width[LEFT] = stem_xpositions_.back ();
310 beam_width[RIGHT] = stem_xpositions_.back ();
311 }
312 }
313
314 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
315 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
316 if (normal_stem_count_)
317 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
318 stem_infos_.back ().dir_);
319
320 is_xstaff_ = has_interface<Align_interface> (common[Y_AXIS]);
321 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
322
323 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
324 edge_beam_counts_ = Drul_array<int>
325 (Stem::beam_multiplicity (stems[0]).length () + 1,
326 Stem::beam_multiplicity (stems.back ()).length () + 1);
327
328 // TODO - why are we dividing by staff_space_?
329 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
330
331 for (LEFT_and_RIGHT (d))
332 {
333 quant_range_[d].set_full ();
334 if (!edge_stems[d])
335 continue;
336
337 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
338 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
339 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
340
341 Direction ed = edge_dirs_[d];
342 heads.widen (0.5 * staff_space_
343 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
344 quant_range_[d][-ed] = heads[ed] + stem_offset;
345 }
346
347 segments_ = Beam::get_beam_segments (beams[i]);
348 vector_sort (segments_, beam_segment_less);
349 for (vsize j = 0; j < segments_.size (); j++)
350 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
351
352 set<Grob *> colliding_stems;
353 for (vsize j = 0; j < collisions.size (); j++)
354 {
355 if (!collisions[j]->is_live ())
356 continue;
357
358 if (has_interface<Beam> (collisions[j]) && Beam::is_cross_staff (collisions[j]))
359 continue;
360
361 Box b;
362 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
363 b[a] = collisions[j]->extent (common[a], a);
364
365 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
366 continue;
367 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
368 continue;
369
370 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
371 b[Y_AXIS] -= my_y;
372 Real width = b[X_AXIS].length ();
373 Real width_factor = sqrt (width / staff_space_);
374
375 for (LEFT_and_RIGHT (d))
376 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
377
378 Grob *stem = unsmob<Grob> (get_object (collisions[j], "stem"));
379 if (has_interface<Stem> (stem) && Stem::is_normal_stem (stem))
380 {
381 colliding_stems.insert (stem);
382 }
383 }
384
385 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
386 {
387 Grob *s = *it;
388 Real x = (robust_relative_extent (s, common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
389
390 Direction stem_dir = get_grob_direction (*it);
391 Interval y;
392 y.set_full ();
393 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
394 - my_y;
395
396 Real factor = parameters_.STEM_COLLISION_FACTOR;
397 if (!unsmob<Grob> (get_object (s, "beam")))
398 factor = 1.0;
399 add_collision (x, y, factor);
400 }
401 x_span_ += beams[i]->spanner_length ();
402 }
403 }
404
Beam_scoring_problem(Grob * me,Drul_array<Real> ys,bool align_broken_intos)405 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
406 {
407 beam_ = dynamic_cast<Spanner *> (me);
408 unquanted_y_ = ys;
409 align_broken_intos_ = align_broken_intos;
410
411 parameters_.fill (me);
412 init_instance_variables (me, ys, align_broken_intos);
413 if (do_initial_slope_calculations_)
414 {
415 least_squares_positions ();
416 slope_damping ();
417 shift_region_to_valid ();
418 }
419 }
420
421 // Assuming V is not empty, pick a 'reasonable' point inside V.
422 static Real
point_in_interval(Interval v,Real dist)423 point_in_interval (Interval v, Real dist)
424 {
425 if (std::isinf (v[DOWN]))
426 return v[UP] - dist;
427 else if (std::isinf (v[UP]))
428 return v[DOWN] + dist;
429 else
430 return v.center ();
431 }
432
433 /* Set stem's shorten property if unset.
434
435 TODO:
436 take some y-position (chord/beam/nearest?) into account
437 scmify forced-fraction
438
439 This is done in beam because the shorten has to be uniform over the
440 entire beam.
441 */
442
443 void
set_minimum_dy(Grob * me,Real * dy)444 set_minimum_dy (Grob *me, Real *dy)
445 {
446 if (*dy)
447 {
448 /*
449 If dy is smaller than the smallest quant, we
450 get absurd direction-sign penalties.
451 */
452
453 Real ss = Staff_symbol_referencer::staff_space (me);
454 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
455 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
456 Real sit = (beam_thickness - slt) / 2;
457 Real inter = 0.5;
458 Real hang = 1.0 - (beam_thickness - slt) / 2;
459
460 *dy = sign (*dy) * std::max (fabs (*dy),
461 std::min (std::min (sit, inter), hang));
462 }
463 }
464
465 void
no_visible_stem_positions()466 Beam_scoring_problem::no_visible_stem_positions ()
467 {
468 if (!head_positions_.size ())
469 {
470 unquanted_y_ = Drul_array<Real> (0.0, 0.0);
471 return;
472 }
473
474 Interval head_positions;
475 Slice multiplicity;
476 for (vsize i = 0; i < head_positions_.size (); i++)
477 {
478 head_positions.unite (head_positions_[i]);
479 multiplicity.unite (beam_multiplicity_[i]);
480 }
481
482 Direction dir = get_grob_direction (beam_);
483
484 if (!dir)
485 programming_error ("The beam should have a direction by now.");
486
487 Real y = head_positions.linear_combination (dir)
488 * 0.5 * staff_space_
489 + dir * beam_translation_ * (multiplicity.length () + 1);
490
491 unquanted_y_ = Drul_array<Real> (y, y);
492 }
493
494 vsize
first_normal_index()495 Beam_scoring_problem::first_normal_index ()
496 {
497 for (vsize i = 0; i < is_normal_.size (); i++)
498 if (is_normal_[i])
499 return i;
500
501 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
502 return 0;
503 }
504
505 vsize
last_normal_index()506 Beam_scoring_problem::last_normal_index ()
507 {
508 for (vsize i = is_normal_.size (); i--;)
509 if (is_normal_[i])
510 return i;
511
512 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
513 return 0;
514 }
515
516 void
least_squares_positions()517 Beam_scoring_problem::least_squares_positions ()
518 {
519 if (!normal_stem_count_)
520 {
521 no_visible_stem_positions ();
522 return;
523 }
524
525 if (stem_infos_.size () < 1)
526 return;
527
528 vsize fnx = first_normal_index ();
529 vsize lnx = last_normal_index ();
530
531 Drul_array<Real> ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
532 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
533
534 Real y = 0;
535 Real slope = 0;
536 Real dy = 0;
537 Real ldy = 0.0;
538 if (!ideal.delta ())
539 {
540 Drul_array<Real> chord (chord_start_y_[0],
541 chord_start_y_.back ());
542
543 /* Simple beams (2 stems) on middle line should be allowed to be
544 slightly sloped.
545
546 However, if both stems reach middle line,
547 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
548
549 For that case, we apply artificial slope */
550 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
551 {
552 /* FIXME. -> UP */
553 Direction d = (Direction) (sign (chord.delta ()) * UP);
554 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
555 unquanted_y_[-d] = -unquanted_y_[d];
556 }
557 else
558 unquanted_y_ = ideal;
559
560 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
561 }
562 else
563 {
564 vector<Offset> ideals;
565 for (vsize i = 0; i < stem_infos_.size (); i++)
566 if (is_normal_[i])
567 ideals.push_back (Offset (stem_xpositions_[i],
568 stem_infos_[i].ideal_y_
569 + stem_ypositions_[i]));
570
571 minimise_least_squares (&slope, &y, ideals);
572
573 dy = slope * x_span_;
574
575 set_minimum_dy (beam_, &dy);
576
577 ldy = dy;
578 unquanted_y_ = Drul_array<Real> (y, (y + dy));
579 }
580
581 musical_dy_ = ldy;
582 set_property (beam_, "least-squares-dy", to_scm (musical_dy_));
583 }
584
585 /*
586 Determine whether a beam is concave.
587
588 A beam is concave when the middle notes get closer to the
589 beam than the left and right edge notes.
590
591 This is determined in two ways: by looking at the positions of the
592 middle notes, or by looking at the deviation of the inside notes
593 compared to the line connecting first and last.
594
595 The tricky thing is what to do with beams with chords. There are no
596 real guidelines in this case.
597 */
598
599 bool
is_concave_single_notes(vector<int> const & positions,Direction beam_dir)600 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
601 {
602 Interval covering;
603 covering.add_point (positions[0]);
604 covering.add_point (positions.back ());
605
606 bool above = false;
607 bool below = false;
608 bool concave = false;
609
610 /*
611 notes above and below the interval covered by 1st and last note.
612 */
613 for (vsize i = 1; i + 1 < positions.size (); i++)
614 {
615 above = above || (positions[i] > covering[UP]);
616 below = below || (positions[i] < covering[DOWN]);
617 }
618
619 concave = concave || (above && below);
620 /*
621 A note as close or closer to the beam than begin and end, but the
622 note is reached in the opposite direction as the last-first dy
623 */
624 int dy = positions.back () - positions[0];
625 int closest = std::max (beam_dir * positions.back (), beam_dir * positions[0]);
626 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
627 {
628 int inner_dy = positions[i] - positions[i - 1];
629 if (sign (inner_dy) != sign (dy)
630 && (beam_dir * positions[i] >= closest
631 || beam_dir * positions[i - 1] >= closest))
632 concave = true;
633 }
634
635 bool all_closer = true;
636 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
637 {
638 all_closer = all_closer
639 && (beam_dir * positions[i] > closest);
640 }
641
642 concave = concave || all_closer;
643 return concave;
644 }
645
646 Real
calc_positions_concaveness(vector<int> const & positions,Direction beam_dir)647 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
648 {
649 Real dy = positions.back () - positions[0];
650 Real slope = dy / static_cast<Real> (positions.size () - 1);
651 Real concaveness = 0.0;
652 for (vsize i = 1; i + 1 < positions.size (); i++)
653 {
654 Real line_y = slope * static_cast<Real> (i) + positions[0];
655 concaveness += std::max (beam_dir * (positions[i] - line_y), 0.0);
656 }
657
658 concaveness /= static_cast<Real> (positions.size ());
659
660 /*
661 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
662 scaling of concaveness doesn't matter much.
663 */
664 if (dy)
665 concaveness /= fabs (dy);
666 return concaveness;
667 }
668
669 Real
calc_concaveness()670 Beam_scoring_problem::calc_concaveness ()
671 {
672 SCM conc = get_property (beam_, "concaveness");
673 if (scm_is_number (conc))
674 return scm_to_double (conc);
675
676 if (is_knee_ || is_xstaff_)
677 return 0.0;
678
679 Direction beam_dir = CENTER;
680 for (vsize i = is_normal_.size (); i--;)
681 if (is_normal_[i] && stem_infos_[i].dir_)
682 beam_dir = stem_infos_[i].dir_;
683
684 if (normal_stem_count_ <= 2)
685 return 0.0;
686
687 vector<int> close_positions;
688 vector<int> far_positions;
689 for (vsize i = 0; i < is_normal_.size (); i++)
690 if (is_normal_[i])
691 {
692 /*
693 For chords, we take the note head that is closest to the beam.
694
695 Hmmm.. wait, for the beams in the last measure of morgenlied,
696 this doesn't look so good. Let's try the heads farthest from
697 the beam.
698 */
699
700 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
701 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
702 }
703
704 Real concaveness = 0.0;
705
706 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
707 {
708 concaveness = 10000;
709 }
710 else
711 {
712 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
713 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
714 }
715
716 return concaveness;
717 }
718
719 void
slope_damping()720 Beam_scoring_problem::slope_damping ()
721 {
722 if (normal_stem_count_ <= 1)
723 return;
724
725 SCM s = get_property (beam_, "damping");
726 Real damping = scm_to_double (s);
727 Real concaveness = calc_concaveness ();
728 if ((concaveness >= 10000) || (damping >= 10000))
729 {
730 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
731 musical_dy_ = 0;
732 damping = 0;
733 }
734
735 if ((damping) && (damping + concaveness))
736 {
737 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
738
739 Real slope = dy && x_span_ ? dy / x_span_ : 0;
740
741 slope = 0.6 * tanh (slope) / (damping + concaveness);
742
743 Real damped_dy = slope * x_span_;
744
745 set_minimum_dy (beam_, &damped_dy);
746
747 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
748 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
749 }
750 }
751
752 void
shift_region_to_valid()753 Beam_scoring_problem::shift_region_to_valid ()
754 {
755 if (!normal_stem_count_)
756 return;
757
758 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
759 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
760
761 /*
762 Shift the positions so that we have a chance of finding good
763 quants (i.e. no short stem failures.)
764 */
765 Interval feasible_left_point;
766 feasible_left_point.set_full ();
767
768 for (vsize i = 0; i < stem_infos_.size (); i++)
769 {
770 // TODO - check for invisible here...
771 Real left_y
772 = stem_infos_[i].shortest_y_
773 - slope * stem_xpositions_ [i];
774
775 /*
776 left_y is now relative to the stem S. We want relative to
777 ourselves, so translate:
778 */
779 left_y += stem_ypositions_[i];
780 Interval flp;
781 flp.set_full ();
782 flp[-stem_infos_[i].dir_] = left_y;
783
784 feasible_left_point.intersect (flp);
785 }
786
787 vector<Grob *> filtered;
788 /*
789 We only update these for objects that are too large for quanting
790 to find a workaround. Typically, these are notes with
791 stems, and timesig/keysig/clef, which take out the entire area
792 inside the staff as feasible.
793
794 The code below disregards the thickness and multiplicity of the
795 beam. This should not be a problem, as the beam quanting will
796 take care of computing the impact those exactly.
797 */
798 Real min_y_size = 2.0;
799
800 // A list of intervals into which beams may not fall
801 vector<Interval> forbidden_intervals;
802
803 for (vsize i = 0; i < collisions_.size (); i++)
804 {
805 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
806 continue;
807
808 if (collisions_[i].y_.length () < min_y_size)
809 continue;
810
811 for (LEFT_and_RIGHT (d))
812 {
813 Real dy = slope * collisions_[i].x_;
814
815 Interval disallowed;
816 for (DOWN_and_UP (yd))
817 {
818 Real left_y = collisions_[i].y_[yd] - dy;
819 disallowed[yd] = left_y;
820 }
821
822 forbidden_intervals.push_back (disallowed);
823 }
824 }
825
826 vector_sort (forbidden_intervals, Interval::left_less);
827 Real beam_left_y = unquanted_y_[LEFT];
828 Interval feasible_beam_placements (beam_left_y, beam_left_y);
829
830 Interval_minefield minefield (feasible_beam_placements, 0.0);
831 for (vsize i = 0; i < forbidden_intervals.size (); i++)
832 minefield.add_forbidden_interval (forbidden_intervals[i]);
833 minefield.solve ();
834 feasible_beam_placements = minefield.feasible_placements ();
835
836 // if the beam placement falls out of the feasible region, we push it
837 // to infinity so that it can never be a feasible candidate below
838 for (DOWN_and_UP (d))
839 {
840 if (!feasible_left_point.contains (feasible_beam_placements[d]))
841 feasible_beam_placements[d] = d * infinity_f;
842 }
843
844 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
845 {
846 // We are somewhat screwed: we have a collision, but at least
847 // there is a way to satisfy stem length constraints.
848 beam_left_y = point_in_interval (feasible_left_point, 2.0);
849 }
850 else if (!feasible_left_point.is_empty ())
851 {
852 // Only one of them offers is feasible solution. Pick that one.
853 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
854 beam_left_y = feasible_beam_placements[UP];
855 else
856 beam_left_y = feasible_beam_placements[DOWN];
857 }
858 else
859 {
860 // We are completely screwed.
861 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
862 }
863
864 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
865 }
866
867 void
generate_quants(vector<unique_ptr<Beam_configuration>> * scores) const868 Beam_scoring_problem::generate_quants (vector<unique_ptr<Beam_configuration>> *scores) const
869 {
870 int region_size = (int) parameters_.REGION_SIZE;
871
872 // Knees and collisions are harder, lets try some more possibilities
873 if (is_knee_)
874 region_size += 2;
875 if (collisions_.size ())
876 region_size += 2;
877
878 Real straddle = 0.0;
879 Real sit = (beam_thickness_ - line_thickness_) / 2;
880 Real inter = 0.5;
881 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
882 Real base_quants [] = {straddle, sit, inter, hang};
883 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
884
885 /* for normal-sized beams, in case of more than 4 beams, the outer beam
886 used for generating quants will never interfere with staff lines, but
887 prevent the inside-staff beams from being neatly positioned.
888 A correctional grid_shift has to be applied to compensate. */
889 Real grid_shift = 0.0;
890 /* grid shift only makes sense for widened normal-sized beams: */
891 if (!is_knee_ && max_beam_count_ > 4 && length_fraction_ == 1.0)
892 grid_shift = (max_beam_count_ - 4) * (1.0 - beam_translation_);
893
894 /*
895 Asymetry ? should run to <= region_size ?
896 */
897 vector<Real> unshifted_quants;
898 for (int i = -region_size; i < region_size; i++)
899 for (int j = 0; j < num_base_quants; j++)
900 {
901 unshifted_quants.push_back (i + base_quants[j]);
902 }
903
904 for (vsize i = 0; i < unshifted_quants.size (); i++)
905 for (vsize j = 0; j < unshifted_quants.size (); j++)
906 {
907 Interval corr (0.0, 0.0);
908 if (grid_shift)
909 for (LEFT_and_RIGHT (d))
910 /* apply grid shift if quant outside 5-line staff: */
911 if ((unquanted_y_[d] + unshifted_quants[i]) * edge_dirs_[d] > 2.5)
912 corr[d] = grid_shift * edge_dirs_[d];
913 auto c = Beam_configuration::new_config
914 (unquanted_y_,
915 Drul_array<Real> (unshifted_quants[i] - corr[LEFT],
916 unshifted_quants[j] - corr[RIGHT]));
917
918 for (LEFT_and_RIGHT (d))
919 {
920 if (!quant_range_[d].contains (c->y[d]))
921 {
922 c.reset ();
923 break;
924 }
925 }
926 if (c)
927 scores->push_back (std::move (c));
928 }
929
930 }
931
one_scorer(Beam_configuration * config) const932 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
933 {
934 score_count++;
935 switch (config->next_scorer_todo)
936 {
937 case SLOPE_IDEAL:
938 score_slope_ideal (config);
939 break;
940 case SLOPE_DIRECTION:
941 score_slope_direction (config);
942 break;
943 case SLOPE_MUSICAL:
944 score_slope_musical (config);
945 break;
946 case FORBIDDEN:
947 score_forbidden_quants (config);
948 break;
949 case STEM_LENGTHS:
950 score_stem_lengths (config);
951 break;
952 case COLLISIONS:
953 score_collisions (config);
954 break;
955 case HORIZONTAL_INTER:
956 score_horizontal_inter_quants (config);
957 break;
958
959 case NUM_SCORERS:
960 case ORIGINAL_DISTANCE:
961 default:
962 assert (false);
963 }
964 config->next_scorer_todo++;
965 }
966
967 Beam_configuration *
force_score(SCM inspect_quants,const vector<unique_ptr<Beam_configuration>> & configs) const968 Beam_scoring_problem::force_score (SCM inspect_quants,
969 const vector<unique_ptr<Beam_configuration>> &configs) const
970 {
971 Drul_array<Real> ins = from_scm<Drul_array<Real>> (inspect_quants);
972 Real mindist = 1e6;
973 Beam_configuration *best = NULL;
974 for (vsize i = 0; i < configs.size (); i++)
975 {
976 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
977 if (d < mindist)
978 {
979 best = configs[i].get ();
980 mindist = d;
981 }
982 }
983 if (mindist > 1e5)
984 programming_error ("cannot find quant");
985
986 while (!best->done ())
987 one_scorer (best);
988
989 return best;
990 }
991
992 Drul_array<Real>
solve() const993 Beam_scoring_problem::solve () const
994 {
995 vector<unique_ptr<Beam_configuration>> configs;
996 generate_quants (&configs);
997
998 if (configs.empty ())
999 {
1000 programming_error ("No viable beam quanting found. Using unquanted y value.");
1001 return unquanted_y_;
1002 }
1003
1004 if (from_scm<bool> (get_property (beam_, "skip-quanting")))
1005 return unquanted_y_;
1006
1007 Beam_configuration *best = NULL;
1008
1009 bool debug
1010 = from_scm<bool> (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
1011 SCM inspect_quants = get_property (beam_, "inspect-quants");
1012 if (scm_is_pair (inspect_quants))
1013 {
1014 debug = true;
1015 best = force_score (inspect_quants, configs);
1016 }
1017 else
1018 {
1019 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
1020 Beam_configuration_less > queue;
1021 for (vsize i = 0; i < configs.size (); i++)
1022 queue.push (configs[i].get ());
1023
1024 /*
1025 TODO
1026
1027 It would be neat if we generated new configurations on the
1028 fly, depending on the best complete score so far, eg.
1029
1030 if (best->done()) {
1031 if (best->demerits < sqrt(queue.size())
1032 break;
1033 while (best->demerits > sqrt(queue.size()) {
1034 generate and insert new configuration
1035 }
1036 }
1037
1038 that would allow us to do away with region_size altogether.
1039 */
1040 while (true)
1041 {
1042 best = queue.top ();
1043 if (best->done ())
1044 break;
1045
1046 queue.pop ();
1047 one_scorer (best);
1048 queue.push (best);
1049 }
1050 }
1051
1052 Drul_array<Real> final_positions = best->y;
1053
1054 #if DEBUG_BEAM_SCORING
1055 if (debug)
1056 {
1057 // debug quanting
1058 int completed = 0;
1059 for (vsize i = 0; i < configs.size (); i++)
1060 {
1061 if (configs[i]->done ())
1062 completed++;
1063 }
1064
1065 string card = best->score_card_ + to_string (" c%d/%zu", completed, configs.size ());
1066 set_property (beam_, "annotation", ly_string2scm (card));
1067 }
1068 #endif
1069
1070 configs.clear ();
1071 if (align_broken_intos_)
1072 {
1073 Interval normalized_endpoints = from_scm (get_property (beam_, "normalized-endpoints"), Interval (0, 1));
1074 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1075
1076 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1077 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1078 }
1079
1080 return final_positions;
1081 }
1082
1083 void
score_stem_lengths(Beam_configuration * config) const1084 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1085 {
1086 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1087 Drul_array<Real> score (0, 0);
1088 Drul_array<int> count (0, 0);
1089
1090 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1091 {
1092 if (!is_normal_[i])
1093 continue;
1094
1095 Real x = stem_xpositions_[i];
1096 Real dx = x_span_;
1097 Real beam_y = dx
1098 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1099 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1100 Real current_y = beam_y + base_lengths_[i];
1101 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1102
1103 Stem_info info = stem_infos_[i];
1104 Direction d = info.dir_;
1105
1106 score[d] += limit_penalty * std::max (0.0, (d * (info.shortest_y_ - current_y)));
1107
1108 Real ideal_diff = d * (current_y - info.ideal_y_);
1109 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1110
1111 /* We introduce a power, to make the scoring strictly
1112 convex. Otherwise a symmetric knee beam (up/down/up/down)
1113 does not have an optimum in the middle. */
1114 if (is_knee_)
1115 ideal_score = pow (ideal_score, 1.1);
1116
1117 score[d] += length_pen * ideal_score;
1118 count[d]++;
1119 }
1120
1121 /* Divide by number of stems, to make the measure scale-free. */
1122 for (DOWN_and_UP (d))
1123 score[d] /= std::max (count[d], 1);
1124
1125 /*
1126 sometimes, two perfectly symmetric kneed beams will have the same score
1127 and can either be quanted up or down.
1128
1129 we choose the quanting in the direction of the slope so that the first stem
1130 always seems longer, reaching to the second, rather than squashed.
1131 */
1132 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1133 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1134
1135 config->add (score[LEFT] + score[RIGHT], "L");
1136 }
1137
1138 void
score_slope_direction(Beam_configuration * config) const1139 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1140 {
1141 Real dy = config->y.delta ();
1142 Real damped_dy = unquanted_y_.delta ();
1143 Real dem = 0.0;
1144 /*
1145 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1146 complex beaming patterns, horizontal is often a good choice.
1147
1148 TODO: find a way to incorporate the complexity of the beam in this
1149 penalty.
1150 */
1151 if (sign (damped_dy) != sign (dy))
1152 {
1153 if (!dy)
1154 {
1155 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1156 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1157 else
1158 dem += parameters_.HINT_DIRECTION_PENALTY;
1159 }
1160 else
1161 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1162 }
1163
1164 config->add (dem, "Sd");
1165 }
1166
1167 // Score for going against the direction of the musical pattern
1168 void
score_slope_musical(Beam_configuration * config) const1169 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1170 {
1171 Real dy = config->y.delta ();
1172 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1173 * std::max (0.0, (fabs (dy) - fabs (musical_dy_)));
1174 config->add (dem, "Sm");
1175 }
1176
1177 // Score deviation from calculated ideal slope.
1178 void
score_slope_ideal(Beam_configuration * config) const1179 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1180 {
1181 Real dy = config->y.delta ();
1182 Real damped_dy = unquanted_y_.delta ();
1183 Real dem = 0.0;
1184
1185 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1186
1187 /* Xstaff beams tend to use extreme slopes to get short stems. We
1188 put in a penalty here. */
1189 if (is_xstaff_)
1190 slope_penalty *= 10;
1191
1192 /* Huh, why would a too steep beam be better than a too flat one ? */
1193 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1194 * slope_penalty;
1195
1196 config->add (dem, "Si");
1197 }
1198
1199 static Real
my_modf(Real x)1200 my_modf (Real x)
1201 {
1202 return x - floor (x);
1203 }
1204
1205 // TODO - there is some overlap with forbidden quants, but for
1206 // horizontal beams, it is much more serious to have stafflines
1207 // appearing in the wrong place, so we have a separate scorer.
1208 void
score_horizontal_inter_quants(Beam_configuration * config) const1209 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1210 {
1211 if (config->y.delta () == 0.0
1212 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1213 {
1214 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1215 if (fabs (round_halfway_up (yshift) - yshift) < 0.01 * staff_space_)
1216 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1217 }
1218 }
1219
1220 /*
1221 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1222 because for 32nd and 64th beams the forbidden quants are relatively
1223 more important than stem lengths.
1224 */
1225 void
score_forbidden_quants(Beam_configuration * config) const1226 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1227 {
1228 Real dy = config->y.delta ();
1229
1230 Real extra_demerit
1231 = parameters_.SECONDARY_BEAM_DEMERIT
1232 / std::max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1233
1234 Real dem = 0.0;
1235 Real eps = parameters_.BEAM_EPS;
1236
1237 for (LEFT_and_RIGHT (d))
1238 {
1239 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1240 {
1241 Direction stem_dir = edge_dirs_[d];
1242
1243 /*
1244 The fudge_factor is to provide a little leniency for
1245 borderline cases. If we do 2.0, then the upper outer line
1246 will be in the gap of the (2, sit) quant, leading to a
1247 false demerit. By increasing the fudge factor to 2.2, we
1248 fix this case.
1249 */
1250 Real fudge_factor = 2.2;
1251 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / fudge_factor);
1252 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / fudge_factor);
1253
1254 Interval gap;
1255 gap.add_point (gap1);
1256 gap.add_point (gap2);
1257
1258 for (Real k = -staff_radius_;
1259 k <= staff_radius_ + eps; k += 1.0)
1260 if (gap.contains (k))
1261 {
1262 Real dist = std::min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1263
1264 /*
1265 this parameter is tuned to grace-stem-length.ly
1266 retuned from 0.40 to 0.39 by MS because of slight increases
1267 in gap.length () resulting from measuring beams at real ends
1268 instead of from the middle of stems.
1269
1270 TODO:
1271 This function needs better comments so we know what is forbidden
1272 and why.
1273 */
1274 Real fixed_demerit = 0.39;
1275
1276 dem += extra_demerit
1277 * (fixed_demerit
1278 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1279 }
1280 }
1281 }
1282
1283 config->add (dem, "Fl");
1284 dem = 0.0;
1285 if (std::max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1286 {
1287 Real straddle = 0.0;
1288 Real sit = (beam_thickness_ - line_thickness_) / 2;
1289 Real inter = 0.5;
1290 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1291
1292 for (LEFT_and_RIGHT (d))
1293 {
1294 if (edge_beam_counts_[d] >= 2
1295 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1296 {
1297 // TODO up/down symmetry.
1298 if (edge_dirs_[d] == UP && dy <= eps
1299 && fabs (my_modf (config->y[d]) - sit) < eps)
1300 dem += extra_demerit;
1301
1302 if (edge_dirs_[d] == DOWN && dy >= eps
1303 && fabs (my_modf (config->y[d]) - hang) < eps)
1304 dem += extra_demerit;
1305 }
1306
1307 if (edge_beam_counts_[d] >= 3
1308 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1309 {
1310 // TODO up/down symmetry.
1311 if (edge_dirs_[d] == UP && dy <= eps
1312 && fabs (my_modf (config->y[d]) - straddle) < eps)
1313 dem += extra_demerit;
1314
1315 if (edge_dirs_[d] == DOWN && dy >= eps
1316 && fabs (my_modf (config->y[d]) - straddle) < eps)
1317 dem += extra_demerit;
1318 }
1319 }
1320 }
1321
1322 config->add (dem, "Fs");
1323 }
1324
1325 void
score_collisions(Beam_configuration * config) const1326 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1327 {
1328 Real demerits = 0.0;
1329 for (vsize i = 0; i < collisions_.size (); i++)
1330 {
1331 Interval collision_y = collisions_[i].y_;
1332 Real x = collisions_[i].x_;
1333
1334 Real center_beam_y = y_at (x, config);
1335 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1336
1337 Real dist = infinity_f;
1338 if (!intersection (beam_y, collision_y).is_empty ())
1339 dist = 0.0;
1340 else
1341 dist = std::min (beam_y.distance (collision_y[DOWN]),
1342 beam_y.distance (collision_y[UP]));
1343
1344 Real scale_free
1345 = std::max (parameters_.COLLISION_PADDING - dist, 0.0)
1346 / parameters_.COLLISION_PADDING;
1347 Real collision_demerit = collisions_[i].base_penalty_ *
1348 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1349
1350 if (collision_demerit > 0)
1351 {
1352 demerits += collision_demerit;
1353 }
1354 }
1355
1356 config->add (demerits, "C");
1357 }
1358