Pixel dispersion (dissolving) algorithms

Question

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

  • http://natureofcode.com/book/chapter-4-particle-systems
  • http://natureofcode.com/book/chapter-6-autonomous-agents/ (6.4 Arriving Behavior)

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):

Answer 1

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.

Answer 2

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.