Algorithme de De Casteljau

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

L'algorithme de De Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour calculer des polynômes écrit dans la base de Bernstein et dessiner des courbes et des surfaces de Bézier.

L'idée principale de l'algorithme repose sur le fait qu'une restriction d'une courbe de Bézier est aussi une courbe de Bézier. À partir de la courbe initiale, on trouve les points de contrôle des deux courbes définies pour t\in[0,1/2] et t\in[1/2,1] et on affiche le pixel qui correspond au point pour t=\frac{1}{2}. On itère le processus sur chacune des deux courbes jusqu'à ce que la précision soit inférieure au pixel.

Sommaire

[modifier] Historique

Historiquement, c'est avec cet algorithme que les travaux de M. De Casteljau commençaient en 1959 chez Citroën. Ils étaient publiés comme des rapports techniques, tenus très au secret par Citroën.

Ces travaux restèrent inconnus jusqu'en 1975 quand W. Böhm en a pris connaissance et les a rendu public.

[modifier] Calcul d'un polynôme dans la base de Bernstein

Soit un polynôme P de degré n écrit dans la base de Bernstein.

P(t) = \sum_{i=0}^{n}\beta_{i}B_i^n(t)

L'algorithme consiste simplement à évaluer la valeur des polynômes de Bernstein en utilisant la propriété de récurrence : B_i^n(u) = (1-u)B_i^{n-1}(u) + u B_{i+1}^{n-1}(u)

[modifier] Afficher une courbe de Bézier

[modifier] Initialisation

Considérons une courbe de Bézier B:[0,1]\to \mathbb{R}^3définie par les points de contrôles P^0_0,\dots,P^0_N.

[modifier] Récurrence

Le but est de construire deux ensembles de points qui seront les points de contrôle des deux moitiés de la courbe de Bézier. Il y a 2 méthodes pour le faire :

  • Méthode constructive (en construisant une suite de milieux)
On définit les points P^1_0,\dots,P^1_{N-1}, P^2_0,\dots,P^2_{N-2},\dots,P^{N-1}_0, P^{N-1}_1, P^N_0 tels que P^j_i soit le milieu de [P^{j-1}_iP^{j-1}_{i+1}].
  • Méthode matricielle (en construisant directement les points comme barycentre, les coefficients étant donnés par les matrices de De Casteljau)
\begin{pmatrix} P_0^0 \\ \vdots \\ P_0^N \end{pmatrix} = D_0^N * \begin{pmatrix} P_0^0 \\ \vdots \\ P_N^0 \end{pmatrix} et \begin{pmatrix} P_0^N \\ \vdots \\ P_N^0 \end{pmatrix} = D_1^N * \begin{pmatrix} P_0^0 \\ \vdots \\ P_N^0 \end{pmatrix}


La courbe de Bézier B passe par le point P^N_0 qui est le point de paramètre t = 1 / 2

On définit les courbes de Bézier B' comme la courbe contrôlée par les points P_0^0,\dots,P_0^N et B'' par les points P_0^N, P_1^{N-1},\dots,P_N^{0}.

On a alors B = B' \cup B''

On applique ensuite l'algorithme récursivement sur B' et B''.

[modifier] Arrêt

Il existe différentes manières de choisir la condition d'arrêt des itérations :

  • Si on fait tous les calculs avec des nombres entiers, un choix peut être de s'arrêter lorsque tous les points sont confondus. (c'est-à-dire que la courbe n'est représentée que par un seul pixel)
  • On effectue M itérations puis on relie les points obtenus (c'est-à-dire que l'on trace le polygone de Bézier), M étant déterminé empiriquement.

[modifier] Complexité

La complexité de cet algorithme est quadratique en nombre de points de contrôle et linéaire en nombre d'itération.

[modifier] Pseudo-code

 Entrée : tableau T[0][0...N] des coordonnées des points de contrôle.

 // Condition d'arrêt
 Si T[0][0] = T[0][1] = ... = T[0][N]  // Si tous les points sont confondus
 alors  
 |
 | Afficher T[0][0]
 | fin
 |
 Sinon  //pour dessiner
 |
 | // Calcul des points intermédiaires
 | Pour i de 1 à N faire
 | |
 | | Pour j de 0 à N-i faire
 | | |
 | | | T[i][j] = milieu de T[i-1][j] T[i-1][j+1]
 | 
 | Afficher T[N][0]
 |   
 | // Préparation appel récursif
 | Pour i de 0 à N faire
 | |
 | | T'[i] = T[i][0]
 | | T"[i] = T[N-i][i]
 |
 | // Appel récursif
 | de_Casteljau(T')
 | de_Casteljau(T")

Remarques :

  • On suppose que tous les calculs sont fait sur des entiers.
  • L'arrêt des itérations est déterminé lorsque les points de contrôle d'une sous-courbe sont confondus.

[modifier] Exemple

[modifier] Voir aussi