Quadtree Grids

In this tutorial, we will be learning to create super versatile generative/random grid layouts in just a few lines of JavaScript. Using a data structure called a Quadtree, we will produce harmonious grids based on random numbers, source images, user input, and more.

The chaotic, yet perfectly aligned world of generative grids is waiting for us — let’s go!

I picked up this technique from one of my all-time favorite design agencies, Pentagram. In their branding work for Graphcore, they use Quadtrees extensively to generate random yet visually coherent patterns.

---

What we are building

First things first, let’s go over exactly what we are cooking up in this tutorial. Here’s an animated example of a generative Quadtree grid in action:

To break this example down into steps:

1. Add some { x, y } points to a 2D space. In this example, the point’s positions are random but biased towards a focal point.
2. Subdivide the space into quadrants based on the density/position of the points
3. Store a reference to the resulting rectangles (these are the grid areas)
4. Use the resulting grid areas to position stuff! In the example above, I am using squares and circles to form a simple pattern.

By experimenting with creative ways to position the points, we can create some super interesting grid layouts. This example uses biased random numbers, but what if, for example — the points came from the brightness values of an image?

We could pass in a picture of a Fibonacci spiral, a circle, a square, whatever, and have our points generate based on its pixel values. The possibilities are endless! Any method for positioning objects in a 2D space will work. The weirder, the better.

How it works

The subdividing magic we see here is all handled by a data structure called a Quadtree. I like to think of Quadtrees as little containers. Once the Quadtree fills with a certain number of objects, it splits itself into four more Quadtrees. Once those Quadtrees fill up, they divide themselves again, and so on.

Quadtrees can be tricky to visualize, so here is an interactive example — click to add objects/points and observe how the Quadtree subdivides. In this example, the maximum number of items a Quadtree can contain is four.

Very satisfying indeed… this is everything we need to know about Quadtrees for this tutorial, but if you would like to learn more about how they work/how you can use them, check out this video by Dan Shiffman.

This tutorial is perfect for folks comfortable with JavaScript and familiar with SVG/HTML Canvas.

Let’s code!

Awesome, I think we are ready to make some grids.

To keep things simple and let us focus on the fun stuff — I have added a handy createQtGrid function to my generative-utils repo. This function takes an array of points and returns a ready-to-use Quadtree grid. If you would like to dive into the source code, it is available in this repository.

This CodePen has all of the boilerplate HTML/JS/CSS needed to follow along with this tutorial.

Biased random grids

To start, let’s create a Quadtree grid with a biased random distribution of points. Biased random numbers work great here, as they provide a strong visual focus. Pure randomness, ironically, tends to look a little boring for Quadtree grids. The grid areas look too uniform, as the points are scattered all over the 2D space.

In this example, we will use an SVG element to render our grid areas. Let’s start by defining a width and height property for the SVG’s viewBox:

const width = 200;
const height = 200;

Next, let’s create a new <svg> element to render our grid. For this, we are going to use svg.js — a JavaScript library that greatly simplifies dynamic SVG scripting. You can read a little more about svg.js in my Generative SVG Starter Kit.

const svg = SVG().viewbox(0, 0, width, height).addTo('body');

Now that we have our SVG element, we can generate some biased random points. To do so, we can make use of the randomBias function. This function returns a random number based on four arguments:

1. Minimum - the lowest value that the returned number could be
2. Maximum - the highest value that the returned number could be
3. Bias - any number between the minimum and maximum number, this is the “focus point”
4. Influence - A number between 0 - 1, this argument determines how close the returned number is likely to be to the bias.

Let’s pop some code in to generate 100 random points, with a focus towards the center of the viewBox, and use svg.js to render them:

const points = [...Array(100)].map(() => {
  return {
    x: randomBias(0, width, width / 2, 1),
    y: randomBias(0, height, height / 2, 1),
    width: 1,
    height: 1,
  };
});

points.forEach((point) => {
  svg.circle(2).cx(point.x).cy(point.y);
});

Each point needs a width and height value to work correctly with createQtGrid.

Nice! Your SVG element should now look something like this:

This point distribution looks lovely, but we should update the code so that the focus point can vary a little. Let’s make that happen:

const focus = {
  x: random(0, width),
  y: random(0, height),
};

const points = [...Array(100)].map(() => {
  return {
    x: randomBias(0, width, focus.x, 1),
    y: randomBias(0, height, focus.y, 1),
    width: 1,
    height: 1,
  };
});

In this snippet, we use the random function to generate a random { x, y } focus point on the grid. Once the code is updated, you should see something like this:

Perfect! This focused-yet-random distribution is going to look great for Quadtree grids. Let’s create one:

const grid = createQtGrid({
  width,
  height,
  points,
  gap: 1,
  maxQtLevels: 4,
});

In this snippet, we call createQtGrid with a width value, a height value, a level limit, and the points we generated just now. We also pass in a gap property to give the grid areas a little breathing room.

The level limit (controlled by maxQtLevels) defines how many times the Quadtree can subdivide. A higher value, paired with a higher number of points, will result in a more detailed grid.

If you console.log(grid) now, you should see an object with a few different properties — at this point, though, we are only interested in the grid areas. Let’s iterate over these and render an SVG <rect> for each one:

grid.areas.forEach((area) => {
  svg
    .rect(area.width, area.height)
    .x(area.x)
    .y(area.y)
    .fill('none')
    .stroke('#000');
});

You should now see something like this:

Excellent. That’s it! We have successfully generated a beautiful generative grid, ready to be filled with anything you like. As a simple example, here’s how we could add a circle to a random selection of the grid areas:

Hey, that’s some pretty cool generative art! All in just a few lines of code, too. We are all done with this demo now, but as a next step, I suggest having a play with the number of points, maximum subdivision amount (maxQtLevels), and the point distribution logic — see what you can create!

Image-based grids

Next up on the generative Quadtree menu are some delicious image-based grids. For this example, we will be using the pixel values of image files to determine our underlying points.

To get set up, we can re-use the SVG element and width/height variables defined in the last demo. Either comment out the previous point generation/render code or fork the pen and create a fresh canvas. Your call!

Ok, all set? Let’s find a suitable image. For our demo, a simple picture comprised of only entirely black or white pixels is perfect. The basic outline of a shape (a circle, square, spiral) is ideal. Think something like this:

If you don’t fancy whipping up any custom images, here are some I made earlier. *Removes pre-made shapes from the weird digital oven…*

• A circle outline
• A square outline
• A golden ratio spiral
• A pentagon

These images are all 192x192px in size, matching the width/height attributes of the example SVG viewBox and Quadtree grid. The image examples are formatted this way to save on having to do any funky calculation. You don’t have to work to this resolution, but try and make sure your image dimensions match the width/height dimensions defined in your code.

Although these source images are quite small, the end result will scale to any size.

Once you have chosen your image, pop back into the code and create a new canvas element, setting its width and height to that of your SVG viewBox/grid and storing its context in a new variable. We will use this canvas in a moment to render our image and extract its pixel data.

const canvas = document.createElement('canvas');
const ctx = canvas.getContext('2d');
canvas.width = width;
canvas.height = height;

Next, let’s load our chosen image. I am using a Fibonacci spiral:

const imageUrl = 'YOUR_IMAGE_URL';
const img = new Image();
img.crossOrigin = 'anonymous';
img.src = imageUrl;

Once the image has loaded, we render it to our canvas, define a new points array, and loop through all of the canvas’s pixels. If a pixel has a red, green, and blue value of 0 (a black pixel), we store its coordinates in the points array — this is why we are using images comprised of only black or white pixels.

You could expand this code to handle full color images, but we are keeping things simple for the demo.

To get some visual feedback on what is happening here, let’s also render an SVG circle at each of these points:

img.onload = () => {
  ctx.drawImage(img, 0, 0);

  const points = [];

  for (let x = 0; x < width; x++) {
    for (let y = 0; y < height; y++) {
      const { data } = ctx.getImageData(x, y, 1, 1);
      if (data[0] + data[1] + data[2] === 0) {
        points.push({ x, y, width: 1, height: 1 });

        svg.circle(1).cx(x).cy(y);
      }
    }
  }
};

For my Fibonacci spiral example, the output of this code looks something like this:

Hey, look at that! It’s the original image turned into { x, y } points. Perfect. Let’s pass these points to our createQtGrid function, just like before. This time, try setting maxQtLevels to a slightly higher number — this should help bring out the detail in the grid:

img.onload = () => {
  ...

  const grid = createQtGrid({
    width,
    height,
    points,
    gap: 1,
    maxQtLevels: 6
  });
}

Now, we can loop through the grid areas in the same way as demo #1, rendering an SVG rectangle at each one:

grid.areas.forEach((area) => {
  svg
    .rect(area.width, area.height)
    .x(area.x)
    .y(area.y)
    .fill('none')
    .stroke('#000');
});

Drumroll, please!

Beautiful! We have created a generative grid layout based on an underlying source image. In this case, that source image is a Fibonacci spiral. Very fancy indeed! Here’s what this grid looks like with some circles/rectangles placed on it:

It’s worth noting that different images will need slightly different maxQtLevels values. Like everything in generative art, there is no single magic number. The best results come from lots of tweaking and squinting at the screen.

Integrating with CSS grid

So far in our Quadtree adventure, we have exclusively used SVG to render our grids, but it seems like a bit of a shame to leave CSS grid out of the party, right?

Well, I have some good news! The area objects that createQtGrid returns also have col and row values. Using these values, we can easily create generative CSS grid layouts — ready to use for all kinds of innovative designs.

I won’t go into too much detail here, as the process for creating CSS grid layouts is identical to that of the previous examples, but here’s a CodePen showing how to use the createQtGrid function with HTML/CSS:

Excellent! Well, that concludes our generative Quadtree journey, folks.