$$ \newcommand{\dint}{\mathrm{d}} \newcommand{\vphi}{\boldsymbol{\phi}} \newcommand{\vpi}{\boldsymbol{\pi}} \newcommand{\vpsi}{\boldsymbol{\psi}} \newcommand{\vomg}{\boldsymbol{\omega}} \newcommand{\vsigma}{\boldsymbol{\sigma}} \newcommand{\vzeta}{\boldsymbol{\zeta}} \renewcommand{\vx}{\mathbf{x}} \renewcommand{\vy}{\mathbf{y}} \renewcommand{\vz}{\mathbf{z}} \renewcommand{\vh}{\mathbf{h}} \renewcommand{\b}{\mathbf} \renewcommand{\vec}{\mathrm{vec}} \newcommand{\vecemph}{\mathrm{vec}} \newcommand{\mvn}{\mathcal{MN}} \newcommand{\G}{\mathcal{G}} \newcommand{\M}{\mathcal{M}} \newcommand{\N}{\mathcal{N}} \newcommand{\S}{\mathcal{S}} \newcommand{\diag}[1]{\mathrm{diag}(#1)} \newcommand{\diagemph}[1]{\mathrm{diag}(#1)} \newcommand{\tr}[1]{\text{tr}(#1)} \renewcommand{\C}{\mathbb{C}} \renewcommand{\R}{\mathbb{R}} \renewcommand{\E}{\mathbb{E}} \newcommand{\D}{\mathcal{D}} \newcommand{\inner}[1]{\langle #1 \rangle} \newcommand{\innerbig}[1]{\left \langle #1 \right \rangle} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\two}{\mathrm{II}} \newcommand{\GL}{\mathrm{GL}} \newcommand{\Id}{\mathrm{Id}} \newcommand{\grad}[1]{\mathrm{grad} \, #1} \newcommand{\gradat}[2]{\mathrm{grad} \, #1 \, \vert_{#2}} \newcommand{\Hess}[1]{\mathrm{Hess} \, #1} \newcommand{\T}{\text{T}} \newcommand{\dim}[1]{\mathrm{dim} \, #1} \newcommand{\partder}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\rank}[1]{\mathrm{rank} \, #1} $$

Computer Aided Geometric Design
Bezier Curves

Introduction

Engineers of the automotive industry created the first geometric models in the 1960’s,and so initiated the domain of CAGD. Beginning in the 1960’s, engineers designing carbody parts started to use computers, an emerging technology, to represent the surfaces they were to produce. Parametric surfaces which had been long known and studied by mathematicians are well suited for representing these surfaces. Nevertheless finding appropriate numerical representations for these surfaces and tools adapted to manipulate them was a completely new task, and therefore developing these new representations was the first goal of the pioneers of the field. These new representations for surfaces, using intuitive numeric parameters to control their shape, quickly made their way to other manufacturers: from car bodies, to airplanes, to mechanical parts. The need for geometric modeling rapidly extended to other domains–to medicine, to architecture, and to geology– following the growing influence of computers. More recently, virtual worlds have also used geometric models, for the conception of physical shapes or simply for representing non physical objects. With the role of computers always increasing,the need for geometric models is growing too. The increase in computational power allows richer models to be developed, and users expect the manipulation tools and algorithms to be increasingly efficient and to offer more and more functionality. The ability to understand, construct and process three-dimensional geometric models on the computer is essential for many modern engineering fields, such as computer-aided design and manufacturing (CAD/CAM), engineering simulation, biomedical imaging, robotics, computer vision, and computer graphics. We focus here on CAGD techniques for modeling freeform curves and surfaces such as body shapes of ships, automobiles and aircrafts. Many consumer products as well as electronic devices are also designed with freeform aesthetic shapes. For this, we need to define the concept of Bezier Curves. Pierre Bezier was a French Arts & Métiers engineer (Pa27) who did his career at Renault.



Linear Bezier curve

Linear Bezier parametric curve is obtained by linear interpolation between two given control points $\textbf{P}_0$ and $\textbf{P}_1$ in the plane.

$$ \text{For all } 0 \leq t \leq 1, \quad \mathcal{BP}\left[P_{0},P_{1}\right](t) = (1-t) \textbf{P}_0 + t \textbf{P}_1 $$

Use your finger or mouse to move nearest control point (the small blue circles)

Here, $\mathcal{BP}$, means Bezier Polynomial parametric curve. In the right window, you can see the basis polynomials of the linear Bezier curve. The red line is $(1-t)$ and the green one is $t$. In this example, the list of control points is $\textbf{P}$=[[0.1,0.1],[0.9,0.9]]

More generally, we have the following definition of Bezier curves:
Let us given $n+1$ points $\textbf{P}_0,...,\textbf{P}_1$, we call Bezier curve a polynomial parametric curve defined by: $$ \text{For all } 0 \leq t \leq 1, \quad \mathcal{BP}\left[P_{0},P_{1},...,P_{n}\right](t) = B^n_0(t) \textbf{P}_0 + B^n_1(t) \textbf{P}_1 + ... + B^n_n(t) \textbf{P}_n $$ where the $B^n_i(t)= C_n^i (1-t)^{n-i}t^i$ for $i=0,...,n$ are the Bernstein polynomials of order $n$ with $C_n^i=\dfrac{n!}{i!(n-i)}$.


Quadratic Bezier curve

Quadratic Bezier curve is obtained from three control points $\textbf{P}_0$, $\textbf{P}_1$ and $\textbf{P}_2$. The Bezier curve is then defined by: $$ \text{For all } 0 \leq t \leq 1, \quad \mathcal{BP}\left[P_{0},P_{1},P_2\right](t) = B^2_0(t) \textbf{P}_0 + B^2_1(t) \textbf{P}_1 + B^2_2(t) \textbf{P}_2 $$ where the $B^2_0(t)=(1-t)^2$, $B^2_1(t)=2t(1-t)$ and $B^2_2(t)=t^2$ are the Bernstein polynomials of order $2$. They define a basis of the vector space of polynomials of degree less or equal to $2$. To the right you can see basis polynomials $B^2_0(t)$, $B^2_1(t)$ and $B^2_2(t)$ in the red, green and blue order.



By construction Bezier curve goes through its terminal control points ($\textbf{P}_0$ and $\textbf{P}_2$ here) and is tangent to the first and last segments of the control polygon. As we can, the Bezier curve "mimics" the shape of the control polygon. This can be possible due to the properties of the Bernstein polynomials. Usually, it is very difficult to design a polynomial curve when the curve is written in the canonical basis. This change of basis creates good visual conditions for "easy" design of the curves.



Cubic Bezier curve

In a similar way, for $n = 3$, we get a cubic Bezier curve


Bezier curve of degree $n = 7$

The initial control points are given by the following list:
$\textbf{P}$ = [[0.1,0.1],[0.1,0.8],[0.8,0.9],[0.8,0.2],[0.5,0.1],[0.3,0.5],[0.5,0.6],[0.9,0.3]]

On the right, we can see all the Bernstein polynomials $B^n_i(t)$ for $i=0,..,7$ needed to design this Bezier parametric curve.

By moving the control points (blue circles), you can see that the red curve, is always located in the convex hull of the control points of the Bezier curve. This property can be demonstrated.



The de Casteljau Algorithm

In 1958, Paul Faget de Casteljau engineer at Citroën, developped a simple algorithm which allows to calculate the value of $\mathcal{BP}(t)$ for any given value of $t$.
For example if $n = 2$ then his algorithm is defined as follows. We fix the value of $t$ (for example $t=\dfrac{1}{2}$) and we calcute the two points $\textbf{P}^{(1)}_0$ and $\textbf{P}^{(1)}_1$ respectively the middle points of segments $[\textbf{P}_0,\textbf{P}_1]$ and $[\textbf{P}_1,\textbf{P}_2]$.
They are calculated as follows for $t=\dfrac{1}{2}$: \[ \begin{array} [c]{l}% \textbf{P}^{(1)}_0 = (1-t) \textbf{P}_0 + t \textbf{P}_1 \\ \textbf{P}^{(1)}_1 = (1-t) \textbf{P}_1 + t \textbf{P}_2 \\ \end{array} \] Finally, by iterating again this barycentric calcultation we obtain: \[ \textbf{P}^{(2)}_0 = \textbf{BP}(t) = (1-t) \textbf{P}^{(1)}_0 + t \textbf{P}^{(1)}_1 \] Note that $\textbf{P}^{(2)}_0$ subdivides the Bezier curve in two quadratic curves. The new curves match the original in position, although they differ in parameterization. The two polygons $[\textbf{P}_0,\textbf{P}^{(1)}_0,\textbf{P}^{(2)}_0]$ and $[\textbf{P}^{(2)}_0,\textbf{P}^{(1)}_1,\textbf{P}_2]$ are the control polygons of two new bezier curves that match perfectly the initial one.


In the following Figure, the two points $\textbf{P}^{(1)}_0$ and $\textbf{P}^{(1)}_1$ are the extremeties of the green segment and the point $\textbf{P}^{(2)}_0$ is the black point. They are calculated by the de Casteljau algorithm for different values of $t = \dfrac{i}{100}$ for $i=0,..,100$. Consequently, by joining all these black points it is possible to draw the Bezier curve in red. We then don't need to calculate the Bernstein polynoms.



More generally, Paul de Casteljau demonstrated the following theorem:
Let us given $n+1$ points $\textbf{P}_0,...,\textbf{P}_n$ and $j$ be a fixed integer of {0,...,n}. It yields: $$ \text{For all } 0 \leq t \leq 1, \quad \mathcal{BP}(t) = B^{n-j}_0(t) \textbf{P}^{(j)}_0 + B^{n-j}_1(t) \textbf{P}^{(j)}_1 + ... + B^{n-j}_n(t) \textbf{P}^{(j)}_{n-j} $$ where $\textbf{P}^{(0)}_i = \textbf{P}_i$ and $\textbf{P}^{(j)}_i = (1-t) \textbf{P}^{(j-1)}_i + t \textbf{P}^{(j-1)}_{i+1}$ for $i=0,...,n-j$.

Exercice[de Casteljau Algorithm]

We want to draw a Bezier curve by using the de Casteljau algorithm.

  • Plot all the Bernstein polynomials for $n=3$. For this, use the following binomial function.

  •             
        import numpy as np
        from math import factorial as fac
        
        def binomial(n,i):
            try:   
                binom=fac(n)/(fac(i)*fac(n-i))
            except ValueError:
                binom=0.0              
            return binom
    
        def bernstein(n,i,t):
            #TO DO               
            return 
    
                
            
            def bernstein(n,i,t):
                res=binomial(n,i)*(1-t)**(n-i)*t**i
                return res
    
            t=np.linspace(0,1,100)
    
            n=3
            for i in range(n+1):
                y=[bernstein(n,i,x) for x in t]
                plt.plot(t,y)
            plt.show()
        
  • By using the result of the previous Theorem, implement the de Casteljau function for $j=n$. This function will return the value of $\mathcal{BP}(t)$ for a given $t$. $\textbf{P}$ is the list of the control points of the Bezier curve.

  •             
        import numpy as np
    
        def decast(t,P):
            #TO DO    
            return
                
            
            def decast(t,P):
                n=len(P)-1
                L0=P
                for k in range(n):
                    L=L0
                    L0=[]
                    for i in range(n-k):
                        L0.append(np.dot(1-t,L[i])+np.dot(t,L[i+1]))
                return L0[0][0],L0[0][1]
        
  • By using the previous decast function, draw the cubic Bezier curve with control polygon $\textbf{P}=[ [0.1,0.1],[0.9,0.9],[0.1,0.9],[0.9,0.1]]$. For this you can use a subdivision of $[0,1]$ by using np.linspace(0,1,100). Calculate for each values the corresponding values of the Bezier curve. The drawing of the Bezier curve is obtained by joining all these values. As in the previous Bezier examples you can draw also this control polygon.

  •             
        import numpy as np
        import matplotlib.pyplot as plt
    
        def DrawBezier(P,nb=100):
            #TO DO    
            return
                
            
            def DrawBezier(P,nb=100):
                z=np.linspace(0,1,nb)
                X=[]
                Y=[]
                for t in z:
                    x,y=decast(t,P)
                    X.append(x)
                    Y.append(y)
                return X,Y
        
            P=[[0.1,0.1],[0.9,0.9],[0.1,0.9],[0.9,0.1]]
            p=np.transpose(P)
            X,Y=DrawBezier(P)
            # Plot the control polygon of the Bezier curve
            plt.plot(p[0],p[1],'r')
            plt.plot(X,Y)
            plt.show()
        

Geometric Continuity

In practice, the modeled objects can be produced from several Bézier curves. In the following example, the two curves are joined with the $C^3$ continuity. This was done with CATIA V5.



To guarantee a certain regularity of fitting, it is necessary to know how to calculate the derivatives of a Bézier curve. The following proposition makes it possible.
Let us give $n+1$ data points $P_{0},\ldots,P_{n}$ of $\mathbb{R}^{d}$ ($d=2,3,...$) then the derivative of order $k\in \mathbb{I\hspace{-.15em}N}$ is given by $$ \begin{equation} \forall t\in \left[ 0,1\right] ,\text{ }\frac{d^{k}\mathcal{BP}\left[ P_{0},P_{1},\ldots,P_{n}\right] }{dt^{k}}\left( t\right) =\frac{n!}{\left( n-k\right) !}\sum_{i=0}^{n-k}B_{i}^{n-k}\left( t\right) \Delta^{k}P_{i}, \label{DeriveeBezier}% \end{equation} $$ where $\Delta^{k}P_{i}$ is the operator of progressive differences of order $k$ at point $P_{i}$.
For example we have:
$\Delta^{1}P_{i}=P_{i+1}-P_{i}=\overrightarrow{P_{i}P_{i+1}}$ $\Delta^{2}P_{i}=\Delta^{1}\left(\Delta^{1}P_{i}\right) =P_{i+2}-P_{i+1}-P_{i+1}+P_{i}=\overrightarrow{P_{i+1}P_{i}}+\overrightarrow{P_{i+1}P_{i+2}}$.
Moreover, $\Delta^{k}P_{i} =\Delta^{1}\left( \Delta^{k-1}P_{i}\right) =% %TCIMACRO{\dsum \limits_{j=0}^{k}}% %BeginExpansion {\displaystyle \sum \limits_{j=0}^{k}} %EndExpansion \binom{k}{j}\left( -1\right) ^{k-j}P_{i+j}$.
Consequently, we have at the extremities:

$\dfrac{d^{k}\mathcal{BP}\left[ P_{0},P_{1},\ldots,P_{n}\right] }{dt^{k}}\left( 0\right) =\dfrac{n!}{\left( n-k\right) !}\Delta^{k}P_{0}$ $\dfrac{d^{k}\mathcal{BP}\left[P_{0},P_{1},\ldots,P_{n}\right] }{dt^{k}}\left( 1\right) =\dfrac{n!}{\left(n-k\right) !}\Delta^{k}P_{n-k}$.

Exercice [$C^3$-continuity]

In this exercice, we wish to build a cubic Bezier curve with unknow control polygon $\textbf{Q}=[Q_0,Q_1,Q_2,Q_3]$ which joined $C^3$-continuously with a given Bezier curve (See the following Figure)

  • Let us give the cubic Bezier curve with control polygon $\textbf{P}=[ P_0=[0.1,0.1],P_1=[0.9,0.9],P_2=[0.1,0.9],P_3=[0.9,0.1]]$, by using the previous proposition calculate the $C^0$,$C^1$, $C^2$ and $C^3$ derivatives at $t=0$ and $t=1$ respectively.

  • By using the previous results, calculate the values of points $Q_0$, $Q_1$, $Q_2$ and $Q_3$ such that this cubic Bezier curve joins $C^3$ at $t=0$ with the cubic Bezier Curve with control polygon $\textbf{P}$ at $t=1$.

  • Draw these two Bezier curves.

  • $C^0:$ $$\mathcal{BP}[Q](0)=\mathcal{BP}[P](1)$$ Consequently $Q_0= P_3$

    $C^1:$ $$\dfrac{d\mathcal{BP}[Q]}{dt}(0)=\dfrac{d\mathcal{BP}[P]}{dt}(1)$$ Consequently $Q_1-Q_0= P_3-P_2$, it yields that $Q_1=P_3 + (P_3-P_2)$.

    $C^2:$ $$\dfrac{d^2\mathcal{BP}[Q]}{dt^2}(0)=\dfrac{d^2\mathcal{BP}[P]}{dt^2}(1)$$ Consequently $Q_2-2Q_1+Q_0= P_1-2P_2+P_3$, it yields that $Q_2=P_1 + 4(P_3-P_2)$.

    $C^3:$ $$\dfrac{d^3\mathcal{BP}[Q]}{dt^3}(0)=\dfrac{d^3\mathcal{BP}[P]}{dt^3}(1)$$ Consequently $\Delta^{3}Q_0= \Delta^{3}P_0$, it yields that $Q_3=..$.

            P=[[0.1,0.1],[0.9,0.9],[0.1,0.9],[0.9,0.1]]
            p=np.transpose(P)
            X,Y=DrawBezier(P)
            # Plot the control polygon of the Bezier curve
            plt.plot(p[0],p[1],'r')
            plt.plot(X,Y)
    
            # Calculate the control polygon Q for the C2-continuity 
            Q0=P[2]
            Q1=Q0+(np.add(P[2],np.dot(-1,P[1])))
            Q2=np.add(P[0],np.dot(4,(np.add(P[2],np.dot(-1,P[1])))))
            # in this case Q3 is free of constraint
            Q3 = [1,1]
            Q=[Q0,Q1,Q2,Q3]
            q=np.transpose(Q)
            X,Y=DrawBezier(Q)
            plt.plot(q[0],q[1],'r')
            plt.plot(X,Y)
    
            plt.show()
    
            # for the C3 case, the location of Q3 is given by defining
            # the symmetric point of R3 (see the previous Figure)
            # You can calculate it by ourself.
    
        

References

  1. J.H. Ahlberg, E.N. Nilson & J.L. Walsh (1967) The Theory of Splines and Their Applications. Academic Press, New York.
  2. C. de Boor (1978) A Practical Guide to Splines. Springer-Verlag.
  3. G.D. Knott (2000) Interpolating Cubic Splines. Birkhäuser.
  4. H.J. Nussbaumer (1981) Fast Fourier Transform and Convolution Algorithms. Springer-Verlag.
  5. H. Späth (1995) One Dimensional Spline Interpolation. AK Peters.