2 gourlay-breaking.cc -- implement Gourlay_breaking
4 source file of the GNU LilyPond music typesetter
6 (c) 1997--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
9 #include "gourlay-breaking.hh"
11 #include <cmath> // rint
15 #include "international.hh"
17 #include "output-def.hh"
18 #include "paper-column.hh"
19 #include "paper-score.hh"
20 #include "simple-spacer.hh"
24 /// How often to print operator pacification marks?
25 const int HAPPY_DOTS = 3;
28 Helper to trace back an optimal path
32 /** this was the previous. If negative, this break should not be
33 considered: this path has infinite energy
38 Which system number so far?
43 Column_x_positions line_config_;
54 printf ("prev break %d, line %d, demerits %f\n",
55 prev_break_, line_, demerits_);
60 print_break_nodes (vector<Break_node> const &arr)
62 for (vsize i = 0; i < arr.size (); i++)
64 printf ("node %d: ", i);
70 This algorithms is adapted from the OSU Tech report on breaking lines.
72 this function is longish, but not very complicated.
74 TODO: should rewrite. See the function in scm/page-layout.scm for
77 vector<Column_x_positions>
78 Gourlay_breaking::solve ()
80 vector<Break_node> optimal_paths;
82 = pscore_->root_system ()->columns ();
84 vector<vsize> breaks = pscore_->find_break_indices ();
86 Break_node first_node;
87 optimal_paths.push_back (first_node);
89 bool ragged_right = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
90 bool ragged_last = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
92 Real worst_force = 0.0;
93 for (vsize break_idx = 1; break_idx < breaks.size (); break_idx++)
96 start with a short line, add measures. At some point
97 the line becomes infeasible. Then we don't try to add more
99 int minimal_start_idx = -1;
100 Column_x_positions minimal_sol;
101 Column_x_positions backup_sol;
103 Real minimal_demerits = infinity_f;
105 for (vsize start_idx = break_idx; start_idx--;)
107 vector<Grob*> line (all.begin () + breaks[start_idx],
108 all.begin () + breaks[break_idx] + 1);
111 = line_dimensions_int (pscore_->layout (), optimal_paths[start_idx].line_);
112 bool last_line = break_idx == breaks.size () - 1;
113 bool ragged = ragged_right || (last_line && ragged_last);
115 Column_x_positions cp = get_line_configuration (line, line_dims[RIGHT] - line_dims[LEFT],
116 line_dims[LEFT], ragged);
118 if (ragged && last_line)
119 cp.force_ = min (cp.force_, 0.0);
121 if (fabs (cp.force_) > worst_force)
122 worst_force = fabs (cp.force_);
125 We remember this solution as a "should always work
126 solution", in case everything fucks up. */
127 if (start_idx == break_idx - 1)
132 if (optimal_paths[start_idx].demerits_ >= infinity_f)
133 this_demerits = infinity_f;
135 this_demerits = combine_demerits (optimal_paths[start_idx].line_config_, cp)
136 + optimal_paths[start_idx].demerits_;
138 if (this_demerits < minimal_demerits)
140 minimal_start_idx = start_idx;
142 minimal_demerits = this_demerits;
146 we couldn't satisfy the constraints, this won't get better
147 if we add more columns, so we get on with the next one
149 if (!cp.satisfies_constraints_)
154 if (minimal_start_idx < 0)
156 bnod.demerits_ = infinity_f;
157 bnod.line_config_ = backup_sol;
158 bnod.prev_break_ = break_idx - 1;
162 bnod.prev_break_ = minimal_start_idx;
163 bnod.demerits_ = minimal_demerits;
164 bnod.line_config_ = minimal_sol;
166 bnod.line_ = optimal_paths[bnod.prev_break_].line_ + 1;
167 optimal_paths.push_back (bnod);
169 if (! (break_idx % HAPPY_DOTS))
170 progress_indication (string ("[") + to_string (break_idx) + "]");
173 /* do the last one */
174 if (breaks.size () % HAPPY_DOTS)
175 progress_indication (string ("[") + to_string (breaks.size ()) + "]");
177 progress_indication ("\n");
179 vector<int> final_breaks;
180 vector<Column_x_positions> lines;
182 /* skip 0-th element, since it is a "dummy" elt*/
183 for (vsize i = optimal_paths.size () - 1; i > 0;)
185 final_breaks.push_back (i);
186 vsize prev = optimal_paths[i].prev_break_;
191 if (be_verbose_global)
193 message (_f ("Optimal demerits: %f",
194 optimal_paths.back ().demerits_) + "\n");
197 if (optimal_paths.back ().demerits_ >= infinity_f)
198 warning (_ ("no feasible line breaking found"));
200 for (vsize i = final_breaks.size (); i--;)
202 Column_x_positions cp (optimal_paths[final_breaks[i]].line_config_);
204 lines.push_back (cp);
205 if (!cp.satisfies_constraints_)
206 warning (_ ("can't find line breaking that satisfies constraints"));
211 Gourlay_breaking::Gourlay_breaking ()
216 TODO: uniformity parameter to control rel. importance of spacing differences.
220 mixing break penalties and constraint-failing solutions is confusing.
223 Gourlay_breaking::combine_demerits (Column_x_positions const &prev,
224 Column_x_positions const &this_one) const
226 Real break_penalties = 0.0;
227 Grob *pc = this_one.cols_.back ();
230 SCM pen = pc->get_property ("line-break-penalty");
231 if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
232 break_penalties += scm_to_double (pen);
236 Q: do we want globally non-cramped lines, or locally equally
239 There used to be an example file input/test/uniform-breaking to
240 demonstrate problems with this approach. When music is gradually
241 becoming denser, the uniformity requirement makes lines go from
242 cramped to even more cramped (because going from cramped
243 3meas/line to relatively loose 2meas/line is such a big step.
247 Real demerit = abs (this_one.force_) + abs (prev.force_ - this_one.force_)
250 if (!this_one.satisfies_constraints_)
253 If it doesn't satisfy constraints, we make this one
256 add 20000 to the demerits, so that a break penalty
257 of -10000 won't change the result */
258 demerit = max ((demerit + 20000), 2000.0);