`saveGif()` (specifically: `_generateGlobalPalette()`) fails for large amount of frames

[jchwenger]

Most appropriate sub-area of p5.js?

• [ ] Accessibility
• [ ] Color
• [ ] Core/Environment/Rendering
• [ ] Data
• [ ] DOM
• [ ] Events
• [X] Image
• [ ] IO
• [ ] Math
• [ ] Typography
• [ ] Utilities
• [ ] WebGL
• [ ] Build process
• [ ] Unit testing
• [ ] Internationalization
• [ ] Friendly errors
• [ ] Other (specify if possible)

p5.js version

/! p5.js v1.9.4 May 21, 2024 /

Web browser and version

Firefox 128.0.2 (64 bits) / 126.0.6478.183 (Official Build) (arm64)

Operating system

MacOS Sonoma 14.4

Steps to reproduce this

Hello lovely p5.js people!

I think I came across a little bug when trying to create a (big) gif.

Steps:

1. Run the following sketch
2. Check error in the console after all the frames have been recording

Snippet:

function setup() {
  createCanvas(800,800);
  background(127);
}

function draw() {
  fill(random(255), random(255), random(255));
  circle(random(width), random(height), random(10));
}

function keyPressed() {
  if (key === 'g') {
    console.log('saving gif');
    const frames = 5000;
    saveGif(
      `humongous.gif`,
        frames, {
          units: "frames",
          delay: 0,
      }
    );
  }
}

In Firefox, the frames get collected, but it is the creation of the color palette that fails (when creating the Uint8Array here).

I'm thinking a potential solution would be to merge the pixels in chunks, instead of all at once?

It's a bit outrageous to want this feature, but it would be super lovely to make it robust even to mammoth gifs 🩶🦣. I created a fairly long animation, and was hoping to export it as a gif, but that would mean 12k frames 🙈...

Is it something you would be interested in looking into? I'm not quite set up to make a PR, but I could try looking into this.

Thanks in advance, any idea or thought would be welcome!

Note: In Chrome, I get RangeError: Failed to execute 'getImageData' on 'CanvasRenderingContext2D': Out of memory at ImageData creation even before all the frames are done being collected. I haven't investigated this.

[welcome[bot]]

Welcome! 👋 Thanks for opening your first issue here! And to ensure the community is able to respond to your issue, please make sure to fill out the inputs in the issue forms. Thank you!

[davepagurek]

A possible approach to this could be to only randomly add pixel colors from frames if the array is going to be too large (maybe picking some reasonable threshold for what "too large" means) so that we can constrain the length used to generate the palette to whatever we need. That would probably deal with the first reported issue here. The second, where Chrome runs out of memory trying to grab all the frames, is a harder one to deal with -- we could maybe store frames in a compressed format (even lossless compression like png) to save space, and only convert to raw ImageData as we need to add that frame to the gif.

Both are feasible in theory if anyone wants to try taking it on!

[jchwenger]

Wouldn't something like this (untested) solve both issues? (Disclosure: this is reworked from a Ch*tGPT suggestion.)

function _mergePalettes(targetPalette, addedPalette) {
  // TODO: implement
}

// chunkSize: is there a way to compute browser maximum?
function _generateGlobalPalette(frames, chunkSize=1000) {
  let colorPalette;

  // loop over the frames chunk by chunk
  for (let i = 0; i < frames.length; i += chunkSize) {

    let end = Math.min(i + chunkSize, frames.length);

    // make an array the size of every possible color in chunkSize frames
    // that is: width * height * chunkSize.
    let tmpColors = new Uint8Array((end - i) * frames[0].length);

    // put every frame one after the other in sequence.
    // this array will hold absolutely every pixel from the current chunk.
    // the set function on the Uint8Array works super fast tho!
    for (let f = i; f < end; f++) {
      tmpColors = tmpColors.concat(frames[f]);
    }

    // quantize this chunk into 256 colors and merge it!
    let tempPalette = (0, _gifenc.quantize)(new Uint8Array(tmpColors), 256, {
      format: 'rgba4444',
      oneBitAlpha: true
    });

    // How to do this is the question
    _mergePalettes(colorPalette, tempPalette);
  }

  return colorPalette;
}

The structure of the quantized color array is still unclear to me, but if it's just sorted ints, it should be a case for a smart insertion algorithm, maybe?

[davepagurek]

Generating the palette in chunks and merging them is another way to get a smaller palette, yep! I suppose the challenge will be, converting all the frames into colors with the final global index. If you wait until you have the final palette to do it, you'd still have to store all the frame data until the end, so you might end up with the Chrome memory issue still. If you convert chunks to their "local" palette, and then after merging the palettes, update both the chunk's frames and the previously converted frames to reference new palette indices based on how the global palette changed. The earliest frames will end up subject to the most color swaps, and might have the most color distortion from their original color, because we're throwing out information each time.

That approach is also potentially feasible, it just comes with its own challenges too.

[jchwenger]

Hmm, ok, thanks for this. I'm afraid I'm not following 100%, as the underlying process for the construction of the palette isn't clear to me yet! I guess I would have to get familiar with gifenc to get a better grasp of how the palette works in the first place...