Line data Source code
1 : /*
2 : * SPDX-License-Identifier: GPL-3.0-only
3 : * MuseScore-CLA-applies
4 : *
5 : * MuseScore Studio
6 : * Music Composition & Notation
7 : *
8 : * Copyright (C) 2023 MuseScore Limited and others
9 : *
10 : * This program is free software: you can redistribute it and/or modify
11 : * it under the terms of the GNU General Public License version 3 as
12 : * published by the Free Software Foundation.
13 : *
14 : * This program is distributed in the hope that it will be useful,
15 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 : * GNU General Public License for more details.
18 : *
19 : * You should have received a copy of the GNU General Public License
20 : * along with this program. If not, see <https://www.gnu.org/licenses/>.
21 : */
22 : #include <algorithm>
23 : #include <cfloat>
24 :
25 : #include "accidentalslayout.h"
26 : #include "layoutcontext.h"
27 : #include "../paddingtable.h"
28 : #include "shape.h"
29 : #include "tlayout.h"
30 :
31 : #include "dom/accidental.h"
32 : #include "dom/chord.h"
33 : #include "dom/ledgerline.h"
34 : #include "dom/note.h"
35 : #include "dom/score.h"
36 :
37 : using namespace mu::engraving;
38 : using namespace mu::engraving::rendering::score;
39 :
40 3043 : AccidentalsLayout::AccidentalsLayoutContext::AccidentalsLayoutContext(std::vector<Accidental*> acc,
41 3043 : std::vector<Chord*> ch)
42 3043 : : allAccidentals(std::move(acc)), chords(std::move(ch))
43 : {
44 3043 : sortTopDown(allAccidentals);
45 3043 : stackedAccidentals.reserve(allAccidentals.size());
46 3043 : stackedAccidentalsShape.elements().reserve(4 * allAccidentals.size());
47 :
48 3043 : initConstants();
49 3043 : }
50 :
51 3043 : void AccidentalsLayout::AccidentalsLayoutContext::initConstants()
52 : {
53 3043 : m_spatium = allAccidentals.front()->spatium();
54 :
55 : // Hardcoded engraving parameters that don't have a style (some of these may get a style in future)
56 3043 : m_verticalAccidentalToAccidentalClearance = 0.15 * m_spatium;
57 3043 : m_verticalSharpToSharpClearance = 0.05 * m_spatium;
58 3043 : m_verticalAccidentalToChordClearance = 0.10 * m_spatium;
59 3043 : m_additionalPaddingForVerticals = 0.1 * m_spatium;
60 3043 : m_xPosSplitThreshold = 0.5 * m_spatium;
61 3043 : m_xVerticalAlignmentThreshold = 0.75 * m_spatium;
62 3043 : m_sharpAndNaturalLedgerLinePadding = 0.1 * m_spatium;
63 3043 : m_reducedFlatToNotePadding = 0.15 * m_spatium;
64 3043 : m_flatKerningOfFourth = -0.15 * m_spatium;
65 3043 : m_naturalKerningOfFourth = -0.05 * m_spatium;
66 :
67 3043 : const MStyle& style = allAccidentals.front()->style();
68 3043 : m_accidentalAccidentalDistance = style.styleAbsolute(Sid::accidentalDistance);
69 3043 : m_orderFollowNoteDisplacement = style.styleB(Sid::accidentalOrderFollowsNoteDisplacement);
70 3043 : m_alignOctavesAcrossSubChords = style.styleB(Sid::alignAccidentalOctavesAcrossSubChords);
71 3043 : m_keepSecondsTogether = style.styleB(Sid::keepAccidentalSecondsTogether);
72 3043 : m_alignOffsetOctaves = style.styleB(Sid::alignOffsetOctaveAccidentals);
73 3043 : }
74 :
75 88588 : void AccidentalsLayout::layoutAccidentals(const std::vector<Chord*>& chords, LayoutContext& ctx)
76 : {
77 88588 : std::vector<Accidental*> allAccidentals;
78 88588 : std::vector<Accidental*> redundantAccidentals;
79 88588 : std::vector<Accidental*> invisibleAccidentals;
80 :
81 88588 : collectAccidentals(chords, allAccidentals, redundantAccidentals, invisibleAccidentals);
82 :
83 88596 : for (Accidental* acc : invisibleAccidentals) {
84 8 : acc->computeMag();
85 8 : TLayout::layoutAccidental(acc, acc->mutldata(), ctx.conf());
86 8 : double x = -acc->ldata()->bbox().width();
87 8 : x -= acc->note() ? acc->note()->pos().x() : 0.0;
88 8 : acc->setPos(x, 0.0);
89 : }
90 :
91 88588 : if (allAccidentals.empty()) {
92 85545 : return;
93 : }
94 :
95 3043 : for (Accidental* acc : redundantAccidentals) {
96 0 : acc->setPos(0.0, 0.0);
97 0 : acc->setbbox(RectF());
98 : }
99 :
100 7049 : for (Accidental* acc : allAccidentals) {
101 4006 : acc->setPos(0.0, 0.0);
102 4006 : acc->computeMag();
103 4006 : TLayout::layoutAccidental(acc, acc->mutldata(), ctx.conf());
104 : }
105 :
106 3043 : AccidentalsLayoutContext accidentalsLayoutContext(std::move(allAccidentals), chords);
107 3043 : doAccidentalPlacement(accidentalsLayoutContext);
108 259678 : }
109 :
110 88588 : void AccidentalsLayout::collectAccidentals(const std::vector<Chord*> chords, std::vector<Accidental*>& allAccidentals,
111 : std::vector<Accidental*>& redundantAccidentals, std::vector<Accidental*>& invisibleAccidentals)
112 : {
113 138368 : for (const Chord* chord : chords) {
114 108399 : for (const Note* note : chord->notes()) {
115 58619 : Accidental* acc = note->accidental();
116 58619 : if (!acc) {
117 54605 : continue;
118 : }
119 4014 : if (accidentalIsRedundant(acc, allAccidentals)) {
120 0 : redundantAccidentals.push_back(acc);
121 4014 : } else if (!acc->addToSkyline()) {
122 8 : invisibleAccidentals.push_back(acc);
123 : } else {
124 4006 : allAccidentals.push_back(acc);
125 : }
126 : }
127 : }
128 88588 : }
129 :
130 4014 : bool AccidentalsLayout::accidentalIsRedundant(const Accidental* acc, const std::vector<Accidental*>& allAccidentals)
131 : {
132 5803 : for (const Accidental* otherAcc : allAccidentals) {
133 1789 : if (otherAcc->accidentalType() == acc->accidentalType() && otherAcc->line() == acc->line()) {
134 0 : return true;
135 : }
136 : }
137 :
138 4014 : return false;
139 : }
140 :
141 3043 : void AccidentalsLayout::doAccidentalPlacement(AccidentalsLayoutContext& ctx)
142 : {
143 3043 : createChordsShape(ctx);
144 :
145 3043 : findOctavesAndSeconds(ctx);
146 3043 : splitIntoSubChords(ctx);
147 :
148 6171 : for (std::vector<Accidental*>& accidentalSubChord : ctx.accidentalSubChords) {
149 3128 : layoutSubChord(accidentalSubChord, ctx);
150 : }
151 :
152 3043 : verticallyAlignAccidentals(ctx);
153 3043 : }
154 :
155 3043 : void AccidentalsLayout::findOctavesAndSeconds(const AccidentalsLayoutContext& ctx)
156 : {
157 7049 : for (Accidental* acc1 : ctx.allAccidentals) {
158 4006 : std::vector<Accidental*>& octaves = acc1->mutldata()->octaves.mut_value();
159 4006 : octaves.clear();
160 4006 : std::vector<Accidental*>& seconds = acc1->mutldata()->seconds.mut_value();
161 4006 : seconds.clear();
162 11590 : for (Accidental* acc2 : ctx.allAccidentals) {
163 7584 : if (acc2 == acc1) {
164 4006 : continue;
165 : }
166 3578 : if (isOctave(acc1, acc2)) {
167 416 : octaves.push_back(acc2);
168 3162 : } else if (abs(acc1->line() - acc2->line()) == 1) {
169 232 : seconds.push_back(acc2);
170 : }
171 : }
172 : }
173 3043 : }
174 :
175 3043 : void AccidentalsLayout::splitIntoSubChords(AccidentalsLayoutContext& ctx)
176 : {
177 3043 : ctx.accidentalSubChords.reserve(2);
178 :
179 3043 : std::vector<Accidental*> firstGroup;
180 3043 : firstGroup.reserve(ctx.allAccidentals.size());
181 3043 : firstGroup.push_back(ctx.allAccidentals.front());
182 3043 : ctx.accidentalSubChords.push_back(firstGroup);
183 :
184 : static constexpr int LINE_DIFF_OF_SEVENTH = 6;
185 :
186 4006 : for (size_t i = 1; i < ctx.allAccidentals.size(); ++i) {
187 963 : Accidental* prevAcc = ctx.allAccidentals[i - 1];
188 963 : Accidental* curAcc = ctx.allAccidentals[i];
189 963 : bool startNewGroup = curAcc->line() - prevAcc->line() >= LINE_DIFF_OF_SEVENTH;
190 963 : if (startNewGroup) {
191 936 : ctx.accidentalSubChords.push_back(std::vector<Accidental*> { curAcc });
192 : } else {
193 651 : ctx.accidentalSubChords.back().push_back(curAcc);
194 : }
195 : }
196 :
197 3043 : mergeAdjacentSubGroupsIfTooSmall(ctx);
198 :
199 3043 : ctx.subChordsCountBeforeOctaveMerge = ctx.accidentalSubChords.size();
200 3043 : if (ctx.alignOctavesAcrossSubChords()) {
201 0 : mergeSubGroupsWithOctavesAcross(ctx);
202 : }
203 3043 : }
204 :
205 3043 : void AccidentalsLayout::mergeAdjacentSubGroupsIfTooSmall(AccidentalsLayoutContext& ctx)
206 : {
207 3043 : const double approxOffsetNoteThreshold = 0.5 * ctx.spatium();
208 3043 : bool groupingChanged = false;
209 3270 : do {
210 3270 : groupingChanged = false;
211 3582 : for (size_t i = 0; i < ctx.accidentalSubChords.size() - 1; ++i) {
212 312 : std::vector<Accidental*>& thisGroup = ctx.accidentalSubChords[i];
213 312 : std::vector<Accidental*>& nextGroup = ctx.accidentalSubChords[i + 1];
214 312 : bool groupIsSmall = thisGroup.size() + nextGroup.size() <= ctx.smallGroupLimit();
215 312 : bool nextStartsWithOffsetNote = nextGroup.front()->note()->x() > approxOffsetNoteThreshold;
216 312 : if (groupIsSmall && !nextStartsWithOffsetNote) {
217 227 : groupingChanged = true;
218 227 : thisGroup.insert(thisGroup.end(), nextGroup.begin(), nextGroup.end());
219 227 : ctx.accidentalSubChords.erase(ctx.accidentalSubChords.begin() + i + 1);
220 : }
221 : }
222 : } while (groupingChanged);
223 3043 : }
224 :
225 0 : void AccidentalsLayout::mergeSubGroupsWithOctavesAcross(AccidentalsLayoutContext& ctx)
226 : {
227 0 : auto isOctaveAcrossGroups = [](const std::vector<Accidental*>& group1, const std::vector<Accidental*>& group2) {
228 0 : for (const Accidental* acc1 : group1) {
229 0 : for (Accidental* octaveAcc : acc1->ldata()->octaves.value()) {
230 0 : if (muse::contains(group2, octaveAcc)) {
231 0 : return true;
232 : }
233 : }
234 : }
235 0 : return false;
236 : };
237 :
238 0 : bool foundOctave = false;
239 0 : do {
240 0 : foundOctave = false;
241 0 : for (size_t i = 0; i < ctx.accidentalSubChords.size() - 1; ++i) {
242 0 : std::vector<Accidental*>& thisGroup = ctx.accidentalSubChords[i];
243 0 : for (size_t j = i + 1; j < ctx.accidentalSubChords.size(); ++j) {
244 0 : std::vector<Accidental*>& nextGroup = ctx.accidentalSubChords[j];
245 0 : foundOctave = isOctaveAcrossGroups(thisGroup, nextGroup);
246 0 : if (foundOctave) {
247 0 : thisGroup.insert(thisGroup.end(), nextGroup.begin(), nextGroup.end());
248 0 : ctx.accidentalSubChords.erase(ctx.accidentalSubChords.begin() + j);
249 0 : break;
250 : }
251 : }
252 0 : if (foundOctave) {
253 0 : break;
254 : }
255 : }
256 : } while (foundOctave);
257 0 : }
258 :
259 3043 : void AccidentalsLayout::createChordsShape(AccidentalsLayoutContext& ctx)
260 : {
261 3043 : ctx.chordsShape.clear();
262 :
263 6237 : for (const Chord* chord : ctx.chords) {
264 3194 : PointF chordPos = keepAccidentalsCloseToChord(chord) ? PointF() : chord->pos();
265 6767 : for (const LedgerLine* ledger : chord->ledgerLines()) {
266 3573 : ctx.chordsShape.add(ledger->shape().translate(ledger->pos() + chordPos));
267 : }
268 8539 : for (const Note* note : chord->notes()) {
269 5345 : SymId noteSym = note->ldata()->cachedNoteheadSym;
270 5345 : if (noteSym == SymId::noSym) {
271 4445 : noteSym = note->noteHead();
272 : }
273 5345 : ctx.chordsShape.add(note->symShapeWithCutouts(noteSym).translate(note->pos() + chordPos));
274 : }
275 3194 : const Stem* stem = chord->stem();
276 3194 : if (stem && stem->addToSkyline()) {
277 2560 : ctx.chordsShape.add(stem->shape().translate(stem->pos() + chordPos));
278 : }
279 : }
280 3043 : }
281 :
282 3128 : void AccidentalsLayout::layoutSubChord(std::vector<Accidental*>& accidentals, AccidentalsLayoutContext& ctx)
283 : {
284 3128 : computeOrdering(accidentals, ctx);
285 :
286 7134 : for (Accidental* acc : accidentals) {
287 4006 : stackAccidental(acc, ctx);
288 : }
289 3128 : }
290 :
291 4006 : void AccidentalsLayout::stackAccidental(Accidental* acc, AccidentalsLayoutContext& ctx)
292 : {
293 4006 : Shape accShape = acc->shape();
294 4006 : accShape.translateY(acc->note()->y());
295 :
296 4006 : double x = minAccidentalToChordDistance(acc, accShape, ctx);
297 4006 : accShape.translateX(-x);
298 :
299 4006 : double minDistToAccidGroup = minAccidentalToAccidentalGroupDistance(acc, accShape, ctx.stackedAccidentalsShape, ctx);
300 4006 : accShape.translateX(-minDistToAccidGroup);
301 4006 : x += minDistToAccidGroup;
302 :
303 4006 : setXposRelativeToSegment(acc, -x);
304 :
305 4006 : checkZeroColumn(acc, ctx);
306 4006 : ctx.stackedAccidentalsShape.add(accShape);
307 4006 : ctx.stackedAccidentals.push_back(acc);
308 4006 : }
309 :
310 4006 : void AccidentalsLayout::checkZeroColumn(Accidental* acc, const AccidentalsLayoutContext& ctx)
311 : {
312 4006 : int column = acc->ldata()->column;
313 4006 : if (column != 0) {
314 557 : return;
315 : }
316 :
317 3449 : RectF thisBBox = acc->ldata()->bbox().translated(xPosRelativeToSegment(acc), 0.0);
318 4105 : for (Accidental* stackedAcc : ctx.stackedAccidentals) {
319 656 : RectF placedBBox = stackedAcc->ldata()->bbox().translated(xPosRelativeToSegment(stackedAcc), 0.0);
320 656 : if (thisBBox.right() < placedBBox.left()) {
321 12 : column = std::max(column, stackedAcc->ldata()->column.value() + 1);
322 : }
323 : }
324 3449 : acc->mutldata()->column = column;
325 : }
326 :
327 3128 : void AccidentalsLayout::computeOrdering(std::vector<Accidental*>& accidentals, AccidentalsLayoutContext& ctx)
328 : {
329 3128 : AccidentalGroups priorityGroups = splitIntoPriorityGroups(accidentals, ctx);
330 :
331 3128 : accidentals.clear();
332 6274 : for (std::vector<Accidental*>& group : priorityGroups) {
333 3146 : determineStackingOrder(group, ctx);
334 3146 : accidentals.insert(accidentals.end(), group.begin(), group.end());
335 : }
336 :
337 3128 : applyOrderingOffsets(accidentals);
338 3128 : }
339 :
340 3128 : AccidentalGroups AccidentalsLayout::splitIntoPriorityGroups(std::vector<Accidental*>& accidentals, AccidentalsLayoutContext& ctx)
341 : {
342 3128 : AccidentalGroups groups;
343 :
344 3128 : if (ctx.orderFollowNoteDisplacement()) {
345 0 : AccidentalGroups noteSplitGroups = splitAccordingToNoteDisplacement(accidentals, ctx);
346 0 : for (auto noteSplitGroup : noteSplitGroups) {
347 0 : AccidentalGroups accidSplitGroups = splitAccordingToAccidDisplacement(noteSplitGroup, ctx);
348 0 : groups.insert(groups.end(), accidSplitGroups.begin(), accidSplitGroups.end());
349 0 : }
350 0 : } else {
351 3128 : groups = splitAccordingToAccidDisplacement(accidentals, ctx);
352 : }
353 :
354 3128 : size_t curGroupsCount = groups.size();
355 3128 : if (ctx.alignOctavesAcrossSubChords()) {
356 0 : mergeSubGroupsWithOctavesAcross(ctx);
357 0 : if (groups.size() != curGroupsCount) {
358 0 : for (auto& subGroup : groups) {
359 0 : sortTopDown(subGroup);
360 : }
361 : }
362 : }
363 :
364 3128 : return groups;
365 0 : }
366 :
367 3128 : AccidentalGroups AccidentalsLayout::splitAccordingToAccidDisplacement(std::vector<Accidental*>& accidentals,
368 : const AccidentalsLayoutContext& ctx)
369 : {
370 3128 : AccidentalGroups subGroups = groupAccidentalsByXPos(accidentals, ctx);
371 :
372 3128 : muse::remove_if(subGroups, [](auto& subGroup) {
373 6256 : return subGroup.size() == 0;
374 : });
375 :
376 3128 : if (subGroups.size() > 1 && subGroups[0].size() > 1) {
377 4 : moveOctavesToSecondGroup(subGroups);
378 : }
379 :
380 6274 : for (std::vector<Accidental*>& subGroup : subGroups) {
381 3146 : sortTopDown(subGroup);
382 : }
383 :
384 3128 : return subGroups;
385 0 : }
386 :
387 3128 : AccidentalGroups AccidentalsLayout::groupAccidentalsByXPos(std::vector<Accidental*>& accidentals, const AccidentalsLayoutContext& ctx)
388 : {
389 3128 : std::map<double, std::vector<Accidental*> > groupsOfEqualX;
390 :
391 7134 : for (Accidental* acc : accidentals) {
392 4006 : Shape accRoughShape = Shape(acc->symBbox(acc->symId()), acc);
393 4006 : accRoughShape.translateY(acc->note()->y());
394 4006 : double x = -minAccidentalToChordDistance(acc, accRoughShape, ctx) + acc->symWidth(acc->symId());
395 4006 : groupsOfEqualX[std::round(x)].push_back(acc);
396 4006 : }
397 :
398 3128 : double splitPoint = DBL_MAX;
399 3128 : double prevX = (*groupsOfEqualX.begin()).first;
400 6691 : for (auto& pair : groupsOfEqualX) {
401 3581 : double curX = pair.first;
402 3581 : if (curX - prevX > ctx.xPosSplitThreshold()) {
403 18 : splitPoint = curX;
404 18 : break;
405 : }
406 3563 : prevX = curX;
407 : }
408 :
409 3128 : AccidentalGroups subGroups(2);
410 6712 : for (auto& pair : groupsOfEqualX) {
411 3584 : if (pair.first >= splitPoint) {
412 43 : for (Accidental* acc : pair.second) {
413 22 : subGroups[0].push_back(acc);
414 22 : acc->mutldata()->verticalSubgroup = 0;
415 : }
416 : } else {
417 7547 : for (Accidental* acc : pair.second) {
418 3984 : subGroups[1].push_back(acc);
419 3984 : acc->mutldata()->verticalSubgroup = 1;
420 : }
421 : }
422 : }
423 :
424 3128 : return subGroups;
425 3128 : }
426 :
427 4 : void AccidentalsLayout::moveOctavesToSecondGroup(AccidentalGroups& subGroups)
428 : {
429 4 : IF_ASSERT_FAILED(subGroups.size() == 2) {
430 0 : return;
431 : }
432 :
433 4 : std::vector<Accidental*>& firstGroup = subGroups[0];
434 4 : std::vector<Accidental*>& secondGroup = subGroups[1];
435 4 : auto iter = firstGroup.begin();
436 12 : while (iter != firstGroup.end()) {
437 8 : Accidental* acc = *iter;
438 8 : bool removeOne = false;
439 8 : for (Accidental* octaveAcc : acc->ldata()->octaves.value()) {
440 6 : if (muse::contains(secondGroup, octaveAcc)) {
441 6 : removeOne = true;
442 6 : secondGroup.push_back(acc);
443 6 : acc->mutldata()->verticalSubgroup = 1;
444 6 : break;
445 : }
446 : }
447 8 : if (removeOne) {
448 6 : iter = firstGroup.erase(iter);
449 : } else {
450 2 : ++iter;
451 : }
452 : }
453 : }
454 :
455 0 : AccidentalGroups AccidentalsLayout::splitAccordingToNoteDisplacement(std::vector<Accidental*>& accidentals,
456 : const AccidentalsLayoutContext& ctx)
457 : {
458 0 : AccidentalGroups subGroups = groupAccidentalsByNoteXPos(accidentals);
459 :
460 0 : if (ctx.keepSecondsTogether()) {
461 0 : moveSecondsInSameGroup(subGroups);
462 : }
463 :
464 0 : for (size_t i = 0; i < subGroups.size(); ++i) {
465 0 : for (Accidental* acc : subGroups[i]) {
466 0 : acc->mutldata()->verticalSubgroup = static_cast<int>(i);
467 : }
468 : }
469 :
470 0 : return subGroups;
471 0 : }
472 :
473 0 : AccidentalGroups AccidentalsLayout::groupAccidentalsByNoteXPos(const std::vector<Accidental*>& accidentals)
474 : {
475 0 : AccidentalGroups subGroups;
476 :
477 0 : std::map<double, std::vector<Accidental*> > groupsOfEqualNoteX;
478 0 : for (Accidental* accidental : accidentals) {
479 0 : Note* note = accidental->note();
480 0 : double x = std::round(note->pos().x() + note->chord()->pos().x());
481 0 : groupsOfEqualNoteX[x].push_back(accidental);
482 : }
483 :
484 0 : for (auto iter = groupsOfEqualNoteX.rbegin(); iter != groupsOfEqualNoteX.rend(); ++iter) {
485 0 : subGroups.push_back((*iter).second);
486 : }
487 :
488 0 : return subGroups;
489 0 : }
490 :
491 0 : void AccidentalsLayout::moveSecondsInSameGroup(AccidentalGroups& subGroups)
492 : {
493 0 : bool secondMoved = false;
494 0 : do {
495 0 : secondMoved = false;
496 0 : for (size_t i = 0; i < subGroups.size() - 1; ++i) {
497 0 : std::vector<Accidental*>& thisGroup = subGroups[i];
498 0 : std::vector<Accidental*>& nextGroup = subGroups[i + 1];
499 0 : for (size_t j = 0; j < thisGroup.size(); ++j) {
500 0 : Accidental* acc1 = thisGroup[j];
501 0 : for (Accidental* secondAcc : acc1->ldata()->seconds.value()) {
502 0 : if (muse::remove(nextGroup, secondAcc)) {
503 0 : secondMoved = true;
504 0 : auto position = thisGroup.begin() + j;
505 0 : if (secondAcc->line() < acc1->line()) {
506 0 : thisGroup.insert(position, secondAcc);
507 : } else {
508 0 : thisGroup.insert(position + 1, secondAcc);
509 : }
510 0 : break;
511 : }
512 : }
513 0 : if (secondMoved) {
514 0 : break;
515 : }
516 : }
517 0 : if (nextGroup.size() == 0) {
518 0 : subGroups.erase(subGroups.begin() + i + 1);
519 : }
520 0 : if (secondMoved) {
521 0 : break;
522 : }
523 : }
524 : } while (secondMoved);
525 0 : }
526 :
527 3146 : void AccidentalsLayout::determineStackingOrder(std::vector<Accidental*>& accidentals, AccidentalsLayoutContext& ctx)
528 : {
529 3146 : size_t groupSize = accidentals.size();
530 :
531 3146 : if (groupSize <= ctx.smallGroupLimit()) {
532 3073 : computeStandardOrdering(accidentals, ctx);
533 73 : } else if (groupSize > ctx.largeGroupLimit()
534 73 : || (ctx.alignOctavesAcrossSubChords() && ctx.subChordsCountBeforeOctaveMerge > 1)) {
535 3 : computeCompactOrdering(accidentals, ctx);
536 : } else {
537 70 : computeOrderingWithLeastColumns(accidentals, ctx);
538 : }
539 3146 : }
540 :
541 70 : void AccidentalsLayout::computeOrderingWithLeastColumns(std::vector<Accidental*>& accidentals, AccidentalsLayoutContext& ctx)
542 : {
543 70 : std::vector<Accidental*> standardOrdered = accidentals;
544 70 : computeStandardOrdering(standardOrdered, ctx);
545 :
546 70 : std::vector<Accidental*> compactOrdered = accidentals;
547 70 : computeCompactOrdering(compactOrdered, ctx);
548 :
549 140 : auto totalColumns = [&](std::vector<Accidental*>& accGroup) {
550 140 : std::map<Accidental*, int> accidentalColumn;
551 140 : accidentalColumn[accGroup.front()] = 0;
552 140 : int maxColumn = 0;
553 646 : for (size_t i = 1; i < accGroup.size(); ++i) {
554 506 : Accidental* acc1 = accGroup[i];
555 506 : accidentalColumn[acc1] = maxColumn;
556 1712 : for (int j = static_cast<int>(i - 1); j >= 0; --j) {
557 1206 : Accidental* acc2 = accGroup[j];
558 1206 : if (accidentalColumn[acc2] < maxColumn) {
559 601 : continue;
560 : }
561 605 : if (!canFitInSameColumn(acc1, acc2, ctx)) {
562 321 : maxColumn += 1;
563 321 : accidentalColumn[acc1] = maxColumn;
564 : }
565 : }
566 : }
567 140 : return maxColumn;
568 140 : };
569 :
570 70 : accidentals = totalColumns(compactOrdered) < totalColumns(standardOrdered) ? compactOrdered : standardOrdered;
571 70 : }
572 :
573 3143 : void AccidentalsLayout::computeStandardOrdering(std::vector<Accidental*>& accidentals, AccidentalsLayoutContext& ctx)
574 : {
575 3143 : std::vector<Accidental*> accidentalsPlaced;
576 3143 : accidentalsPlaced.reserve(accidentals.size());
577 :
578 3143 : AccidentalsVectorView accidentalsToPlace { accidentals };
579 :
580 3143 : bool pickFromTop = true;
581 6987 : while (!accidentalsToPlace.empty()) {
582 3844 : Accidental* acc = pickFromTop ? accidentalsToPlace.pop_front() : accidentalsToPlace.pop_back();
583 3844 : accidentalsPlaced.push_back(acc);
584 :
585 3844 : if (ctx.keepSecondsTogether()) {
586 0 : findAndInsertSecond(acc, accidentalsPlaced, accidentalsToPlace, ctx);
587 : }
588 :
589 3844 : const bool foundOctave = findAndInsertOctave(acc, accidentalsPlaced, accidentalsToPlace, ctx);
590 3844 : if (foundOctave) {
591 137 : pickFromTop = true;
592 : } else {
593 3707 : pickFromTop = !pickFromTop;
594 : }
595 : }
596 :
597 3143 : accidentals = accidentalsPlaced;
598 3143 : }
599 :
600 73 : void AccidentalsLayout::computeCompactOrdering(std::vector<Accidental*>& accidentals, AccidentalsLayoutContext& ctx)
601 : {
602 73 : const size_t totAccidNumber = accidentals.size();
603 73 : Accidental* const bottomAcc = accidentals.back();
604 :
605 73 : std::vector<Accidental*> accidentalsPlaced;
606 73 : accidentalsPlaced.reserve(totAccidNumber);
607 :
608 73 : AccidentalsVectorView accidentalsToPlace { accidentals };
609 :
610 73 : bool pickFromTop = true;
611 321 : while (!accidentalsToPlace.empty()) {
612 248 : Accidental* acc = pickFromTop ? accidentalsToPlace.pop_front() : accidentalsToPlace.pop_back();
613 248 : accidentalsPlaced.push_back(acc);
614 :
615 248 : bool foundOneThatFits = false;
616 248 : bool hitBottom = false;
617 :
618 248 : if (findAndInsertOctave(acc, accidentalsPlaced, accidentalsToPlace, ctx, !pickFromTop, pickFromTop)) {
619 42 : foundOneThatFits = true;
620 42 : acc = accidentalsPlaced.back();
621 42 : if (acc == bottomAcc) {
622 21 : hitBottom = true;
623 : }
624 : }
625 :
626 : // fit others into same column
627 443 : const auto pred = [&](Accidental* acc2) {
628 443 : if ((pickFromTop && acc2->line() < acc->line()) || (!pickFromTop && acc2->line() > acc->line())) {
629 55 : return false;
630 : }
631 388 : if (canFitInSameColumn(acc, acc2, ctx)) {
632 64 : if (acc2->ldata()->octaves.value().size() > 0) {
633 10 : return false;
634 : }
635 54 : foundOneThatFits = true;
636 54 : accidentalsPlaced.push_back(acc2);
637 54 : acc = acc2;
638 54 : if (acc2 == bottomAcc) {
639 20 : hitBottom = true;
640 : }
641 54 : return true;
642 : }
643 324 : return false;
644 248 : };
645 :
646 248 : if (pickFromTop) {
647 177 : accidentalsToPlace.remove_if(pred);
648 : } else {
649 71 : accidentalsToPlace.reverse_remove_if(pred);
650 : }
651 :
652 248 : if (ctx.keepSecondsTogether()) {
653 0 : for (Accidental* alreadyPlacedAcc : accidentalsPlaced) {
654 0 : findAndInsertSecond(alreadyPlacedAcc, accidentalsPlaced, accidentalsToPlace, ctx);
655 : }
656 : }
657 :
658 248 : if (hitBottom || (foundOneThatFits && totAccidNumber <= ctx.largeGroupLimit())) {
659 87 : pickFromTop = true;
660 : } else {
661 161 : pickFromTop = !pickFromTop;
662 : }
663 : }
664 :
665 73 : accidentals = accidentalsPlaced;
666 73 : }
667 :
668 0 : void AccidentalsLayout::findAndInsertSecond(Accidental* acc, std::vector<Accidental*>& accidentalsPlaced,
669 : AccidentalsVectorView& accidentalsToPlace, AccidentalsLayoutContext& ctx)
670 : {
671 0 : const std::vector<Accidental*>& seconds = acc->ldata()->seconds.value();
672 0 : for (Accidental* secondAcc : seconds) {
673 0 : const bool removed = accidentalsToPlace.remove(secondAcc);
674 0 : if (removed) {
675 0 : if (ctx.orderFollowNoteDisplacement() && secondAcc->note()->x() > acc->note()->x()) {
676 0 : auto position = std::find(accidentalsPlaced.begin(), accidentalsPlaced.end(), acc);
677 0 : accidentalsPlaced.insert(position, secondAcc);
678 : } else {
679 0 : accidentalsPlaced.push_back(secondAcc);
680 : }
681 : }
682 : }
683 0 : }
684 :
685 4092 : bool AccidentalsLayout::findAndInsertOctave(Accidental* acc, std::vector<Accidental*>& accidentalsPlaced,
686 : AccidentalsVectorView& accidentalsToPlace, AccidentalsLayoutContext& ctx, bool acceptAbove,
687 : bool acceptBelow)
688 : {
689 4092 : bool foundOctave = false;
690 4092 : int thisLine = acc->line();
691 4092 : const std::vector<Accidental*>& octaves = acc->ldata()->octaves.value();
692 4424 : for (Accidental* octaveAcc : octaves) {
693 332 : const bool removed = accidentalsToPlace.remove_if([&](Accidental* a) {
694 475 : if (a == octaveAcc) {
695 183 : int octaveLine = octaveAcc->line();
696 183 : bool acceptOctave = (octaveLine < thisLine && acceptAbove) || (octaveLine > thisLine && acceptBelow);
697 183 : if (acceptOctave) {
698 183 : foundOctave = true;
699 183 : return true;
700 : }
701 : }
702 292 : return false;
703 : });
704 :
705 332 : if (removed) {
706 183 : accidentalsPlaced.push_back(octaveAcc);
707 :
708 183 : if (ctx.keepSecondsTogether()) {
709 0 : findAndInsertSecond(octaveAcc, accidentalsPlaced, accidentalsToPlace, ctx);
710 : }
711 : }
712 : }
713 :
714 4092 : return foundOctave;
715 : }
716 :
717 3128 : void AccidentalsLayout::applyOrderingOffsets(std::vector<Accidental*>& accidentals)
718 : {
719 : // Set default stacking number
720 3128 : int stackingNumber = 0;
721 7134 : for (Accidental* acc : accidentals) {
722 4006 : acc->mutldata()->stackingNumber = stackingNumber;
723 4006 : ++stackingNumber;
724 : }
725 :
726 : // Limit stacking offsets within boundaries
727 7134 : for (Accidental* acc : accidentals) {
728 4006 : int actualStackingOrder = acc->stackingOrder();
729 4006 : if (actualStackingOrder < 0) {
730 0 : acc->setStackingOrderOffset(acc->stackingOrderOffset() - actualStackingOrder);
731 4006 : } else if (actualStackingOrder >= stackingNumber) {
732 0 : int diff = actualStackingOrder - stackingNumber;
733 0 : acc->setStackingOrderOffset(acc->stackingOrderOffset() - diff - 1);
734 : }
735 : }
736 :
737 : // Sort vector
738 3128 : std::sort(accidentals.begin(), accidentals.end(), [](const Accidental* acc1, const Accidental* acc2) {
739 1756 : int stackingOrder1 = acc1->stackingOrder();
740 1756 : int stackingOrder2 = acc2->stackingOrder();
741 1756 : return stackingOrder1 == stackingOrder2 ? acc1->stackingOrderOffset() < acc2->stackingOrderOffset() : stackingOrder1 < stackingOrder2;
742 : });
743 3128 : }
744 :
745 8012 : double AccidentalsLayout::minAccidentalToChordDistance(Accidental* acc, const Shape& accShape, const AccidentalsLayoutContext& ctx)
746 : {
747 8012 : double dist = -DBL_MAX;
748 25769 : for (const ShapeElement& accidentalElement : accShape.elements()) {
749 17757 : double accTop = accidentalElement.top();
750 17757 : double accBottom = accidentalElement.bottom();
751 153792 : for (const ShapeElement& chordElement : ctx.chordsShape.elements()) {
752 136035 : double chordElementTop = chordElement.top();
753 136035 : double chordElementBottom = chordElement.bottom();
754 136035 : if (mu::engraving::intersects(accTop, accBottom, chordElementTop, chordElementBottom,
755 : ctx.verticalAccidentalToChordClearance())) {
756 77983 : double padding = computePadding(acc, chordElement.item(), ctx);
757 77983 : padding += additionalPaddingForVerticals(acc, chordElement.item(), ctx);
758 77983 : dist = std::max(dist, accidentalElement.right() - chordElement.left() + padding);
759 : }
760 136035 : dist = std::max(dist, kerningLimitationsIntoChord(acc, accShape, chordElement, ctx));
761 : }
762 : }
763 :
764 8012 : return dist;
765 : }
766 :
767 136035 : double AccidentalsLayout::kerningLimitationsIntoChord(Accidental* acc, const Shape& accShape, const ShapeElement& chordElement,
768 : const AccidentalsLayoutContext& ctx)
769 : {
770 136035 : const EngravingItem* chordItem = chordElement.item();
771 136035 : if (!chordItem) {
772 0 : return 0.0;
773 : }
774 :
775 136035 : AccidentalType accType = acc->accidentalType();
776 136035 : if (chordItem->isLedgerLine() && (accType == AccidentalType::NATURAL || accType == AccidentalType::SHARP)) {
777 30317 : if (chordItem->y() > accShape.top() && chordItem->y() < accShape.bottom()) {
778 8567 : return accShape.right() - chordElement.left() + ctx.sharpAndNaturalLedgerLinePadding();
779 : }
780 : }
781 :
782 127468 : return 0.0;
783 : }
784 :
785 77983 : double AccidentalsLayout::computePadding(Accidental* acc, const EngravingItem* chordElement, const AccidentalsLayoutContext& ctx)
786 : {
787 77983 : AccidentalType accType = acc->accidentalType();
788 77983 : bool isFlat = accType == AccidentalType::FLAT || accType == AccidentalType::FLAT2;
789 :
790 77983 : bool kernFlatIntoLedger = isFlat && chordElement->isLedgerLine() && chordElement->y() > acc->note()->y();
791 77983 : if (kernFlatIntoLedger) {
792 148 : return 0.0;
793 : }
794 :
795 77835 : const double yApproxThresholdForSharpLedgerKerning = 1.1 * ctx.spatium();
796 47207 : bool kernSharpIntoLedger = accType == AccidentalType::SHARP && chordElement->isLedgerLine()
797 125042 : && chordElement->y() > acc->note()->y() + yApproxThresholdForSharpLedgerKerning;
798 77835 : if (kernSharpIntoLedger) {
799 580 : return 0.0;
800 : }
801 :
802 77255 : bool kernFlatIntoNote = isFlat && chordElement->isNote() && chordElement->y() > acc->note()->y();
803 77255 : if (kernFlatIntoNote) {
804 550 : return ctx.reducedFlatToNotePadding();
805 : }
806 :
807 76705 : const PaddingTable& paddingTable = acc->score()->paddingTables().horizontalPaddingTable();
808 :
809 76705 : return paddingTable.at(ElementType::ACCIDENTAL).at(chordElement->type()) * 0.5 * (acc->mag() + chordElement->mag());
810 : }
811 :
812 4391 : double AccidentalsLayout::minAccidentalToAccidentalGroupDistance(Accidental* acc, Shape accShape, const Shape& accidentalsShape,
813 : const AccidentalsLayoutContext& ctx)
814 : {
815 4391 : double dist = 0.0;
816 4391 : int column = acc->ldata()->column;
817 :
818 : bool collisionFound;
819 4391 : int iter = 0;
820 : static constexpr int safetyNet = 50;
821 : do {
822 5263 : ++iter;
823 5263 : double curDist = 0.0;
824 5263 : collisionFound = false;
825 23039 : for (const ShapeElement& groupElement : accidentalsShape.elements()) {
826 17776 : const Accidental* acc2 = toAccidental(groupElement.item());
827 :
828 17776 : if (isExceptionOfFourth(acc, acc2)) {
829 135 : double distFourth = kerningOfFourth(accShape, groupElement, ctx);
830 135 : if (!muse::RealIsNull(distFourth) && distFourth > curDist) {
831 20 : collisionFound = true;
832 20 : curDist = distFourth;
833 : }
834 135 : column = std::max(column, acc2->ldata()->column + 1);
835 135 : continue;
836 135 : }
837 :
838 17641 : double vertPadding = verticalPadding(acc, acc2, ctx);
839 17641 : double horPadding = horizontalPadding(acc, acc2, ctx);
840 : // If the tolerance for detecting intersections is the same as the padding,
841 : // we may randomly detect wrong intersections just because of rounding errors
842 17641 : double horPaddingWithTolerance = 0.999 * horPadding;
843 17641 : if (accShape.intersects(groupElement.adjusted(-horPaddingWithTolerance, -vertPadding, horPaddingWithTolerance, vertPadding))) {
844 2998 : collisionFound = true;
845 : } else {
846 14643 : continue;
847 : }
848 :
849 2998 : if (!isExceptionOfNaturalsSixth(acc, acc2)) {
850 2998 : column = std::max(column, acc2->ldata()->column + 1);
851 : }
852 :
853 2998 : double groupTop = groupElement.top();
854 2998 : double groupBottom = groupElement.bottom();
855 13877 : for (ShapeElement& accElement : accShape.elements()) {
856 10879 : if (mu::engraving::intersects(accElement.top(), accElement.bottom(), groupTop, groupBottom, vertPadding)) {
857 8000 : double minDist = accElement.right() - groupElement.left() + horPadding;
858 8000 : minDist += additionalPaddingForVerticals(acc, acc2, ctx);
859 8000 : curDist = std::max(curDist, minDist);
860 : }
861 : }
862 : }
863 :
864 5263 : accShape.translateX(-curDist);
865 5263 : dist += curDist;
866 5263 : } while (collisionFound && iter < safetyNet);
867 :
868 4391 : IF_ASSERT_FAILED(iter < safetyNet) {
869 0 : LOGE() << "Accidental layout error.";
870 : }
871 :
872 4391 : acc->mutldata()->column = column;
873 :
874 4391 : return dist;
875 : }
876 :
877 17776 : bool AccidentalsLayout::isExceptionOfFourth(const Accidental* acc1, const Accidental* acc2)
878 : {
879 17776 : if (!acc1 || !acc2) {
880 0 : return false;
881 : }
882 :
883 35552 : if ((acc1->bracket() == AccidentalBracket::BRACKET || acc2->bracket() == AccidentalBracket::BRACKET)
884 35552 : && acc1->mag() == 1 && acc2->mag() == 1) {
885 0 : return false;
886 : }
887 :
888 17776 : AccidentalType accType1 = acc1->accidentalType();
889 17776 : AccidentalType accType2 = acc2->accidentalType();
890 :
891 16087 : return (accType1 == AccidentalType::FLAT || accType1 == AccidentalType::FLAT2)
892 1779 : && (accType2 == AccidentalType::FLAT || accType2 == AccidentalType::FLAT2 || accType2 == AccidentalType::NATURAL)
893 35552 : && acc1->line() - acc2->line() == 3;
894 : }
895 :
896 3991 : bool AccidentalsLayout::isExceptionOfNaturalsSixth(const Accidental* acc1, const Accidental* acc2)
897 : {
898 3991 : return acc1->accidentalType() == AccidentalType::NATURAL
899 124 : && acc2->accidentalType() == AccidentalType::NATURAL
900 4115 : && abs(acc2->line() - acc1->line()) == 5;
901 : }
902 :
903 993 : bool AccidentalsLayout::canFitInSameColumn(const Accidental* acc1, const Accidental* acc2, AccidentalsLayoutContext& ctx)
904 : {
905 993 : if (isExceptionOfNaturalsSixth(acc1, acc2)) {
906 2 : return true;
907 : }
908 :
909 991 : RectF acc1Box = acc1->ldata()->bbox().translated(PointF(0.0, acc1->note()->y()));
910 991 : RectF acc2Box = acc2->ldata()->bbox().translated(PointF(0.0, acc2->note()->y()));
911 :
912 991 : return !mu::engraving::intersects(acc1Box.top(), acc1Box.bottom(), acc2Box.top(), acc2Box.bottom(),
913 991 : verticalPadding(acc1, acc2, ctx));
914 : }
915 :
916 3578 : bool AccidentalsLayout::isOctave(const Accidental* acc1, const Accidental* acc2)
917 : {
918 3578 : return acc1->accidentalType() == acc2->accidentalType() && std::abs(acc2->line() - acc1->line()) % 7 == 0;
919 : }
920 :
921 135 : double AccidentalsLayout::kerningOfFourth(const Shape& accShape, const ShapeElement& accGroupShapeElement,
922 : const AccidentalsLayoutContext& ctx)
923 : {
924 135 : AccidentalType accType2 = toAccidental(accGroupShapeElement.item())->accidentalType();
925 :
926 135 : return accShape.right() - accGroupShapeElement.left()
927 135 : + (accType2 == AccidentalType::NATURAL ? ctx.naturalKerningOfFourth() : ctx.flatKerningOfFourth());
928 : }
929 :
930 85983 : double AccidentalsLayout::additionalPaddingForVerticals(const Accidental* acc, const EngravingItem* item,
931 : const AccidentalsLayoutContext& ctx)
932 : {
933 100970 : if (acc->accidentalType() != AccidentalType::NATURAL || acc->bracket() != AccidentalBracket::NONE
934 100970 : || (!item->isAccidental() && !item->isStem())) {
935 82934 : return 0.0;
936 : }
937 :
938 3049 : if (item->isAccidental()) {
939 239 : const Accidental* acc2 = toAccidental(item);
940 239 : AccidentalType accType2 = acc2->accidentalType();
941 239 : if (accType2 != AccidentalType::NATURAL && accType2 != AccidentalType::FLAT && accType2 != AccidentalType::FLAT2) {
942 102 : return 0.0;
943 : }
944 137 : int lineDiff = acc2->line() - acc->line();
945 137 : if (lineDiff < -2 || lineDiff > 5) {
946 56 : return 0.0;
947 : }
948 : }
949 :
950 2891 : return ctx.additionalPaddingForVerticals();
951 : }
952 :
953 3043 : void AccidentalsLayout::verticallyAlignAccidentals(AccidentalsLayoutContext& ctx)
954 : {
955 3043 : std::set<Accidental*> accidentalsAlreadyGrouped;
956 3043 : std::map<Accidental*, std::vector<Accidental*> > verticalSets;
957 :
958 3043 : if (ctx.alignOffsetOctaves()) {
959 0 : collectVerticalSetsOfOffsetOctaves(accidentalsAlreadyGrouped, verticalSets, ctx);
960 : }
961 :
962 3043 : collectVerticalSets(accidentalsAlreadyGrouped, verticalSets, ctx);
963 :
964 3043 : if (verticalSets.empty()) {
965 2757 : return;
966 : }
967 :
968 : // Turn map into vector
969 286 : AccidentalGroups vertSets;
970 286 : vertSets.reserve(verticalSets.size());
971 604 : for (auto& pair : verticalSets) {
972 318 : vertSets.push_back(pair.second);
973 : }
974 :
975 : // Sort vertical sets by column
976 286 : std::sort(vertSets.begin(), vertSets.end(), [&](auto& set1, auto& set2) {
977 43 : return set1.front()->ldata()->column < set2.front()->ldata()->column;
978 : });
979 :
980 286 : alignVerticalSets(vertSets, ctx);
981 5800 : }
982 :
983 0 : void AccidentalsLayout::collectVerticalSetsOfOffsetOctaves
984 : (std::set<Accidental*>& accidentalsAlreadyGrouped, std::map<Accidental*, std::vector<Accidental*> >& verticalSets,
985 : AccidentalsLayoutContext& ctx)
986 : {
987 0 : for (std::vector<Accidental*>& accidentalGroup : ctx.accidentalSubChords) {
988 0 : for (size_t i = 0; i < accidentalGroup.size(); ++i) {
989 0 : Accidental* acc1 = accidentalGroup[i];
990 0 : acc1->ldata()->column.value();
991 0 : if (muse::contains(accidentalsAlreadyGrouped, acc1)) {
992 0 : continue;
993 : }
994 0 : double x1 = xPosRelativeToSegment(acc1);
995 0 : for (size_t j = i + 1; j < accidentalGroup.size(); ++j) {
996 0 : Accidental* acc2 = accidentalGroup[j];
997 0 : if (!isOctave(acc1, acc2) || muse::contains(accidentalsAlreadyGrouped, acc2)) {
998 0 : continue;
999 : }
1000 0 : double x2 = xPosRelativeToSegment(acc2);
1001 0 : bool alignOctave = abs(x1 - x2) < 2.0 * ctx.spatium();
1002 0 : acc2->ldata()->column.value();
1003 0 : if (alignOctave) {
1004 0 : std::vector<Accidental*>& verticalSet = verticalSets[acc1];
1005 0 : if (verticalSet.empty()) {
1006 0 : verticalSet.push_back(acc1);
1007 : }
1008 0 : verticalSet.push_back(acc2);
1009 0 : accidentalsAlreadyGrouped.insert(acc1);
1010 0 : accidentalsAlreadyGrouped.insert(acc2);
1011 0 : int maxColumn = 0;
1012 0 : for (Accidental* acc : verticalSet) {
1013 0 : maxColumn = std::max(maxColumn, acc->ldata()->column.value());
1014 : }
1015 0 : for (Accidental* acc : verticalSet) {
1016 0 : acc->mutldata()->column = maxColumn;
1017 : }
1018 : }
1019 : }
1020 : }
1021 : }
1022 0 : }
1023 :
1024 3043 : void AccidentalsLayout::collectVerticalSets(
1025 : std::set<Accidental*>& accidentalsAlreadyGrouped, std::map<Accidental*, std::vector<Accidental*> >& verticalSets,
1026 : AccidentalsLayoutContext& ctx)
1027 : {
1028 7049 : for (size_t i = 0; i < ctx.allAccidentals.size(); ++i) {
1029 4006 : Accidental* acc1 = ctx.allAccidentals[i];
1030 4006 : if (muse::contains(accidentalsAlreadyGrouped, acc1)) {
1031 348 : continue;
1032 : }
1033 3658 : int column1 = acc1->ldata()->column;
1034 3658 : int verticalSub1 = acc1->ldata()->verticalSubgroup;
1035 3658 : double x1 = xPosRelativeToSegment(acc1);
1036 5359 : for (size_t j = i + 1; j < ctx.allAccidentals.size(); ++j) {
1037 1701 : Accidental* acc2 = ctx.allAccidentals[j];
1038 2982 : if (acc2->accidentalType() != acc1->accidentalType() || muse::contains(accidentalsAlreadyGrouped, acc2)
1039 2982 : || !muse::RealIsEqual(acc1->mag(), acc2->mag())) {
1040 692 : continue;
1041 : }
1042 1009 : int column2 = acc2->ldata()->column;
1043 1009 : int verticalSub2 = acc2->ldata()->verticalSubgroup;
1044 1009 : double x2 = xPosRelativeToSegment(acc2);
1045 1009 : bool alignAccidentals = column1 == column2 && verticalSub1 == verticalSub2 && abs(x1 - x2) < ctx.xVerticalAlignmentThreshold();
1046 1009 : if (alignAccidentals) {
1047 348 : std::vector<Accidental*>& verticalSet = verticalSets[acc1];
1048 348 : if (verticalSet.empty()) {
1049 318 : verticalSet.push_back(acc1);
1050 : }
1051 348 : verticalSet.push_back(acc2);
1052 348 : accidentalsAlreadyGrouped.insert(acc1);
1053 348 : accidentalsAlreadyGrouped.insert(acc2);
1054 : }
1055 : }
1056 : }
1057 3043 : }
1058 :
1059 286 : void AccidentalsLayout::alignVerticalSets(AccidentalGroups& vertSets, AccidentalsLayoutContext& ctx)
1060 : {
1061 286 : AccidentalGroups accidentalColumns;
1062 653 : for (std::vector<Accidental*>& group : ctx.accidentalSubChords) {
1063 1340 : for (Accidental* acc : group) {
1064 973 : size_t column = acc->ldata()->column;
1065 1546 : while (accidentalColumns.size() <= column) {
1066 573 : accidentalColumns.push_back(std::vector<Accidental*>());
1067 : }
1068 973 : accidentalColumns[column].push_back(acc);
1069 : }
1070 : }
1071 :
1072 604 : for (std::vector<Accidental*>& vertSet : vertSets) {
1073 : // Align the set
1074 318 : double x = DBL_MAX;
1075 984 : for (Accidental* acc : vertSet) {
1076 666 : double rightEdge = acc->ldata()->bbox().right() + xPosRelativeToSegment(acc);
1077 666 : x = std::min(x, rightEdge);
1078 : }
1079 984 : for (Accidental* acc : vertSet) {
1080 666 : double bboxRight = acc->ldata()->bbox().right();
1081 666 : setXposRelativeToSegment(acc, x - bboxRight);
1082 : }
1083 :
1084 : // Re-check the outer ones for collisions
1085 318 : size_t curColumn = vertSet.front()->ldata()->column.value();
1086 318 : Shape accidentalGroupShape;
1087 975 : for (size_t column = 0; column < accidentalColumns.size(); ++column) {
1088 657 : if (column < curColumn) {
1089 41 : continue;
1090 : }
1091 1667 : for (Accidental* acc : accidentalColumns[column]) {
1092 1051 : double curXPos = xPosRelativeToSegment(acc);
1093 1051 : Shape accShape = acc->shape().translate(PointF(curXPos, acc->note()->y()));
1094 1051 : if (!muse::contains(vertSet, acc)) {
1095 385 : double minDistToAccidGroup = minAccidentalToAccidentalGroupDistance(acc, accShape, accidentalGroupShape, ctx);
1096 385 : accShape.translateX(-minDistToAccidGroup);
1097 385 : setXposRelativeToSegment(acc, curXPos - minDistToAccidGroup);
1098 : }
1099 1051 : accidentalGroupShape.add(accShape);
1100 1051 : }
1101 : }
1102 318 : }
1103 286 : }
1104 :
1105 5057 : void AccidentalsLayout::setXposRelativeToSegment(Accidental* accidental, double x)
1106 : {
1107 5057 : Note* note = accidental->note();
1108 5057 : Chord* chord = note ? note->chord() : nullptr;
1109 5057 : if (note) {
1110 5057 : x -= note->pos().x();
1111 : }
1112 5057 : if (chord && !keepAccidentalsCloseToChord(chord)) {
1113 4990 : x -= chord->pos().x();
1114 : }
1115 5057 : accidental->mutldata()->setPosX(x);
1116 5057 : }
1117 :
1118 10489 : double AccidentalsLayout::xPosRelativeToSegment(const Accidental* accidental)
1119 : {
1120 10489 : Note* note = accidental->note();
1121 10489 : Chord* chord = note ? note->chord() : nullptr;
1122 10489 : double x = accidental->ldata()->pos().x();
1123 10489 : if (note) {
1124 10489 : x += note->pos().x();
1125 : }
1126 10489 : if (chord && !keepAccidentalsCloseToChord(chord)) {
1127 10356 : x += chord->pos().x();
1128 : }
1129 10489 : return x;
1130 : }
1131 :
1132 6189 : void AccidentalsLayout::sortTopDown(std::vector<Accidental*>& accidentals)
1133 : {
1134 6189 : std::sort(accidentals.begin(), accidentals.end(), [](const Accidental* acc1, const Accidental* acc2){
1135 2501 : int line1 = acc1->line();
1136 2501 : int line2 = acc2->line();
1137 2501 : if (line1 == line2) {
1138 27 : Note* note1 = acc1->note();
1139 27 : Note* note2 = acc2->note();
1140 27 : return note1->x() + note1->chord()->x() > note2->x() + note2->chord()->x();
1141 : }
1142 2474 : return line1 < line2;
1143 : });
1144 6189 : }
1145 :
1146 18740 : bool AccidentalsLayout::keepAccidentalsCloseToChord(const Chord* chord)
1147 : {
1148 18740 : return chord->isTrillCueNote() || chord->isGraceAfter();
1149 : }
1150 :
1151 18632 : double AccidentalsLayout::verticalPadding(const Accidental* acc1, const Accidental* acc2, const AccidentalsLayoutContext& ctx)
1152 : {
1153 32954 : double verticalClearance = acc1->accidentalType() == AccidentalType::SHARP && acc2->accidentalType() == AccidentalType::SHARP
1154 32954 : ? ctx.verticalSharpToSharpClearance() : ctx.verticalAccidentalToAccidentalClearance();
1155 18632 : return verticalClearance *= 0.5 * (acc1->mag() + acc2->mag());
1156 : }
1157 :
1158 17641 : double AccidentalsLayout::horizontalPadding(const Accidental* acc1, const Accidental* acc2, const AccidentalsLayoutContext& ctx)
1159 : {
1160 17641 : return ctx.accidentalAccidentalDistance() * (0.5 * (acc1->mag() + acc2->mag()));
1161 : }
|
