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 parametric curve is obtained by linear interpolation between two given control points $\textbf{P}_0$ and $\textbf{P}_1$ in the plane.

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]]

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.

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.

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.

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.

Python Solution
$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.