Issue 80637 - Random shuffling for dissolve transition is poor
Summary: Random shuffling for dissolve transition is poor
Alias: None
Product: Impress
Classification: Application
Component: code (show other issues)
Version: OOo 2.2.1
Hardware: All All
: P4 Trivial (vote)
Target Milestone: 3.4.0
Assignee: groucho266
QA Contact: issues@graphics
Depends on:
Reported: 2007-08-13 09:27 UTC by neilfbrown
Modified: 2017-05-20 10:30 UTC (History)
1 user (show)

See Also:
Issue Type: PATCH
Latest Confirmation in: ---
Developer Difficulty: ---


Note You need to log in before you can comment on or make changes to this issue.
Description neilfbrown 2007-08-13 09:27:51 UTC
The code in

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.
Comment 1 christian.guenther 2007-09-05 15:47:38 UTC
Set to ne and change the target.
In my mind this is an enhancement and not a bug.
Comment 2 christian.guenther 2007-09-05 15:57:57 UTC
In my mind it's an enhancement but nevertheless I send it to you.
Please have a look.
Comment 3 clippka 2010-09-29 09:11:55 UTC
reassigned to active slideshow developer, changing issue type to patch
Comment 4 groucho266 2010-10-14 10:41:14 UTC
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.
Comment 5 neilfbrown 2010-10-14 11:35:34 UTC
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.
Comment 6 groucho266 2010-10-14 12:37:25 UTC
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

Comment 7 groucho266 2010-10-14 13:08:29 UTC
Fixed as outlined above.
Comment 8 clippka 2011-02-09 11:33:40 UTC
verified that patch looks good and is applied to cws impress195