\Annee{2007}
\Auteur{Fr\'ed\'eric \textsc{Le Roux}}
\AutresAuteurs{}
\Date{2007/01/15}
\Titre{Introduction aux courbes de B\'ezier}
\Niveau{\DEUGi} %Le niveau principal. Typiquement: \DEUGi (=1ere annee), \DEUGii (=2eme annee), \Licence, ...
\NiveauxSecondaires{}

\AnglePedagogique{\AQuoiCaSert} %l'angle pedagogique principal. Typiquement: \AQuoiCaSert, \Experimental, ...

\AnglesSecondaires{} %Eventuellement, les angles pedagogiques secondaires separes par des virgules

\Theme{\GeometrieDiff} %Theme principal. Typiquement: \AlgLin, \Suites, \Series, ...

\ThemesSecondaires{Courbes param\'etr\'ees} 

\Objectif{Dans cet exercice, on d\'efinit les courbes de B\'ezier cubiques, et on \'etudie l'algorithme de trac\'e d\^u \`a  Casteljau. L'introduction est extraite d'un \emph{Cours de calculus}, voir \htmladdnormallink{http://math.u-psud.fr/\~{ }leroux}{http://math.u-psud.fr/~leroux}.}

\begin{exo}

Vous \^etes-vous d\'ej\`a demand\'e comment l'ordinateur dessine les lettres que l'on voit \`a l'\'ecran ?
Dans les ann\'ees 1980, quand les ordinateurs personnels commen\c caient tout juste \`a se r\'epandre, l'ordinateur avait en m\'emoire un dessin de chacune des 26 lettres de l'alphabet (sans compter les lettres accentu\'ees). Une lettre \'etait stock\'ee sous la forme d'une grille $8 \times 8$ dans laquelle chaque case \'etait allum\'ee
 ou \'eteinte (noire ou blanche, ce qui en m\'emoire correspond au symbole $0$ ou $1$).
 Par exemple, le ``e'' pouvait  ressembler au dessin de gauche de la figure~\ref{police}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=5cm]{police1-tiff.eps}
\hspace{2cm}
\includegraphics[width=5cm]{police2-tiff.eps}
\caption{Zoom sur un ``e'' : \`a gauche, avec un ordinateur des ann\'ees 1980 ; \`a droite, avec un ordinateur actuel}
\label{police}
\end{center}
\end{figure}


Cette m\'ethode avait de nombreux inconv\'enients. En particulier, si l'on voulait grossir le texte \`a l'\'ecran, l'ordinateur ne pouvait que grossir la grille, et on voyait appara\^itre
les gros carr\'es qui d\'efinissaient la lettre, exactement comme sur le dessin ci-dessus.
En comparaison, avec un ordinateur actuel,
on peut zoomer ``\`a l'infini'' sans voir appara\^itre de gros carr\'es ; pourtant, l'\'ecran lui-m\^eme est toujours une grille de pixels (ici, 1024 sur 768) : c'est donc que le ``e'' sur lequel on a zoom\'e n'est pas obtenu \`a partir d'une lettre de taille normale en effectuant un pur agrandissement (une homoth\'etie !), sans quoi les carr\'es appara\^itraient assez vite.
 Il semble que les lettres ne soient plus d\'efinies au moyen d'une grille, mais \`a l'aide de courbes lisses, et que l'ordinateur recalcule des d\'etails suppl\'ementaires \`a chaque nouvel agrandissement.
\emph{Quelles sont les courbes utilis\'ees pour produire ces lettres, et comment 
sont-elles d\'efinies ?}

Une recherche rapide nous apprend que ces courbes sont des \emph{courbes de B\'ezier}. La plupart des logiciels de dessin permettent de tracer de telles courbes. On voit que ces courbes sont d\'efinies tr\`es facilement : on donne un point de d\'epart, et une vitesse en ce point ; 
et un point d'arriv\'ee, et une vitesse au point d'arriv\'ee ; et le logiciel nous trace la courbe de B\'ezier  correspondante. La figure~\ref{police-e} montre comment la lettre ``e'' peut \^etre fabriqu\'ee en assemblant un certain nombre de courbes de B\'ezier.
La g\'eom\'etrie se glisse  parfois \`a des endroits inattendus...

Comment sont d\'efinies math\'ematiquement ces courbes de B\'ezier, 
et comment l'ordinateur les dessine ? C'est ce que nous allons apprendre dans cet exercice.

\begin{figure}[htbp]
\begin{center}\hspace{-2cm}\vspace{-2cm}
\parbox{\textwidth}{
\framebox{
\centerline{\includegraphics[angle=-90,width=12cm]{police3-e.eps}}
}}
\caption{Extrait de \emph{Caract\`eres num\'eriques : introduction}, de Jacques Andr\'e}
\label{police-e}
\end{center}
\end{figure}




\footnotesize 
\paragraph{Histoire de B\'ezier (liocity.free.fr)}
Au d\' ebut des ann\' ees 60, les machines num\' eriques ne savaient usiner de fa\c con pr\' ecise que des courbes simples comme des paraboles ou des ellipses.  Une seconde cat\' egorie d'objets, au contraire, offrait une forme a priori peu pr\' ecise, d\' etermin\' ee exp\' erimentalement. Les h\' elices d'avions, les coques de bateaux et les carrosseries de voitures \' etaient trac\' ees \`a main lev\' ee, sans que l'on puisse d\' ecrire leurs formes par une formule math\' ematique.

Pierre B\' ezier, ing\' enieur fran\c cais dipl\^om\' e du Conservatoire national des arts et m\' etiers, poursuivait, une carri\`ere \`a la R\' egie Renault, atteignant le poste de directeur des m\' ethodes m\' ecaniques.

Les machines \`a commande num\' erique de cette \' epoque offraient une programmation limit\' ee. Il fallait les alimenter avec des nombres, ce que l'on savait faire pour des d\' eplacements \' el\' ementaires comme des droites, des arcs de cercle, et \`a la rigueur des ellipses. Mais il n'\' etait pas question de programmer des courbes quelconques, trac\' ees \`a la main, faute d'une d\' efinition num\' erique de celles-ci. 
Pierre B\' ezier chercha donc comment traduire math\' ematiquement une courbe, puis une surface, dessin\' ees \`a main lev\' ee. Il lui fallait concevoir un syst\`eme capable de g\' erer des courbes gauches, c'est-\`a-dire de manipuler des surfaces en 3D, d'o� la n\' ecessit\' e de d\' efinir un mod\`ele math\' ematique qui ne soit pas limit\' e \`a des courbes en deux dimensions. Enfin, l'ing\' enieur entendait inventer un syst\`eme complet pour cr\' eer un objet en volume \`a partir d'un dessin, le tout avec une rapidit\' e d'ex\' ecution suffisante, et compr\' ehensible intuitivement.

Mais ses recherches n'\' etaient pas enti\`erement originales. D\`es 1958, un math\' ematicien employ\' e par Citroen, Paul de Casteljau, s'\' etait attaqu\' e au m\^eme probl\`eme. Paul de Casteljau \' etait charg\' e de num\' eriser une courbe, une fois celle-ci trac\' ee, sans se poser la question d'une correction a posteriori. Il d\' efinissait ses courbes comme caract\' eris\' ees par des p\^oles, d'une fa\c con nettement moins parlante que les points de contr\^ole de B\' ezier.

L'aventure de Pierre B\' ezier aurait pu s'arr\^eter l\`a. Mais un groupe de d\' eveloppeurs li\' es \`a Apple cr\' ea un langage adapt\' e \`a la future imprimante laser con\c cue pour le Mac. Il s'agissait de trouver un moyen de d\' efinir math\' ematiquement une courbe, comme le trac\' e d'un caract\`ere, avant de l'envoyer \`a l'imprimante. L'un de ces d\' eveloppeurs connaissait le travail du Fran\c cais. Tout naturellement, il choisit les courbes de B\' ezier comme base du langage PostScript et fonda la soci\' et\' e Adobe. Microsoft adopta \`a son tour les polices true-type \`a partir de Windows 3.1. Ces polices utilisent les courbes de B\' ezier pour d\' efinir les caract\`eres aux formes arrondies.
\normalsize






\partie{D\'efinition des courbes de B\'ezier}

On se donne quatre points $A_{0}, A_{1}, A_{2}, A_{3}$ dans le plan,
et on cherche \`a d\'efinir une courbe param\'etr\'ee 
\begin{itemize}
\item qui part de $A_{0}$ et arrive en  $A_{3}$ ;
\item qui est  tangente en $A_{0}$ \`a la droite $(A_{0}A_{1})$,
\item qui est  tangente en $A_{3}$ \`a la droite $(A_{2}A_{3})$,
\item qui est d\'efinie par des polyn\^omes de petit degr\'e.
\end{itemize}

Pour cela,  on d\'efinit les quatre polyn\^omes (dits \emph{polyn\^omes de Bernstein} de degr\'e $3$)
$$
p_{0}(t) = (1-t)^3, \ \ \  p_{1}(t) = 3t(1-t)^2,  \ \ \ p_{2}(t) = 3t^2(1-t),  \ \ \ p_{3}(t) = t^3.
$$  
Soit $\alpha$ la courbe param\'etr\'ee d\'efinie, pour $t \in [0,1]$, par les formules suivantes, 
o\`u $A_{0}=(x_{0},y_{0})$, \textit{etc.}.
$$\left\{
\begin{array}{lll}
x(t) & = & x_{0}p_{0}(t) + x_{1}p_{1}(t) + x_{2}p_{2}(t) +x_{3}p_{3}(t)     \\
y(t) &  = & y_{0}p_{0}(t) + y_{1}p_{1}(t) + y_{2}p_{2}(t) +y_{3}p_{3}(t)
\end{array}
\right.
$$


\qst{Cas particulier} On consid\`ere ici les points $A_{0}=(0,0), A_{1}=(0,1), A_{2}=(1,1), A_{3}=(1,0)$. Dans ce cas, expliciter les formules d\'efinissant la courbe $\alpha$.
\'Etudier et dessiner la courbe.

%la formule\footnote{Remarque : dans cette formule, on utilise la notation $A.k$ o\`u $A$ est un point et $k$ un nombre. Par d\'efinition, la multiplication se fait coordonn\'ee par coordonn\'ee (les coordonn\'ees de $A.k$ sont celles  de $A$ multipli\'ees par $k$). M\^eme remarque pour l'addition de deux points.
%}
%$$
%\alpha(t) = A_{0}.p_{0}(t) +  A_{1}.p_{1}(t) +  A_{2}.p_{2}(t) +  A_{3}.p_{3}(t).
%$$


\qst{Cas g\'en\'eral} 

On consid\`ere ici quatre points quelconques $A_{0}, A_{1}, A_{2}, A_{3}$.

 \sq Montrer que la courbe $\alpha$ d\'efinie plus haut r\'epond au probl\`eme. 

 On l'appellera \emph{courbe de B\'ezier associ\'ee aux quatre points $A_{0}, \dots, A_{3}$.}
On pourra faire le calcul \`a l'aide du tableau suivant.
\[
\begin{array}{cccc|cccc|cccc|cccc|cccc|cccc}
  p_{0}(t)&&&& p_{1}(t)  &&&& p_{2}(t) &&&& p_{3}(t)&&&& x(t) &&&& y(t) &&& \\
\hline
 p_{0}(0)=    &&&& p_{1}(0)= &&&& p_{2}(0)= &&&& p_{3}(0)= &&&&x(0)= &&&&y(0)= & \\
\hline
 p_{0}(1)= &&&& p_{1}(1)= &&&& p_{2}(1)= &&&& p_{3}(1)= &&&&x(1)= &&&&y(1)= & \\
\hline
 p_{0}'(0)= &&&& p_{1}'(0)= &&&& p_{2}'(0)= &&&& p_{3}'(0)= &&&&x'(0)= &&&&y'(0)= & \\
\hline
 p_{0}'(1)= &&&& p_{1}'(1)= &&&& p_{2}'(1)= &&&& p_{3}'(1)= &&&&x'(1)= &&&&y'(1)= & \\
\end{array}
\]

\sq Que vaut  le vecteur $\alpha'(0)$ en fonction du vecteur $\overrightarrow{A_{0}A_{1}}$ ? et $\alpha'(1)$ en fonction de $\overrightarrow{A_{2}A_{3}}$ ?

\qst{}
Calculer la vitesse  de $\alpha$ au point $t=1/2$,    et exprimer cette vitesse \`a l'aide des vecteurs
$\overrightarrow{A_{0}A_{3}}$ et $\overrightarrow{A_{1}A_{2}}$.


%\qst{} \emph{(optionnelle)} Donner \emph{sans calculs} la courbe de B\'ezier  associ\'ee aux quatre points 
%$A'_{0}=(0,0), A'_{1}=(1,0), A'_{2}=(1,1), A'_{3}=(0,1)$.

%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%
\partie{Trac\'e r\'ecursif d'une courbe de B\'ezier : l'algorithme de Casteljau}


\begin{figure}[htbp]
\def\JPicScale{1}
\begin{center}
\input{Casteljau.tex}
\caption{Construction de Casteljau}
\label{castel}
\end{center}
\end{figure}

\paragraph{Description g\'eom\'etrique  de l'algorithme}
\`A partir des quatre points $A_{0}, A_{1}, A_{2} , A_{3}$, on construit les points $B_{0}, B_{1},B_{2} , B_{3}$ et $C_{0}, C_{1}, C_{2} , C_{3}$ en prenant des milieux successifs comme sur le dessin de la figure~\ref{castel}~: $B_{0} = A_{0}$ ; $B_{1}$ est le milieu des points  $A_{0}$ et $A_{1}$ ; $B_{2}$ est le milieu de $B_{1}$ et du milieu de $A_{1}$ et $A_{2}$ ; \textit{etc.}.

La remarque de Paul de Casteljau\footnote{Math\'ematicien, embauch\'e \`a la fin des ann\'ees 1950 par Citro\"en pour trouver une m\'ethode permettant de d\'efinir num\'eriquement  les courbes dessin\'ees par le bureau d'\'etude, afin d'assurer une transmission pr\'ecise \`a l'atelier de fabrication. Il est le co-inventeur des courbes de B\'ezier et de leur application \`a l'automobile.}
est la suivante : \emph{la courbe de B\'ezier $\alpha$ associ\'ee aux quatres points  
$A_{0}, \dots , A_{3}$ s'obtient en concat\'enant\footnote{Concat\'ener, c'est mettre bout-\`a-bout.}  la courbe de B\'ezier  associ\'ee \`a  $B_{0}, \dots , B_{3}$ et la courbe de B\'ezier associ\'ee \`a  $C_{0}, \dots , C_{3}$.} Nous allons essayer de v\'erifier cette remarque.


\qst{} \sq Trouver les coordonn\'ees du point $B_{3}$ en fonction de celles des quatres points initiaux $A_{0}, \dots , A_{3}$. 

\sq Montrer que ce point appartient bien \`a l'image de la courbe $\alpha$.

\def\ra{\rightarrow}

\qst{} Soit $\beta : [0,1] \ra \bbR^2$ la courbe param\'etr\'ee obtenue en partant de $\alpha(0)$ \`a $t=0$ et en parcourant l'image de la courbe  $\alpha$ deux fois moins rapidement.

\sq Donner une formule pour la courbe $\beta$ en fonction de la courbe $\alpha$.
\emph{Aide : que vaut $\beta(1)$ ? $\beta(1/2)$ ? $\beta(t)$ ?}

\sq En d\'eduire $\beta'(0)$ et $\beta'(1)$. 

\sq Montrer que la courbe $\beta$ v\'erifie bien les propri\'et\'es  de la courbe de B\'ezier associ\'ee \`a $B_{0}, \dots , B_{3}$  (voir l'exercice pr\'ec\'edent) : 
$$\beta(0) = B_{0}, \ \ \ \beta(1) = B_{3} \ \ \ \beta'(0) = 3.\overrightarrow{B_{0}B_{1}} \ \ \ \beta'(1) = 3.\overrightarrow{B_{2}B_{3}}. $$

\qst{} \emph{(optionnelle)} De m\^eme, donner une formule pour la courbe param\'etr\'ee  $\gamma : [0,1] \ra \bbR^2$ qui part de $\alpha(1/2)$ au temps $t=0$ et arrive  en $\alpha(1)$ \`a $t=1$  en parcourant $\alpha$ deux fois moins rapidement.
\emph{On montrerait comme avant que $\gamma$ v\'erifie les propri\'et\'es de la courbe de B\'ezier associ\'ee \`a $C_{0}, \dots , C_{3}$. On admet que $\beta$ et $\gamma$ sont bien des courbes de B\'ezier.}\footnote{Pour montrer ceci, on utiliserait le fait que si l'on se donne quatre nombres $x_{0}, x'_{0}, x_{1}, x'_{1}$, il existe un unique polyn\^ome $p$ de degr\'e inf\'erieur ou \'egal  \`a $3$ tel que $p(0)= x_{0}, p'(0) = x'_{0}, p(1)= x_{1}, p'(1) = x'_{1}$.}


\qst{} On consid\`ere \`a nouveau  la  courbe de B\'ezier associ\'ee aux quatre points 
$A_{0}=(0,0), A_{1}=(0,1), A_{2}=(1,1), A_{3}=(1,0)$.
 En utilisant la remarque de Casteljau (et non pas la formule d\'efinissant $\alpha$), d\'eterminer les coordonn\'es du  point $\alpha(1/2)$. De m\^eme, d\'eterminer  les points $\alpha(1/4)$ et $\alpha(3/4)$. %Utiliser ces points pour tester la formule obtenue pour $\alpha$ dans l'exercice pr\'ec\'edent.

\qst{} On choisit $4$ points quelconques $A'_{0}, A'_{1}, A'_{2}, A'_{3}$
dans le plan. On voudrait tracer la courbe de B\'ezier correspondante $\alpha$.
En utilisant la construction g\'eom\'etrique donn\'ee par l'algorithme de Casteljau, 
placer les points $\alpha(1/2)$, puis $\alpha(1/4)$ et  $\alpha(3/4)$, puis encore quatre autres points. Esquisser le trac\'e de la courbe $\alpha$.




\end{exo}


