Le tracé des transitions

Pour dessiner des automates « à la main », on utilise des courbes pour tracer les liaisons. Pour les faire dessiner par un programme, la solution peut être d'utiliser des courbes de BEZIER. Elles serviront uniquement en tant qu'outil ici et ne font donc pas partie intégrante de ce TIPE. Néanmoins, un peu de théorie et quelques explications semblaient indispensables.

Remarque : Tous les développements théoriques suivants sont tirés du Cours d'Infographie [5] de Patrick TRAU^3.1.

On a souvent besoin de représenter avec l'ordinateur des courbes ou surfaces dont le type n'est soit non classifiable (ni parabole, ni cercle, ...) soit non connu à l'avance. On les regroupe généralement sous le nom de « courbes et surfaces non mathématiques », car l'équation mathématique n'est pas connue par le programmeur. Ces courbes ou surfaces sont en général définies par un ensemble de points, plus ou moins nombreux.

Introduction

Le problème qui se posait à la régie RENAULT consistait à représenter les surfaces de carrosserie dessinées par les designers, pour réaliser les matrices d'emboutissage. La pièce était définie par des sections planes successives. A l'arrivée des machines à commande numérique, la méthode manuelle a du être abandonnée. Après création d'une maquette 3D (en bois, plâtre, ... modifiée au fur et à mesure), la surface était déterminée par une matrice de points obtenus à l'aide d'une machine à mesurer en 3D. Pour obtenir une bonne précision, le nombre de points nécessaire est très important. Le nombre de maquettes réalisées en cours de conception étant important (d'où pertes de temps), on a demandé aux stylistes de créer sur ordinateur, les maquettes pouvant alors être facilement et rapidement réalisées en commande numérique.

P. BEZIER^3.2 a du mettre au point une méthode permettant de définir la surface par un nombre minimal de points caractéristiques, permettre de modifier facilement la surface par déplacement d'un minimum de points, pouvoir représenter toute surface (y compris plane), sans « cassure » (continûment dérivable).

Courbes de BEZIER

$$\textrm{Soit} \quad \vec P(u)=\overrightarrow{OA}+f_1(u).\ve... ...\cdots + f_n(u).\vec a_n \quad \textrm{avec} \quad u \in [0;1]$$

Cette définition de la courbe est possible aussi bien en 2D qu'en 3D. Les vecteurs $a_1,\ldots,a_n$ forment le « polygone caractéristique ».

Conditions

On impose à l'origine ($u = 0$) :

• passage en $A$ ( $f_i(0)=0\ \textrm{pour}\ i > 0$)
• la tangente ne dépend que de $\vec a_1$ ( $f'_i(0)=0\ \textrm{pour}\ i > 0$)
• la dérivée seconde ne dépend que de $\vec a_1$ et $\vec a_2$ ( $f''_i(0)=0\ \textrm{pour}\ i > 0$)
• de façon générale, la dérivée k-ième ne dépend que des $k$ vecteurs $\vec a_1$ à $\vec a_k$

De plus, le dernier sommet du polygone caractéristique impose le point final de la courbe ($u=1$), la tangente en ce point ne dépend que du dernier vecteur $\vec a_n$, etc.

Exemple : pour $n=3$, on impose les conditions suivantes :

• passage de la courbe aux deux extrémités du polygone caractéristique :
  
  $$f_1(0) = f_2(0) = f_3(0) = 0 \quad \textrm{et} \quad f_1(1) = f_2(1) = f_3(1) = 1$$
  
  

• la tangente en $A$ ne dépend que de $\vec a_1$ (idem à l'autre extrémité) :
  
  $$\frac{d}{du}f_2(0) = \frac{d}{du}f_3(0) = 0 \quad \textrm{et} \quad \frac{d}{du}f_1(1) = \frac{d}{du}f_2(1)= 0$$
  
  

• la dérivée seconde en A ne dépend que de $\vec a_1$ et $\vec a_2$ :
  
  $$\frac{d^2}{du^2}f_3(0) = 0 \quad \textrm{et} \quad \frac{d^2}{du^2}f_1(1) = 0$$
  
  

Détermination des polynômes de BEZIER

Plaçons-nous encore dans le cas de trois points : on a 12 conditions. On peut donc prendre trois fonctions du troisième degré.

Soit $f_i(u)=a.u^3+b.u^2 + c.u + d$. La dérivée sera donc $f'_i(u)=3a.u^2+2b.u+c$, et la dérivée seconde $f''_i(u)=6a.u+2b$.

$$\begin{array}{rrcll} \textrm{D'où :} & f_1(0)=0 &\ensuremath... ... \multicolumn{5}{c}{\textrm{Donc} \quad f_3(u)=u^3} \end{array}$$

FIGURE 3.1: Tracé des fonctions $f_{im}(u)$ dans le cas $m = 3$

Pierre BEZIER a déterminé le cas général (à l'ordre $m$) :

$$f_{im}(u)=\frac{(-u)^i}{(i-1)!} \frac{d^{i-1}}{du^{i-1}} \le... ...im}(u)=\sum_{k=i}^m{m \choose k}{k-1 \choose i-1}(-1)^{i+k}u^k$$

$$\textrm{avec} \quad {a \choose b}=\frac{a!}{b!(a-b)!}$$

Cette seconde écriture se traduit facilement de manière informatique, bien que comportant beaucoup de calculs.

Forme polynomiale

Plutôt que d'utiliser la formulation vectorielle, on définit le polygone caractéristique par les coordonnées $x_i, y_i, z_i$ de ses sommets. On obtient les coordonnées de tout point de la courbe :

$$\begin{eqnarray*} X(u) & = & \sum_{i=0}^nX_i{n \choose i}u^i(1-u)^{n-i}\\ Y(u) ... ...)^{n-i}\\ Z(u) & = & \sum_{i=0}^nZ_i{n \choose i}u^i(1-u)^{n-i} \end{eqnarray*}$$

Pour accélérer les calculs, on cherchera à stocker dans des tableaux les valeurs intermédiaires réutilisées plusieurs fois pour un tracé. D'autres formulations ont également été développées, on peut les trouver dans divers ouvrages, par exemple dans la collection Maths et CAO.

Intérêt

On peut définir une courbe complexe avec assez peu de points caractéristiques. Certes la courbe ne passe pas par ces points, mais avec un peu d'expérience, on « sent » facilement comment déplacer quelques points caractéristiques pour modifier une courbe. Ceci est encore plus intéressant pour des surfaces tridimensionnelles, où les modifications elles aussi se limiteront aux déplacements de quelques points.

Exemples

Ces exemples (cf. FIGURE 3.2) nous montrent la diversité des courbes possibles avec trois ou quatre points.

FIGURE 3.2: Exemples de courbes de BEZIER

Programmation

Pour tracer une courbe de BEZIER, il faut définir le type des points et de la courbe (cf. PROGRAMME 3.1). Ensuite et pour suivre les conseils précédents, les valeurs des paramètres, c'est-à-dire les coefficients des polygones caractéristiques, sont stockées dans une variable globale pour éviter de les recalculer à chaque tracé. C'est la fonction Cvalues (cf. PROGRAMME 3.2) qui est chargée de ce travail, sachant que l'on utilisera 100 points pour tracer la courbe. Il ne reste plus alors qu'à tracer la courbe de BEZIER (cf. PROGRAMME 3.3), en ayant auparavant crée la liste tValues qui contient les valeurs des paramètres.

PROGRAMME 3.1: Les types pour les courbes de BEZIER

PROGRAMME 3.2: Précalcul des paramètres des courbes de BEZIER

PROGRAMME 3.3: Tracé des courbes de BEZIER