Let it snow!

Written by Bob Lee.

If you sent or received Square Cash recently, you might have noticed slight precipitation backdropping our email headers. It all started last week when we decided to do something special for the holidays. I reckon my teammates thought I was joking when I shouted out with glee, “falling snowflakes!” But then I followed up with a working prototype. What says “Happy Holidays!” better than parallax-scrolling, alpha-composited, bokeh snowflakes, amirite?

While the effect is simple, generating it was anything but. Hacking together a proof-of-concept took moments. Profiling and optimizing the rendering speed and file size required orders of magnitude more effort. We didn’t draw this animation in Photoshop. I wrote a couple hundred lines of Java code instead. The challenges were many, but we Square engineers pride ourselves on our ability to push the envelope at every layer of the stack, up to and including email animations.

Most email clients don’t support HTML5. We’re stuck with 90s era technologies, or in this case, animated GIFs. Obviously the animations should look crisp and beautiful, especially on today’s high resolution displays. We render them at 2X resolution — more than 300k pixels per frame. The animations include custom text. This requires us to render them on the fly and poses some fun challenges. Once rendered, the animation needs to download and play quickly, even over slow mobile networks.

To start, I pored over the 25-year-old GIF spec, reading it backwards and forwards, looking for opportunities to cut down the file size without compromising the design. I used pngquant’s best-of-breed Median Cut quantization algorithm to precompute an optimal 16-color palette. Restricting the animation to 16 colors enabled us to encode the images using 4 bits-per-pixel¹. It also resulted in slight posterization, promoting color repetition and further improving compression, particularly in the gradient at the bottom of the image. I even tried plotting only the pixels that changed between each frame, but to my surprise, the diffs resulted in more complexity, less repetition, and therefore worse compression than the full frames.

The biggest win came from an optical illusion aimed at reducing the total number of frames. The animation looks like it necessitates 240 frames, but it really only requires 60 (a 75% savings). The animation is composed of four layers of snowflakes, each meant to appear a different distance from the observer. As the layers get further away, the snowflakes get smaller, lighter, slower, and denser, resulting in the illusion of depth. Here are the separate layers ordered closest to furthest:

The trick is only the closest layer travels the full height of the frame. The lower layers travel only a fraction of the height, but they tile and repeat, giving the illusion of continuity. For example, during the course of the animation, the second layer travels only half way down the height of the image, but it repeats twice and looks like it scrolls continuously. The third layer travels one third of the way and repeats three times, and the fourth layer travels one fourth of the way and repeats four times. As you can see, this repetition becomes less evident when you layer the snowflakes on top of each other and animate them at different speeds.

The final animation clocks in at less than 650KB — 0.25 bits/pixel! To see it in action, send some Cash to a loved one. And check out the final code below. Consider it my gift to you! Happy holidays.

/*
 * Copyright 2013 Square Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.squareup.franklin.email.image;

import com.google.common.cache.CacheBuilder;
import com.google.common.cache.CacheLoader;
import com.google.common.cache.LoadingCache;
import com.google.common.io.ByteSource;
import com.google.common.io.ByteStreams;
import com.google.common.io.Files;
import com.squareup.common.locale.ISOCurrency;
import com.squareup.common.values.Money;
import java.awt.Color;
import java.awt.GradientPaint;
import java.awt.Graphics2D;
import java.awt.Paint;
import java.awt.RenderingHints;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import javax.imageio.IIOImage;
import javax.imageio.ImageIO;
import javax.imageio.ImageTypeSpecifier;
import javax.imageio.ImageWriteParam;
import javax.imageio.ImageWriter;
import javax.imageio.metadata.IIOInvalidTreeException;
import javax.imageio.metadata.IIOMetadata;
import javax.imageio.metadata.IIOMetadataNode;
import javax.imageio.stream.ImageOutputStream;
import javax.imageio.stream.MemoryCacheImageOutputStream;
import org.apache.commons.io.output.ByteArrayOutputStream;
import org.w3c.dom.Node;

/**
 * Generates animated header images for the holidays.
 *
 * @author Bob Lee
 */
public class HolidayHeader {

  /*
   * Docs for Java's GIF encoder:
   *
   * - Plugin notes: http://docs.oracle.com/javase/6/docs/api/javax/imageio/package-summary.html#gif_plugin_notes
   * - Metadata spec: http://docs.oracle.com/javase/6/docs/api/javax/imageio/metadata/doc-files/gif_metadata.html#gif_stream_metadata_format
   *
   * To inspect GIF file structure:
   *
   * - Daktari: http://interglacial.com/pub/daktari_gif.html
   */

  private static final int FRAMES_PER_SECOND = 24;

  /** Random seed used when positioning flakes. */
  private static final int SEED = 6;

  /** Number of flake layers. */
  private static final int LAYERS = 4;

  /** Number of flakes in the top layer. */
  private static final int FLAKES_IN_TOP_LAYER = 8;

  private static final int MAX_FLAKE_RADIUS = radiusFor(LAYERS - 1);
  private static final int HEIGHT_WITH_PADDING = HeaderImage.HEIGHT + MAX_FLAKE_RADIUS * 2;

  private static final HeaderImage.Color COLOR = HeaderImage.Color.RED;

  /** Constants used for gradient at the bottom of the header. */
  private static final Color TRANSPARENT_BACKGROUND_COLOR =
      new Color(COLOR.backgroundColor().getRGB() & 0x00ffffff, true);
  private static final int GRADIENT_HEIGHT = 200;
  private static final GradientPaint GRADIENT = new GradientPaint(
      0, HeaderImage.HEIGHT - GRADIENT_HEIGHT, TRANSPARENT_BACKGROUND_COLOR, 0,
      HeaderImage.HEIGHT, COLOR.backgroundColor());

  /** Change in y per frame for top layer of flakes. */
  private static final int DY = 10;

  /** The number of frames required for the highest layer of flakes to cycle once. */
  private static final int FRAME_COUNT = HEIGHT_WITH_PADDING / DY;

  /** Frames without the amount overlaid. */
  private static final List<BufferedImage> FRAMES = new ArrayList<>();

  static {
    for (int frameIndex = 0; frameIndex < FRAME_COUNT; frameIndex++) {
      Random random = new Random(SEED);

      // Start with a blank red frame.
      BufferedImage frame = newBuffer();
      Graphics2D g = frame.createGraphics();
      g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
      g.setColor(COLOR.backgroundColor());
      g.fillRect(0, 0, HeaderImage.WIDTH, HeaderImage.HEIGHT);

      // Draw snowflakes in 3D! We draw the snowflakes in layers, starting with the most distant
      // layer. Nearer layers are bigger, faster, brighter, and more sparse, just like real life!
      // To reduce the number of frames–and in turn the file size–lower layers don't scroll the
      // entire height of the image. We tile them vertically so they still scroll continuously.
      // For example, layer 3 moves only 1/3 of the way down during the animation, but we tile it
      // three times so the last frame looks just like the first frame.
      for (int layerIndex = 0; layerIndex < LAYERS; layerIndex++) {
        // We add some padding to the top and bottom and draw outside the bounds of the physical
        // image so snowflakes don't magically appear at the top and disappear when they touch the
        // bottom.
        g.setColor(new Color(255, 255, 255, (layerIndex + 2) * 25));
        int tiles = LAYERS - layerIndex;
        int tileHeight = HEIGHT_WITH_PADDING / tiles;
        int radius = radiusFor(layerIndex);
        int diameter = radius * 2;
        for (int flakeIndex = 0; flakeIndex < FLAKES_IN_TOP_LAYER; flakeIndex++) {
          int x = random.nextInt(HeaderImage.WIDTH);
          int y = random.nextInt(tileHeight);
          y = y + frameIndex * DY / tiles;
          for (int copy = 0; copy < tiles; copy++) {
            g.fillOval(x - radius, (y + copy * tileHeight) % HEIGHT_WITH_PADDING - MAX_FLAKE_RADIUS,
                diameter, diameter);
          }
        }
      }

      // Draw Square logo.
      g.drawImage(HeaderImage.LOGO, null, HeaderImage.LOGO_X, HeaderImage.LOGO_Y);

      // Fade to red at the bottom.
      Paint paint = g.getPaint();
      g.setPaint(GRADIENT);
      g.fillRect(0, HeaderImage.HEIGHT - GRADIENT_HEIGHT, HeaderImage.WIDTH, HeaderImage.HEIGHT);
      g.setPaint(paint);

      FRAMES.add(frame);
    }

    /*
     * Note: I tried storing the differences between frames instead of the entire frames, but
     * the resulting file was actually bigger. This is because the diff images are more complex
     * than the full images and are therefore less compressible.
     */
  }

  private static BufferedImage newBuffer() {
    // Use 4 bits per pixel (i.e. BINARY, not INDEXED).
    return new BufferedImage(HeaderImage.WIDTH, HeaderImage.HEIGHT, BufferedImage.TYPE_BYTE_BINARY,
        COLOR.model());
  }

  private static final IIOMetadata FIRST_FRAME_METADATA = newFrameMetadata(true);
  private static final IIOMetadata FRAME_METADATA = newFrameMetadata(false);

  private static ImageWriter newGifWriter() {
    return ImageIO.getImageWritersByFormatName("gif").next();
  }

  private enum DisposalMethod {
    none, doNotDispose, restoreToBackgroundColor, restoreToPrevious
  }

  private static IIOMetadata newFrameMetadata(boolean first) {
    ImageWriter writer = newGifWriter();
    ImageWriteParam iwp = writer.getDefaultWriteParam();
    IIOMetadata metadata = writer.getDefaultImageMetadata(
        new ImageTypeSpecifier(newBuffer()), iwp);
    String metaFormat = metadata.getNativeMetadataFormatName();
    Node root = metadata.getAsTree(metaFormat);
    IIOMetadataNode gce = (IIOMetadataNode) findChild(root, "GraphicControlExtension");
    gce.setAttribute("userDelay", "FALSE");
    gce.setAttribute("delayTime", String.valueOf(100 / FRAMES_PER_SECOND)); // hundredths of a sec.
    gce.setAttribute("disposalMethod", DisposalMethod.doNotDispose.name());
    if (first) {
      // Use the Netscape application extension to enable looping.
      IIOMetadataNode aes = new IIOMetadataNode("ApplicationExtensions");
      IIOMetadataNode ae = new IIOMetadataNode("ApplicationExtension");
      ae.setAttribute("applicationID", "NETSCAPE");
      ae.setAttribute("authenticationCode", "2.0");
      // Loop infinitely.
      ae.setUserObject(new byte[] { 0x1, 0, 0 });
      aes.appendChild(ae);
      root.appendChild(aes);
    }
    try {
      metadata.setFromTree(metaFormat, root);
    } catch (IIOInvalidTreeException e) {
      throw new AssertionError(e);
    }
    return metadata;
  }

  private static Node findChild(Node root, String name) {
    Node child = root.getFirstChild();
    while (child != null) {
      if (name.equals(child.getNodeName())) return child;
      child = child.getNextSibling();
    }
    throw new AssertionError();
  }

  private static int radiusFor(int layer) {
    return 8 + (layer * 4);
  }

  private static final LoadingCache<Icon, ByteSource> headersWithIcons =
      CacheBuilder.newBuilder().build(new CacheLoader<Icon, ByteSource>() {
        @Override public ByteSource load(Icon icon) throws Exception {
          return withOverlay(HeaderImage.readImage(icon.fileName()));
        }
      });

  /** Creates a header image with the given icon. */
  public static ByteSource withIcon(Icon icon) {
    return headersWithIcons.getUnchecked(icon);
  }

  /** This cache will use ~700MB of memory. */
  private static final LoadingCache<Money, ByteSource> headersWithAmounts =
      CacheBuilder.newBuilder().maximumSize(1000).build(new CacheLoader<Money, ByteSource>() {
        @Override public ByteSource load(Money amount) throws Exception {
          return withOverlay(newAmountImage(amount));
        }
      });

  /** Creates a header image with the given amount. */
  public static ByteSource withAmount(Money amount) {
    return headersWithAmounts.getUnchecked(amount);
  }

  /** Creates a header image with the given image overlaid. */
  private static ByteSource withOverlay(BufferedImage overlay) {
    try {
      int x = (HeaderImage.WIDTH / 2) - (overlay.getWidth() / 2);
      int y = 200;

      ByteArrayOutputStream bout = new ByteArrayOutputStream();
      ImageOutputStream iout = new MemoryCacheImageOutputStream(bout);
      ImageWriter writer = newGifWriter();
      writer.setOutput(iout);
      writer.prepareWriteSequence(null);

      boolean first = true;
      BufferedImage buffer = newBuffer();
      Graphics2D g = buffer.createGraphics();
      g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
      for (BufferedImage frame : FRAMES) {
        g.drawImage(frame, null, 0, 0);
        g.drawImage(overlay, null, x, y);

        // All of our frames share the same color table. Because we explicitly set per-frame
        // metadata without including a local color table, Java won't emit a local color table.
        // Java will automatically use the first frame's color table as the global color table.
        IIOImage ii = new IIOImage(buffer, null, first ? FIRST_FRAME_METADATA : FRAME_METADATA);
        writer.writeToSequence(ii, null);
        first = false;
      }

      writer.endWriteSequence();
      iout.close();

      return ByteStreams.asByteSource(bout.toByteArray());
    } catch (IOException e) {
      throw new AssertionError(e);
    }
  }

  private static BufferedImage newAmountImage(Money amount) {
    Dimensions textDimensions = new Dimensions(440, 218);
    BufferedImage amountImage = new BufferedImage(
        textDimensions.width(), textDimensions.height(), BufferedImage.TYPE_INT_ARGB);
    Graphics2D g = amountImage.createGraphics();
    AmountImage.drawAmount(g, 0, 0, amount, textDimensions, Color.WHITE);
    return amountImage;
  }
}

Bob Lee - Profile *Reinventing something as fundamental as paths was hard. The solution we came up with may seem obvious, but there were…*medium.com