Chaikin’s Algorithm for Drawing Curves

Photo by Clark Van Der Beken on Unsplash

Whether you are a programmer who loves to generate art via code, or an artist who ventures into programming, you need to master some simple drawing algorithms.

Nowadays, we have several frameworks that help us to work with generative art in a simplified way. But if you, like me, prefer to create your own methods, you’ve probably already started studying some mathematical forms for drawing curves.

One of the most used forms today is the Bézier curve, as it takes into account two or three control points in addition to the main points and, through mathematical calculations, determines all the intermediate points of the curve.

This type of curve requires relatively simple mathematical calculation, but it can be a bit scary for those who don’t do well with parametric equations.

Figure 1 — Quadratic Bézier curve

But there are other interesting methods. I want to introduce you to an interesting approach which is a numerical method. Through a few iterations of a simple algorithm, it is possible to generate a simple, smooth curve.

George Chaikin

George Chaikin was Professor of Art and Mathematics at Lehman College of the City University of New York. More than a professor, he was a scientist and an artist and brought great contributions to Computer Graphics.

In 1974 he introduced an innovative method of refining curves by cutting the straight segments that make up the curve. After a while, this algorithm was dropped because more efficient ones appeared. However, due to its simplicity, it can be quickly implemented in systems that do not need a lot of computing power.

The Bézier curve, mentioned above, had already appeared in academia since the 1960s, but Chaikin decided to approach curve smoothing from a new perspective. Instead of using control points, he decided to work with cuts on the straight segments that make up a polygon.

The Algorithm

Chaikin’s algorithm is quite simple and produces an interesting result depending on the number of iterations we use.

STEP 1

To start, we draw a line that will represent a polygon (open or closed) that encapsulates our curve. In Figure 2, the four main points (P1 to P4) were traced.

Figure 2 — Polygon encapsulating the curve

STEP 2

Next, we must create new points on each line segment (formed by the points in sequence, taken two by two) so that they are 25% and 75% of the size of the segment. See in Figure 3 that all the points that meet this demand were drawn:

Figure 3 — control points

STEP 3

The next step of the algorithm is to connect the points so that the second point of a segment connects to the first control point of the next segment, as shown in Figure 4.

Figura 4 — Connection of control points

STEP 4

Now we can connect the dots to get an approximate curve. For convenience, we move the first control point to the position of the first point of the polygon and the last control point to the last point of the polygon, as shown in Figure 5.

Figura 5 — result of an iteration of the algorithm

And presto, this is the algorithm.

To make the curve smoother, just repeat the process recursively, considering the new generated segments as part of the initial polygon. See how the curve is already much smoother with two iterations of the algorithm. In Figure 6, we have the initial figure being the polygon in red (the result of the first iteration) and, in blue, the result of the second iteration.

Figura 6 — result of two iterations of the Chaikin algorithm

Testing

Want to test your drawing skills and see how the algorithm behaves with different input parameters? I made a specific playground for this:

https://pedrocacique.com/art/chaikin/

You can also clone this javascript project on GitHub:

https://github.com/phcacique/chaikin

Have fun!