SymmetricalDataSecurity: Chaikin’s Algorithm: Drawing Curves

Bezier curves are super useful and are built in to most drawing APIs. But usually they are limited to drawing curves between four points – two end points and two control points. Sometimes it is useful to draw points through a bunch of other points.

Many years ago I learned a technique to do this. It involves taking a list of points and calculating another set of points that is made up of the mid points between each consecutive pair of points. Then you draw a series of consecutive quadratic curves, using the mid points as the end points and the original points as control points. It sounds a bit confusing, and to be fair, it is a somewhat complex process. But it works great. I recently discovered that this technique is known as piecewise Bezier curves. I described the technique in detail in this Coding Math video, so I won’t go into it again here.

Even more recently, I discovered Chaikin’s Algorithm, which accomplishes the exact same thing, but in a very different way. In fact, the results of this algorithm will draw the exact same curve as the method I’ve been using for years.

The Basics

The core strategy here is to take each pair of points in the list and convert it to two new points. Those points will be 1/4 and 3/4 along the original line segment formed by the original two points. That’s not super clear maybe, but once you see it, it’s pretty obvious.

The original line goes from point 0 to point 1. (You can drag those points around, btw.) But new points are created at 25% and 75% of the way along that line. And a new, darker line is drawn there. Here’s the core code for that:

function chaikin(p0, p1) {
  const percent = 0.25;
  const dx = p1.x - p0.x;
  const dy = p1.y - p0.y;
  return [
    {
      x: p0.x + dx * percent,
      y: p0.y + dy * percent,
    },
    {
      x: p0.x + dx * (1 - percent),
      y: p0.y + dy * (1 - percent),
    },
  ];
}

This function takes two points and returns two points that are at those relative positions just described.

There’s also a slider there, that will let you change that percentage from 25% to anything from 0-50%. You can move that around to get an idea how that works.

So far, so good. Now we need to do that to multiple points beyond two.

Making a Path

This next version does the same thing, but between three points.

The code for calculating the new points is exactly the same. We get two points for point 0 and point1. And another two for point 1 and point 2. This gives us a total of four points, which lets us draw three line segments. You can already see how it’s cutting the curve up a bit.

Generalizing for More Points

Now we need to make this function a bit more useful. Instead of taking and returning two points, let’s have it take an array of points and return an array of points. Here’s the code for this new version:

function chaikin(points) {
  const path = [];
  const percent = 0.25
  for (let i = 0; i < points.length - 1; i++) {
    const p0 = points[i];
    const p1 = points[i + 1];
    const dx = p1.x - p0.x;
    const dy = p1.y - p0.y;
    path.push({
      x: p0.x + dx * percent,
      y: p0.y + dy * percent,
    });
    path.push({
      x: p0.x + dx * (1 - percent),
      y: p0.y + dy * (1 - percent),
    });
  }
  return path;
}

So, we get a list of points and immediately make a new empty array of points. In line 4 we start a loop with i going from 0 to one less than the total points. This lets us get each pair of points as points[i] and points[i + 1]. Lines 7-16 create the two new points between this pair and add them to the new array. When we get to the end, we return that array. Here’s what we get when we do that:

The points are randomly placed this time, so you might need to move them around a bit to get a clear picture of what’s going on. This example uses five points, but it’s already set up to handle any length path of points you want to throw at it.

Also try using the slider again to see how this affects the “curve” that’s forming.

Smoothing the Curve

There are two issues to solve now. One is that while we’ve cut some corners, we still don’t have a smooth curve. The other issue is that we’re losing the start and end of our original set of points. In the above example you can see that the newly created path starts quite a bit away from the original points 0 and 4.

The next bits of code addresses both of those. First, we’ll smooth things out. The strategy for this is very simple. Just run the chaikin function a few more times! I created a new function called smooth that takes a list of points and a number of times to iterate. It just replaces the old points for the new points the specified amount of times and returns the result:

function smooth(points, iter) {
  for (let i = 0; i < iter; i++) {
    points = chaikin(points);
  }
  return points;
}

Now we’ll preserve our start and end points in the chaikin function itself.

function chaikin(points) {
  const first = points[0];
  const last = points[points.length - 1];

  const path = [first];
  const percent = 0.25;
  for (let i = 0; i < points.length - 1; i++) {
    const p0 = points[i];
    const p1 = points[i + 1];
    const dx = p1.x - p0.x;
    const dy = p1.y - p0.y;
    path.push({
      x: p0.x + dx * percent,
      y: p0.y + dy * percent,
    });
    path.push({
      x: p0.x + dx * (1 - percent),
      y: p0.y + dy * (1 - percent),
    });
  }
  path.push(last)
  return path;
}

We just get references to the first and last points as first and last and add first to the new array before we do anything, and then push last onto the end when we are done. Simple enough, and here’s the result:

For this penultimate version, I upped the number of points to eight. You’ll probably have to drag them around to untangle the random spaghetti they create. But now you see we have a nice beautiful curve going exactly from point 0 to point 7.

With this, we can ask and answer a couple of questions.

What happens if you use percentages other than 25%?

Well, you can make your own mind up here, but fro my viewpoint it looks like crap at anything other than exactly 0.25. You might be able to go down to 0.22 or up to 0.27 or 0.28 and have it look OK, but 0.25 is perfect.

How many iterations should you use in the smooth function?

Basically, as many as it takes to look good. That’s going to vary by the size of your curve. In this small demo, 4 iterations seems pretty close to perfect. If you were to double the size of this, you’d start to see some chunkiness at 4, which goes away when you use 5 iterations. Anything beyond that looks the same. I’m pretty sure that for larger and larger curves, you’d have to increase the number of iterations slightly. But don’t overdo it. If you see some slight chunkiness at a certain level, there’s a good chance that just doing one more iteration will take care of it. The number of points and segments increases geometrically as you do more iterations, so don’t go overboard.

Closing the Loop

The last trick up my sleeve is making this a closed loop. In other words, making a smooth path from the last point back through the first.

To do this, we want to avoid doing that fix we did in the last step where we saved the first and last points. Instead, we want to run the Chaikin algorithm on the last point and the first point to give us two more points in between them, just like we did for every other pair of points. In this final bit of code, I added a parameter to both the smooth and chaikin functions that controls this behavior.

function smooth(points, closed, iter) {
  for (let i = 0; i < iter; i++) {
    points = chaikin(points, closed);
  }
  return points;
}

function chaikin(points, closed) {
  const first = points[0];
  const last = points[points.length - 1];

  const path = [];
  if (!closed) {
    path.push(first)
  }
  for (let i = 0; i < points.length - 1; i++) {
    const p0 = points[i];
    const p1 = points[i + 1];
    const dx = p1.x - p0.x;
    const dy = p1.y - p0.y;
    path.push({
      x: p0.x + dx * 0.25,
      y: p0.y + dy * 0.25,
    });
    path.push({
      x: p0.x + dx * 0.75,
      y: p0.y + dy * 0.75,
    });
  }
  if (!closed) {
    path.push(last)
  } else {
    const dx = first.x - last.x;
    const dy = first.y - last.y;
    path.push({
      x: last.x + dx * 0.25,
      y: last.y + dy * 0.25,
    });
    path.push({
      x: last.x + dx * 0.75,
      y: last.y + dy * 0.75,
    });
  }

  return path;
}

You can see I’m using conditional statements on the closed var to determine whether or not first and last get added to the new path. If we are closing the loop, lines 33-42 take care of adding those two new points.

And here’s the final demo. Note that I removed the percentage slider and hardcoded the percentages in the code.

After rearranging the spaghetti, toggle the closed state off and on and see how it fills in a curve between points 7 and 0.

Summary

As I mentioned, I’ve been using my own piecewise Bezier curve function for years now and have it in the libraries I’ve created across multiple languages. The final question for me is, whether to switch it over to use Chaikin, or continue using what I have.

I think in the end, I’m going to keep using my existing method. My reasoning.

I’ve done plenty of tests using both methods simultaneously and verified that they draw exactly the same curves.
While my original method is a bit more to get your head around conceptually (maybe?), it’s already written and has worked perfectly with no need of any changes for years. So there’s no brain drain in continuing to use it.
I haven’t done any measurements, but I’m fairly certain my original method is more performant. It always just does a single loop through the list – O(n) – and for a list of length n it just needs to create n-1 new mid points. Then it uses the built-in quadratic curve function to connect everything. Whereas the Chaikin method with five iterations creates n*2-2 points per iteration, compounding each time. That’s a lot of new points and line segments. ~~And it will run in O(n*m) time – where n is the number of points and m is the number of iterations. (Hopefully I got all that right.)~~ I’m pretty sure that’s not right, because n is going to increase on each iteration, so it’s worse then O(n*m).
Finally, the need to specify how many times you want to iterate is a big minus for me. My original method will draw a perfectly smooth curve no matter the size of the drawing. With Chaikin, you need to specify the iterations. You could hard code it, but then you’re either doing too much work, or if you wind up drawing something really big, it’s not enough.