Bezier and Picasso curves

Pablo Picasso in his studio on the background of the painting "Kitchen", a photograph of Herbert Liszt.

Artist and simplicity

One of my favorite works of Pablo Picasso - this is his linear drawings. He painted animals on some of them: an owl, a camel, a butterfly, etc. This work entitled “The Dog” hangs on my wall:

(You can go to an interactive demo in which we recreated “The Dog” using the mathematical calculations presented in the article)
')
These drawings are extremely simple, but somehow they manage to deeply touch the viewer. They create the impression of simplicity of composition and implementation. One hand movement and signature create a true masterpiece! The drawing at the same time seems to be both a careless improvisation and a carefully selected overture in a symphony of grace. In fact, we know that Picasso’s work process was deep. For example, in the years 1945-1946, Picasso created a series of eleven drawings (lithographs, to be more precise), demonstrating his gradual progress in visualizing the bull. The first ones were more or less similar to realistic ones, but later we see how the bull turns into its very essence, and the last figure consists of only a dozen lines. In the process of developing a series of drawings, we see a bull resembling some of Picasso's other works (number 9 reminds me of a sculpture in the Chicago-based Daley Center Plaza ). Here you can read more about the series of lithographs.

"Bull" Picasso. Photo taken by Jeremy Kuhn at the Art Institute of Chicago. Click on image to enlarge it.

I will not pretend to be an experienced artist (I could not draw a bull, even if my life depended on it), but I can recognize the mathematical aspects of his paintings and write a damn good program. There is one obvious way to consider linear Picasso-style drawings as mathematical objects, and these are of course Bezier curves. Let's start by studying the theory of Bezier curves, and then we write a program to draw them. The mathematics used in it does not require any additional knowledge, except for the fundamentals of algebra and polynomials, and I will try to go into complex details as little as possible. We will study a very simple algorithm for drawing Bezier curves, implement it in Javascript, and then recreate one of Picasso’s linear drawings using several Bezier curves.

Bezier curves and parameterization

When someone asks to recall the “curves,” most people (perhaps poisoned by teaching the basics of mathematics) either start shaking with fear, or draw part of the graph of a polynomial. Although it is quite correct and respected curves, but they represent only a small part of the world of curves. We are especially interested in curves that are not part of the function graphs.

Three patterns.

For example, a piece is a physical pattern used to (manually) draw smooth curves. Just connecting the edges of any part of these curves, we usually can not get a graph of the function. Obviously, we need a more general idea of what curves are. The problem is that in different areas of mathematics under the "curve" refers to different concepts. The curves that we will study, called "Bezier curves", are a special case of one-parameter polynomial plane curves . It sounds too complicated, but in fact it means that the whole curve can be set by two polynomials: one for values

x

$x$ and second for values

y

$y$ . Both polynomials have one variable, which we call

t

$t$ (

t

$t$ defined on the set of real numbers).

The example should be clearer. Let's pick up two simple polynomials from

t

$t$ let's say

x (t) = t^{2}

$x (t) = t ^ 2$ and

y (t) = t^{3}

$y (t) = t ^ 3$ . If we want to find points on this curve, we simply select values.

t

$t$ and substitute them into both equations. For example, substituting

t = 2

$t = 2$ we will get a point

(4, 8)

$(4, 8)$ on the curve. Placing all such values on the graph, we get a curve that is definitely not a graph of the function:

But it is obvious that we can write any function with one variable.

f (x)

$f (x)$ in this parametric form: just choose

x (t) = t

$x (t) = t$ and

y (t) = f (t)

$y (t) = f (t)$ . So, they are actually more general objects than ordinary functions (however, in this article we will work only with polynomials).

Briefly repeat: a polynomial flat curve with one parameter is defined as a pair of polynomials

x (t), y (t)

$x (t), y (t)$ from one variable

t

$t$ . Sometimes, when we need to express the whole system with a single equation, we can take the coefficients of general degrees

t

$t$ and write them as vectors

x

$x$ and

y

$y$ . Thanks to the above example

x (t) = t^{2}, y (t) = t^{3}

$x (t) = t ^ 2, y (t) = t ^ 3$ we can rewrite it as

m a t h b f f (t) = (0, 1) t^{3} + (1, 0) t^{2}

$\ mathbf {f} (t) = (0,1) t ^ 3 + (1,0) t ^ 2$ .

Here, the coefficients are points on a plane (the same as the vectors), and we select the function

f

$f$ bold to emphasize that the output is a period. Learners of linear algebra can understand that pairs of polynomials form a linear space, and combine them as

(0, t^{3}) + (t^{2}, 0) = (t^{2}, t^{3})

$(0, t ^ 3) + (t ^ 2, 0) = (t ^ 2, t ^ 3)$ . But it will be more convenient for us to take points as coefficients of one polynomial.

We will also limit our attention to considering one-parameter flat curves described by a polynomial for which the variable

t

$t$ allowed on the interval from zero to one. This restriction may seem strange, but in fact, any finite one-parameter flat curve described by a polynomial can be written this way (we will not go into details of how this is implemented). For the sake of brevity, hereinafter, I will call a one-parameter flat curve defined by a polynomial in which

t

$t$ is in the range from zero to one, just “curve”.

With these curves, we can do very interesting things. For example, for any two points in the plane

P = (p_{1}, p_{2}), Q = (q_{1}, q_{2})

$P = (p_1, p_2), Q = (q_1, q_2)$ we can describe the line between them as a curve:

m a t h b f L (t) = (1 - t) P + t Q

$\ mathbf {L} (t) = (1-t) P + tQ$ . And in fact, with

t = 0

$t = 0$ value

m a t h b f L (t)

$\ mathbf {L} (t)$ exactly equal

P

$P$ at

t = 1

$t = 1$ exactly equal

Q

$Q$ , and the equation is a linear polynomial with

t

$t$ . Moreover (if you do not go into the details of the analysis), the line

m a t h b f L

$\ mathbf {L}$ passes with "unit speed" from

P

$P$ before

Q

$Q$ . In other words, we can perceive

m a t h b f L

$\ mathbf {L}$ as describing the movement of a particle from

Q

$Q$ on time and during

1 / 4

$1/4$ the particle will travel by a quarter, and during

1 / 2

$1/2$ half way through, etc. (An example of a straight line that does not have a unit speed is, for example

(1 - t^{2}) P + t^{2} Q

$(1-t ^ 2) P + t ^ 2 Q$ .)

For a more general case, let's add a third point.

R

$R$ . We can describe the path going through

P

$P$ at

R

$R$ and he is “headed” by a dot

Q

$Q$ lying in the middle. This idea of a “guiding” point is a bit abstract, but in terms of computation it is not more complex. Instead of moving from one point to another at a constant speed, we want to move from one line to another at a constant speed. That is, we can name two curves that describe straight lines from

P t o Q

$P \ to Q$ and

Q t o R

$Q \ to R$ curves

m a t h b f L_{1}

$\ mathbf {L} _1$ and

m a t h b f L_{2}

$\ mathbf {L_2}$ . Then the curve, "directed" by the point

Q

$Q$ can be written as a curve

d i s p l a y s t y l e m a t h b f F (t) = (1 - t) m a t h b f L_{1} (t) + t m a t h b f L_{2} (t)

$\ displaystyle \ mathbf {F} (t) = (1-t) \ mathbf {L} _1 (t) + t \ mathbf {L} _2 (t)$

By completing all these multiplications, we get the formula

d i s p l a y s t y l e m a t h b f F (t) = (1 - t)^{2} P + 2 t (1 - t) Q + t^{2} R

$\ displaystyle \ mathbf {F} (t) = (1-t) ^ 2 P + 2t (1-t) Q + t ^ 2 R$

Over time dot

m a t h b f F (t)

$\ mathbf {F} (t)$ moves along a straight line between points

m a t h b f L_{1} (t)

$\ mathbf {L} _1 (t)$ and

m a t h b f L_{2} (t)

$\ mathbf {L} _2 (t)$ that are also moving. So we get a curve that looks like this.

This screenshot is taken from the amazing demo of data visualization consultant Jason Davis. He perfectly demonstrates a mathematical idea. In the demo, you can drag all three points to see how this affects the final curve. It is worth playing with her at least five minutes.

The whole idea of Bezier curves is to summarize this principle: having a list of points

P_{0}, d o t s, P_{n}

$P_0, \ dots, P_n$ on the plane, we want to describe a curve that runs from the first to the last point, and “goes” between the other points. The Bezier curve is the implementation of such a curve (one-parameter flat curve defined by a polynomial), which becomes an inductive continuation of the above: we move with unit velocity from the Bezier curve given by the first

n - 1

$n-1$ points of the list to the curve given by the last

n - 1

$n-1$ points. In the simplest case, this is a straight line segment (or a single point, if you like). From a formal point of view,

Definition: for a given set of points in the plane

P_{0}, d o t s, P_{n}

$P_0, \ dots, P_n$ we recursively define the degree bezier curve

n - 1

$n-1$ as

\ begin {aligned} \ mathbf {B} _ {P_0} (t) & = P_0 \\ \ mathbf {B} _ {P_0 P_1 \ dots P_n} (t) & = (1-t) \ mathbf {B } _ {P_0 P_1 \ dots P_ {n-1}} + t \ mathbf {B} _ {P_1P_2 \ dots P_n} (t) \ end {aligned}

$\ begin {aligned} \ mathbf {B} _ {P_0} (t) & = P_0 \\ \ mathbf {B} _ {P_0 P_1 \ dots P_n} (t) & = (1-t) \ mathbf {B } _ {P_0 P_1 \ dots P_ {n-1}} + t \ mathbf {B} _ {P_1P_2 \ dots P_n} (t) \ end {aligned}$

We will call

P_{0}, d o t s, P_{n}

$P_0, \ dots, P_n$ control points

m a t h b f B

$\ mathbf {B}$ .

Although the concept of moving at a unit rate between two lower-order Bezier curves is the real essence of the matter (and allows us to approach the solution from a computational point of view), you can simply multiply all this (using the formula of binomial coefficients) and get the formula explicitly. She will be next:

d i s p l a y s t y l e m a t h b f B_{P_{0} d o t s P_{n}} = s u m_{k = 0}^{n} b i n o m n k (1 - t)^{n - k} t^{k} P_{k}

$\ displaystyle \ mathbf {B} _ {P_0 \ dots P_n} = \ sum_ {k = 0} ^ n \ binom {n} {k} (1-t) ^ {n-k} t ^ k P_k$

For example, a cubic Bezier curve with control points

P_{0}, P_{1}, P_{2}, P_{3}

$P_0, P_1, P_2, P_3$ will have an equation

d i s p l a y s t y l e (1 - t)^{3} P_{0} + 3 (1 - t)^{2} t P_{1} + 3 (1 - t) t^{2} P_{2} + t^{3} P_{3}

$\ displaystyle (1-t) ^ 3 P_0 + 3 (1-t) ^ 2t P_1 + 3 (1-t) t ^ 2 P_2 + t ^ 3 P_3$

Higher order Bezier curves can be quite difficult to display geometrically. For example, the fifth degree Bezier curve (with six control points) is shown below.

Fifth degree Bezier curve, illustration from Wikipedia.

Drawn additional line segments demonstrate the recursive nature of the curve. The simplest ones are green dots moving between control points. Blue points move along straight line segments between green points, pink points move between blue points, orange points between pink points, and finally, a red point moves along a straight line segment between orange points.

Without the recursive structure of the problem (simply from observing the curve) it would be difficult to understand how all this can be calculated. But as we will see, the Bezier curve rendering algorithm is very natural.

Bezier curves as data and de castelgio algorithm

Let's derive and implement an algorithm for drawing a Bezier curve on the screen, taking advantage only of the ability to draw straight lines. For simplicity, we restrict ourselves to considering only third-degree Bezier curves (cubic). Indeed, any Bezier curve can be written by a recursive definition as a combination of cubic curves, and in practice cubic curves provide a balance between computational efficiency and expressiveness. All the code in this post is written in Javascript and posted on the page of this blog on Github .

So, the cubic Bezier curve is represented in the program by a list of four points. For example,

var curve = [[1,2], [5,5], [4,0], [9,3]];

In most graphic libraries (including the standard HTML5 canvas ), there is a graphic primitive capable of displaying Bezier curves based on a list of four points. But suppose we have no such function. Suppose we can only draw straight lines. How can we draw an approximation of a Bezier curve? If such an algorithm exists (and it exists, and we will be convinced of it), then we can create such an exact approximation that it will be visually indistinguishable from the true Bezier curve.

The most important property of Bezier curves, which will allow us to create such an algorithm, is as follows:

Any Cubic Bezier Curve

$\ mathbf {B}$ from beginning to end can be divided into two, which together will describe the same curve as

$\ mathbf {B}$ .

Let's see how to do it. Let be

m a t h b f B

$\ mathbf {B}$ will be a cubic Bezier curve with control points

P_{0}, P_{1}, P_{2}, P_{3}

$P_0, P_1, P_2, P_3$ and suppose that we want to divide it exactly in half. We note that the curve formula at the substitution

1 / 2

$1/2$ take the form

d i s p l a y s t y l e m a t h b f B (1 / 2) = f r a c 1 2^{3} (P_{0} + 3 P_{1} + 3 P_{2} + P_{3})

$\ displaystyle \ mathbf {B} (1/2) = \ frac {1} {2 ^ 3} (P_0 + 3P_1 + 3P_2 + P_3)$

Moreover, our recursive definition gives us a way to calculate a point on the basis of curves of a lesser degree. But when calculations are performed at 1/2, their formulas are simple enough to write. The image looks like this:

Green dots are curves of the first degree, pink dots are curves of the second degree, and the blue dot is a cubic curve. We note that since each of the curves is calculated at

t = 1 / 2

$t = 1/2$ , each of these points can be described as a midpoint of points already known to us. therefore

m_{0} = (P_{0} + P_{1}) / 2, q_{0} = (m_{0} + m_{1}) / 2

$m_0 = (P_0 + P_1) / 2, q_0 = (m_0 + m_1) / 2$ , etc.

In fact, the division into two curves we need is exactly given by these points. That is, half the curve is given

m a t h b f L (t)

$\ mathbf {L} (t)$ with control points

P_{0}, m_{0}, q_{0}, m a t h b f B (1 / 2)

$P_0, m_0, q_0, \ mathbf {B} (1/2)$ while the “right” half

m a t h b f R (t)

$\ mathbf {R} (t)$ has control points

m a t h b f B (1 / 2), q_{1}, m_{2}, P_{3}

$\ mathbf {B} (1/2), q_1, m_2, P_3$ .

How can we be sure that these are exactly the same Bezier curves? Well, it's just polynomials. We can test them for equality with intricate algebraic calculations. But it is worth noting that since

m a t h b f L (t)

$\ mathbf {L} (t)$ passes only halfway along

m a t h b f B (t)

$\ mathbf {B} (t)$ , then checking them for equality is similar to equating

m a t h b f L (t)

$\ mathbf {L} (t)$ with

m a t h b f B (t / 2)

$\ mathbf {B} (t / 2)$ , insofar as

t

$t$ varies from zero to one,

t / 2

$t / 2$ varies from zero to half. Similarly, we can compare

m a t h b f B ((t + 1) / 2)

$\ mathbf {B} ((t + 1) / 2)$ with

m a t h b f R (t)

$\ mathbf {R} (t)$ .

Algebraic calculations are very complicated, but quite feasible. To prove this, I cite a screencast of how I perform calculations that prove the identity of the two curves.

Now that we have checked everything, we have a good algorithm for dividing the cubic Bezier curve (or any Bezier curve) into two parts. In Javascript, it will look like this:

 function subdivide(curve) { var firstMidpoints = midpoints(curve); var secondMidpoints = midpoints(firstMidpoints); var thirdMidpoints = midpoints(secondMidpoints); return [[curve[0], firstMidpoints[0], secondMidpoints[0], thirdMidpoints[0]], [thirdMidpoints[0], secondMidpoints[1], firstMidpoints[2], curve[3]]]; }

Here, a curve is a list of four points, as described at the beginning of this section, and the output is a list of two curves with correct control points. The used midpoints function midpoints quite simple, and for completeness, we also add it here:

 function midpoints(pointList) { var midpoint = function(p, q) { return [(p[0] + q[0]) / 2.0, (p[1] + q[1]) / 2.0]; }; var midpointList = new Array(pointList.length - 1); for (var i = 0; i < midpointList.length; i++) { midpointList[i] = midpoint(pointList[i], pointList[i+1]); } return midpointList; }

It simply receives a list of points as input and calculates their successive middle points. That is a list of

n

$n$ points turns into a list of

n - 1

$n-1$ points. As we have seen, we need to call this function.

d - 1

$d-1$ to calculate the segmentation of a bezier curve

d

$d$ .

As I explained earlier, we can continue to subdivide our curve again and again, until each of the small parts becomes almost straight. That is, our function for drawing the Bezier curve will be as follows:

 function drawCurve(curve, context) { if (isFlat(curve)) { drawSegments(curve, context); } else { var pieces = subdivide(curve); drawCurve(pieces[0], context); drawCurve(pieces[1], context); } }

To put it in words, since our curve is not “flat”, we want to recursively subdivide and draw each part. If it is flat , then we can simply draw three line segments and it is logical to assume that this will be a good approximation. The context variable used here is the canvas on which drawing should be performed; it needs to be passed to the drawSegments function, which simply drawSegments straight line on the canvas.

Of course, this presents us with an obvious question: how can we determine that the Bezier curve is flat? There are many ways to do this. You can calculate deviation angles (from a straight line) at each internal control point and add them. Or you can calculate the volume of the quadrilateral formed. However, the calculation of angles and volumes is usually not so convenient: it takes a lot of time to calculate angles, the volumes have stability problems, and stable algorithms are not very simple. We need a measurement for which simple arithmetic is sufficient and, possibly, tests of several logical conditions.

It turns out that such a measurement exists. It was originally attributed to Roger Wilcox, but it is rather simply displayed manually.

In essence, we want to measure the “flatness” of a cubic Bezier curve by calculating the distance from a real curve during

t

$t$ to the point where the curve should be during

t

$t$ if it is straight.

Formally, having given

m a t h b f B (t)

$\ mathbf {B} (t)$ with control points

P_{0}, P_{1}, P_{2}, P_{3}

$P_0, P_1, P_2, P_3$ , we can define a rectilinear cubic Bezier curve as a colossal sum

d i s p l a y s t y l e m a t h b f S (t) = (1 - t)^{3} P_{0} + 3 (1 - t)^{2} t l e f t (f r a c 23 P_{0} + f r a c 13 P_{3} r i g h t) + 3 (1 - t) t^{2} l e f t (f r a c 13 P_{0} + f r a c 23 P_{3} r i g h t) + t^{3} P_{3}

$\ displaystyle \ mathbf {S} (t) = (1-t) ^ 3P_0 + 3 (1-t) ^ 2t \ left (\ frac {2} {3} P_0 + \ frac {1} {3} P_3 \ right) + 3 (1-t) t ^ 2 \ left (\ frac {1} {3} P_0 + \ frac {2} {3} P_3 \ right) + t ^ 3 P_3$

Nothing magical happens here. We just set a Bezier curve with control points.

P_{0}, f r a c 23 P_{0} + f r a c 13 P_{3}, f r a c 13 P_{0} + f r a c 23 P_{3}, P_{3}

$P_0, \ frac {2} {3} P_0 + \ frac {1} {3} P_3, \ frac {1} {3} P_0 + \ frac {2} {3} P_3, P_3$ . We need to perceive them as points that are on 0, 1/3, 2/3 and 1 fractions of the path from

P_{0}

$P_0$ before

P_{3}

$P_3$ on a straight line.

Now we will set the function

d (t) = l e f t | m a t h b f B (t) - m a t h b f S (t) r i g h t |

$d (t) = \ left \ | \ mathbf {B} (t) - \ mathbf {S} (t) \ right \ |$ which will be the distance between two curves at the same time

t

$t$ . Flatness value

m a t h b f B

$\ mathbf {B}$ - this is the maximum function

d

$d$ for all values

t

$t$ . If the flatness value is below a certain tolerance level, then we will consider the curve to be flat.

By adding a little algebra, we can simplify this expression. First, the value

t

$t$ , for which the distance is maximal, similar to the one with the maximum square, so we can avoid calculating the square root at the end and take this into account when choosing a flatness tolerance.

Now let's write the difference as one polynomial. First, we can get rid of threes in

m a t h b f S (t)

$\ mathbf {S} (t)$ and write a polynom like

d i s p l a y s t y l e m a t h b f S (t) = (1 - t)^{3} P_{0} + (1 - t)^{2} t (2 P_{0} + P_{3}) + (1 - t) t^{2} (P_{0} + 2 P_{3}) + t^{3} P_{3}

$\ displaystyle \ mathbf {S} (t) = (1-t) ^ 3 P_0 + (1-t) ^ 2t (2P_0 + P_3) + (1-t) t ^ 2 (P_0 + 2P_3) + t ^ 3 P_3$

and therefore

m a t h b f B (t) - m a t h b f S (t)

$\ mathbf {B} (t) - \ mathbf {S} (t)$ equals (when adding coefficients of similar members

(1 - t)^{i} t^{j}

$(1-t) ^ it ^ j$

d i s p l a y s t y l e (1 - t)^{2} t (3 P_{1} - 2 P_{0} - P_{3}) + (1 - t) t^{2} (3 P_{2} - P_{0} - 2 P_{3})

$\ displaystyle (1-t) ^ 2t (3 P_1 - 2P_0 - P_3) + (1-t) t ^ 2 (3P_2 - P_0 - 2P_3)$

Carry out the brackets

(1 - t) t

$(1-t) t$ from both members and denoting

a = 3 P_{1} - 2 P_{0} - P_{3}

$a = 3P_1 - 2P_0 - P_3$ ,

b = 3 P_{2} - P_{0} - 2 P_{3}

$b = 3P_2 - P_0 - 2P_3$ get

d i s p l a y s t y l e d^{2} (t) = l e f t | (1 - t) t ((1 - t) a + t b) r i g h t |^{2} = (1 - t)^{2} t^{2} l e f t | (1 - t) a + t b r i g h t |^{2}

$\ displaystyle d ^ 2 (t) = \ left \ | (1-t) t ((1-t) a + tb) \ right \ | ^ 2 = (1-t) ^ 2t ^ 2 \ left \ | (1-t) a + tb \ right \ | ^ 2$

Since the maximum of the product is the product of maxima, we can limit the above value to the product of two maxima. The reason for this is that we can simply calculate the two maxima separately. Calculate the maximum is easy and without separation, but with this method we will need fewer computation steps in the finished algorithm, and the visual result will be just as good.

Applying elementary calculations with a single variable, we obtain that the maximum value

(1 - t)^{2} t^{2}

$(1-t) ^ 2t ^ 2$ for

0 l e q t l e q 1

$0 \ leq t \ leq 1$ turns out to be equal

1 / 16

$1/16$ . And the norm of a vector is simply the sum of the squares of its components. If a

a = (a_{x}, a_{y})

$a = (a_x, a_y)$ and

b = (b_{x}, b_{y})

$b = (b_x, b_y)$ then the norm presented above is equal to

d i s p l a y s t y l e ((1 - t) a_{x} + t b_{x})^{2} + ((1 - t) a_{y} + t b_{y})^{2}

$\ displaystyle ((1-t) a_x + tb_x) ^ 2 + ((1-t) a_y + tb_y) ^ 2$

And note: for any real numbers

z, w

$z, w$ magnitude

(1 - t) z + t w

$(1-t) z + tw$ is exactly the straight line of

z

$z$ at

w

$w$ which is well known to us. Maximum for all

t

$t$ from zero to one will obviously be equal to the maximum of the end points

z, w

$z, w$ . So the maximum of our distance function

d^{2} (t)

$d ^ 2 (t)$ is limited

d i s p l a y s t y l e f r a c 116 (t e x t m a x (a_{x}^{2}, b_{x}^{2}) + t e x t m a x (a_{y}^{2}, b_{y}^{2}))

$\ displaystyle \ frac {1} {16} (\ text {max} (a_x ^ 2, b_x ^ 2) + \ text {max} (a_y ^ 2, b_y ^ 2))$

And so our flatness condition is that this restriction is less than a certain tolerance. We can safely factor 1/16 into this tolerance limit, and this will be enough to write the function.

 function isFlat(curve) { var tol = 10; // ,   50,    var ax = 3.0*curve[1][0] - 2.0*curve[0][0] - curve[3][0]; ax *= ax; var ay = 3.0*curve[1][1] - 2.0*curve[0][1] - curve[3][1]; ay *= ay; var bx = 3.0*curve[2][0] - curve[0][0] - 2.0*curve[3][0]; bx *= bx; var by = 3.0*curve[2][1] - curve[0][1] - 2.0*curve[3][1]; by *= by; return (Math.max(ax, bx) + Math.max(ay, by) <= tol); }

Here she is. We wrote a simple HTML page to access the canvas element and several auxiliary functions for drawing straight line segments when the curve is sufficiently flat, and presented the final result in this interactive demo (control points can be moved).

The image you see on this page (below) is my visualization of Picasso's “Dogs”, drawn as a sequence of Bezier curves. I think that the similarity is quite convincing.

Picasso's "dog", assembled from a sequence of nine Bezier curves.

Although the drawing itself was not invented by us (and therefore we cannot put our signature under it), we could represent it as a sequence of Bezier curves. One can only call them artwork. Here we have reduced the presentation to a single file: the first line is the size of the canvas, and each subsequent line represents a cubic Bezier curve. Comments added for better readability.

"Dog", Jeremy Kun, 2013.

Standardization seems to me important, so we will define a new file type ".bezier", which will have the format shown above:

 int int (int) curve (int) curve ...

Here, the first two integers determine the size of the canvas, the first (optional) integer in each line sets the width of the line , and the curve has the form

 [int,int] [int,int] ... [int,int]

If the int at the beginning of the line is missing, then the line is given a width of three pixels.

In general, the .bezier file can define a curve with an arbitrary number of control points, however, the code presented above does not draw them in general. As an exercise, try to write a program that receives a .bezier file as input, and creates an image of the image at the output. To do this, we need to expand the algorithm presented above so that it can draw arbitrary Bezier curves, cyclically performing calculations of midpoints and tracking those of them that turn out to be the final subdivision. Or, you can write a program that receives a .bezier file with only cubic Bezier curves, and an output SVG drawing file (SVG only supports cubic Bezier curves). That is, the .bezier file is a simplification (fewer features) and an extension (Bezier curves of arbitrary degree) to the SVG file.

We did not go as deeply into the theory of Bezier curves as we could. If you want to study the subject more deeply (and using mathematics), then see this long introductory course . It contains almost everything you need to know about Bezier curves, and also presents interactive demos written at Processing.

Art of low complexity

What we did with Picasso's The Dog has a certain philosophical meaning. Earlier in this blog we explored the idea of art of low complexity , and here it is fully applicable. The basic idea is that “beautiful” art has a description of a small length; if it is more formal, then the “complexity” of an object (presented in the text) is the length of the shortest program that yields this object in the absence of input data. Read more about this in our introduction to the Kolmogorov complexity . The fact that we can describe the linear drawings of Picasso by a small number of Bezier curves (and a relatively short program that gives Bezier curves at the output) should be a profound statement about the beauty of art itself. Obviously, this view is very subjective, but he has his supporters .

Today there is an interest in computer-generated art. For example, in these recent programming competitions (the article is in Dutch), participants were given the task to generate a drawing resembling the work of Pete Mondrian . The idea was that the more elegant the algorithm, the higher its rating would be. To generate the works of Mondrian, the winner used MD5 hashes, and there are many other impressive examples (the link above presents a gallery of finished works).

In the previous post on the art of low complexity, we explored the possibility of representing all images in a coordinate system in which circles with a shaded inner space are used. But it is obvious that in such a coordinate system it is impossible to imagine a “Dog” with very low complexity. Bezier curves appear to be much more natural coordinate systems. Small improvements, including the length of the lines and small distortions, do not affect the final complexity. A cubic Bezier curve can be described by any set of four points, and for more “entangled” descriptions (with increased complexity), more points are required. Bezier curves can be arbitrarily scaled, and this will not significantly change the complexity of the curve (although scaling by many orders of magnitude will add an increase in complexity with a logarithmic factor, it is quite small). Curves with a large width of lines are a bit more complicated than with a small width, and more numerous curves are needed to represent a variety of small sharp bends than for long and smooth arcs.

The disadvantage is the complexity of the representation in the form of a Bezier curve of a circle. In fact, this is definitely not possible . Despite the simplicity of this object (it is even defined as the only polynomial, albeit with two variables), the best thing to do with it is to approximate it. The same applies to ellipses. In fact, there are ways to circumvent this problem (the concept of rational Bezier curves , which are partial polynomials), but they add inherent complexity to the drawing algorithm, and approximations using ordinary Bezier curves look quite good.

So, we define the complexity of the picture as the number of bits in the form of a .bezier file (comments are not taken into account in the calculations).

The real reward that we are still exploring will be finding a way to automatically generate art. That is, the implementation of one of two possibilities:

Having set something like a random initial number (seed), write a program that creates a pseudo-random linear pattern.
After creating the drawing, create a .bezier image that accurately reproduces the drawing as a linear drawing.

We will try to explore these features in a subsequent post. This may require some local search algorithms, genetic algorithms or other methods.

Source: https://habr.com/ru/post/344814/

All Articles

Bezier and Picasso curves

Artist and simplicity

Bezier curves and parameterization

Bezier curves as data and de castelgio algorithm

Art of low complexity

More articles: