Posts

Building Glyphs with Chaikin Curves

While playing around with Chaikin curves (which I first heard about from Ben Kovach in his talk about generative art) I saw that using them to connect some random points on a screen made some cool-looking glyphs. A randomly generated language!

Overview

Chaikin curves (developed by George Chaikin in '74) create a smooth curve from a series of points by cutting the corners off of the curve.

Given a set of points, we take each line segment and:

  1. Split it into three segments: the first 25% of the curve, the middle 50%, and the last 25%.
  2. Discard the first and last quarters of the original segment
  3. Save the start and end points of the middle line segment as the new points in the curve

In doing so, we add more points each time we run the algorithm, with the line segments getting shorter, resulting in a smoother curve. We can run the algorithm recursively and get progressively shorter line segments and a smoother line.

And then if we're dealing with a closed shape instead of a series of line segments, we also need to make a line segment out of the first and last points.

That's pretty much it, so let's build it.

Coding the algorithm

First, we're going to code the algorithm, and then we'll use it on a canvas to make some glyphs that are pretty and unintelligible (what I strive for in my life, too).

Let's start off with some tests so that we're clear on what we're building.

Base case

This is going to be a recursive algorithm. On the first run through with this algorithm, we're still going to have a pretty jagged curve. But once we run through it four or five times, the curve's going to be as smooth as butter.

Since it's recursive, we want to return the points of the curve once we have no more steps so that we don't get caught in an infinite loop.

// chaikin.js
// javascript's standard assert library - no need to install anything for this
const { deepEqual } = require("assert")
// write a simple assert method with slightly better logging
const assert = (actual, expected, message) => {
  try {
    deepEqual(actual, expected, message)
  } catch (err) {
    console.error("ERROR! ", message)
    console.log("Expected: ")
    console.dir(err.expected)
    console.log("Actual: ")
    console.dir(err.actual)
  }
}
const chaikin = () => {
  /* Coming soon! */
  return {}
}
// our test points
const points = [
  [100, 100],
  [400, 300],
  [700, 200],
]
assert(
  chaikin({ points, step: 0 }).points,
  points,
  "returns input points once base case is reached"
)

If we run this test (with node chaikin.js), we get an error, since the chaikin function doesn't currently do anything. So, let's get the test passing:

const { deepEqual } = require("assert")
const assert = (actual, expected, message) => {
  try {
    deepEqual(actual, expected, message)
  } catch (err) {
    console.error("ERROR! ", message)
    console.log("Expected: ")
    console.dir(err.expected)
    console.log("Actual: ")
    console.dir(err.actual)
  }
}
// NEW!
const chaikin = ({ points, level }) => {
  if (step <= 0) {
    // return this in an object, in case we need to return more properties later
    return { points }
  }
}
const points = [
  [100, 100],
  [400, 300],
  [700, 200],
]
assert(
  chaikin({ points, step: 0 }).points,
  points,
  "returns input points once base case is reached"
)

Recursive case for open curves

Base case is covered! Now we can start finding the points. We'll start with open curves. The test case is going to involve us doing a little bit of math by hand with our test points to ensure we're looking for the correct numbers.

Calculating test case result by hand

Given points of [100,100], [400, 300], [700, 200], what would we expect the output to be? The algorithm says that we want one point to be one quarter through the line segment, and the other point to be three quarters through. Let's calculate the end points of the middle 50% line segment.

chaikin line segment

We know the first point and second point ([100,100] and [400, 300]) x values are 400 - 100 = 300 pixels apart. 25% of that is 75, and 75% is 225, so we would expect x1 to be at 100 + 75 = 175 and x2 to be at 100 + 225 = 325.

For the y values, we've got a difference of 300 - 100 = 200. 25% and 75% are 50 and 150, respectively. So, y1 and y2 are going to be 100 + 50 and 100 + 150.

So, the two points that come from the first line segment are [175, 150] and [325, 250].

And for the second line segment ([400, 300] and [700, 200]), the two points will be: [475, 270] and [625, 225].

Let's add those for the test case, using a step of 1 so that we don't hit the base case immediately.

deepEqual(
  chaikin({ points, step: 1 }).points,
  [
    [175, 150],
    [325, 250],
    [475, 275],
    [625, 225],
  ],
  "returns points 25% and 75% through each line segment"
)

Finding the formula to calculate these values

Okay, we've got our test case. But as it stands, it's going to be hard to write an algorithm to calculate these points with the step-by-step math. Let's find a formula to make this all easier.

To get the first points values, the 25% one, we took the difference between the x values and then added 25% of that difference to the first point's x value.

And for the second point, the 75% one, we took the difference between the x values and then added 75% of that difference to the first x value. In a formula:

point1's x:
xP1 = x1 + 0.25 * (x2 - x1)
xP1 = x1 + (0.25 * x2) - (0.25 * x1)
xP1 = (0.75 * x1) + (0.25 * x2)
point2's x:
xP2 = x1 + (0.75) * (x2 - x1)
xP2 = x1 + (0.75 * x2) - (0.75 * x1)
xP2 = (0.25 * x1) + (0.75 * x2)

Okay! Let's get these formulas into the chaikin algorithm. For each line segment, we need to use these formulas on both the x and y values to create the two new points.

const chaikin = ({ points, step }) => {
  if (step <= 0) {
    return { points }
  }
  // NEW!
  const result = []
  for (let i = 0; i < points.length - 1; i++) {
    // current and next point in the curve
    const pointA = points[i]
    const pointB = points[i + 1]
    const [xA, yA] = pointA
    const [xB, yB] = pointB
    // 25%-in point's x and y
    const x1 = 0.25 * xB + 0.75 * xA
    const y1 = 0.25 * yB + 0.75 * yA
    // 75%-in point's x and y
    const x2 = 0.75 * xB + 0.25 * xA
    const y2 = 0.75 * yB + 0.25 * yA
    result.push([x1, y1])
    result.push([x2, y2])
  }
  // call chaikin again with:
  // - one fewer step remaining
  // - our result points that we just calculated as the new input
  return chaikin({ points: result, step: step - 1 })
}

When we run the tests again, all should be passing. At this point, we could run the chaikin function with greater numbers of levels, and we'd get a smoother and smoother curve, as we'll see displayed soon. But first, let's cover the case for closed polygons.

Covering the closed curve case

The difference here between the open curves is that we need to make one last extra line segment that connects the last point with the first point.

Using the same input points for our test case, we'd now expect to get 2 more points, from the [700, 500] and [100,100] line segment.

Let's calculate these two new points' values by hand first again:

const x1 = 0.75 * 700 + 0.25 * 100 // 550
const y1 = 0.75 * 200 + 0.25 * 100 // 175
const x2 = 0.25 * 700 + 0.75 * 100 // 250
const y2 = 0.25 * 200 + 0.75 * 100 // 125

The last two expected points are [550, 175] and [250, 125]. We'll also need to told when we run the function whether we should calculate these last two points with a boolean flag. I'll name it isClosed. The test case will look like this:

assert(
  chaikin({ points, step: 1, isClosed: true }).points, // new isClosed flag is true
  [
    [175, 150],
    [325, 250],
    [475, 350],
    [625, 450],
    [550, 175],
    [250, 125],
  ],
  "returns points 25% and 75% through each line segment for a closed polygon"
)

Running this test fails because we're not doing anything with the isClosed value in our chaikin function yet. If the value is true, we just want to run the for loop one more time, meaning we'll run the function points.length times (3, in our test case) instead of points.length - 1 times. Let's toss that in:

// NEW! add the isClosed argument, defaulting to false
const chaikin = ({ points, step, isClosed = false }) => {
  if (step <= 0) {
    return { points, isClosed }
  }
  const result = []
  // NEW! use the isClosed variable to determine the max for loop index
  const maxIndex = isClosed ? points.length : points.length - 1
  for (let i = 0; i < maxIndex; i++) {
    const pointA = points[i]
    const pointB = points[i + 1]
    const [xA, yA] = pointA
    const [xB, yB] = pointB
    // 25% in point's x and y
    const x1 = 0.25 * xB + 0.75 * xA
    const y1 = 0.25 * yB + 0.75 * yA
    // 75% in point's x and y
    const x2 = 0.75 * xB + 0.25 * xA
    const y2 = 0.75 * yB + 0.25 * yA
    result.push([x1, y1])
    result.push([x2, y2])
  }
  // NEW! pass the isClosed value to any future calls
  return chaikin({ points: result, step: step - 1, isClosed })
}

Almost there, but we've still got a problem. If you can't spot it, you can see an error message when we try to run this as is. If the curve is closed, i can get up to 2 with our test input points of length 3. When we get to i being 2, we can calculate pointA as points[2]. But when we try to get pointB, we're trying to get points[3], which doesn't exist!

Instead, we want to get points[0], the first point, for pointB. 0 just so happens to be the remainder when we divide the index of 3 by points.length. We'll use that fact in order to prevent our current error with the modulus, or remainder, operator. Then, instead of finding points[3], we'll look for points[(the remainder of i+1) / points.length] == points[0 / 3] == points[0].

Let's make the switch:

const chaikin = ({ points, step, isClosed = false }) => {
  if (step <= 0) {
    return { points, isClosed }
  }
  const result = []
  const maxIndex = isClosed ? points.length : points.length - 1
  for (let i = 0; i < maxIndex; i++) {
    const pointA = points[i]
    // NEW: use the modulus operator to avoid an index that's too high
    const pointB = points[(i + 1) % points.length]
    const [xA, yA] = pointA
    const [xB, yB] = pointB
    // 25% in point's x and y
    const x1 = 0.25 * xB + 0.75 * xA
    const y1 = 0.25 * yB + 0.75 * yA
    // 75% in point's x and y
    const x2 = 0.75 * xB + 0.25 * xA
    const y2 = 0.75 * yB + 0.25 * yA
    result.push([x1, y1])
    result.push([x2, y2])
  }
  return chaikin({ points: result, step: step - 1, isClosed })
}

Our chaikin function is complete! We've got some test cases to give us some confidence that the algorithm is working. Let's get it onto a canvas now to see it in action.

Using the algorithm on a canvas

Set up the canvas

To start using this on a canvas, we'll need to make an html page. We can take our chaikin implementation and put it into a script tag at the end of the body.

<!-- index.html -->
<body>
  <canvas></canvas>
  <script>
    const chaikin = ({ points, step, isClosed = false }) => {
      /* exact implementation we just wrote */
    }
    var canvas = document.querySelector("canvas")
    var context = canvas.getContext("2d")
    // set the size to smaller of window width or height
    var size = Math.min(window.innerWidth, window.innerHeight)
    canvas.width = size - 100
    canvas.height = size - 100
    // draw a gray rectangle covering the entire canvas
    context.rect(0, 0, canvas.width, canvas.height)
    context.fillStyle = "rgba(0,0,0, 0.1)"
    context.fill()
  </script>
</body>

If you open up this html file and see a gray box, all is working well. You can also throw all of this code into an HTML file on Codepen to see it all working:

Draw some curves

First, let's just draw some hard-coded points. Let's move down the canvas and ping pong between 0 and the full width as the x coordinates. Then, we'll draw both that curve and the chaikin curve with 5 steps of recursion, which should lead to a pretty smooth curve.

<body>
  <canvas></canvas>
  <script>
    const chaikin = ({ points, step, isClosed = false }) => {
      /* ... */
    }
    var canvas = document.querySelector("canvas")
    var context = canvas.getContext("2d")
    var size = Math.min(window.innerWidth, window.innerHeight)
    canvas.width = size - 100
    canvas.height = size - 100
    context.rect(0, 0, canvas.width, canvas.height)
    context.fillStyle = "rgba(0,0,0, 0.1)"
    context.fill()
    // NEW!
    // create the points
    const points = [
      [0, 0],
      [canvas.width, canvas.height * 0.25],
      [0, canvas.height * 0.5],
      [canvas.width, canvas.height * 0.75],
      [0, canvas.height],
    ]
    // draw the original points as a thin black line
    context.beginPath()
    context.lineWidth = 1
    context.moveTo(points[0][0], points[0][1])
    points.forEach(([x, y]) => {
      context.lineTo(x, y)
    })
    context.stroke()
    // draw the chaikin-ed points
    const { points: chaikinPoints } = chaikin({ points, step: 5 })
    context.lineWidth = 5
    context.strokeStyle = "red"
    context.beginPath()
    context.moveTo(chaikinPoints[0][0], chaikinPoints[0][1])
    chaikinPoints.forEach(([x, y]) => {
      context.lineTo(x, y)
    })
    context.stroke()
  </script>
</body>

Draw a glyph

A chaikin curve on a canvas! We did it! If we want to make some random glyphs, all we'll need to do is use random points instead of the hard-coded ping-pong points I made.

To make this easier on ourselves, let's make a helper function to create a point. Given a starting x and y, as well as a width and height of the box that the point needs to be in, we'll return an [x,y] point with a random coordinates inside of that box.

Then we'll create a set of 10 or so random points and draw a curve of those ten points at 4 steps.

<body>
  <canvas></canvas>
  <script>
    const chaikin = ({ points, step, isClosed = false }) => {
      /* ... */
    }
    var canvas = document.querySelector("canvas")
    var context = canvas.getContext("2d")
    var size = Math.min(window.innerWidth, window.innerHeight)
    canvas.width = size - 100
    canvas.height = size - 100
    context.lineWidth = 1
    context.rect(0, 0, canvas.width, canvas.height)
    context.fillStyle = "rgba(0,0,0, 0.1)"
    context.fill()
    // NEW!
    const createRandomPoint = ({ x, y, width, height }) => {
      const randomX = x + Math.random() * width
      const randomY = y + Math.random() * height
      return [Math.floor(randomX), Math.floor(randomY)]
    }
    const points = []
    const pointsCount = 10
    for (let i = 0; i < pointsCount; i++) {
      points.push(
        createRandomPoint({
          x: 0,
          y: 0,
          width: canvas.width,
          height: canvas.height,
        })
      )
    }
    // draw the chaikin-ed points
    const { points: chaikinPoints } = chaikin({ points, step: 5 })
    context.lineWidth = 5
    context.strokeStyle = "black"
    context.beginPath()
    context.moveTo(chaikinPoints[0][0], chaikinPoints[0][1])
    chaikinPoints.forEach(([x, y]) => {
      context.lineTo(x, y)
    })
    context.stroke()
  </script>
</body>

Bonus! Further refinements

We're pretty much where we need to be already. Refreshing the page will keep creating new random glyphs. There are two more steps I want to tackle to make the glyphs more centered and more random.

Center the glyph

First, let's work on centering the glyph. To do this, my plan is to find the bounding box of the chaikin points to get the minimum and maximum x and y values in the curve. Then, we can find the center of the outer box we put the chaikin curve's random points in as well as the center of the chaikin bounding box. With both centers, we can calculate how far off the center of the smaller chaikin box is, and then shift every point in the chaikin curve that many pixels so that the centers for both boxes are the same.

For that, we'll first need to create a getBounds function that will return the minimum and maximum x and y values for a set of points.

Writing the getBounds function

const getBounds = points => {
  let minX, minY, maxX, maxY
  if (!Array.isArray(points) || !points.length) {
    throw "Expected an array with more than zero elements"
  }
  points.forEach(([x, y]) => {
    // set new minimum if value:
    //  1. doesn't exist (but isn't 0)
    //  2. is less than the current minimum
    if ((!minX && minX !== 0) || x <= minX) {
      minX = x
    }
    // set new maximum if value:
    //  1. doesn't exist (but isn't 0)
    //  2. is more than the current maximum
    if ((!maxX && maxX !== 0) || x >= maxX) {
      maxX = x
    }
    if ((!minY && minY !== 0) || y <= minY) {
      minY = y
    }
    if ((!maxY && maxY !== 0) || y >= maxY) {
      maxY = y
    }
  })
  return {
    min: [minX, minY],
    max: [maxX, maxY],
  }
}

Use getBounds

Okay, now let's figure out the center of both boxes and shift the chaikin box to line up with the center of the outer box.

<script>
  const getBounds = points => {
    /* ... */
  }
  const { points: chaikinPoints } = chaikin({ points, step: 5 })
  // use the getBounds function to determine the height, width, and center
  // of the chaikin curve
  const { min: chaikinMin, max: chaikinMax } = getBounds(chaikinPoints)
  const [chaikinMinX, chaikinMinY] = chaikinMin
  const [chaikinMaxX, chaikinMaxY] = chaikinMax
  const chaikinWidth = chaikinMaxX - chaikinMinX
  const chaikinHeight = chaikinMaxY - chaikinMinY
  const chaikinCenterX = chaikinMinX + chaikinWidth / 2
  const chaikinCenterY = chaikinMinY + chaikinHeight / 2
  // these values need to correspond to the x, y, width and height
  // values we used to create the random points.
  const outerBoxCenterX = 0 + canvas.width / 2
  const outerBoxCenterY = 0 + canvas.height / 2
  // find the difference between the outerBoxCenter and chaikinCenter
  const xShiftForChaikin = outerBoxCenterX - chaikinCenterX
  const yShiftForChaikin = outerBoxCenterY - chaikinCenterY
  // shift the chaikin curve points by the required shift to center them
  const shiftedChaikinPoints = chaikinPoints.map(([x, y]) => {
    return [x + xShiftForChaikin, y + yShiftForChaikin]
  })
  // draw the new, shifted chaikin curve
  context.beginPath()
  context.moveTo(shiftedChaikinPoints[0][0], shiftedChaikinPoints[0][1])
  shiftedChaikinPoints.forEach(([x, y]) => {
    context.lineTo(x, y)
  })
  context.stroke()
</script>

Whew! Okay, now when you refresh the page, you should be getting a chaikin curve glyph that looks centered in the canvas.

Randomize the glyph creation

Last thing we'll do today is randomize the number of points in the curve, as well as whether the curve is closed. These are much easier than the centering. All we'll need to do is change the pointsCount variable from a hard-coded 10 to use two new pointsMinimum and pointsVariance variables.

const pointsMinimum = 5
const pointsVariance = 5
const pointsCount = pointsMinimum + Math.floor(Math.random() * pointsVariance)

You can play around with the minimum and variance to get the shapes that you want.

And then for randomly choosing whether the curve is closed, update the chaikin call to have an isClosed parameter of Math.random() > 0.5. You'll also want to now return the isClosed parameter where we call chaikin so that we can draw the curve with the final line segment connected.

const { points: chaikinPoints, isClosed: isChaikinClosed } = chaikin({
  points,
  step: 5,
  isClosed: Math.random() > 0.5,
})

And then we'll update the drawing portion of the code to check whether the curve is closed:

/* ... */
context.beginPath()
context.moveTo(chaikinPoints[0][0], chaikinPoints[0][1])
chaikinPoints.forEach(([x, y]) => {
  context.lineTo(x, y)
})
// NEW!
if (isChaikinClosed) {
  context.lineTo(chaikinPoints[0][0], chaikinPoints[0][1])
}
context.stroke()

Conclusion

Check out the Codepen below for the code we wrote.

From here, you'd be ready to explore what else chaikin curves could do. Some options:

  1. arrange a number of glyphs in a nice grid
  2. randomly place 100 chaikin curves on the screen
  3. lower the opacity of the curve and draw hundreds on the screen
  4. create a curve from a starting curve of 100 random points

If you make something cool, send me a screenshot!

Until next time ✌️

©2020 Matthew Knudsen