Apache OpenOffice (AOO) Bugzilla – Issue 80637
Random shuffling for dissolve transition is poor
Last modified: 2017-05-20 10:30:41 UTC
The code in http://graphics.openoffice.org/source/browse/graphics/slideshow/source/engine/transitions/randomwipe.cxx to shuffle the squares for a 'dissolve' wipe is poor. When watching the desolve, it is easy to see a raster-scan which some randomness is over-layed on. A better approach would be: for (i=0; i< nElements; i++) { j = getRandomOrdinal(nElements-i) // swap m_positions[i], m_positions[j] } that would ensure every element had and equal chance of being swapped.
Set to ne and change the target. In my mind this is an enhancement and not a bug.
In my mind it's an enhancement but nevertheless I send it to you. Please have a look.
reassigned to active slideshow developer, changing issue type to patch
The current code looks like this: for ( sal_Int32 i = (nElements / 2); i--; ) { const sal_Int32 pos1 = getRandomOrdinal(nElements); const sal_Int32 pos2 = getRandomOrdinal(nElements); const ::basegfx::B2DPoint point( m_positions[ pos1 ] ); m_positions[ pos1 ] = m_positions[ pos2 ]; m_positions[ pos2 ] = point; } I can see no mathematical problem with it, nor can I see noteworthy visual artifacts when the effect is executed. With the "patch" in the first post many elements will be moved twice to a new location. This can still happen with the original code, but not in so many cases. For all these reasons I will not change the code. If someone can point out any actual flaw in it then I will, of course, reconsider.
Mathematical problem: The current algorithm generates 'nElements' random numbers ranging from 0 to nElements-1. This means that the number of distinct values generated will be significantly less than nElements, as there will be repeats. To demonstrate, the following 1 line bash script: for i in `seq 1 256` ; do echo $[RANDOM/128] ; done | sort -u | wc -l generates 256 (16*16) random numbers from 0 to 255 and counts unique values. It produces counts from 149 to 178 in 1024 runs. Thus when used in the 'dissolve' transition, between 78 and 107 (30% - 40%) of squares will not be shuffled. and so will appear to change in sequence. This is not a random shuffling. The alternate code is slightly wrong. the 'swap' should be for positions 'i' and 'i+j'. The reasoning which shows that this is a correctly random shuffle is simply that the first swap places a completely random element in the first position. The second swap places a random choice from the remaining elements in the second position. The third swap places a random choice from the remaining elements in the third position. etc. Yes, it does move some elements multiple times, but so does the current code. Visually: At 16x16, you can see the effect, but it is not very pronounced. It depends on how lucky you are with your random numbers. If you increase it to 64x64 (to match the competition) you will see that it is more noticeable. Up to you if you fix it of course. Thanks for taking the time to look at it.
Thanks for the explanation. I clearly did not think long enough about this. You are right that with a 64x64 grid the effect does not look randomly distributed anymore. Reopened.
Fixed as outlined above.
verified that patch looks good and is applied to cws impress195