Building our bubbly holiday poster

Now that the web version of our 2013 holiday poster is live, I figured I’d talk a little about how it was built.

I spent a little time last January trying, unsuccessfully, to make a web version of last year’s poster. I got as far as using D3, a JavaScript data visualization library, to generate a Delaunay triangulation of a field of random points before running out of time, but as you can see, the result is too chaotic to resemble the beautiful, organic pattern of the poster.

Check out this Pen!

This year, I was determined to do better.

Patterning

This year’s poster continues the theme of an organic-looking pattern, but uses circles this time.

You can see that this pattern, like 2012’s triangular pattern, isn’t random at all. Instead, the circle sizes tend to smoothly change from small to large, and circles tend to sit next to simliarly-sized circles.

I’ve been slowly reading through Daniel Shiffman’s The Nature of Code, and in the introduction, he introduces the concept of Perlin noise. Perlin noise generators create random values where the next value is similar to its neighbors. This sounded perfect for seeding the circle values.

Using Jonas Wagner’s simplex-noise.js, it was trivial to build a little CoffeeScript noise generator:

class Poster.Noise
  constructor: (@scale) ->
    @simplex = new SimplexNoise

  for_point: (x, y) ->
    x = x / @scale
    y = y / @scale

    @simplex.noise2D(x, y) * 0.5 + 0.5 # translate from -1-1 to 0-1

Changing the scale value zoom in or out of the noise field, essentially making the “clouds” big and fluffy, or small and chaotic. I opted for zoomed-in noise, yielding bigger, fluffier clouds. You can see it in action here. Once the page is loaded, hit “n” to toggle the noise.

Generating

So, how do you translate a noise field into a bunch of smushed-together circles? My first attempt was to use the noise field to determine the probability of placing a circle at any given point (and therefore the radius), but that led to overlapping, poorly-spaced circles. Using D3’s force layout module to compact the space was a disaster, since the layout started out so far from optimal. It just exploded.

After a few false starts, I borrowed a circle-packing method from D3’s pack Layout module; given two circles and a radius, it places the third tangent to them. My final layout algorithm looks like this:

1. Randomly place a circle, reading the noise field to set its radius.
2. Place a second circle tangent to the first. This is a seed “spoke” for the next step, since the packing function requires two circles to place a third.
3. Walk around the first circle, generating new circles that are tangent to it, the central “hub”, and the most-recently placed “spoke” circle. Instead of checking to see if we’ve walked all the way around the hub, just generate 8 new circles to be safe. For each new circle:
   • Start with the smallest possible radius.
   • If the noise field at that circle’s center point requires a larger circle, bump the radius and place again.
   • Keep walking outward until the circle matches the noise or hits its max size.
4. Check to see if any of these circles overlap any others, or fall outside the viewport. If so, toss ‘em in the garbage.
5. Push the remaining circles into a working queue.
6. Grab the next circle in the queue and repeat steps 3–6 until the queue’s empty!

Slowed down, it looks a little like this:

Here’s a sketch of the implementation in CoffeeScript:

class Poster
  constructor: () ->
    @nodes = []

    @queue = []

    # start with a random point
    x = Math.random() * @w()
    y = Math.random() * @h()
    angle = Math.PI / 4 
    n0 = { x: x, y: y, r: @r_for_point(x, y), i: 0 }
    @nodes.push n0
    @queue.push n0

    x = x + n0.r * Math.cos(angle)
    y = y + n0.r * Math.sin(angle)
    r = @r_for_point(x + n0.r, y)
    n1 = {
      r: r
      x: x + r * Math.cos(angle)
      y: y + r * Math.sin(angle)
      i: 1
    }
    @nodes.push n1
    @queue.push n1

    @node_id = 2
    @q = d3.geom.quadtree(@nodes,
                          -@padding,
                          -@padding,
                          @w() + @padding,
                          @h() + @padding)
    @place_next_nodes()

  place_next_nodes: () =>
    if (node = @queue.shift())
      temp_nodes = []
      for i in [0...8]
        new_node = { r: @radius_min }
        if i is 0
          placement_node = if node.i is 0 then @nodes[1] else @nodes[node.i - 1]
        else
          placement_node = temp_nodes[i - 1]

        # Walk towards optimal size/fit
        while true
          @pack(node, placement_node, new_node)
          if (@r_for_point(new_node.x, new_node.y) > new_node.r)
            new_node.r += 1
          else
            break
        temp_nodes.push(new_node)
      for candidate_node in temp_nodes
        unless @should_cull(candidate_node)
          candidate_node.i = @node_id++
          @queue.push(candidate_node)
          @nodes.push(candidate_node)
          @q.add(candidate_node)
          @circles = @svg.selectAll("circle")
              .data(@nodes)
            .enter().append("svg:circle")
              .attr("r", (d) -> d.r)
              .attr("cx", (d) -> d.x)
              .attr("cy", (d) -> d.y)
      _.defer(@place_next_nodes)
    else
      @init_graph()

You can see the full CoffeeScript code over at GitHub.

I’m very grateful for D3’s quadtree implementation. Without some sort of spatial index, collision detection would get out of hand very quickly. You’d have to literally test each circle against every other existing one to see if they collided. The quadtree takes you from O(n²) to O(n log n) — which turns out to be just fast enough to make the generator watchable.

Compacting

The generated circles looked pretty cool, but since I was only guaranteeing that each circle touched two others, there were a lot of gaps in the arrangement, as you can see.

Luckily, though, since they’re basically placed where they need to be and none of them are overlapping, it was no big deal to turn on D3’s force layout from earlier and compact the space. Unlike with randomly placed overlapping circles, in this case, the force layout gradually pulls the circles together until a stable state is reached and the layout terminates.

Downloading

At long last, I finally had a field of circles that looked a lot like the source image, but my idea for the final product was to use the circles as a slowly undulating backdrop underneath the inspirational message of the poster. As cool as the generator looks, it takes way too long to generate a whole page full of circles, so I reluctantly decided I’d have to render them out to a file and then import the data in the poster itself.

It’s actually not much fun extracting generated data from a web page using Chrome’s developer tools. If you try to inspect a large array in the console, it’s broken up into chunks of a hundred elements, and you can’t get at the entire array.

You can get around this by invoking JSON.stringify(poster.nodes) and then copy/pasting the giant JSON string into a text file, but there’s an easier option.

Using a handful of polyfills, and following a great HTML5 Rocks tutorial by Eli Grey, I was able to save off the resulting JSON directly to disk, which made it much easier to build up a bunch of layouts to pick from. The code for this was trivial:

download_json: () ->
  data = (cx: d.x, cy: d.y, r: d.r for d in @nodes)
  bb = new BlobBuilder()
  bb.append JSON.stringify(data)
  blob = bb.getBlob "application/json;charset=#{document.characterSet}"
  saveAs blob, "bubbles.json"

I’m not an expert on the File API, and based on the article, it sounds like this interface may be removed from the spec in the future. Even with polyfills, this only worked for me in Chrome, so I wouldn’t recommend it for a production system. But for this use case, it was the perfect solution.

Next time, on Bubblepiece Theatre

That’s about it for the generator. In the next post, I’ll talk about building the poster itself, and the effort that went into its animation. In the meantime, you should follow us on Twitter, and if any of this sounds interesting to you, check out our job postings!

Further reading

• Building Our Bubbly Holiday Poster, Part II
• Bubble Charts in D3
• Image-Based Circle Packing