preface

Bezier curve is a very important parametric curve in Computer Graphics. It plays an important role in front end fields, especially in visualization projects. For example:

  1. Cubic – Bezier easing function is used in CSS animation
  2. Use bezier curve to fit the points in the line chart to make the line chart look smoother and more beautiful.
  3. The pen tool

Today we will start from the definition of Bezier curve, and then to the application of Bezier curve, to introduce you in depth what bezier curve is.

The definition of Bessel curves

Recursive definition

First bezier curve

Let’s first look at the Bezier curve:

In the figure, the yellow ball’s trajectory is the Bezier curve.

From the figure above, we can see that a bezier curve has two control points. Let the position of the yellow ball be determined by a parameter t∈[0,1]t\in[0,1]t∈[0,1].

So:


P = ( 1 – t ) P 1 + t P 2 P = (1-t)P_1 + tP_2

or


P = P 1 + t ( P 2 – P 1 ) P = P_1 + t(P_2 – P_1)

And we can see that this is a formula for linear interpolation.

Quadratic Bezier curve

So let’s look at the quadratic Bezier curve again:

From the figure above, we can see that the quadratic Bezier curve has three control points. The trajectories of the green dots in the figure are quadratic Bessel curves. The steps to generate the motion trajectory are as follows:

  1. Connect the three control points in turn, resulting in two straight lines (the two gray lines in the figure above)
  2. According to the current parameter T, determine the position of the two new points in the above two lines obtained by linear interpolation (the two orange points in the figure above).
  3. Connect the above two points and obtain the last point by linear interpolation according to the parameter T again.
  4. This last point is called a Bessel curve

At this point, I believe the reader has a general understanding of the Bezier curve, so let’s look at the bezier curve three times

Cubic Bezier curve

Similar to the quadratic bezier curve, we can also recurse to obtain new points by continuous linear interpolation according to the current parameter t∈[0,1]t\in[0,1]t∈[0,1], and finally obtain the motion trajectory of a point as a bezier curve.

The mathematical expression of Bessel curve

Above, we have given the mathematical expression of a Bezier curve (linear interpolation) : P=(1−t)P1+tP2P =(1-t)P_1 + tP_2P=(1−t)P1+tP2.

So what about the mathematical expressions for quadratic bezier curves, cubic bezier curves, or even n-th Bezier curves?

Derivation of mathematical expression of quadratic Bessel curve

From the figure above, the position of P is the final position we want to find. Point the PPP is by P1 ‘, P2 ‘P_1, P_2’ ‘P1, P2’ and parameter t ∈ \ [0, 1] t in [0, 1] t ∈ joint decision [0, 1]. So:


P = ( 1 – t ) P 1 ‘ + t P 2 ‘ (a) P = (1-t)P_1′ + tP_2′ \tag{a}

‘P1, P2’ P_1, P_2 ‘ ‘P1, P2’ is by P1, P2, P3P_1, P_2, P_3P1, P2, P3 decisions, so there is:


P 1 ‘ = ( 1 – t ) P 1 + t P 2 (b) P_1′ = (1-t)P_1 + tP_2 \tag{b}

P 2 ‘ = ( 1 – t ) P 2 + t P 3 (c) P_2′ = (1-t)P_2 + tP_3 \tag{c}

Let’s substitute b and c into a. You can get:


P = ( 1 – t ) 2 P 1 + 2 ( 1 – t ) t P 2 + t 2 P 3 (d) P = (1-t)^2P_1 + 2(1-t)tP_2 + t^2P_3 \tag{d}

Formula D is the mathematical expression of quadratic Bessel curve.

The mathematical expression of Bessel curves of any degree

Similar to the derivation process of quadratic Bessel curve, we can also derive the mathematical expressions of cubic Bessel curve and quartic Bessel curve. We write the expressions of one-time Bessel curve and quartic Bessel curve together. Let’s observe the relation between their coefficients.

First bezier curve:


P = ( 1 – t ) P 1 + t P 2 P = (1-t)P_1 + tP_2

Quadratic Bezier curve:


P = ( 1 – t ) 2 P 1 + 2 ( 1 – t ) t P 2 + t 2 P 3 P = (1-t)^2P_1 + 2(1-t)tP_2 + t^2P_3

Cubic Bezier curve:


P = ( 1 – t ) 3 P 1 + 3 ( 1 – t ) 2 t P 2 + 3 ( 1 – t ) t 2 P 3 + t 3 P 4 P = (1-t)^3P_1 +3(1-t)^2tP_2 + 3(1-t)t^2P_3 + t^3P_4

Fourth bezier curve:


P = ( 1 – t ) 4 P 1 + 4 ( 1 – t ) 3 t P 2 + 6 ( 1 – t ) 2 t 2 P 3 + 4 ( 1 – t ) t 3 P 4 + t 4 P 5 P = (1-t)^4P_1 +4(1-t)^3tP_2 + 6(1-t)^2t^2P_3 + 4(1-t)t^3P_4 + t^4P_5

Tips: Line up their coefficients and look at them. Think about it for a while

Careful readers should also see the pattern, we write their coefficients in turn:

Is this triangle familiar? This is the famous Yanghui triangle!

Yang Hui trigonometry, a geometric arrangement of binomial coefficients in a triangle, appeared in a detailed Explanation of the Algorithm in Nine Chapters written by Yang Hui, a mathematician of the Southern Song Dynasty in 1261. In Europe, PASCAL (1623—-1662) discovered this pattern in 1654, so the table is also known as PASCAL’s triangle. PASCAL’s discovery was 393 years later than Yang Hui’s and 600 years later than Jia Xian’s

Yang Hui’s triangle has an important property: the MTH number of the NTH row can be expressed as:


C n – 1 m – 1 = ( n – 1 ) ! ( m – 1 ) ! C_{n-1}^{m-1} = \frac{(n-1)! }{(m-1)! }

That’s the number of combinations of m minus 1 elements from n minus 1 different elements.

So, now that we have the distribution of their coefficients, we can easily write the mathematical expression of the n-subbessel curve:


P = ∑ i = 0 n C n i ( 1 – t ) n – i t i P i P = \sum_{i=0}^{n}C_n^i(1-t)^{n-i}t^iP_i

This is the introduction of the definition of Bessel curve, and we will start from some practical application problems, hoping that the reader will have a deeper understanding of the Bessel curve.

Application of Bessel curves

A, CSS animation in the easing function

Bezier curves are often used as a relaxation function when creating some animations or transition effects in web pages. For example:

.transition {
    transition: left 2s cubic-bezier(0.5.0.15.0.5.0.9); }Copy the code

So here’s a classic example of using Bessel curves as easing functions. The function of the easing function is to map a linearly changing parameter T to another value t’ through a series of operations. For example, the value of 0.5 mapped by the above easing function is 0.51875

You can check out the Besser curve formed by these parameters in Cubic-bezier.com/.

The four numbers we filled in cubic- Bezier are the x and y coordinates of points P2 and P3 in the figure above. P2 = (0.5, 0.15) P3 = (0.5, 0.9).

Let’s illustrate this with an animation where an element moves from left=0 to left=200 in 2s using the above easing function. The specific calculation process is as follows:

For the evaluation of the easing function in the figure above, we calculate progress by time lost/total time, where progress represents the value of x in the Bezier curve.

Since we don’t have a mapping between x and y, how do we compute the y value of the Bessel curve, based on the value of x?

Fortunately, we have the parametric equation of the Bessel curve, we have the function P(t)=xP(t) =xP(t) =x, and if we can compute t from x, then we can substitute t into the parametric equation to get the value of y.

So, now the question becomes: How do we solve the equation P(t)=xP(t) =xP(t) =x?

First let’s consider a problem like this: Leetcode-367. Valid Perfect squares

Given a positive integer num, write a function that returns true if num is a perfect square, and false otherwise.

In simple terms, how do I square a number without using math. SQRT?

Here is a very practical method of solving equations through iteration: Newton’s method.

Newton’s method

Newton’s method is a method of solving the roots of an equation using the idea of approximation. If we want to solve for x2=4x^2 = 4×2=4, we need to solve for the root of the equation x2−4=0x^ 2-4 = 0x2−4=0, that is, to find the intersection point of the graph of the function and the X-axis.

The solution process is roughly as follows:

  1. Select an initial value xnx_nxn
  2. In function image (xn, f (xn)) (x_n, f (x_n) (xn, f (xn)) as a function of the tangent and the tangent with the x axis intersection with xn x_ + 1 + 1} {n xn + 1 point
  3. Judge whether the difference between the values of f(xn+1)f(x_{n+1})f(xn+1) and f(xn)f(X_n)f(xn) f(xn+1) is less than a certain precision (the precision value is set by itself). If the precision is reached, the iteration is terminated; otherwise, step 2 is repeated.

F (xn+1)f(x_{n+1})f(xn+1)


x n + 1 = x n – f ( x n ) f ‘ ( x n ) x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)}

So that’s Newton’s method.

With an equation solving tool like Newton’s method, we can now solve the above problem: solving the equation P(t)=xP(t) =xP(t) =x is equivalent to solving the equation P(t)−x=0P(t) -x =0P(t) −x=0

We can write a function to implement this method:

function solveCurveX(x: number) {
    var t2 = x;
    var derivative;
    var x2;
    // 8 is the maximum number of Newtonian iterations, which can be set by itself to prevent the function from converging into an infinite loop
    for (let i = 0; i < 8; i++) {
        x2 = fn(t2) - x;
        if (Math.abs(x2) < ZERO_LIMIT) {
            return t2;
        }
        derivative = fnDerivativeX(t2);
        if (Math.abs(derivative) < ZERO_LIMIT) {
            break;
        }
        t2 -= x2 / derivative;
    }
    return t2;
Copy the code

Note that in the for loop section of the above code, the number of loops is set to 8. This is to set the maximum number of iterations, because Newton’s method does not apply to all equations. First, ensure that the equations have roots and are monotonous and convergent during the iteration interval. If the above conditions are not met, using Newton’s method will trap the program in an infinite loop.

Now we have obtained the t value corresponding to x by using the function solveCurveX, and then we can get the final y value by substituting the T value into the equation of the Bessel curve.

Second, bezier curve re-parameterization

Let’s move on to the second application scenario. Think about a problem like this: I define a path L using a Bessel curve, and now I want something to move uniformly along the path of a Bessel curve. How do I do that?

Some readers may have thought of one:

I can divide the parameter t∈[0,1]t\in[0,1]t∈[0,1] into equal parts, and then substitute it into the equation of the Bessel curve to get a set of coordinates, and then I set the coordinates I just calculated for the object.

Is this really okay? The answer is no. Let’s look at a Bezier curve that looks like this
t ∈ [ 0 . 1 ] T \ [0, 1] in With an average of 25 points, the 25 points on the curve are as follows:

As can be seen in the figure above, points are obviously more dense at the places where the curve is severely curved, whereas points are sparse at the places where the curve is not severely curved. This leads to a problem: where the curve is curved badly, the object moves slowly, and where the curve is not curved badly, the object moves fast. This is not the uniform motion we want to get.

What do we do if we want to get the effect of uniform motion? As the careful reader may have noticed, what we should do is not divide the parameter T evenly, but we should divide the Bezier curveThe total lengthIt’s only right to split it evenly. The effect of equalizing the length of the curve is as follows:

And then, we want to be able to find the corresponding parameter T for any length of the curve, and then substitute the inverse parameter T into the equation of the Bessel curve to get the final coordinates.

To summarize the general steps:

  1. So let’s figure out the total length of the curve
  2. The total length L of the curve is divided evenly
  3. Solve for the parameter T corresponding to any curve length L
  4. The final coordinates are obtained by substituting the parameter T into the Equation of the Bessel curve

Now solve the first problem: how to find the total length L of the curve.

The easiest way to do this is to divide a Bessel curve into lines and add up the lengths of those lines. But with the improvement of the precision of segmentation, the computation is also very large.

But it’s a good idea, and calculus is exactly that. So, can we use calculus to figure out the length of the curve? The answer is yes.

We’re approximating the curve by a little line, which we call DSDSDS. So the whole length of the curve is going to be the integral over the whole curve. As follows:


S = ∫ L d s S = \int_{L}ds

For DSDSDS, dx2+dy2\ SQRT {dx^2 +dy ^2}dx2+dy2. Since we are using parametric equations, by


d x d t = ϕ ‘ ( t )     d x = ϕ ‘ ( t ) d t \frac{dx}{dt} = \phi'(t) \\\ \\\ dx = \phi'(t)dt

d y d t = Bits of ‘ ( t )     d y = Bits of ‘ ( t ) d t \frac{dy}{dt} = \psi'(t) \\\ \\\ dy = \psi'(t)dt

You can get


d s = d x 2 + d y 2 = ϕ ‘ 2 ( t ) + Bits of ‘ 2 ( t ) d t ds = \sqrt{dx^2 + dy^2} = \sqrt{\phi’^2(t) + \psi’^2(t)}dt

Since ϕ(t)\phi(t)ϕ(t) is the same as a function of ψ(t)\psi(t)ψ(t), and it represents the distance between two points. so


ϕ ‘ 2 ( t ) + Bits of ‘ 2 ( t ) d t = ∣ ∣ P ‘ ( t ) ∣ ∣ \sqrt{\phi’^2(t) + \psi’^2(t)}dt = ||P'(t)||

The total length of the curve is 0


S = ∫ 0 1 ∣ ∣ P ‘ ( t ) ∣ ∣ d t S = \int_0^1||P'(t)||dt

For any parameter t∈[0,1]t\in[0,1]t∈[0,1] the corresponding curve length is:


L ( t ) = ∫ 0 t ∣ ∣ P ‘ ( x ) ∣ ∣ d x L(t) = \int_0^t||P'(x)||dx

Now another problem arises, now that we have an expression for how to compute the length of the curve, but how do we compute the integral?

The gauss-Lengendre quadrquadration method, a fast method for calculating a double integral, is introduced here

Gauss-lengendre quadrature

The specific principle is not introduced, simply speaking, is to look up the table. I can only say that Gauss is a god.

The formula is as follows:


∫ a b f ( x ) d x = b – a 2 ∑ i = 1 n w i f ( b – a 2 x i + b + a 2 ) \int _ { a } ^ { b } f ( x ) dx = \frac{b – a}{2} \sum_{i=1}^{n}w_i f(\frac{b-a}{2}x_i + \frac{b + a}{2})

So now we can figure out the total length of the Bessel curve and the length at any t in terms of the path integral of the Bessel curve and the Gauss-Ludgend product. And then the question is, how do I find the corresponding t for any length L?

Doesn’t the question seem too familiar? That’s right, just using Newton’s method.


t = a – L ( a ) L ‘ ( a ) t = a – \frac{L(a)}{L'(a)}

Among them


L ‘ ( a ) = ∣ ∣ P ‘ ( a ) ∣ ∣ L'(a) = ||P'(a)||

But Newton’s method is not universal, there are not unique solutions for higher order equations, for example, for a cubic equation here, there may be one solution, two solutions, three solutions. The root that we use Newton’s method to solve for may not be the root that we want. Therefore, the following situation may occur when the bezier curve is re-parameterized by the above method:

As shown in the figure above, the blue point in the figure is the point corresponding to the corresponding T value obtained by Newton’s method after evenly dividing the length of the curve. And we can see that this is obviously a problem, and the reason for that is because the equation has multiple roots, and because of the problem of choosing an initial value, we didn’t get the one root that we wanted. As shown in the figure below:

As shown in the figure above, due to the problem of selecting the initial point, some points in the middle state “jump” occurred in the iteration process, so as to find the more distant root, but this is not what we want. So how do you avoid this? Here we take the next best thing and use dichotomy to find the root.

Find the root by dichotomy

The dichotomy always finds the root closest to the initial value, so there is no “jump” like Newton’s method. However, dichotomy is not as efficient as Newton’s method. Dichotomy as a classical algorithm, here is not much to describe.

After we use dichotomy to solve the equation, we can get the correct effect, as shown in the figure below:

Now we have completed the re-parameterization of the Bessel curve.

Let’s move on to the next application scenario:

Three, Bezier curve segmentation

Those of you who have used the Pen tool in Photoshop should know that you can insert control points into an existing path at will. This is the process of dividing a Bezier curve, where you divide a Bezier curve in two, and you make sure that the connection between the two curves is smooth and continuous. So where should the control points of the two bezier curves be?

As shown in the figure above, points A, B, C and D are the Bezier curve formed by the control points. Now we need to divide this curve at point E. Then what are the control points of the two divided curves respectively?

Looking at the figure above, my intuition tells me that the control points of the Bezier curve on the left look like A, F, I, E, and the control points of the Bezier curve on the right look like E, J, H, D. So, is that really the case?

Suppose that A, F, I and E are the control points of the segmtioned left Bezier curve.

According to the definition of Bessel curve, the formula of Bessel curve composed of A, B, C and D can be written as:


E = ( 1 – t ) 3 A + 3 ( 1 – t ) 2 t B + 3 ( 1 – t ) t 2 C + t 3 D t ∈ [ 0 . 1 ] E = (1 – t) ^ 3 + 3) (1 – t ^ 2 TB + 3 (1 – t) t ^ 2 c + t ^ 3 d t \ \ quad in [0, 1]

Then the Bezier curves A, F, I and E on the left can be expressed as:


E l = ( 1 – e ) 3 A + 3 ( 1 – e ) 2 t F + 3 ( 1 – e ) e 2 I + e 3 E e ∈ [ 0 . 1 ] (a) E_l = (1 -) e ^ 3 a + 3 (1 – e) ^ 2 + 3 tf (1 -) e e ^ 2 ^ 3 + e I e \ quad e \ \ [0, 1] in the tag {a}

In the above formula, F and I can be written as:


F = ( 1 – t ) A + t B (b) F = (1 – t)A+ tB \tag{b}

I = ( 1 – t ) F + t G = ( 1 – t ) 2 A + 2 ( 1 – t ) t B + t 2 C (c) I= (1 – t)F+ tG = (1-t)^2A+2(1-t)tB+t^2C \tag{c}

By substituting Equations (b) and (c) into equation (a), we can get:


E l = ( 1 – e t ) 3 A + 3 ( 1 – e t ) 2 t B + 3 ( 1 – e t ) ( e t ) 2 C + ( e t ) 3 D e ∈ [ 0 . 1 ] . e t ∈ [ 0 . t ] E_l = (1 – et) ^ 3 a + 3 (1 – et) ^ 2 TB + 3 (1 – et) (et) ^ 2 c + (et) ^ 3 d \ \ quad e in [0, 1], et \ [0, t] in

If u=etu =etu =et, u∈[0,t]u\in[0,t]u∈[0,t]


E l = ( 1 – u ) 3 A + 3 ( 1 – u ) 2 t B + 3 ( 1 – u ) u 2 C + u 3 D u ∈ [ 0 . t ] (d) E_l = (1-u)^3A + 3(1-u)^2tB + 3(1-u)u^2C + u^3D\quad u\in[0,t] \tag{d}

We can see that equation (a) and Equation (d) have exactly the same functional equation, and the domain of definition is also exactly the same. That is, A, F, I, E are the control points of the left Bezier curve after division. Similarly, for the right bezier curve, we can also prove that E, J, H, D are the new control points of the right Bezier curve.

Next, let’s move on to the final application scenario: fitting a series of points using a Bezier curve.

Four, Bezier curve fitting broken line

Drawing line charts is a very common requirement. We can use Canvas or SVG to draw line charts. We can simply put all the points end to end, but such a line chart is too hard. The diagram below:

If you’ve used a chart library like Echarts, you’ll see a line chart that looks like this:

It looks a lot softer. The technique behind this is Bessel curves. It replaces a straight line with a Bezier curve to create a smooth transition at the corners.

As shown in the figure above, we need to fit the broken lines A, B, I and J. Here’s a simple formula:


P i l = P i – ( P i + 1 – P i – 1 ) e   P i r = P i + ( P i – 1 – P i + 1 ) e P_{il} = P_i – (P_{i+1} – P_{i-1})e \\\ P_{ir} = P_i + (P_{i-1} – P_{i+1})e

Where, e is the parameter used to control the smoothness of the curve, e∈[0,1]e\in[0,1]e∈[0,1]

For starting points are: Pi + 1 = PiP_ = P_ {I + 1} {I} Pi + 1 = Pi, end points are: Pi – 1 = PiP_ {1} I – = P_ {I} – 1 = Pi Pi

According to the above formula, we achieved the following effects:

As you can see, the overall effect is very good.

These are all examples of Bessel curves used in this article.

conclusion

To summarize, this article mainly describes the following aspects:

  1. Introduces the definition of Bessel curve (recursive definition and mathematical definition)
  2. In the mathematical definition, the distribution law of various coefficients in the analytic formula of Bessel curve (Yang Hui triangle, binomial distribution, combination number) is revealed.
  3. This paper introduces the calculation logic behind the use of Bessel curve as easing function in CSS
  4. How to re-parameterize Bessel curves
  5. Introduces Newton’s method of solving equations and some of its problems (using dichotomy to avoid, but the operation speed will be reduced)
  6. How to use bezier curves to make line charts more rounded

I hope that readers will have a deeper understanding of the Bezier curve through reading this article, and you can self-implement by coding some of the algorithms mentioned in this article, which will greatly improve your coding ability and mathematical ability.

If you found this article useful, please like 👍