Poor accidental layout on large / complex chords

• Mar 18, 2014 - 15:33
S4 - Minor

Windows 7, 6d1da20ec129c

The new algorithm handles most cases very well and puts us much more in line with other programs. The one place where we still fall short is large chords (over an octave) with many accidentals:


The zig-zag algorithm does a very poor job with these, creating a distacting wedge shape with a large gap in the middle. It also fails to align accidentals an octave apart. I was originally willing to accept this as I didn't see an easy way around it and didn't really understand what the expected result should be.

But I now see exactly how the algorithm could work, and it's not hard at all to do what LilyPond does here:


This particular case is maybe not the worst offender, but it does illustrate the difference clearly. LilyPond is identifying sets of accidentals an octave apart and aligning them first in columns (working right to left). Had there been any accidentals *not* duplicated in another octave, LilyPond would zig-zag them to the left of the octave columns. Other programs don't bother trying to align octaves and can get marginally tighter spacing in some cases by using a more ad-hoc approach, but the algorithm is not as straightforward, and you don't get the nicely aligned octaves.

So my plan is to use the LilyPond model for chords larger than an octave. Optimal or not, it's a definite improvement over the plain zig zag for large chords, it aligns octaves, and it should not be difficult to implement.

At that point, I will stop messing with this, as I think we need predictable defaults moving forward.


Marc, I didn't want to keep appending things to the other now-completed issue and PR, but I've managed to create a somewhat simple case where note and accidental alignment between voices is still off. Since you are still going to adjust the algo for accidental stacking, this seemed a proper place to post.


Note how the third chord overlaps the voice noteheads (A and G), and the natural is too far away from the A. It would appear that the algo assumes there is an accidental still displaying on the A in voice 1 from the previous chord, and moves the natural.

Attachment Size
01.png 7.05 KB

Ick. I suspect this will turn out to be one or two unrelated issues, and it doesn't really relate to stacking per se as I'm talking about in this issue (which has to do with multiple accidentals). Would you mind posting this as a separate issue, and including the MSCZ file? Looks like the voice assignment is rather odd here - judging by the colors, I'm thinking you're forcing voice 1 stems down and voice 2 stems up? My code doesn't deliberately make assumption about which voices have which stem directions so I'm not saying that's why it doesn't work, but I want to be sure I'm reproducing your case correctly.

FWIW, I'm assuming the trigger will turn out to be the fact that there is a second and a unison conflict on the same note.

Now that I've played with this some more, and inverted the voices, I'm not sure this is really a valid issue so disregard this.

FWIW, the fix that was just merged is actually better than what is shown above. Check out the further improved version of the bottom two chords (top two should be the same):


In case it isn't apparent, the leftmost accidentals that were otherwise kind of hanging off in space have been tucked in.

Attachment Size
accidental-6-ref-new.png 12.05 KB

Marc, I'm thinking out loud here, and I've been wondering about the limitations of the algorithm you've worked on. I realize you are using worse-than worst case examples, but...


In the first bass clef example, there seems to be lots of room inside the flats for other flats. I don't know the limitations of how collision detection works, so instead of using octaves like it is now, is there a way to detect how much distance up or down (fourth, fifth, etc) you can safely go before placing the next accidental?

Attachment Size
03.png 22.2 KB

I'm thinking maybe our posts crossed - I actually fixed exactly those cases after submitting the PR but before it was merged:-).

I have found this whole experience fascinating, and I certainly welcome discussion.

Octaves are special, according to both Gould and Spreadbury, and should always be aligned where possible (and it pretty much always is). So we want notes an octave apart to be in the same column. The only question is whether or not we fit anything else along with them.

What I do now is first set up columns for the octaves to the right, with the columns themselves zig zagging (highest top note, then lowest bottom note, etc). If there are notes that have no octave match, I try to squeeze them into the existing columns (working right to left), and only ones I cannot squeeze in hang off to the left, using the same basic zig zag algorithm used for chords under an octave.

What has become clear from my investigation is that no single algorithm is going to yield optimal results always. If you haven't already, see http://blog.steinberg.net/accidental-stacking-comparison/ to get an idea of just how much variety these is between programs here. No program wins on all of chords used in the comparison, but pretty much all of the first five as a group are better than either of the last two as a group. MuseScore 1.3 is E, probably dead worst of the bunch.

Here's how we do now:


I'd say we're squarely in the group with the first five at this point, and that's good enough for me. Any "holes" you see here where it appears we could have fit another accidental in, there is just barely *not* enough room given the default style setting of forcing 0.22sp space between accidentals. If I reduce that to zero, I can plug the hole in the very last (bottom right) chord, but it's not an improvement overall.

Now, there *are* still opportunities for further improvement of course. There always are. For example, there are cases where the octave columns themselves can be combined - two accidentals an octave apart in one column, neither of which conflict with either of the accidentals an octave apart in another column. But detecting these opportunities would require quite a bit of looping and a whole bunch more floating point comparisons. And this actually won't happen in real life unless the accidentals in question are either double sharps or else if each column actually consists of accidentals that are actually *two* octaves apart. And the latter case isn't playable by a human being on any instrument I can think of :-). So it just isn't worth it, IMHO.

Attachment Size
Steinberg-Accidental-Comparison-2.0.png 49.99 KB

Yes, the posts crossed. I still wonder if there is room for improvement, but is the horiz and vert space required between accidentals the limiting factor? For example:


I've circled the flats that would seem to be able to fit next to the stacked chord in the first accidental column. Is this a space limitation?

In fact, in almost each example there seems to be extra space along the initial vertical accidental row where others could be put in, thus packing the accidentals even tighter.

Attachment Size
04.png 5.98 KB

What you are showing here is a good example of the specific remaining opportunity for improvement I mentioned being possible but expensive to check for, and it would only pay off in cases too rate to worry about. That is, your circled accidentals are all in the octave columns themselves - they aren't the unmatched accidentals that I do insert into earlier columns where possible.

Yes, merging of the octave columns themselves would save space in this particular example, although I note we couldn't do it for *both* pairs of notes in your example - it would be one or the other. So we'd only save one column worth of space. And as I wrote, this only likely to work if the notes in each column are actually *two* octaves apart rather than one, which is indeed the case here. Furthermore, the notes between the columns have to basically be a seventh apart for it to be likely to work. And when you see there being opportunities to do this in many of the examples - that's actually not true if you want to keep the columns intact. That is, you might be able to merge one note of an octave pair into a different column, but you can't move them both in any of the Steinberg examples.

That said, I could see it happening in cases where both hands in a piano part are playing identical chords two octaves apart and for whatever reason, both hands are notated in one staff in separate voices. I don't know, I'll think about it. Maybe there would be a way to detect that type of situation without having to do an exhaustive set of comparisons of all notes in all columns. But I'm still betting not one chord in a thousand would end up benefiting from this.

I agree, given the extreme examples being bandied about. In my normal writing, I might see 3 accidentals in one staff, which will all nicely align now.

Exciting times in MuseScore 2.0 right now. Some of the changes recently committed (yours especially), or up'n-coming are very exciting. After months of being in waiting mode for 2.0 to be stable, I'm back in full swing, with a lengthy list of bugs'n things to submit.