Pixel dispersion (dissolving) algorithms

This YouTube video of a flip-dot display (physical b/w pixels) shows the reverse of an effect that might be called dissolve or dispersion, i.e. a text emerges from noise by pixels moving in to form letters. Here's a short cropped clip showing just the "crystallization" (wouldn't that be an appropriate name?):

(source: BREAKFAST NY)

Looking for more info on this or similar effects I found After Effects: Text That Blows Away Like Sand which has a Shatter effect, apparently a 3D particle system with physics simulation.

For a particle system, I can imagine that "dissolving" every pixel (of a character) randomly wouldn't be too hard. Reversing the effect as shown in the video could be done using a precalculated sequence or even just animated sprites for each letter. Or, each pixel in the noise gets chosen to gravitate towards a letter (seems more complicated, may require clustering).

Then I found an implementation and live demo:

• Particles text effects

Uses particles with a seek behavior to make up a word. The word is loaded into memory so that each particle can figure out their own position they need to seek. Inspired by Daniel Shiffman's arrival explantion from The Nature of Code. (natureofcode.com)

https://www.openprocessing.org/sketch/377231

The reference resolves to

I think the effect is very similar, so I think they used a particle system.

Q: Is there an approach that does not require particles (i.e. less memory-expensive)?

Just for comparison, here's an attempt at creating a "normal" animated noise dissolve (random dither), as suggested in a comment, but I think it's obvious that the pixels in the original do move and it's not just a binary blending effect:

It requires at least one random value for each pixel: on which frame of the animation to become active.

This is what trichoplax's solution looks like (pseudorandomly swapping 10,000 neighboring pixels in each of 100 frames, and then reversing it using the same pseudorandom number sequence, just reversed):

• Are you looking for a memory-efficient way of producing this exact effect (particles moving into their required positions), or are you looking for similar effects that don't look quite the same but are easier/more memory-efficient to implement? For example. fading in the final text whilst simultaneously fading out animated white noise would have a similar feel, but wouldn't really look like moving particles, so we need to know precisely what you require in order to be able to answer. May 14, 2017 at 15:24
• The random dots dissolving into text doesn't look to me like the dots move at all. It looks like random noise which is then blended with the letters using the "noise dissolve" blend mode or transition. May 14, 2017 at 15:45
• @trichoplax Same effect with "moving" binary pixels May 14, 2017 at 15:53
• @user118321 I think I understand what you mean: Wouldn't that require non-random noise blend masks (to blend all pixels within a few transition frames)? That would require full frame animated masks (and the respective memory). May 14, 2017 at 15:53
• @trichoplax If I understand correctly, that sounds good indeed - but it'll take some time for me to try. Thanks for now, I'll report back! May 15, 2017 at 19:01

A very simple low memory approach

If you really want to use as little memory as possible, it can be done with not much more memory than that required to store a single image (the first frame) provided it is acceptable to do some preprocessing in advance.

If you copy the following jumbled image, this jsfiddle will take it as input:

It will then move the pixels around one step at a time so they drift into place to give the original image again:

This does not require any memory for tracking particles. The algorithm is very simple:

• Pick a pixel at random
• Swap it with one of its 4 neighbours
• Repeat a million times

No additional memory is required as no particles are being used. We're simply swapping pixels at random, with no destination locations in mind. The key is in choosing that apparently jumbled initial image to have the pixels in exactly the right places such that applying a million random swaps will happen to leave all the pixels in exactly the right places to give the desired text.

Setting up the initial jumbled image

To do that, this preparatory jsfiddle takes an image as input and outputs a jumbled image that is precisely arranged to work as input for the main jsfiddle.

This one takes more memory, but is still a very simple algorithm:

• Generate a large number of random numbers and store them
• Using these numbers in reverse order* (using the last first):
• Pick a pixel at random
• Swap it with one of its 4 neighbours
• Repeat a million times

This is exactly the opposite of what the main jsfiddle will do, so the jumbling will be completely reversed, restoring the original image. You can paste in a colour image, or if you want just text with only black and white pixels that will work too. The example image shown above is between these two extremes, as it has greyscale pixels for the antialiasing, which wander around alongside the black and white pixels.

A million pixel swaps works for fairly small images. For larger sizes this won't jumble them enough to completely obscure the original image, so you would need to adjust the number of swaps.

Languages without reseeding

Note that this only works because the pseudorandom number generator is reseeded at the start of both algorithms, to ensure that they are both working with exactly the same list of "random" numbers. Most languages will allow you to reseed the random number generator, making this an easy approach. JavaScript does not, so the jsfiddles include an implementation of xorshift to allow reseeding.

Even with a language that does allow reseeding, if the hardware is particularly limited then you may want to consider xorshift as it is very fast and uses only 4 bytes of memory for its state. It's also only a few lines of code.

*Note that the order isn't quite the same as just reversed. In this example code, three random numbers are used for each pair of pixels to be swapped. So the order of each triple must be kept the same to avoid choosing different pairs of pixels. For example:

[1, 2, 3], [4, 5, 6], [7, 8, 9]

must be reversed to

[7, 8, 9], [4, 5, 6], [1, 2, 3]

in order that the same x value, y value and direction be chosen for each pixel pair when running in reverse.

• If this site gets stack snippets at some point, I'll replace the jsfiddles with stack snippets so it can all be viewed from the answer post. May 18, 2017 at 0:30
• Thanks for this nice demo of your initial idea. I'll post a capture of the animation tomorrow for you to integrate into your post. I think this might be called a (pseudo) random-random walk? This might be extended with more directionality at the cost of additional state memory for each pixel (3 bits). But the effect is close enough to the original's presumed particle effect. I'll try to find out if there are any RNGs/LSFR whose state can be set without iteration (for the reverse operation) and then implement this on a microcontroller. Thanks again. May 18, 2017 at 5:36
– Jack
May 18, 2017 at 22:34
• @Jackalope thank you! My approach is less sophisticated and I can't imagine why the memory would need to be so restricted, but assuming that it is, this was the simplest I could think of. May 22, 2017 at 12:11

You could do this entirely within an OpenGL/WebGL fragment shader:

Attach the image you wish to emerge as a texture/sampler2D. Attach uniforms for the current time, as well as the time you want the effect to finish.

uniform sampler2D myTexture;
uniform float currentTime;
uniform float finishTime;

#define TWO_PI 6.283185307179586476925286766559


Next, apply a deterministic pseudo-random noise algorithm for displacing pixels a given distance and compass direction. Something like:

float rand(vec2 co){
return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}
float R = rand(thisPixel.xy);

var float timeLeft = clamp((finishTime - currentTime) * R, 0.0, 10000.0);

float direction = classic1dPerlinNoise( R + currentTime ) * TWO_PI;
float offsetX = thisPixel.x + sin(direction) * timeLeft / 500.0;
float offsetY = thisPixel.Y + cos(direction) * timeLeft / 500.0;
vec2 texCoord = vec2( offsetX, offsetY );


Note, the above clamp stops the effect at the appropriate time, as well as sets a maximum (10 sec, in this example) duration of the effect.

Finally, look up your texture sample:

gl_FragColor = gl_Color * texture2D(myTexture, texCoord);


Voila! While the pixels may not navigate around each other, they'll at least wander into place, each arriving at it's own distinct time within the timeframe allotted to the effect, and using very little memory and CPU time.

• My first attempt to run this on shadertoy.com is missing a few pieces. If you know the site, could you please have a look? May 16, 2017 at 6:47
• Yes, this wasn't intended to be a complete program. I was just trying to explain my method. In looking at it again, I think I'll need to revise it. I don't have time right now, but I'll try to get an example up & running soon.
– Jack
May 16, 2017 at 19:23
• Yes, of course. I'm just not able to fill in the gaps on my own without spending too much time with WebGL/Shadertoy, but I thought I'd give it a bit of a try. However, while I'm curious to see how this works and to get a glimpse at the result, it's not ultimately the approach I am looking for, since it requires complex graphics hardware and is way beyond a "simple" algorithm. May 16, 2017 at 19:42
• Actually, almost everybody has the hardware needed to view WebGL. caniuse.com/#feat=webgl
– Jack
May 17, 2017 at 3:50