<< Mécanique 2 : Dynamique linéaire et rotationnelle

Table des matières

Épilogue >>

Chapitre 13

Courbes en 3D

Je n’ai pas découvert les courbes ; je n’ai fait que les dévoiler.

— Mae West (1892–1980)

Ce chapitre traite de la façon de représenter mathématiquement des courbes en 3D. Recréer une courbe à partir de sa définition mathématique est relativement facile ; la partie délicate est d’obtenir une courbe avec les propriétés souhaitées, ou alternativement, de créer un outil que les designers peuvent utiliser pour dessiner de telles courbes. Notre objectif dans ce chapitre est de fournir une introduction gracieuse et intuitive aux mathématiques des courbes. Par rapport à la plupart des autres livres sur le sujet, notre but est d’aborder les points les plus importants, sans s’arrêter tous les deux paragraphes pour prouver ce que nous affirmons être vrai. (Nous nous arrêterons cependant périodiquement pour discuter de la prononciation correcte, ce qui est probablement approprié étant donné que la plupart des personnes qui ont développé les mathématiques que nous utiliserons dans ce chapitre étaient françaises.) Les courbes et les splines sont très utiles pour toutes sortes de raisons. Il y a des applications évidentes comme déplacer des objets sur des trajectoires courbes. Mais les coordonnées de notre courbe n’ont pas besoin d’avoir une interprétation spatiale ; essentiellement, chaque fois que nous souhaitons ajuster une fonction pour une couleur, une intensité, ou une autre propriété à des points de données donnés, nous avons une application potentielle pour les courbes et les splines.

Le chapitre est divisé grossièrement en deux parties. La première partie porte sur les courbes simples, « courtes » qui peuvent être décrites par une équation.

• La Section 13.1 introduit le type spécifique de courbe sur lequel nous nous concentrons presque exclusivement : la courbe polynomiale paramétrique. (Elle accorde une attention particulière aux polynômes cubiques.)

• La Section 13.2 décrit l’interpolation polynomiale, par laquelle une courbe est enfilée à travers des points de contrôle spécifiés.

• La Section 13.3 discute de la forme Hermite, qui décrit une courbe en termes de ses points d’extrémité et des dérivées à ces points d’extrémité.

• La Section 13.4 montre comment la forme Bézier spécifie les points d’extrémité de la courbe, plus des points de contrôle intérieurs qui influencent la forme de la courbe mais ne sont pas interpolés.

• La Section 13.5 montre comment subdiviser une courbe en plus petits morceaux.

La seconde moitié du chapitre couvre les splines, qui sont des courbes plus longues créées en joignant ensemble plusieurs courbes successivement.

• La Section 13.6 introduit quelques notations, terminologies et concepts de base.

• La Section 13.7 discute de la façon de joindre des courbes Hermite ou Bézier en une spline.

• La Section 13.8 examine les conditions de continuité (lissage) pour les splines.

• La Section 13.9 termine la discussion sur les splines en examinant diverses méthodes pour déterminer automatiquement les tangentes d’une spline aux points de contrôle.

13.1Courbes polynomiales paramétriques

Nous nous concentrons ici presque exclusivement sur un type particulier de courbe, la courbe polynomiale paramétrique. Il est important de comprendre ce que les deux adjectifs paramétrique et polynomial signifient, donc la Section 13.1.1 et la Section 13.1.2 les discutent en détail. La Section 13.1.3 passe en revue quelques notations alternatives utiles. La Section 13.1.4 examine la droite, qui est un exemple particulièrement instructif de courbe polynomiale paramétrique. La Section 13.1.5 examine la relation entre les points d’extrémité de la courbe et les coefficients polynomiaux. La Section 13.1.6 discute des dérivées, telles que la vitesse et l’accélération, et montre comment elles sont liées aux vecteurs tangents et à la courbure locale.

13.1.1Courbes paramétriques

Le mot paramétrique dans la phrase « courbe polynomiale paramétrique » signifie (pas entièrement par surprise) que la courbe peut être décrite par une fonction d’un paramètre indépendant, auquel on attribue souvent le symbole $t$. Cette fonction de courbe est de la forme $\mathbf{p}(t)$, prenant une entrée scalaire (le paramètre $t$) et retournant le point sur la courbe correspondant à cette valeur de paramètre comme sortie vectorielle. La fonction $\mathbf{p}(t)$ trace la forme de la courbe au fur et à mesure que $t$ varie. Par exemple, considérons la description paramétrique classique d’un cercle unité,

$$\begin{matrix} \begin{matrix} {x(t)} & {= \cos(2\pi t),} \\ {y(t)} & {= \sin(2\pi t).} \\ \end{matrix} \\ \end{matrix}$$

Description paramétrique d’un cercle

Nous avons brièvement introduit la représentation paramétrique des primitives géométriques dans la Section 9.1. Prenons un moment pour passer en revue certaines des formes alternatives de cette section afin de comprendre les façons de décrire une courbe qui ne sont pas paramétriques. Une représentation implicite est une relation vraie pour tous les points de la forme décrite ; par exemple, le cercle unité peut être décrit implicitement comme l’ensemble des points satisfaisant $x^{2} + y^{2} = 1$. Une autre alternative à la forme paramétrique est la forme fonctionnelle, dans laquelle une coordonnée est exprimée comme une fonction de l’autre coordonnée ou des autres coordonnées ; par exemple, la moitié supérieure d’un cercle unité peut être décrite sous forme fonctionnelle comme $y = \sqrt{1 - x^{2}}$.

La courbe $\mathbf{p}(t)$ pourrait être infinie, notamment si nous ne posons aucune limite sur la plage de $t$. Il est souvent utile de sélectionner un segment fini en restreignant $t$ à un domaine borné particulier, le plus couramment le domaine $\lbrack 0,1\rbrack$. Il est naturel de désigner la direction « avant » comme la direction d’augmentation de $t$, donc la courbe « commence » à $t = 0$, « se termine » à $t = 1$, et consiste en tous les points entre les deux.

Parfois nous pensons à la fonction de position $\mathbf{p}(t)$ comme une seule fonction qui donne un résultat vectoriel ; d’autres fois il sera utile d’extraire la fonction pour une coordonnée spécifique. Par exemple, la fonction scalaire $x(t)$ spécifie la coordonnée $x$ de $\mathbf{p}(t)$, donc en deux dimensions $\mathbf{p}(t) = \left( x(t),\, y(t) \right)$. Notez que chaque coordonnée est spécifiée par une fonction qui dépend uniquement de la valeur du paramètre de sorte que chaque coordonnée est indépendante des autres. Nous travaillons dans le plan pour la majorité de ce chapitre car presque tous les aspects importants des courbes paramétriques peuvent être démontrés en 2D et, en général, l’extension en trois dimensions est directe.

13.1.2Courbes polynomiales

Maintenant que nous savons ce que signifie l’adjectif paramétrique, tournons notre attention vers le second mot important, polynomial. Une courbe paramétrique polynomiale est une fonction de courbe paramétrique $\mathbf{p}(t)$ qui peut être écrite comme un polynôme en $t$ :

Forme paramétrique polynomiale de degré arbitraire  $\mathbf{n}$

$$\mathbf{p}(t) = \mathbf{c}_{0} + \mathbf{c}_{1}t + \mathbf{c}_{2}t^{2} + \cdots + \mathbf{c}_{n - 1}t^{n - 1} + \mathbf{c}_{n}t^{n}.$$

Le nombre $n$ est appelé le degré du polynôme. Les polynômes de degré plus élevé sont plus flexibles dans le sens où ils peuvent décrire des courbes avec plus d’« ondulations ». Cependant, parfois des « ondulations » supplémentaires apparaissent que nous ne voulons pas ;1 plus à ce sujet dans la Section 13.6.

Nous avons déjà vu un exemple de fonction de courbe paramétrique mais non polynomiale—le cercle paramétrique donné par l’Équation (13.1). Les expressions pour $x(t)$ et $y(t)$ ne sont pas des polynômes car elles utilisent des fonctions trigonométriques. Un cercle complet ne peut pas être décrit sous forme polynomiale paramétrique, bien qu’un arc circulaire puisse être décrit par une courbe rationnelle. Une courbe rationnelle est essentiellement le résultat de la division d’une courbe par une autre, un peu comme la géométrie projective des coordonnées homogènes (voir la Section 6.4.1). La courbe au dénominateur est une courbe 1D. Les courbes rationnelles ne sont pas aussi courantes dans les jeux vidéo que les courbes polynomiales simples et ne sont pas discutées dans ce livre.

Ce qui nous intéresse le plus sont les courbes polynomiales paramétriques de degré 3, connues sous le nom de courbes cubiques. Les courbes cubiques sont celles qui peuvent être exprimées sous la forme indiquée dans l’Équation (13.2).

Courbe cubique en forme monomiale

$$\begin{matrix} {\mathbf{p}(t) = \mathbf{c}_{0} + \mathbf{c}_{1}t + \mathbf{c}_{2}t^{2} + \mathbf{c}_{3}t^{3}.} \\ \end{matrix}$$

Cette méthode de description des courbes est souvent appelée la forme monomiale ou la forme puissance, pour souligner le fait que la courbe est spécifiée en listant les coefficients des puissances de $t$. Les Sections 13.2–13.4 discutent d’autres méthodes de description d’une courbe avec des données géométriques plus directes, comme une liste de points de contrôle par lesquels la courbe doit passer ou que la courbe doit approcher. Ces autres formes sont encore des courbes polynomiales dans le sens où elles peuvent être converties en forme monomiale.

Une fois que nous avons les coefficients, il est facile de reconstruire la courbe en évaluant la fonction $\mathbf{p}(t)$ pour différentes valeurs de $t$. Par exemple, disons que nous voulons déplacer une plateforme le long d’un chemin dans un jeu vidéo. Notre acteur de plateforme aurait une variable d’état pour mémoriser sa position paramétrique $t$ le long du chemin, et à chaque pas de temps de simulation, nous mettrions à jour $t$ et définirons la position de la plateforme à $\mathbf{p}(t)$.

Supposons que nous devons afficher une courbe. Une façon simple de faire cela est de l’approximer avec, disons, 10 segments de ligne, en échantillonnant la courbe à $t = 0,\frac{1}{10},\frac{2}{10},\ldots,\frac{9}{10},1$ et en dessinant des segments de ligne entre des points d’échantillonnage consécutifs. Nous pouvons réduire l’erreur dans l’approximation à n’importe quel seuil souhaité simplement en utilisant plus de points d’échantillonnage. Nous pouvons faire bien mieux que cette approche naïve en subdivisant de manière adaptative la courbe, en utilisant plus de segments dans les parties « plus courbées » et moins dans les parties « plus droites ».

Mais d’où viennent les coefficients $\mathbf{c}_{0},\mathbf{c}_{1},\mathbf{c}_{2},\mathbf{c}_{3}$ ? Comment pouvons-nous les définir pour concevoir une courbe particulière ? En général, la forme monomiale est particulièrement mal adaptée à cette tâche, donc nous utilisons d’autres formes et les convertissons en forme monomiale lorsque c’est approprié. (Dans de nombreux cas, nous n’avons pas besoin du tout de la forme monomiale !) Avant de discuter de ces autres formes, cependant, nous devons introduire quelques notations et concepts supplémentaires sur les courbes.

13.1.3Notation matricielle

Nous pouvons réécrire la forme monomiale (l’Équation (13.2)) de plusieurs façons différentes. Il est utile de pouvoir référencer un coefficient pour une coordonnée particulière. Par exemple, en 2D utilisons la notation $\mathbf{c}_{i} = \begin{bmatrix} c_{1,i} & c_{2,i} \\ \end{bmatrix}$ de sorte que nous avons un polynôme par coordonnée :

Courbe cubique 2D en forme monomiale développée

$$\begin{matrix} {x(t)} & {= c_{1,0} + c_{1,1}t + c_{1,2}t^{2} + c_{1,3}t^{3},} \\ {y(t)} & {= c_{2,0} + c_{2,1}t + c_{2,2}t^{2} + c_{2,3}t^{3}.} \\ \end{matrix}$$

Certains livres aiment écrire cela plus compactement en utilisant la notation matricielle. Mettons les coefficients dans une matrice $\mathbf{C}$ et créons un vecteur colonne $\mathbf{t}$ à partir des puissances de $t$, tel que $\mathbf{t}_{i} = t^{i - 1}$ :

$$\begin{matrix} \mathbf{C} & {= \begin{bmatrix} c_{1,0} & c_{1,1} & c_{1,2} & c_{1,3} \\ c_{2,0} & c_{2,1} & c_{2,2} & c_{2,3} \\ \end{bmatrix},} & \mathbf{t} & {= \begin{bmatrix} t^{0} \\ t^{1} \\ t^{2} \\ t^{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ t \\ t^{2} \\ t^{3} \\ \end{bmatrix}.} & & \\ \end{matrix}$$

Maintenant nous pouvons exprimer notre fonction de courbe $\mathbf{p}(t)$ comme un seul produit matriciel :

Courbe cubique 2D en forme monomiale, exprimée comme un produit matriciel

$$\begin{matrix} {\mathbf{p}(t) = \mathbf{C}\mathbf{t} = \begin{bmatrix} c_{1,0} & c_{1,1} & c_{1,2} & c_{1,3} \\ c_{2,0} & c_{2,1} & c_{2,2} & c_{2,3} \\ \end{bmatrix}\begin{bmatrix} 1 \\ t \\ t^{2} \\ t^{3} \\ \end{bmatrix}.} \\ \end{matrix}$$

N’essayez pas encore d’appliquer des interprétations géométriques. Le vecteur $\mathbf{t}$ ne doit pas être interprété comme un point dans l’espace, et la matrice $\mathbf{C}$ n’est pas une matrice de transformation. Bien que nous soyons sur le point d’apprendre comment extraire la signification géométrique de $\mathbf{C}$, les techniques sont très différentes de celles apprises dans les chapitres précédents. Pour l’instant, soyons simplement heureux d’utiliser la notation matricielle uniquement pour des raisons de compacité.

La matrice $\mathbf{C}$ doit être aussi « haute » que le nombre de dimensions des données ; par exemple, trois si nous avons des données 3D. Cependant, nous n’avons pas besoin de faire référence à des coordonnées spécifiques $x$, $y$, ou $z$ souvent dans ce chapitre car la plupart des idées fonctionnent de la même façon en 3D ou en 2D (ou même en 1D !). Nous pouvons simplement laisser chaque coefficient $\mathbf{c}_{i}$ sous forme vectorielle et supposer qu’il est un vecteur de la dimension appropriée, de sorte que chaque $\mathbf{c}_{i}$ correspond à une seule colonne de $\mathbf{C}$ :

Coefficients comme vecteurs colonnes

$$\begin{matrix} \mathbf{C} & {= \begin{bmatrix} | & | & | & | \\ \mathbf{c}_{0} & \mathbf{c}_{1} & \mathbf{c}_{2} & \mathbf{c}_{3} \\ | & | & | & | \\ \end{bmatrix},} & {\mathbf{p}(t)} & {= \mathbf{C}\mathbf{t} = \begin{bmatrix} | & | & | & | \\ \mathbf{c}_{0} & \mathbf{c}_{1} & \mathbf{c}_{2} & \mathbf{c}_{3} \\ | & | & | & | \\ \end{bmatrix}\begin{bmatrix} 1 \\ t \\ t^{2} \\ t^{3} \\ \end{bmatrix}.} \\ \end{matrix}$$

Lorsqu’on traite un polynôme de degré plus élevé, la matrice $\mathbf{C}$ est plus large et le vecteur puissance $\mathbf{t}$ est plus grand, car nous avons plus de coefficients et plus de puissances de $t$. Cela n’a pas seulement du sens, c’est la règle : pour que le produit $\mathbf{C}\mathbf{t}$ soit licite selon les règles de l’algèbre linéaire, le nombre de colonnes dans $\mathbf{C}$ doit correspondre au nombre de lignes dans $\mathbf{t}$.

13.1.4Deux types triviaux de courbes

Bien que vous lisiez cette section parce que vous voulez apprendre à dessiner une courbe, permettez une brève digression pour mentionner deux types triviaux de « courbes » : un segment de droite et un point.

Nous avons montré comment représenter un segment de droite paramétriquement dans la Section 9.2 lorsque nous avons discuté des rayons. Considérons un rayon du point $\mathbf{p}_{0}$ au point $\mathbf{p}_{1}$. Si nous laissons $\mathbf{d}$ être le vecteur delta $\mathbf{p}_{1} - \mathbf{p}_{0}$, alors le rayon est exprimé paramétriquement comme

Segment de droite paramétrique

$$\begin{matrix} {\mathbf{p}(t) = \mathbf{p}_{0} + \mathbf{d}t.} \\ \end{matrix}$$

Observez que c’est un polynôme du type que nous avons considéré, où $\mathbf{c}_{0} = \mathbf{p}_{0}$, $\mathbf{c}_{1} = \mathbf{d}$, et les autres coefficients sont nuls. En d’autres termes, cette courbe linéaire est une courbe polynomiale de degré 1.

Aussi ennuyeuses que soient les droites, il y a une forme encore moins intéressante qui peut être représentée sous forme polynomiale paramétrique : le point. En abaissant le degré du polynôme de 1 à 0, on obtient une soi-disant courbe constante. Dans ce cas, la fonction $\mathbf{p}(t) = \mathbf{c}_{0}$ retourne toujours la même valeur, résultant en une « courbe » qui est un seul point stationnaire.

13.1.5Points d’extrémité en forme monomiale

Clairement, l’une des propriétés les plus basiques d’une courbe que nous voulons contrôler sont les emplacements de son début et de sa fin, $\mathbf{p}(0)$ et $\mathbf{p}(1)$, respectivement. Voyons à quoi ressemble $\mathbf{p}(t)$ aux points d’extrémité. Nous utiliserons le cas cubique comme exemple. À $t = 0$, nous avons

$\mathbf{c}_{0}$ spécifie le point de départ

$$\mathbf{p}(0) = \mathbf{c}_{0} + \mathbf{c}_{1}(0) + \mathbf{c}_{2}(0)^{2} + \mathbf{c}_{3}(0)^{3} = \mathbf{c}_{0}.$$

En d’autres termes, $\mathbf{c}_{0}$ spécifie le point de départ de la courbe. Voyons maintenant ce qui se passe à la fin de la courbe à $t = 1$ :

Le point d’extrémité est la somme des coefficients

$$\mathbf{p}(1) = \mathbf{c}_{0} + \mathbf{c}_{1}(1) + \mathbf{c}_{2}(1)^{2} + \mathbf{c}_{3}(1)^{3} = \mathbf{c}_{0} + \mathbf{c}_{1} + \mathbf{c}_{2} + \mathbf{c}_{3}.$$

Donc le point d’extrémité de la courbe est donné par la somme des coefficients.

13.1.6Vitesses et tangentes

Nous pouvons penser aux courbes comme étant soit statiques soit dynamiques. Dans le sens statique, une courbe définit une forme. Nous opérons dans ce mode de pensée lorsque nous utilisons une courbe pour décrire la coupe transversale d’une aile d’avion ou une portion de la lettre « S » dans la police Times Roman. Dans le sens dynamique, une courbe peut être une trajectoire ou un chemin d’un objet dans le temps, avec le paramètre $t$ comme « temps » et la fonction de position $\mathbf{p}(t)$ décrivant la position d’une particule au temps $t$ alors qu’elle se déplace le long du chemin.

Si nous considérons uniquement la forme statique de la courbe, alors le timing de la courbe n’a pas d’importance et notre tâche est un peu plus facile. Par exemple, lors de la définition d’une forme, peu importe quel point d’extrémité est considéré comme le « début » et lequel est la « fin » ; mais si nous utilisons la courbe pour définir un chemin parcouru dans le temps, alors il importe beaucoup où le chemin commence et où il se termine.

En utilisant le cadre mental dynamique et en pensant aux courbes comme des chemins et pas seulement des formes, certaines questions naturelles à poser sont : « Dans quelle direction la particule se déplace-t-elle à un moment donné ? » « À quelle vitesse se déplace-t-elle ? » Ces questions peuvent être répondues si nous créons une autre fonction $\mathbf{v}(t)$ qui décrit la vitesse instantanée de la particule au temps $t$.

L’expression « vitesse instantanée » implique que la vitesse change au fil du temps. Donc l’étape logique suivante est de demander : « À quelle vitesse la vitesse change-t-elle ? » Ainsi il est également utile de définir une fonction d’accélération instantanée $\mathbf{a}(t)$ qui décrit le taux auquel la vitesse de la particule change au temps $t$.

Si vous avez suivi au moins un semestre de calcul infinitésimal, ou si vous avez lu le Chapitre 11, vous devriez reconnaître que la fonction de vitesse $\mathbf{v}(t)$ est la première dérivée de la fonction de position $\mathbf{p}(t)$ parce que la vitesse mesure le taux de changement de position dans le temps. De même, la fonction d’accélération $\mathbf{a}(t)$ est la dérivée de la fonction de vitesse $\mathbf{v}(t)$ parce que l’accélération mesure le taux de changement de la vitesse dans le temps.

Nous considérons des courbes où $\mathbf{p}(t)$ est un polynôme en $t$ ici, donc les dérivées sont trivialement obtenues. Les fonctions de position, de vitesse et d’accélération pour les polynômes de degré arbitraire $n$ sont

La vitesse et l’accélération sont les première et seconde dérivées, vous vous souvenez ?

$$\begin{matrix} {\mathbf{p}(t)} & {= \mathbf{c}_{0} + \mathbf{c}_{1}t + \mathbf{c}_{2}t^{2} + \cdots + \mathbf{c}_{n - 1}t^{n - 1} + \mathbf{c}_{n}t^{n},} \\ {\mathbf{v}(t) = \overset{˙}{\mathbf{p}}(t)} & {= \mathbf{c}_{1} + 2\mathbf{c}_{2}t + \cdots + (n - 1)\mathbf{c}_{n - 1}t^{n - 2} + n\mathbf{c}_{n}t^{n - 1},} \\ {\mathbf{a}(t) = \overset{˙}{\mathbf{v}}(t) = \overset{¨}{\mathbf{p}}(t)} & {= 2\mathbf{c}_{2} + \cdots + (n - 1)(n - 2)\mathbf{c}_{n - 1}t^{n - 3} + n(n - 1)\mathbf{c}_{n}t^{n - 2}.} \\ \end{matrix}$$

Les dérivées des courbes cubiques sont particulièrement remarquables et apparaissent plusieurs fois dans ce chapitre.

Vitesse et accélération de la courbe monomiale cubique

$$\begin{matrix} {\mathbf{p}(t)} & {= \mathbf{c}_{0} + \mathbf{c}_{1}t + \mathbf{c}_{2}t^{2} + \mathbf{c}_{3}t^{3},} \\ {\mathbf{v}(t) = \overset{˙}{\mathbf{p}}(t)} & {= \mathbf{c}_{1} + 2\mathbf{c}_{2}t + 3\mathbf{c}_{3}t^{2},} \\ {\mathbf{a}(t) = \overset{˙}{\mathbf{v}}(t) = \overset{¨}{\mathbf{p}}(t)} & {= 2\mathbf{c}_{2} + 6\mathbf{c}_{3}t.} \\ \end{matrix}$$

Examinons maintenant la vitesse et l’accélération dans le cas particulier d’un rayon paramétrique. En appliquant les fonctions de vitesse et d’accélération des Équations (13.5) et (13.6) à la paramétrisation originale d’un rayon de l’Équation (13.3), on obtient

Vitesse et accélération d’un rayon

$$\begin{matrix} {\mathbf{p}(t)} & {= \mathbf{p}_{0} + \mathbf{d}t,} \\ {\mathbf{v}(t)} & {= \mathbf{c}_{1} + 2\mathbf{c}_{2}t + 3\mathbf{c}_{3}t^{2} = \mathbf{d},} \\ {\mathbf{a}(t)} & {= 2\mathbf{c}_{2} + 6\mathbf{c}_{3}t = 0.} \\ \end{matrix}$$

Comme on s’y attendait, la vitesse est constante ; il n’y a pas d’accélération.

Parfois deux courbes définissent la même forme mais des chemins différents (voir la Figure 13.1). Nous avons déjà mentionné un exemple de cela : si nous parcourons le chemin en sens inverse, il trace toujours la même forme. Une façon plus générale de générer des chemins alternatifs qui tracent la même forme est de reparamétriser la courbe. Par exemple, reparamétrisons notre segment de droite $\mathbf{p}(t) = \mathbf{p}_{0} + \mathbf{d}t$. Nous allons créer une nouvelle fonction $s(t) = t^{2}$ et voir à quoi ressemble $\mathbf{p}(s(t))$ :

$$\mathbf{p}(s(t)) = \mathbf{p}(t^{2}) = \mathbf{p}_{0} + \mathbf{d}t^{2}.$$

Figure 13.1 Deux courbes qui définissent la même « forme », mais pas le même « chemin »

Notez que les deux courbes dans la Figure 13.1 définissent la même forme statique, mais des chemins différents. À gauche, la particule se déplace à vitesse constante, mais à droite elle commence lentement et accélère jusqu’à la fin.

Si nous utilisons une courbe comme forme et non comme chemin, alors cette reparamétrisation n’a pas d’effet visible. Mais cela ne signifie pas que les dérivées de la courbe sont sans importance dans le contexte de la conception de formes. Imaginez que nous créons une police de caractères en utilisant une courbe pour définir un segment de la lettre S. Dans cette situation, nous n’aurions peut-être pas à nous soucier de la vitesse en un point quelconque, mais nous nous soucierions beaucoup de la tangente de la ligne en un point donné. La tangente en un point est la direction dans laquelle la courbe se déplace en ce point, la ligne qui effleure juste la courbe. La tangente est essentiellement la vitesse normalisée de la courbe. Définissons formellement la tangente d’une courbe comme le vecteur unitaire pointant dans la même direction que la vitesse :

Le vecteur tangent

$$\mathbf{t}(t) = \hat{\mathbf{v}}(t) = \frac{\mathbf{v}(t)}{\parallel {\mathbf{v}(t)} \parallel}.$$

Les dérivées d’ordre supérieur ont également une signification géométrique. La dérivée seconde est liée à la courbure, qui est parfois notée $\kappa$, la lettre grecque minuscule kappa. Nous pouvons définir une mesure de courbure en considérant un cercle d’un rayon donné. Un cercle de rayon $r$ a une courbure égale à $\kappa = 1/r$ partout sur le cercle. Une portion droite d’une courbe a une courbure nulle, ce qui peut être interprété comme la courbure d’un cercle de rayon infini. La courbure est calculée par la formule

Courbure

$$\kappa(t) = \frac{\parallel {\mathbf{v}(t) \times \mathbf{a}(t)} \parallel}{{\parallel {\mathbf{v}(t)} \parallel}^{3}}.$$

13.2Interpolation polynomiale

Vous êtes probablement déjà familier avec l’interpolation linéaire. Étant donné deux valeurs « extrémités », créer une fonction qui évolue à un taux constant (spatialement, en ligne droite) de l’une à l’autre. Nous disons que la fonction interpole les deux points de contrôle, ce qui signifie qu’elle passe par les points de contrôle et peut être utilisée pour calculer des valeurs intermédiaires.

L’interpolation polynomiale est similaire. Étant donné une série de points de contrôle, notre objectif est de construire un polynôme qui les interpole. Le degré du polynôme dépend du nombre de points de contrôle. Un polynôme de degré $n$ peut être fait pour interpoler $n + 1$ points de contrôle. Par exemple, l’interpolation linéaire est simplement une interpolation polynomiale de premier degré. Nous sommes principalement intéressés par les courbes cubiques (de troisième degré) dans ce chapitre, donc nous créons des polynômes qui interpolent quatre points de contrôle.

Dans le contexte de la conception de courbes, dire qu’une courbe interpole des points de contrôle est de mettre l’accent spécifique sur le fait que la courbe passe à travers les points de contrôle. Cela contraste avec une courbe qui simplement approxime les points de contrôle, ce qui signifie qu’elle ne passe pas à travers les points mais est attirée vers eux d’une certaine façon. Nous utilisons le mot « nœud » pour faire référence aux points de contrôle qui sont interpolés, évoquant la métaphore d’une corde avec des nœuds dedans. Il semblerait au premier abord qu’un schéma d’interpolation rendrait tout schéma d’approximation obsolète, mais nous verrons que les techniques d’approximation ont leurs avantages.

L’interpolation polynomiale est un problème classique avec plusieurs solutions bien étudiées. Comme ce livre est sur les mathématiques 3D, nous abordons la discussion principalement en termes géométriques, mais sachez que la plupart de la littérature sur l’interpolation polynomiale adopte une vue plus générale, car la tâche d’ajuster une fonction à un ensemble de points de données a une applicabilité large.

Pour faciliter la discussion, nous utilisons un exemple particulier de courbe, montré dans la Figure 13.2. C’est un peu comme un S mis sur le côté. Nous avons marqué les quatre points de contrôle sur la courbe que nous essayons d’interpoler. Nous avons choisi de placer les coordonnées $y$ sur l’intervalle $\lbrack 2,3\rbrack$ pour des raisons qui seront utiles plus tard.

@l@ $\begin{matrix} t & {x(t)} & {y(t)} \\ 0 & 0 & 2 \\ {1/3} & {1/3} & 3 \\ {2/3} & {2/3} & 2 \\ 1 & 1 & 3 \\ \end{matrix}$

Figure 13.2Une courbe exemple et quatre points de contrôle. Peut-on dessiner cette forme ?

Notez que nous devons spécifier non seulement la position de chaque point de contrôle (les coordonnées $x$ et $y$), mais le temps auquel nous voulons que la courbe atteigne ce point de contrôle (la valeur $t$). Nous utilisons la notation que les valeurs indépendantes (les « valeurs de temps ») des points de contrôle sont nommées $t_{1},t_{2},\ldots,t_{n}$ et les variables dépendantes (les valeurs de coordonnées spatiales à ces moments) sont $y_{1},y_{2},\ldots,y_{n}.$ Le symbole $P$ représente la fonction polynomiale que nous cherchons : $y_{i} = P(t_{i})$.

Le tableau des valeurs de temps $t_{1}\ldots t_{n}$ est connu dans d’autres contextes sous le nom de vecteur de nœuds ou séquence de nœuds. Le mot « vecteur » indique que la séquence des valeurs $t$ est un tableau de nombres, et non pas que ces nombres forment un vecteur au sens géométrique du terme. Si les $t$s sont espacés uniformément comme dans notre exemple, alors nous avons un vecteur de nœuds uniforme ; sinon, nous disons que le vecteur de nœuds est non uniforme. (Pour éviter toute confusion, précisons que le vecteur de nœuds est la séquence des valeurs $t$, et non pas la séquence des points de contrôle.)

Qu’en est-il de la coordonnée $x$ ? Comme les coordonnées $x$ et $y$ sont indépendantes l’une de l’autre, une application générale d’ajustement de courbe 2D implique deux problèmes unidimensionnels séparés. Hormis le fait que les deux problèmes utilisent le même vecteur de nœuds, les coordonnées sont sinon sans rapport. Même si la Figure 13.2 peut ressembler à une courbe 2D, elle est plus correctement interprétée comme un graphique d’une coordonnée (la coordonnée $y$) en fonction du temps. Nous avons choisi comme exemple de courbe un S mis sur le côté, plutôt qu’un S dans son orientation normale, puisque ce dernier n’est pas le graphique d’une fonction (techniquement c’est appelé une relation car elle associe plus d’une valeur de $y$ à chaque valeur de $x$).

Cela dit, il y a deux façons d’interpréter la Figure 13.2. Nous pouvons l’interpréter soit comme une fonction 1D de $y(t)$, soit comme une courbe 2D, où l’une des coordonnées a la forme triviale $x = t$. C’est une source courante de confusion lorsqu’on regarde des diagrammes de courbes dans ce livre et ailleurs. Assurez-vous de prêter une attention particulière à l’axe horizontal pour être sûr de savoir s’il s’agit d’un graphique d’une coordonnée dans le temps ou d’une représentation de la courbe 2D qui inclut le comportement des deux coordonnées spatiales. La littérature traditionnelle sur l’interpolation polynomiale est surtout en termes abstraits de toute fonction de la forme $y = f(x)$. Dans ce contexte, $x$ serait la variable indépendante plutôt qu’une valeur dépendante comme c’est le cas pour nous. La notation que nous avons choisie évite le symbole $x$ et ses connotations associées.

Nous sommes maintenant prêts à répondre à une question que certains lecteurs pourraient se poser : « Je ne me soucie pas du moment où la courbe atteint les points, je veux juste une forme lisse qui passe par les points. » Malheureusement, cela ne définit pas une courbe de manière non ambiguë—nous devons fournir d’autres critères pour préciser la forme, et une façon de faire est d’associer des valeurs de temps à chaque point de contrôle. Dans les applications typiques d’interpolation polynomiale, nous voulons pouvoir spécifier les valeurs de la variable dépendante, car nous essayons d’ajuster une fonction à des points de données connus. Il existe des façons raisonnables de synthétiser cette information si nous ne l’avons pas—par exemple, en rendant la différence entre les valeurs $t$ adjacentes proportionnelle à la distance euclidienne entre les points de contrôle correspondants. Cependant, le fait général que l’interpolation polynomiale nous demande de fournir les valeurs $t$ alors que nous n’avons souvent pas de bonne façon de décider ce qu’elles devraient être est un présage de découvertes ultérieures.

Maintenant que nous avons établi les règles de base, essayons de créer cette courbe. Nous adoptons d’abord une approche géométrique dans la Section 13.2.1. Puis, dans la Section 13.2.2, nous examinons le problème d’une perspective mathématique légèrement plus abstraite.

13.2.1Algorithme d’Aitken

Notre première approche de l’interpolation polynomiale est une technique récursive due à Alexander Aitken (1895–1967). Comme beaucoup d’algorithmes récursifs, il fonctionne sur le principe de diviser pour régner. Pour résoudre un problème difficile, nous le divisons d’abord en deux (ou plus) problèmes plus faciles, résolvons les problèmes plus faciles indépendamment, puis combinons les résultats pour obtenir la solution au problème plus difficile. Dans ce cas, le problème « difficile » est de créer une courbe qui interpole $n$ points de contrôle. Nous divisons cette courbe en deux courbes « plus faciles » : (1) une qui interpole seulement les premiers $n - 1$ points, en ignorant le dernier point ; et (2) une autre qui interpole les derniers $n - 1$ points sans se soucier du premier point. Ensuite, nous mélangeons ces deux courbes ensemble.

Prenons le cas cubique important (troisième degré) comme exemple. Une courbe cubique a quatre points de contrôle $y_{1}\ldots y_{4}$ que nous souhaitons interpoler aux temps correspondants $t_{1}\ldots t_{4}$. En appliquant l’approche « diviser pour régner », nous divisons cela en deux problèmes plus petits : une courbe pour interpoler $y_{1}\ldots y_{3}$, et une autre courbe pour interpoler $y_{2}\ldots y_{4}$. Comme chacune de ces courbes a trois points de contrôle, ce sont des courbes quadratiques (de second degré). Bien sûr, l’ajustement de courbe quadratique est encore un problème « difficile » pour nous, et chaque courbe doit donc être subdivisée davantage.

Considérons la première courbe quadratique, entre $y_{1}$, $y_{2}$ et $y_{3}$. Nous subdivisons encore cette courbe en deux parties, la première partie entre $y_{1}$ et $y_{2}$ et l’autre partie entre $y_{2}$ et $y_{3}$. Ces deux courbes n’ont que deux points de contrôle chacune ; ce sont des segments de droite. Enfin, un problème vraiment « facile » !

Puisque nous avons beaucoup de courbes à ce stade, nous devons inventer une notation pour elles. Nous notons $y_{i}^{1}(t)$ la courbe linéaire entre $y_{i}$ et $y_{i + 1}$, la notation $y_{i}^{2}(t)$ désigne la courbe quadratique entre $y_{i}$ et $y_{i + 2}$, et ainsi de suite. En d’autres termes, l’exposant indique le niveau de récursion dans l’algorithme diviser pour régner (et aussi le degré du polynôme), et l’indice s’indexe le long de la longueur de la courbe.

Examinons la première courbe quadratique $y_{1}^{2}(t)$ qui interpole $y_{1}$, $y_{2}$ et $y_{3}$. Elle est formée en mélangeant ensemble les deux droites contenant les deux premiers segments linéaires. Un exemple d’un tel mélange est montré dans la Figure 13.3. (Cette figure n’utilise pas les données de notre exemple S ; c’est un cas moins symétrique qui illustre mieux le processus de mélange.) Notez que chaque segment de courbe est un intervalle d’une courbe infinie qui est définie pour toute valeur de $t$.

Figure 13.3 Création d’une courbe quadratique comme mélange de deux segments linéaires selon l’algorithme d’Aitken

Examinons maintenant les mathématiques derrière cela. Tout est interpolation linéaire. Les plus faciles sont les segments linéaires, qui sont définis par interpolation linéaire entre les points de contrôle adjacents :

Interpolation linéaire entre deux points de contrôle

$$\begin{matrix} {y_{1}^{1}(t)} & {= \frac{(t_{2} - t)y_{1} + (t - t_{1})y_{2}}{t_{2} - t_{1}},} & {y_{2}^{1}(t)} & {= \frac{(t_{3} - t)y_{2} + (t - t_{2})y_{3}}{t_{3} - t_{2}}.} \\ \end{matrix}$$

La courbe quadratique est un peu plus compliquée. Nous interpolons linéairement entre les segments de droite :

L’interpolation linéaire de droites donne une courbe quadratique

$$y_{1}^{2}(t) = \frac{(t_{3} - t)\left\lbrack y_{1}^{1}(t) \right\rbrack + (t - t_{1})\left\lbrack y_{2}^{1}(t) \right\rbrack}{t_{3} - t_{1}}.$$

Nous espérons que vous pouvez voir le motif—chaque courbe est le résultat de l’interpolation linéaire de deux courbes de degré inférieur. L’algorithme d’Aitken peut être résumé succinctement comme une relation de récurrence.

Algorithme d’Aitken

$$\begin{matrix} {y_{i}^{0}(t)} & {= y_{i},} \\ {y_{i}^{j}(t)} & {= \frac{(t_{i + j} - t)\left\lbrack y_{i}^{j - 1}(t) \right\rbrack + (t - t_{i})\left\lbrack y_{i + 1}^{j - 1}(t) \right\rbrack}{t_{i + j} - t_{i}}.} \\ \end{matrix}$$

L’algorithme d’Aitken fonctionne parce que, à chaque niveau, les deux courbes mélangées touchent déjà les points de contrôle du milieu. Les deux points de contrôle les plus extérieurs ne sont touchés que par une courbe ou l’autre, mais pour ces valeurs de $t$, les poids de mélange atteignent leurs valeurs extrêmes et tout le poids est donné à la courbe qui touche le point de contrôle.

Figure 13.4Deux niveaux de l’algorithme d’Aitken

Maintenant que nous avons l’idée de base, appliquons-la à notre S mis sur le côté. La Figure 13.4 montre l’algorithme d’Aitken au travail avec nos quatre points de données. Sur la gauche, les trois segments linéaires sont mélangés pour former deux segments quadratiques. Sur la droite, les deux courbes quadratiques se mélangent, donnant le résultat final que nous cherchions : une spline cubique qui interpole les quatre points de contrôle.

Nous avons donc réussi à interpoler les quatre points de contrôle, et accompli l’objectif fixé au début de cette section, n’est-ce pas ? Eh bien, pas tout à fait. Bien que notre courbe passe par les points de contrôle, ce n’est pas vraiment la courbe que nous voulions. Si nous comparons la courbe sur le côté droit de la Figure 13.4 avec la courbe que nous avions l’intention de créer au début de cette section dans la Figure 13.2, nous voyons que la courbe produite par l’algorithme d’Aitken dépasse la valeur $y$ des deux points de contrôle du milieu. Nous avons découvert une vérité gênante.2

L’interpolation polynomiale ne nous donne pas vraiment le type de contrôle que nous voulons pour la conception de courbes dans des contextes géométriques.

Mais ne désespérez pas ! Nous avons appris plusieurs idées importantes qui seront utiles lorsque nous discuterons des courbes Bézier dans la Section 13.4 et des splines dans la Section 13.6. En fait, nous allons demander votre patience pour nous permettre d’étendre un peu la discussion sur l’interpolation polynomiale. C’est un peu comme regarder le film Titanic ; même si vous savez que le voyage se terminera tragiquement, vous pourriez quand même trouver quelque chose d’utile en chemin. Nous promettons que les autres techniques dans ce chapitre auront une valeur pratique aussi bien qu’éducative.

D’ailleurs, vous avez peut-être remarqué que nous n’avons pas vraiment calculé le polynôme $P$ qui produit la courbe. Travailler à travers ces mathématiques est direct, mais un peu fastidieux et pas très instructif. Le point important est que l’algorithme d’Aitken est un processus récursif de mélange de courbes et fonctionne par interpolation linéaire répétée. De plus, pourquoi s’embêter avec les détails alors que nous avons des ordinateurs pour résoudre les problèmes d’algèbre ?3 Cependant, vous n’avez pas à vous sentir lésé par des auteurs paresseux. Si vous voulez vraiment savoir quel est le polynôme (ou si vous voulez juste avoir l’impression d’en avoir pour votre argent), continuez à lire. Nous le découvrirons dans la prochaine section en utilisant une méthode différente qui est moins fastidieuse mathématiquement.

13.2.2Polynômes de base de Lagrange

La Section 13.2.1 a appliqué l’intuition géométrique au problème d’interpolation polynomiale et a abouti à l’algorithme d’Aitken. Maintenant nous abordons le sujet d’un point de vue mathématique plus abstrait.

Une approche mathématique au problème d’interpolation vient de l’algèbre linéaire.4 Chaque point de contrôle nous donne une équation, et chaque coefficient nous donne une inconnue. Ce système d’équations peut être mis dans une matrice $n \times n$,5 qui peut être résolue par des techniques standard telles que l’élimination gaussienne ou la décomposition LU. Ces techniques sont hors du cadre de ce livre, mais vous pouvez en apprendre plus dans pratiquement n’importe quel bon livre sur l’algèbre linéaire ou les méthodes numériques.

Résoudre une matrice est un processus de calcul relativement long, nécessitant $O(n^{3})$ temps pour une matrice $n \times n$ dans le pire cas. Heureusement, il existe des approches plus efficaces. Comme nous l’avons fait avec l’algorithme d’Aitken, nous résolvons un grand problème complexe en le divisant en une série de problèmes plus petits et plus simples, et en combinant ensuite ces résultats. L’algorithme d’Aitken est une procédure récursive, mais ici nous allons créer un problème « simple » par point de contrôle.

Ignorons les $y$’s pour l’instant et pensons seulement aux $t$’s. Et si nous pouvions créer un polynôme pour chaque nœud $t_{i}$ tel que le polynôme évalue à l’unité à ce nœud, mais pour tous les autres nœuds il évalue à zéro ? Si nous notons le $i$ième polynôme comme $\ell_{i}$, alors cette idée peut être exprimée en langage mathématique : $\ell_{i}(t_{i}) = 1$, et $\ell_{i}(t_{j}) = 0$ pour tout $j \neq i$. Par exemple, supposons $n = 4$. Alors nos polynômes auraient les valeurs suivantes aux nœuds :

$$\begin{matrix} {\ell_{1}(t_{1})} & {= 1,} & {\ell_{1}(t_{1})} & {= 0,} & {\ell_{3}(t_{1})} & {= 0,} & {\ell_{4}(t_{1})} & {= 0,} \\ {\ell_{1}(t_{2})} & {= 0,} & {\ell_{2}(t_{2})} & {= 1,} & {\ell_{3}(t_{2})} & {= 0,} & {\ell_{4}(t_{2})} & {= 0,} \\ {\ell_{1}(t_{3})} & {= 0,} & {\ell_{2}(t_{3})} & {= 0,} & {\ell_{3}(t_{3})} & {= 1,} & {\ell_{4}(t_{3})} & {= 0,} \\ {\ell_{1}(t_{4})} & {= 0,} & {\ell_{2}(t_{4})} & {= 0,} & {\ell_{3}(t_{4})} & {= 0,} & {\ell_{4}(t_{4})} & {= 1.} \\ \end{matrix}$$

Si nous étions capables de créer des polynômes avec les propriétés ci-dessus, nous pourrions les utiliser comme polynômes de base. Nous scalerions chaque polynôme de base $\ell_{i}$ par la valeur de coordonnée correspondante $y_{i}$, et additionnerions tous les polynômes mis à l’échelle :

Polynôme interpolant en forme de base de Lagrange

$$\begin{matrix} {P(t) = \sum\limits_{i = 1}^{n}y_{i}\ell_{i}(t) = y_{1}\ell_{1}(t) + y_{2}\ell_{2}(t) + \cdots + y_{n - 1}\ell_{n - 1}(t) + y_{n}\ell_{n}(t).} \\ \end{matrix}$$

Vous voudrez peut-être prendre un moment pour vous convaincre que ce polynôme interpole effectivement les points de contrôle, c’est-à-dire que $P(t_{i}) = y_{i}$.

Notez que les polynômes de base ne dépendent que du vecteur de nœuds (les $t$’s) et non des valeurs de coordonnées (les $y$’s). À cause de cela, un ensemble de polynômes de base peut être utilisé pour construire rapidement de multiples courbes avec le même vecteur de nœuds. C’est précisément la situation dans laquelle nous nous trouvons lorsque nous traitons une courbe 3D, qui est en réalité trois courbes unidimensionnelles qui partagent la même séquence de nœuds.

Bien sûr, tout cela fonctionnerait seulement si nous connaissions les polynômes de base, et trouver $\ell_{i}$ est lui-même un problème d’interpolation polynomiale. Cependant, les « points de données » que nous voulons que $\ell_{i}$ interpole sont tous soit 0 soit 1, donc $\ell_{i}$ peut être exprimé sous une forme simple. De tels polynômes de base sont appelés polynômes de base de Lagrange.6 Un polynôme de base de Lagrange7 $\ell_{i}$ pour le vecteur de nœuds $t_{1}\ldots t_{n}$ ressemble à l’Équation (13.8) :

Polynôme de base de Lagrange

$$\begin{matrix} {\ell_{i}(t)\ = \!\prod\limits_{\substack{1 \leq j \leq n, \\ j \neq i}}\!\frac{t - t_{j}}{t_{i} - t_{j}}\ = \ \frac{t - t_{0}}{t_{i} - t_{0}}\cdots\frac{t - t_{i - 1}}{t_{i} - t_{i - 1}}\ \frac{t - t_{i + 1}}{t_{i} - i_{i + 1}}\cdots\frac{t - t_{n}}{t_{i} - t_{n}}.} \\ \end{matrix}$$

Cette astuce fonctionne parce qu’au nœud $t_{i}$, tous les termes dans le produit valent 1, ce qui fait que l’expression entière évalue à 1, et à tout autre nœud, l’un des termes dans le produit est 0, ce qui fait que l’expression entière évalue à 0.

Appliquons cela à notre exemple de courbe S. Rappelons qu’elle utilisait le vecteur de nœuds uniforme $(0,\frac{1}{3},\frac{2}{3},1)$. Ici, nous travaillons le premier polynôme de base et présentons simplement les résultats pour les autres :

$$\begin{matrix} {\ell_{1}(t)} & {= \left( \frac{t - t_{2}}{t_{1} - t_{2}} \right)\left( \frac{t - t_{3}}{t_{1} - t_{3}} \right)\left( \frac{t - t_{4}}{t_{1} - t_{4}} \right) = \left( \frac{t - 1/3}{0 - 1/3} \right)\left( \frac{t - 2/3}{0 - 2/3} \right)\left( \frac{t - 1}{0 - 1} \right)} \\ & {= \left( \frac{3t - 1}{- 1} \right)\left( \frac{3t - 2}{- 2} \right)\left( \frac{t - 1}{- 1} \right) = \frac{(3t - 1)(3t - 2)(t - 1)}{- 2}} \\ & {= - (9/2)t^{3} + 9t^{2} - (11/2)t + 1,} \\ \end{matrix}$$

$$\begin{matrix} {\ell_{2}(t)} & {= (27/2)t^{3} - (45/2)t^{2} + 9t,} \\ {\ell_{3}(t)} & {= - (27/2)t^{3} + 18t^{2} - (9/2)t,} \\ {\ell_{4}(t)} & {= (9/2)t^{3} - (9/2)t^{2} + t.} \\ \end{matrix}$$

La Figure 13.5 montre à quoi ressemblent ces polynômes de base.

Figure 13.5Polynômes de base cubiques de Lagrange pour le vecteur de nœuds uniforme

Maintenant que nous avons les polynômes de base de Lagrange pour le vecteur de nœuds, insérons les valeurs $y$ de notre exemple de courbe S (la Figure 13.2) dans l’Équation (13.7) pour obtenir le polynôme d’interpolation complet :

$$\begin{matrix} {P(t)} & {= y_{1}\ell_{1}(t) + y_{2}\ell_{2}(t) + y_{3}\ell_{3}(t) + y_{4}\ell_{4}(t)} \\ & {= 2\lbrack - (9/2)t^{3} + 9t^{2} - (11/2)t + 1\rbrack + 3\lbrack(27/2)t^{3} - (45/2)t^{2} + 9t\rbrack} \\ & {\quad\quad + 2\lbrack - (27/2)t^{3} + 18t^{2} - (9/2)t\rbrack + 3\lbrack(9/2)t^{3} - (9/2)t^{2} + t\rbrack} \\ & {= - 9t^{3} + 18t^{2} - 11t + 2 + (81/2)t^{3} - (135/2)t^{2} + 27t} \\ & {\quad\quad - 27t^{3} + 36t^{2} - 9t + (27/2)t^{3} - (27/2)t^{2} + 3t} \\ & {= 18t^{3} - 27t^{2} + 10t + 2.} \\ \end{matrix}$$

Montrons ces résultats graphiquement. Tout d’abord, nous mettons à l’échelle chaque polynôme de base par la valeur de coordonnée correspondante, comme indiqué dans la Figure 13.6.

Enfin, l’addition des vecteurs de base mis à l’échelle donne le polynôme d’interpolation $P$, la courbe bleue en haut de la Figure 13.7.

Figure 13.6 Mise à l’échelle de chaque polynôme de base de Lagrange par la valeur de coordonnée correspondante

Figure 13.7 La courbe d’interpolation est la somme des polynômes de base mis à l’échelle

Nous utilisons le mot base dans polynôme de base pour souligner le fait que nous pouvons utiliser ces polynômes comme blocs de construction pour reconstruire absolument n’importe quel polynôme, étant donné les valeurs du polynôme aux nœuds. C’est le même concept de base qu’un vecteur de base (voir la Section 3.3.3) : tout vecteur arbitraire peut être décrit comme une combinaison linéaire des vecteurs de base. Dans notre cas, l’espace couvert par la base n’est pas un espace géométrique 3D, mais l’espace vectoriel de tous les polynômes possibles d’un certain degré, et les valeurs d’échelle pour chaque courbe sont les valeurs connues du polynôme aux nœuds.

Mais il y a une autre façon de comprendre la multiplication et la somme qui se passe. Au lieu de penser aux polynômes comme les blocs de construction et aux points de contrôle comme les facteurs d’échelle, nous pouvons voir chaque point de la courbe comme le résultat d’une moyenne pondérée des points de contrôle, où les polynômes de base fournissent les poids de mélange. Donc les points de contrôle sont les blocs de construction et les polynômes de base fournissent les facteurs d’échelle, bien que nous préférions être plus spécifiques et appeler ces facteurs d’échelle coordonnées barycentriques. Nous avons introduit les coordonnées barycentriques dans le contexte des triangles dans la Section 9.6.3, mais le terme fait référence à une technique générale de description d’une valeur comme une moyenne pondérée de points de données.

Nous pouvons penser aux polynômes de base comme des fonctions qui donnent des coordonnées barycentriques (poids de mélange).

Notez que certaines valeurs sont négatives ou supérieures à 1 sur certains intervalles, ce qui explique pourquoi l’interpolation polynomiale directe dépasse les points de contrôle. Quand toutes les coordonnées barycentriques sont dans la plage $\lbrack 0,1\rbrack$, le point résultant est garanti de se situer à l’intérieur de l’enveloppe convexe des points de contrôle. (L’enveloppe convexe est le plus petit polygone qui contient tous les points de contrôle. Elle « emballe » les points de contrôle, un peu comme si vous tendiez un élastique autour des points de contrôle et que vous le relâchiez.) Mais quand nous avons une coordonnée en dehors de cet intervalle, le point résultant pourrait s’étendre en dehors de l’enveloppe convexe. Dans le cadre de la conception de courbes géométriques, la garantie de l’enveloppe convexe est très utile. La Section 13.4 montre que les courbes Bézier offrent cette garantie à travers la base de Bernstein.

13.2.3Résumé de l’interpolation polynomiale

Nous avons abordé l’interpolation polynomiale de deux perspectives. L’algorithme d’Aitken est une approche géométrique basée sur l’interpolation linéaire répétée, et avec lui nous pouvons calculer un point sur la courbe pour un $t$ donné sans connaître le polynôme de la courbe. L’interpolation de Lagrange fonctionne en créant des fonctions de base qui ne dépendent que du vecteur de nœuds. Nous pouvons voir l’utilisation des polynômes de base de deux façons. Soit nous pouvons penser à mettre à l’échelle chaque polynôme de base par la valeur de coordonnée correspondante et ensuite les additionner tous, soit nous pouvons penser aux polynômes comme des fonctions qui calculent des coordonnées barycentriques utilisées comme poids de mélange dans une simple moyenne pondérée des points de coordonnées.

Les deux méthodes donnent la même courbe lorsqu’elles sont données les mêmes données. De plus, ce polynôme est unique—aucun autre polynôme du même degré n’interpole les points de données. Un argument informel pour expliquer pourquoi c’est vrai est le suivant : un polynôme de degré $n$ a $n + 1$ degrés de liberté, correspondant aux $n + 1$ coefficients en forme monomiale. Par conséquent, le polynôme de degré $n$ qui interpole $n + 1$ points de contrôle doit être unique. (Farin [1] donne un argument plus rigoureux.)

Pour les besoins de la conception de courbes, l’interpolation polynomiale n’est pas idéale, principalement en raison de notre incapacité à contrôler le dépassement. Le dépassement est garanti par le fait que les polynômes de base de Lagrange sous-jacents ne sont pas restreints à l’intervalle unité $\lbrack 0,1\rbrack$, et la courbe s’échappe de l’enveloppe convexe des points de contrôle.

L’interpolation polynomiale directe trouve des applications limitées dans les jeux vidéo, mais notre étude a introduit les thèmes de l’interpolation linéaire répétée et des polynômes de base. Nous avons également vu un peu de la belle dualité entre les deux techniques.

13.3Courbes de Hermite

L’interpolation polynomiale tente de contrôler l’intérieur de la courbe en faisant passer la courbe par des nœuds spécifiés. Cela ne fonctionne pas aussi bien que nous le voudrions, en raison de la tendance à osciller et à dépasser, alors essayons une approche différente. Nous voudrons toujours spécifier les positions des points d’extrémité, bien sûr. Mais au lieu de spécifier les positions intérieures à interpoler, contrôlons la forme de la courbe à travers les tangentes aux points d’extrémité. Une courbe ainsi spécifiée est dite courbe de Hermite ou une courbe en forme de Hermite, nommée en l’honneur de Charles Hermite8 (1822–1901).

La forme de Hermite spécifie une courbe en listant ses positions et dérivées de début et de fin. Une courbe cubique n’a que quatre coefficients, ce qui permet la spécification uniquement des premières dérivées, les vitesses aux points d’extrémité. Donc décrire une courbe cubique en forme de Hermite se résume aux quatre informations suivantes :

• La position de départ à $t = 0$,

• La première dérivée (vitesse initiale) à $t = 0$,

• La position finale à $t = 1$,

• La première dérivée (vitesse finale) à $t = 1$.

Appelons les positions de départ et de fin souhaitées $\mathbf{p}_{0}$ et $\mathbf{p}_{1}$ et les vitesses de départ et de fin $\mathbf{v}_{0}$ et $\mathbf{v}_{1}$. La Figure 13.8 montre quelques exemples de courbes de Hermite cubiques. Notez que les vecteurs de vitesse $\mathbf{v}_{0}$ et $\mathbf{v}_{1}$ ont été dessinés à un tiers de leur longueur réelle. Une raison de faire cela est d’économiser de l’espace, et une autre aura du sens plus tard une fois que nous apprendrons les courbes Bézier dans la Section 13.4.

Figure 13.8Quelques courbes cubiques de Hermite

Déterminer les coefficients monomiales à partir des valeurs de Hermite est un processus algébrique relativement direct de combinaison des équations précédemment discutées dans ce chapitre. Les quatre valeurs de Hermite peuvent être traduites dans le système d’équations suivant :

$$\begin{matrix} {\mathbf{p}(0)} & {= \mathbf{p}_{0}} & {\Longrightarrow} & & \mathbf{c}_{0} & {= \mathbf{p}_{0},} & & \\ {\mathbf{v}(0)} & {= \mathbf{v}_{0}} & {\Longrightarrow} & & \mathbf{c}_{1} & {= \mathbf{v}_{0},} & & \\ {\mathbf{v}(1)} & {= \mathbf{v}_{1}} & {\Longrightarrow} & & {\mathbf{c}_{1} + 2\mathbf{c}_{2} + 3\mathbf{c}_{3}} & {= \mathbf{v}_{1},} & & \\ {\mathbf{p}(1)} & {= \mathbf{p}_{1}} & {\Longrightarrow} & & {\mathbf{c}_{0} + \mathbf{c}_{1} + \mathbf{c}_{2} + \mathbf{c}_{3}} & {= \mathbf{p}_{1}.} & & \\ \end{matrix}$$

Système d’équations pour les conditions de Hermite

Les Équations (13.9) et (13.12), qui spécifient les points d’extrémité, reprennent simplement ce que nous avons dit dans la Section 13.1.5. Les Équations (13.10) et (13.11), qui spécifient les vitesses, découlent directement des équations de vitesse pour un polynôme cubique (l’Équation (13.5)). L’ordre dans lequel ces équations sont listées est une convention utilisée dans d’autres ouvrages sur les courbes, et l’utilité de cette convention deviendra apparente plus tard dans ce chapitre.

La résolution de ce système d’équations donne une méthode pour calculer les coefficients monomiales à partir des positions et dérivées de Hermite :

Conversion de la forme de Hermite en forme monomiale

$$\begin{matrix} \mathbf{c}_{0} & {= \mathbf{p}_{0},} \\ \mathbf{c}_{1} & {= \mathbf{v}_{0},} \\ \mathbf{c}_{2} & {= - 3\mathbf{p}_{0} - 2\mathbf{v}_{0} - \mathbf{v}_{1} + 3\mathbf{p}_{1},} \\ \mathbf{c}_{3} & {= 2\mathbf{p}_{0} + \mathbf{v}_{0} + \mathbf{v}_{1} - 2\mathbf{p}_{1}.} \\ \end{matrix}$$

Nous pouvons également écrire ces équations dans la notation matricielle compacte introduite dans la Section 13.1.2. Rappelons que lorsque nous mettons les coefficients comme colonnes dans une matrice $\mathbf{C}$, et les puissances de $t$ dans le vecteur colonne $\mathbf{t}$, nous pouvons exprimer une courbe polynomiale comme le produit matriciel $\mathbf{C}\mathbf{t}$,

Nous pouvons écrire la forme monomiale en utilisant la notation matricielle, vous vous souvenez ?

$$\mathbf{p}(t) = \mathbf{C}\mathbf{t} = \begin{bmatrix} | & | & | & | \\ \mathbf{c}_{0} & \mathbf{c}_{1} & \mathbf{c}_{2} & \mathbf{c}_{3} \\ | & | & | & | \\ \end{bmatrix}\begin{bmatrix} 1 \\ t \\ t^{2} \\ t^{3} \\ \end{bmatrix},$$

où $\mathbf{p}(t)$ et chacun des vecteurs de coefficients $\mathbf{c}_{i}$ sont des vecteurs colonnes dont la hauteur correspond au nombre de dimensions géométriques (1D, 2D ou 3D). La hauteur de $\mathbf{t}$ correspond au nombre de $\mathbf{c}$’s, qui dépend du degré de la courbe.

La matrice de coefficients $\mathbf{C}$ peut être exprimée comme un produit matriciel en mettant les positions et vitesses de Hermite comme colonnes dans une matrice $\mathbf{P}$ et en multipliant par une matrice de conversion $\mathbf{H}$ :

Courbe cubique de Hermite en utilisant la notation matricielle

$$\mathbf{p}(t) = \mathbf{C}\mathbf{t} = \mathbf{P}\mathbf{H}\mathbf{t} = \begin{bmatrix} | & | & | & | \\ \mathbf{p}_{0} & \mathbf{v}_{0} & \mathbf{v}_{1} & \mathbf{p}_{1} \\ | & | & | & | \\ \end{bmatrix}\begin{bmatrix} 1 & 0 & {- 3} & 2 \\ 0 & 1 & {- 2} & 1 \\ 0 & 0 & {- 1} & 1 \\ 0 & 0 & 3 & {- 2} \\ \end{bmatrix}\begin{bmatrix} 1 \\ t \\ t^{2} \\ t^{3} \\ \end{bmatrix}.$$

Nous pouvons interpréter le produit $\mathbf{P}\mathbf{H}\mathbf{t}$ de deux façons. Si nous le regroupons comme $\mathbf{P}(\mathbf{H}\mathbf{t})$, alors le produit matriciel $\mathbf{H}\mathbf{t}$ peut être interprété comme des fonctions de base de Hermite ; nous en dirons plus sur cette base bientôt. Ou bien, nous pouvons penser à $\mathbf{C} = \mathbf{P}\mathbf{H}$, auquel cas, la multiplication par $\mathbf{H}$ peut être considérée comme une conversion de la base de Hermite à la base monomiale, essentiellement une reformulation des Équations (13.13)–(13.16).

Nous soulignons que les adjectifs « monomiale », « Hermite » et « Bézier » font référence à différentes façons de décrire le même ensemble de courbes polynomiales ; ce ne sont pas des ensembles de courbes différents. Nous convertissons une courbe de la forme de Hermite à la forme monomiale en utilisant les Équations (13.13)–(13.16), et de la forme monomiale à la forme de Hermite avec les Équations (13.9)–(13.12).

Examinons de plus près la base de Hermite et espérons acquérir quelque intuition géométrique sur la raison pour laquelle elle fonctionne. Rappelons que nous pouvons interpréter les fonctions de base comme des fonctions de $t$ donnant des coordonnées barycentriques. Pour les courbes cubiques de Hermite, quatre valeurs sont mélangées : les deux positions et les deux vecteurs de vitesse.9 Ainsi, nous avons quatre fonctions de base qui sont les éléments du résultat en colonne du produit matriciel $\mathbf{H}\mathbf{t}$. En développant le produit, nous obtenons

$$\begin{matrix} {\mathbf{p}(t)} & {= \mathbf{P}(\mathbf{H}\mathbf{t})} \\ & {= \begin{bmatrix} | & | & | & | \\ \mathbf{p}_{0} & \mathbf{v}_{0} & \mathbf{v}_{1} & \mathbf{p}_{1} \\ | & | & | & | \\ \end{bmatrix}\left( \begin{bmatrix} 1 & 0 & {- 3} & 2 \\ 0 & 1 & {- 2} & 1 \\ 0 & 0 & {- 1} & 1 \\ 0 & 0 & 3 & {- 2} \\ \end{bmatrix}\begin{bmatrix} 1 \\ t \\ t^{2} \\ t^{3} \\ \end{bmatrix} \right)} \\ & {= \begin{bmatrix} | & | & | & | \\ \mathbf{p}_{0} & \mathbf{v}_{0} & \mathbf{v}_{1} & \mathbf{p}_{1} \\ | & | & | & | \\ \end{bmatrix}\begin{bmatrix} {1 - 3t^{2} + 2t^{3}} \\ {t - 2t^{2} + t^{3}} \\ {- t^{2} + t^{3}} \\ {3t^{2} - 2t^{3}} \\ \end{bmatrix}.} \\ \end{matrix}$$

Ensuite, nous nommons ces fonctions de base (les lignes de $\mathbf{H}\mathbf{t}$) comme $H_{0}\!(t)\ldots H_{3}\!(t)$ (vous pouvez voir ces mêmes fonctions indexées avec différents indices dans d’autres sources) :

Les fonctions de base cubiques de Hermite

$$\begin{matrix} {H_{0}\!(t)} & {= 1 - 3t^{2} + 2t^{3},} \\ {H_{1}\!(t)} & {= t - 2t^{2} + t^{3},} \\ {H_{2}\!(t)} & {= - t^{2} + t^{3},} \\ {H_{3}\!(t)} & {= 3t^{2} - 2t^{3}.} \\ \end{matrix}$$

Maintenant, développer la multiplication matricielle rend explicite que ces fonctions servent de poids de mélange :

Interprétation des fonctions de base de Hermite comme poids de mélange

$$\begin{matrix} {\mathbf{p}(t)} & {= \begin{bmatrix} | & | & | & | \\ \mathbf{p}_{0} & \mathbf{v}_{0} & \mathbf{v}_{1} & \mathbf{p}_{1} \\ | & | & | & | \\ \end{bmatrix}\begin{bmatrix} {H_{0}\!(t)} \\ {H_{1}\!(t)} \\ {H_{2}\!(t)} \\ {H_{3}\!(t)} \\ \end{bmatrix}} \\ & {= H_{0}\!(t)\,\mathbf{p}_{0} + H_{1}\!(t)\,\mathbf{v}_{0} + H_{2}\!(t)\,\mathbf{v}_{1} + H_{3}\!(t)\,\mathbf{p}_{1}.} \\ \end{matrix}$$

La Figure 13.9 montre un graphique des fonctions de base de Hermite.

Figure 13.9Les fonctions de base de Hermite

Faisons maintenant quelques observations. Premièrement, notez que $H_{0}\!(t) + H_{3}\!(t) = 1$, donc ceux qui s’opposent à l’idée d’additionner des « points » peuvent pousser un soupir de soulagement, car nous pouvons interpréter la situation comme une combinaison barycentrique propre des points.

La courbe $H_{3}\!(t)$ mérite une attention particulière. Elle est également connue sous le nom de fonction smoothstep et est vraiment une perle que tout programmeur de jeux devrait connaître. Cette fonction se trouve dans de nombreux endroits, notamment dans le langage de shading Renderman et HLSL. Pour supprimer le sentiment rigide et robotique de toute interpolation linéaire (notamment les transitions de caméra), calculez simplement la fraction d’interpolation normalisée $t$ comme d’habitude (dans la plage $0 \leq t \leq 1$), et remplacez ensuite $t$ par $3t^{2} - 2t^{3}$. Voilà ! Tout semblera soudainement plus soigné. La raison est que la fonction smoothstep élimine le saut soudain de vitesse aux points d’extrémité : $H_{3}^{\prime}(0) = H_{3}^{\prime}(1) = 0$.

Smoothstep est votre ami

La fonction de base de Hermite $H_{3}\!(t)$ est également connue sous le nom de fonction smoothstep. Presque toute transition basée sur l’interpolation linéaire, notamment une transition de caméra, paraît mieux lorsqu’elle est remplacée par la fonction smoothstep.

Un dernier mot sur les courbes de Hermite. Comme les autres formes pour les courbes polynomiales, il est possible de concevoir un schéma pour des courbes de Hermite de degré plus élevé, bien que le polynôme cubique soit le plus couramment utilisé dans l’infographie et l’animation. Avec la spline cubique, nous avons spécifié la position (la dérivée « 0ème ») et les vitesses (premières dérivées) aux points d’extrémité. Une courbe de Hermite quintique (de cinquième degré) est obtenue lorsque nous spécifions également les accélérations (secondes dérivées).

13.4Courbes de Bézier

Ce chapitre a jusqu’ici discuté un certain nombre d’idées sur les courbes qui étaient instructives, mais il n’a pas encore décrit une façon entièrement pratique de concevoir une courbe. Tout cela va changer dans cette section.10 Les courbes de Bézier ont été inventées par Pierre Bézier (1910–1999), un ingénieur français,11 pendant qu’il travaillait pour le constructeur automobile Renault. Les courbes de Bézier ont de nombreuses propriétés souhaitables qui les rendent bien adaptées à la conception de courbes. Notamment, les courbes de Bézier approximent plutôt qu’interpolent : bien qu’elles passent bien à travers les premiers et derniers points de contrôle, elles ne passent qu’à proximité des points intérieurs. Pour cette raison, les points de contrôle de Bézier sont appelés « points de contrôle » plutôt que « nœuds ». Quelques exemples de courbes cubiques de Bézier sont montrés dans la Figure 13.10.

Figure 13.10Quelques courbes cubiques de Bézier

Rappelons la Section 13.2 que le problème d’interpolation polynomiale avait deux solutions qui produisaient le même résultat. L’algorithme d’Aitken était une technique de construction récursive qui faisait appel à notre sens géométrique, et une approche plus abstraite a donné les polynômes de base de Lagrange. Les courbes de Bézier présentent une dualité similaire. La contrepartie de l’algorithme d’Aitken pour les courbes de Bézier est l’algorithme de de Casteljau, une technique géométrique récursive pour construire des courbes de Bézier par interpolation linéaire répétée ; c’est le sujet de la Section 13.4.1. L’analogue à la base de Lagrange est la base de Bernstein, discutée dans la Section 13.4.2. Après avoir examiné les deux côtés de cette pièce, la Section 13.4.3 étudie les dérivées12 des courbes de Bézier et révèle la relation avec la forme de Hermite.

Nous avons vu une belle coopération entre les mathématiques et la géométrie dans ce livre, mais la convergence est particulièrement élégante pour les courbes de Bézier. Il semble que presque chaque propriété importante des courbes de Bézier ait été découverte de manière indépendante plusieurs fois par des chercheurs dans différents domaines. Le livre de Rogers [4] comprend un regard intéressant sur cette histoire.

$t = .25$	$t = .50$	$t = .75$
Unknown environment ’picture’	Unknown environment ’picture’	Unknown environment ’picture’
Unknown environment ’picture’	Unknown environment ’picture’	Unknown environment ’picture’
Unknown environment ’picture’	Unknown environment ’picture’	Unknown environment ’picture’
Unknown environment ’picture’	Unknown environment ’picture’	Unknown environment ’picture’

Figure 13.11L’algorithme de Casteljau appliqué à une courbe cubique

13.4.1L’algorithme de Casteljau

L’algorithme de Casteljau définit une méthode pour construire des courbes de Bézier par interpolation linéaire répétée. Il a été créé en 1959 par le physicien et mathématicien Paul de Casteljau (1910–1999).13 Nous montrons comment l’algorithme fonctionne pour le cas cubique important comme exemple. D’abord, une notation est nécessaire. Une courbe cubique est définie par quatre points de contrôle, $\mathbf{b}_{0}\ldots\mathbf{b}_{3}$. Notez que les points de contrôle de Bézier sont traditionnellement indexés en commençant à zéro (ce qui plaira aux programmeurs C parmi nous). De plus, comme avec l’algorithme d’Aitken, nous ajoutons un exposant pour indiquer le niveau de récursion. Les points de contrôle originaux se voient attribuer le niveau 0, donc $\mathbf{b}_{i}^{0} = \mathbf{b}_{i}$.

Cela étant dit, considérons une valeur de paramètre spécifique $t$ de 0 à 1. L’algorithme de Casteljau construit géométriquement le point correspondant sur la courbe $\mathbf{p}(t)$ comme suit. Entre chaque paire de points de contrôle consécutifs, nous interpolons selon la fraction $t$ pour obtenir un nouveau point. Ainsi, en commençant avec les quatre points de contrôle originaux $\mathbf{b}_{0}^{0}\ldots\mathbf{b}_{3}^{0}$, nous dérivons trois nouveaux points $\mathbf{b}_{0}^{1}$, $\mathbf{b}_{1}^{1}$ et $\mathbf{b}_{2}^{1}$. Un autre cycle d’interpolation entre chaque paire de ces trois points nous donne deux points $\mathbf{b}_{0}^{2}$ et $\mathbf{b}_{1}^{2}$, et une interpolation finale donne le point $\mathbf{b}_{0}^{3} = \mathbf{p}(t)$ que nous cherchons. La Figure 13.11 montre l’algorithme de Casteljau appliqué à la même courbe à $t = .25$, $t = .50$ et $t = .75$.

Il est utile d’écrire tous les $\mathbf{b}$s de manière triangulaire, comme indiqué dans la Figure 13.12. Chaque point intermédiaire est le résultat de l’interpolation linéaire entre deux points de la ligne supérieure.

$\begin{matrix} \mathbf{b}_{0}^{0} & & & & \mathbf{b}_{1}^{0} & & & & \mathbf{b}_{2}^{0} & & & & \mathbf{b}_{3}^{0} \\ & \searrow & & \swarrow & & \searrow & & \swarrow & & \searrow & & \swarrow & \\ & & \mathbf{b}_{0}^{1} & & & & \mathbf{b}_{1}^{1} & & & & \mathbf{b}_{2}^{1} & & \\ & & & \searrow & & \swarrow & & \searrow & & \swarrow & & & \\ & & & & \mathbf{b}_{0}^{2} & & & & \mathbf{b}_{1}^{2} & & & & \\ & & & & & \searrow & & \swarrow & & & & & \\ & & & & & & \mathbf{b}_{0}^{3} & & & & & & \\ \end{matrix}$

Figure 13.12 Relations hiérarchiques dans l’algorithme de Casteljau pour une courbe cubique

En combinant ces relations récursives avec la formule d’interpolation linéaire de base, nous obtenons la relation de récurrence de Casteljau.

Relation de récurrence de Casteljau

$$\begin{matrix} {\mathbf{b}_{i}^{0}(t)} & {= \mathbf{b}_{i},} \\ {\mathbf{b}_{i}^{n}(t)} & {= (1 - t)\lbrack\mathbf{b}_{i}^{n - 1}\!(t)\rbrack + t\lbrack\mathbf{b}_{i + 1}^{n - 1}\!(t)\rbrack.} \\ \end{matrix}$$

Le Listing 13.1 illustre comment l’algorithme de Casteljau pourrait être implémenté en C++ pour évaluer une courbe de Bézier pour une valeur spécifique de $t$. L’appelant passe les points de contrôle originaux dans un tableau, qui est également utilisé comme espace de travail temporaire car l’opération est effectuée en place. Chaque itération de la boucle externe effectue un cycle d’interpolation, remplaçant les points à un niveau par les points au niveau suivant numéroté plus haut. Ce processus est poursuivi jusqu’à ce qu’il ne reste qu’un seul point, le résultat souhaité $\mathbf{p}(t)$. Cet exemple est destiné à illustrer le fonctionnement de l’algorithme, et non pas à faire quoi que ce soit de particulièrement rapide ou à fournir une interface propre.

Vector3 deCasteljau(
    int n,            // ordre de la courbe, le nombre de points
    Vector3 points[], // tableau de points. Écrasé, car
                      // l'algorithme fonctionne en place
    float t           // valeur de paramètre que nous souhaitons évaluer
) {

    // Effectuer la conversion en place
    while (n > 1) {
        --n;

        // Effectuer le prochain cycle d'interpolation, réduisant le
        // degré de la courbe d'un.
        for (int i = 0 ; i < n ; ++i) {
            points[i] = points[i]*(1.0f-t) + points[i+1]*t;
        }
    }

    // Le résultat est maintenant dans le premier emplacement.
    return points[0];
}

Cela nous donne une méthode pour localiser un point à tout $t$ donné par interpolation répétée, mais cela ne nous donne pas directement une expression en forme fermée pour calculer le point en termes de points de contrôle. Nous soulignons qu’une telle expression en forme fermée n’est souvent pas nécessaire, mais dérivons-la en forme monomiale quand même. Nous cherchons un polynôme regroupé par puissances de $t$. Nous allons progresser des cas linéaires et quadratiques vers le cas cubique. La Section 13.4.2 présente un motif général menant à l’expression pour les courbes de degré arbitraire. Le cas linéaire vient directement de la relation de récurrence sans aucun travail réel :

$$\begin{matrix} {\mathbf{b}_{i}^{0}(t)} & {= \mathbf{b}_{i},} \\ {\mathbf{b}_{i}^{1}(t)} & {= (1 - t)\lbrack\mathbf{b}_{i}^{0}\!(t)\rbrack + t\lbrack\mathbf{b}_{i + 1}^{0}\!(t)\rbrack} \\ & {= (1 - t)\mathbf{b}_{i} + t\mathbf{b}_{i + 1}} \\ & {= \mathbf{b}_{i} + t(\mathbf{b}_{i + 1} - \mathbf{b}_{i}).} \\ \end{matrix}$$

Appliquer un niveau de plus nous donne un polynôme quadratique :

$$\begin{matrix} {\mathbf{b}_{i}^{2}(t)} & {= (1 - t)\lbrack\mathbf{b}_{i}^{1}\!(t)\rbrack + t\lbrack\mathbf{b}_{i + 1}^{1}\!(t)\rbrack} \\ & {= (1 - t)\lbrack\mathbf{b}_{i} + t(\mathbf{b}_{i + 1} - \mathbf{b}_{i})\rbrack + t\lbrack\mathbf{b}_{i + 1} + t(\mathbf{b}_{i + 2} - \mathbf{b}_{i + 1})\rbrack} \\ & {= \lbrack\mathbf{b}_{i} + t(\mathbf{b}_{i + 1} - \mathbf{b}_{i})\rbrack - t\lbrack\mathbf{b}_{i} + t(\mathbf{b}_{i + 1} - \mathbf{b}_{i})\rbrack} \\ & {\quad\quad + t\lbrack\mathbf{b}_{i + 1} + t(\mathbf{b}_{i + 2} - \mathbf{b}_{i + 1})\rbrack} \\ & {= \mathbf{b}_{i} + t(\mathbf{b}_{i + 1} - \mathbf{b}_{i}) - t\mathbf{b}_{i} - t^{2}(\mathbf{b}_{i + 1} - \mathbf{b}_{i})} \\ & {\quad\quad + t\mathbf{b}_{i + 1} + t^{2}(\mathbf{b}_{i + 2} - \mathbf{b}_{i + 1})} \\ & {= \mathbf{b}_{i} + t(2\mathbf{b}_{i + 1} - 2\mathbf{b}_{i}) + t^{2}(\mathbf{b}_{i} - 2\mathbf{b}_{i + 1} + \mathbf{b}_{i + 2}).} \\ \end{matrix}$$

En d’autres termes, les courbes de Bézier quadratiques, qui ont trois points de contrôle, peuvent être exprimées en forme monomiale comme

Courbe de Bézier quadratique en forme monomiale

$$\begin{matrix} {\mathbf{p}(t) = \mathbf{b}_{0}^{2}\!(t) = \mathbf{b}_{0} + t(2\mathbf{b}_{1} - 2\mathbf{b}_{0}) + t^{2}(\mathbf{b}_{0} - 2\mathbf{b}_{1} + \mathbf{b}_{2}).} \\ \end{matrix}$$

Avant d’effectuer le dernier cycle d’interpolation pour obtenir la courbe cubique, examinons de plus près l’expression quadratique dans l’Équation (13.17). Cette conversion de la forme de Bézier à la base monomiale peut être écrite avec moins de lettres en utilisant la notation matricielle introduite précédemment dans ce chapitre. Après avoir mis les points de contrôle $\mathbf{b}_{0}$, $\mathbf{b}_{1}$, $\mathbf{b}_{2}$ en colonnes dans une matrice $\mathbf{B}$, nous pouvons écrire

Courbe de Bézier quadratique en notation matricielle

$$\begin{matrix} {\mathbf{p}(t) = \mathbf{C}\mathbf{t} = \mathbf{B}\mathbf{M}\mathbf{t} = \begin{bmatrix} | & | & | \\ \mathbf{b}_{0} & \mathbf{b}_{1} & \mathbf{b}_{2} \\ | & | & | \\ \end{bmatrix}\begin{bmatrix} 1 & {- 2} & 1 \\ 0 & 2 & {- 2} \\ 0 & 0 & 1 \\ \end{bmatrix}\begin{bmatrix} 1 \\ t \\ t^{2} \\ \end{bmatrix}.} \\ \end{matrix}$$

Comme nous l’avons vu dans la Section 13.3 avec les courbes de Hermite, les deux façons différentes de regrouper le produit $\mathbf{B}\mathbf{M}\mathbf{t}$ mènent à deux interprétations différentes. Si nous effectuons la multiplication $\mathbf{B}\mathbf{M}$ en premier, nous obtenons la matrice de coefficients monomiales $\mathbf{C}$, ce qui signifie que $\mathbf{M}$ est une matrice de conversion de la forme de Bézier à la forme monomiale. L’évaluation directe de la forme monomiale est plus rapide que l’implémentation de l’algorithme de Casteljau, et cette forme peut donc être préférable dans les situations où nous devons évaluer la même courbe pour de nombreuses valeurs différentes de $t$, par exemple, lors du déplacement d’un objet dans le temps le long d’un chemin décrit par une courbe de Bézier. (Cependant, il faut être conscient des problèmes liés à la précision. Par exemple, nous pouvons nous assurer que l’exécution de de Casteljau avec $t = 1.0$ produit un résultat qui correspond exactement au dernier point de contrôle. Cependant, en substituant $t = 1.0$ dans le polynôme en forme monomiale, les coefficients peuvent ne pas se sommer exactement à cette valeur en raison de la représentation en virgule flottante.)

L’autre façon de regrouper le produit $\mathbf{B}\mathbf{M}\mathbf{t}$ est d’effectuer la multiplication côté droit en premier : $\mathbf{B}(\mathbf{M}\mathbf{t})$. Lorsque nous substituons une valeur spécifique de $t$, le produit $\mathbf{M}\mathbf{t}$ donne un vecteur colonne de coordonnées barycentriques. Si nous effectuons cette multiplication en laissant $t$ comme variable, nous obtenons un vecteur colonne de polynômes qui peuvent être interprétés comme une base. Les polynômes de base pour les courbes de Bézier sont la base de Bernstein, discutée dans la Section 13.4.2.

Revenons à l’interpolation répétée. Un dernier cycle nous donne le polynôme cubique :

Un dernier tour d’itération de Casteljau donne le polynôme cubique.
\
Ouf, tout développer comme ça est assez épuisant !

$$\begin{matrix} {\mathbf{b}_{i}^{3}(t)} & {= (1 - t)\lbrack\mathbf{b}_{i}^{2}\!(t)\rbrack + t\lbrack\mathbf{b}_{i + 1}^{2}\!(t)\rbrack} \\ & {= (1 - t)\lbrack\mathbf{b}_{i} + t(2\mathbf{b}_{i + 1} - 2\mathbf{b}_{i}) + t^{2}(\mathbf{b}_{i} - 2\mathbf{b}_{i + 1} + \mathbf{b}_{i + 2})\rbrack} \\ & {\quad\quad + t\lbrack\mathbf{b}_{i + 1} + t(2\mathbf{b}_{i + 2} - 2\mathbf{b}_{i + 1}) + t^{2}(\mathbf{b}_{i + 1} - 2\mathbf{b}_{i + 2} + \mathbf{b}_{i + 3})\rbrack} \\ & {= \lbrack\mathbf{b}_{i} + t(2\mathbf{b}_{i + 1} - 2\mathbf{b}_{i}) + t^{2}(\mathbf{b}_{i} - 2\mathbf{b}_{i + 1} + \mathbf{b}_{i + 2})\rbrack} \\ & {\quad\quad - t\lbrack\mathbf{b}_{i} + t(2\mathbf{b}_{i + 1} - 2\mathbf{b}_{i}) + t^{2}(\mathbf{b}_{i} - 2\mathbf{b}_{i + 1} + \mathbf{b}_{i + 2})\rbrack} \\ & {\quad\quad + t\lbrack\mathbf{b}_{i + 1} + t(2\mathbf{b}_{i + 2} - 2\mathbf{b}_{i + 1}) + t^{2}(\mathbf{b}_{i + 1} - 2\mathbf{b}_{i + 2} + \mathbf{b}_{i + 3})\rbrack} \\ & {= \mathbf{b}_{i} + t(2\mathbf{b}_{i + 1} - 2\mathbf{b}_{i}) + t^{2}(\mathbf{b}_{i} - 2\mathbf{b}_{i + 1} + \mathbf{b}_{i + 2})} \\ & {\quad\quad - t\mathbf{b}_{i} - t^{2}(2\mathbf{b}_{i + 1} - 2\mathbf{b}_{i}) - t^{3}(\mathbf{b}_{i} - 2\mathbf{b}_{i + 1} + \mathbf{b}_{i + 2})} \\ & {\quad\quad + t\mathbf{b}_{i + 1} + t^{2}(2\mathbf{b}_{i + 2} - 2\mathbf{b}_{i + 1}) + t^{3}(\mathbf{b}_{i + 1} - 2\mathbf{b}_{i + 2} + \mathbf{b}_{i + 3})} \\ \end{matrix}$$

$$\begin{matrix} & {= \mathbf{b}_{i} + t(3\mathbf{b}_{i + 1} - 3\mathbf{b}_{i}) + t^{2}(3\mathbf{b}_{i} - 6\mathbf{b}_{i + 1} + 3\mathbf{b}_{i + 2})} \\ & {\quad\quad\; + t^{3}( - \mathbf{b}_{i} + 3\mathbf{b}_{i + 1} - 3\mathbf{b}_{i + 2} + \mathbf{b}_{i + 3}).} \\ \end{matrix}$$

En réécrivant la dernière ligne, mais cette fois en supposant que le niveau cubique est le niveau final de récursion, nous avons

Courbe de Bézier cubique en forme monomiale

$$\begin{matrix} \begin{matrix} {\mathbf{p}(t) = \mathbf{b}_{0}^{3}(t)} & {= \mathbf{b}_{0} + t(3\mathbf{b}_{1} - 3\mathbf{b}_{0}) + t^{2}(3\mathbf{b}_{0} - 6\mathbf{b}_{1} + 3\mathbf{b}_{2})} \\ & {\quad\quad + t^{3}( - \mathbf{b}_{0} + 3\mathbf{b}_{1} - 3\mathbf{b}_{2} + \mathbf{b}_{3}).} \\ \end{matrix} \\ \end{matrix}$$

Juste pour s’assurer que vous ne l’avez pas manqué, l’Équation (13.19) nous indique comment convertir une courbe de Bézier cubique en forme monomiale. Comme c’est important, écrivons-le un peu plus délibérément comme

Coefficients monomiales cubiques à partir de points de contrôle de Bézier

$$\begin{matrix} \mathbf{c}_{0} & {= \mathbf{b}_{0},} \\ \mathbf{c}_{1} & {= - 3\mathbf{b}_{0} + 3\mathbf{b}_{1},} \\ \mathbf{c}_{2} & {= 3\mathbf{b}_{0} - 6\mathbf{b}_{1} + 3\mathbf{b}_{2},} \\ \mathbf{c}_{3} & {= - \mathbf{b}_{0} + 3\mathbf{b}_{1} - 3\mathbf{b}_{2} + \mathbf{b}_{3}.} \\ \end{matrix}$$

Nous pouvons maintenant mettre cette conversion dans une matrice comme nous l’avons fait avec le cas quadratique dans l’Équation (13.18). L’équation cubique pour un point spécifique sur la courbe $\mathbf{p}(t)$ est écrite en notation matricielle comme

Courbe de Bézier cubique en notation matricielle

$$\mathbf{p}(t) = \mathbf{C}\mathbf{t} = \mathbf{B}\mathbf{M}\mathbf{t} = \begin{bmatrix} | & | & | & | \\ \mathbf{b}_{0} & \mathbf{b}_{1} & \mathbf{b}_{2} & \mathbf{b}_{3} \\ | & | & | & | \\ \end{bmatrix}\begin{bmatrix} 1 & {- 3} & 3 & {- 1} \\ 0 & 3 & {- 6} & 3 \\ 0 & 0 & 3 & {- 3} \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}\begin{bmatrix} 1 \\ t \\ t^{2} \\ t^{3} \\ \end{bmatrix}.$$

Nous pouvons également inverser ce processus, ce qui signifie que nous pouvons convertir n’importe quelle courbe polynomiale de la forme monomiale à la forme de Bézier. Étant donné n’importe quelle courbe polynomiale, les points de contrôle de Bézier qui décrivent la courbe sont déterminés de manière unique :

Calcul des points de contrôle de Bézier à partir de coefficients monomiales

$$\begin{matrix} \mathbf{b}_{0} & {= \mathbf{c}_{0},} \\ \mathbf{b}_{1} & {= \mathbf{c}_{0} + (1/3)\mathbf{c}_{1},} \\ \mathbf{b}_{2} & {= \mathbf{c}_{0} + (2/3)\mathbf{c}_{1} + (1/3)\mathbf{c}_{2},} \\ \mathbf{b}_{3} & {= \mathbf{c}_{0} + \mathbf{c}_{1} + \mathbf{c}_{2} + \mathbf{c}_{3}.} \\ \end{matrix}$$

Et, bien sûr, nous pouvons écrire cela en notation matricielle :

Conversion de la forme monomiale à la forme de Bézier, en notation matricielle

$$\begin{bmatrix} | & | & | & | \\ \mathbf{b}_{0} & \mathbf{b}_{1} & \mathbf{b}_{2} & \mathbf{b}_{3} \\ | & | & | & | \\ \end{bmatrix} = \begin{bmatrix} | & | & | & | \\ \mathbf{c}_{0} & \mathbf{c}_{1} & \mathbf{c}_{2} & \mathbf{c}_{3} \\ | & | & | & | \\ \end{bmatrix}\begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & {1/3} & {2/3} & 1 \\ 0 & 0 & {1/3} & 1 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}.$$

13.4.2La base de Bernstein

La Section 13.4.1 s’est terminée avec un peu d’algèbre pour calculer le polynôme d’une courbe à partir des points de contrôle de Bézier. Ce polynôme était exprimé en forme monomiale, ce qui signifie que les coefficients étaient pour les puissances de $t$. Nous pouvons également écrire le polynôme en forme de Bézier en collectant les termes sur les points de contrôle plutôt que sur les puissances de $t$. Lorsqu’on l’écrit ainsi, chaque point de contrôle a un coefficient qui représente le poids barycentrique en fonction de $t$ que le point de contrôle contribue à la courbe.

Répétons l’exercice d’algèbre de la Section 13.4.1, seulement cette fois nous écrirons les choses d’une façon légèrement différente qui nous mènera à quelques observations. Comme nous l’avons fait avant, nous commençons par le cas linéaire (rappelons, $\mathbf{b}_{i}^{0} = \mathbf{b}_{i}$) :

$$\begin{matrix} {\mathbf{b}_{i}^{1}(t)} & {= (1 - t)\lbrack\mathbf{b}_{i}^{0}\!(t)\rbrack + t\lbrack\mathbf{b}_{i + 1}^{0}\!(t)\rbrack} \\ & {= (1 - t)\mathbf{b}_{i} + t\mathbf{b}_{i + 1}.} \\ \end{matrix}$$

Ensuite vient le cas quadratique :

$$\begin{matrix} {\mathbf{b}_{i}^{2}(t)} & {= (1 - t)\mathbf{b}_{i}^{1}\!(t) + t\mathbf{b}_{i + 1}^{1}\!(t)} \\ & {= (1 - t)\lbrack(1 - t)\mathbf{b}_{i} + t\mathbf{b}_{i + 1}\rbrack + t\lbrack(1 - t)\mathbf{b}_{i + 1} + t\mathbf{b}_{i + 2}\rbrack} \\ & {= (1 - t)^{2}\mathbf{b}_{i} + t(1 - t)\mathbf{b}_{i + 1} + t(1 - t)\mathbf{b}_{i + 1} + t^{2}\mathbf{b}_{i + 2}} \\ & {= (1 - t)^{2}\mathbf{b}_{i} + 2t(1 - t)\mathbf{b}_{i + 1} + t^{2}\mathbf{b}_{i + 2}.} \\ \end{matrix}$$

Et enfin, nous avons le cas cubique :

$$\begin{matrix} {\mathbf{b}_{i}^{3}(t)} & {= (1 - t)\lbrack\mathbf{b}_{i}^{2}\!(t)\rbrack + t\lbrack\mathbf{b}_{i + 1}^{2}\!(t)\rbrack} \\ & {= (1 - t)\lbrack(1 - t)^{2}\mathbf{b}_{i} + 2t(1 - t)\mathbf{b}_{i + 1} + t^{2}\mathbf{b}_{i + 2}\rbrack} \\ & {\quad\quad + t\lbrack(1 - t)^{2}\mathbf{b}_{i + 1} + 2t(1 - t)\mathbf{b}_{i + 2} + t^{2}\mathbf{b}_{i + 3}\rbrack} \\ & {= (1 - t)^{3}\mathbf{b}_{i} + 2t(1 - t)^{2}\mathbf{b}_{i + 1} + t^{2}(1 - t)\mathbf{b}_{i + 2}} \\ & {\quad\quad + t(1 - t)^{2}\mathbf{b}_{i + 1} + 2t^{2}(1 - t)\mathbf{b}_{i + 2} + t^{3}\mathbf{b}_{i + 3}} \\ & {= (1 - t)^{3}\mathbf{b}_{i} + 3t(1 - t)^{2}\mathbf{b}_{i + 1} + 3t^{2}(1 - t)\mathbf{b}_{i + 2} + t^{3}\mathbf{b}_{i + 3}.} \\ \end{matrix}$$

Vous pouvez voir un motif émerger, mais pour le rendre encore plus clair, montrons les courbes jusqu’au degré 5 (nous sauterons l’algèbre ; elle est similaire à ce que nous avons fait ci-dessus) :

Courbes de Bézier de degré 1–5

$$\begin{matrix} {\mathbf{b}_{0}^{1}\!(t)} & {= (1 - t)\mathbf{b}_{0} + t\mathbf{b}_{1},} \\ {\mathbf{b}_{0}^{2}\!(t)} & {= (1 - t)^{2}\mathbf{b}_{0} + 2t(1 - t)\mathbf{b}_{1} + t^{2}\mathbf{b}_{2},} \\ {\mathbf{b}_{0}^{3}\!(t)} & {= (1 - t)^{3}\mathbf{b}_{0} + 3t(1 - t)^{2}\mathbf{b}_{1} + 3t^{2}(1 - t)\mathbf{b}_{2} + t^{3}\mathbf{b}_{3},} \\ \end{matrix}$$

$$\begin{matrix} \begin{matrix} {\mathbf{b}_{0}^{4}\!(t)} & {= (1 - t)^{4}\mathbf{b}_{0} + 4t(1 - t)^{3}\mathbf{b}_{1} + 6t^{2}(1 - t)^{2}\mathbf{b}_{2}} \\ & {\quad\quad + 4t^{3}(t - 1)\mathbf{b}_{3} + t^{4}\mathbf{b}_{4},} \\ \end{matrix} \\ \begin{matrix} {\mathbf{b}_{0}^{5}\!(t)} & {= (1 - t)^{5}\mathbf{b}_{0} + 5t(1 - t)^{4}\mathbf{b}_{1} + 10t^{2}(1 - t)^{3}\mathbf{b}_{2}} \\ & {\quad\quad + 10t^{3}(1 - t)^{2}\mathbf{b}_{3} + 5t^{4}(1 - t)\mathbf{b}_{4} + t^{5}\mathbf{b}_{5}.} \\ \end{matrix} \\ \end{matrix}$$

Le motif est maintenant plus clair. Chaque terme a un coefficient constant, une puissance de $(1 - t)$ et une puissance de $t$. Les puissances de $t$ sont numérotées en ordre croissant, donc $\mathbf{b}_{i}$ a un coefficient $t^{i}$. Les puissances de $(1 - t)$ suivent le motif opposé et sont numérotées en ordre décroissant.

Le motif pour les coefficients constants est un peu plus compliqué. Permettez une brève, mais j’espère intéressante, digression dans la combinatoire. Écrivons les huit premiers niveaux sous forme triangulaire pour rendre le motif un peu plus facile à voir :

Triangle de Pascal

$$\begin{matrix} 0 & & & & & & & & & 1 & & & & & & & & \\ 1 & & & & & & & & 1 & & 1 & & & & & & & \\ 2 & & & & & & & 1 & & 2 & & 1 & & & & & & \\ 3 & & & & & & 1 & & 3 & & 3 & & 1 & & & & & \\ 4 & & & & & 1 & & 4 & & 6 & & 4 & & 1 & & & & \\ 5 & & & & 1 & & 5 & & 10 & & 10 & & 5 & & 1 & & & \\ 6 & & & 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1 & & \\ 7 & & 1 & & 7 & & 21 & & 35 & & 35 & & 21 & & 7 & & 1 & \\ \end{matrix}$$

À l’exception des 1 sur le bord extérieur du triangle, tous les autres nombres sont la somme des deux nombres au-dessus d’eux. Vous regardez un motif de nombres très célèbre qui a été étudié pendant des siècles, connu sous le nom de coefficients binomiaux car la $n$ième ligne donne les coefficients lors du développement du binôme $(a + b)^{n}$. La compulsion d’organiser ces nombres de manière triangulaire comme ceci a frappé de nombreuses personnes, notamment le mathématicien et physicien Blaise Pascal (1623–1662).14 Cet arrangement triangulaire des coefficients binomiaux est connu sous le nom de triangle de Pascal.15

Les coefficients binomiaux ont une notation spéciale. Nous pouvons faire référence au $k$ième nombre sur la ligne $n$ dans le triangle de Pascal (où l’indexation commence à 0 pour $n$ et $k$) en utilisant la notation des coefficients binomiaux comme

Notation des coefficients binomiaux

$${(\frac{n}{k})}.$$

Par exemple, ${(\frac{6}{2})} = 15$. Nous lisons $(\frac{n}{k})$ comme « $n$ choisir $k$ », car la valeur de $(\frac{n}{k})$ est également le nombre de sous-ensembles de $k$ objets pouvant être choisis parmi un ensemble de $n$ objets, en ignorant l’ordre.

Examinons maintenant la formule générale pour calculer les coefficients binomiaux. (Nous soulignons que cette formule est principalement à des fins d’amusement, car notre utilisation des coefficients binomiaux dans ce chapitre sur les courbes sera limitée aux premières lignes du triangle de Pascal.) Rappelons la Section 11.4.6 l’opérateur factorielle, noté $n!$, qui est le produit de tous les nombres entiers jusqu’à $n$ inclus :

Opérateur factorielle

$$n! = \prod\limits_{i = 1}^{n}i = 1 \times 2 \times 3 \times \cdots \times n.$$

En utilisant les factorielles, et en définissant $0! \equiv 1$, nous calculons un coefficient binomial comme

Coefficient binomial

$${(\frac{n}{k})} = \frac{n!}{k!(n - k)!}.$$

Les coefficients binomiaux apparaissent fréquemment dans les applications traitant des combinaisons et des permutations, comme les probabilités et l’analyse des algorithmes. En raison de leur importance, et du nombre étonnamment grand de motifs qui peuvent être trouvés en eux, ils ont fait l’objet d’une très grande quantité d’étude. Une discussion très approfondie des coefficients binomiaux, en particulier concernant leur utilisation dans les algorithmes informatiques, est présentée par Knuth [2].

Revenons aux courbes. Nous avons analysé le motif des poids barycentriques. Réécrivons maintenant une courbe de Bézier, en remplaçant chaque poids de point de contrôle par une fonction $B_{i}^{n}\!(t)$, et en utilisant la formule de courbe cubique (l’Équation (13.26)) comme exemple :

$$\begin{matrix} {\mathbf{b}_{0}^{3}\!(t)} & {= (1 - t)^{3}\mathbf{b}_{0} + 3t(1 - t)^{2}\mathbf{b}_{1} + 3t^{2}(1 - t)\mathbf{b}_{2} + t^{3}\mathbf{b}_{3}} \\ & {= \lbrack B_{0}^{3}\!(t)\rbrack\mathbf{b}_{0} + \lbrack B_{1}^{3}\!(t)\rbrack\mathbf{b}_{1} + \lbrack B_{2}^{3}\!(t)\rbrack\mathbf{b}_{2} + \lbrack B_{3}^{3}\!(t)\rbrack\mathbf{b}_{3}.} \\ \end{matrix}$$

Plus généralement, nous pouvons écrire une courbe de Bézier de degré $n$ (ayant $n + 1$ points de contrôle) comme

Courbe de Bézier de degré arbitraire

$$\mathbf{b}_{0}^{n}\!(t) = \sum\limits_{i = 0}^{n}\lbrack B_{i}^{n}\!(t)\rbrack\mathbf{b}_{i}.$$

$B_{0}^{1}(t) = 1 - t$	$B_{0}^{2}(t) = (1 - t)^{2}$
$B_{1}^{1}(t) = t$	$B_{1}^{2}(t) = 2(1 - t)t$
	$B_{2}^{2}(t) = t^{2}$
$B_{0}^{3}(t) = (1 - t)^{3}$	$B_{0}^{4}(t) = (1 - t)^{4}$
$B_{1}^{3}(t) = 3t(1 - t)^{2}$	$B_{1}^{4}(t) = 4t(1 - t)^{3}$
$B_{2}^{3}(t) = 3t^{2}(1 - t)$	$B_{2}^{4}(t) = 6t^{2}(1 - t)^{2}$
$B_{3}^{3}(t) = t^{3}$	$B_{3}^{4}(t) = 4t^{3}(1 - t)$
	$B_{4}^{4}(t) = t^{4}$

Figure 13.13Polynômes de Bernstein de degrés 1–4

La fonction $B_{i}^{n}\!(t)$ est un polynôme de Bernstein, nommé d’après Sergei Bernstein (1880–1968).16 Nous avons déjà compris le motif de ces polynômes, mais voici la formule précise :

Polynôme de Bernstein

$$B_{i}^{n}\!(t) = {(\frac{n}{i})}t^{i}(1 - t)^{n - i}\ , 0 \leq i \leq n.$$

La Figure 13.13 montre les graphiques des polynômes de Bernstein jusqu’au cas quartique.

Les propriétés des polynômes de Bernstein nous en disent beaucoup sur comment la courbe de Bézier se comporte. Examinons quelques propriétés en particulier.

Somme égale à un. Les polynômes de Bernstein se somment à l’unité pour toutes les valeurs de $t$, ce qui est souhaitable car s’ils ne le faisaient pas, ils ne définiraient pas de véritables coordonnées barycentriques. Ce fait n’est pas immédiatement évident, ni par inspection visuelle de la Figure 13.13 ni par un examen superficiel des équations, mais il peut être démontré. Si vous appréciez l’idée de travailler sur une telle démonstration pour le cas quadratique, consultez l’Exercice 4.

Propriété de l’enveloppe convexe. L’intervalle des polynômes de Bernstein est $0\ldots 1$ sur toute la longueur de la courbe, $0 \leq t \leq 1$. Combinée avec la propriété précédente, cela signifie que les courbes de Bézier obéissent à la propriété de l’enveloppe convexe : la courbe est limitée à rester dans l’ enveloppe convexe des points de contrôle. Comparez cela avec les polynômes de base de Lagrange, qui ne restent pas dans l’intervalle $\lbrack 0,1\rbrack$, ce qui fait que l’interpolation polynomiale n’obéit pas à la propriété de l’enveloppe convexe. Une manifestation de ceci est le dépassement indésirable (“overshooting”) observé dans la Figure 13.4.

Interpolation des extrémités. Les premiers et derniers polynômes atteignent l’unité quand on en a besoin. Parce que $B_{0}^{n}\!(0) = 1$ et $B_{n}^{n}\!(1) = 1$, la courbe passe par les points extrêmes. Remarquez que $t = 0$ et $t = 1$ sont les seuls endroits où l’un des polynômes de base atteint 1, c’est pourquoi les autres points de contrôle sont seulement approximés et non interpolés.

Support global. Tous les polynômes sont non nuls sur l’intervalle ouvert $(0,1$)—c’est-à-dire, toute la courbe à l’exclusion des extrémités. La région où le poids de mélange d’un point de contrôle est non nul est appelée le support du point de contrôle. Partout où le point de contrôle a du support, il exerce une certaine influence sur la courbe.

Les points de contrôle de Bézier ont un support global parce que les polynômes de Bernstein sont non nuls partout sauf aux extrémités. Le résultat pratique est que lorsqu’un point de contrôle est déplacé, toute la courbe est affectée. Ce n’est pas une propriété souhaitable pour la conception de courbes. Une fois qu’une section de la courbe a l’aspect désiré, nous préférerions que la modification d’un autre point de contrôle éloigné ne perturbe pas la section qui avait la forme voulue. Cette situation enviable, connue sous le nom de support local, se produit lorsqu’on déplace un point de contrôle particulier et que seule la partie de la courbe proche de ce point de contrôle est affectée, pour une certaine définition de “proche”.

Le support local signifie que la fonction de base est non nulle seulement dans un intervalle, et en dehors de cet intervalle elle est nulle. Malheureusement, une telle fonction de base ne peut pas être décrite comme un polynôme, et donc aucune courbe polynomiale ne peut obtenir un contrôle local. Cependant, le support local est possible en assemblant de petites courbes qui s’emboîtent juste comme il faut pour former un spline, comme la Section 13.6 le décrit.

Un maximum local. Bien que chaque point de contrôle exerce une influence sur toute la courbe, chacun exerce le plus d’influence en un point particulier le long de la courbe. Chaque polynôme de Bernstein $B_{i}^{n}\!(t)$, qui sert de poids de mélange pour le point de contrôle $\mathbf{b}_{i}$, a un maximum à l’instant propice $t = i/n$. De plus, à cet instant, $\mathbf{b}_{i}$ exerce plus de poids qu’aucun autre point de contrôle.

Ainsi, bien que chaque point sur l’intérieur de la courbe soit influencé dans une certaine mesure par tous les points de contrôle (parce que les points de contrôle de Bézier ont un support global), le point de contrôle le plus proche a la plus grande influence.

13.4.3Dérivées de Bézier et leur Relation
avec la Forme Hermite

Examinons les dérivées d’une courbe de Bézier. Puisque nous utilisons la courbe cubique comme exemple, nous parlons de la vitesse et de l’accélération de la courbe. Rappelez-vous que la vitesse est liée à la tangente (direction) de la courbe, et l’accélération est liée à sa courbure.

La Section 13.1.6 a montré comment obtenir la fonction de vitesse d’une courbe à partir des coefficients monomials :

Position et vitesse d’une courbe cubique

$$\begin{matrix} {\mathbf{p}(t)} & {= \mathbf{c}_{0} + \mathbf{c}_{1}t + \mathbf{c}_{2}t^{2} + \mathbf{c}_{3}t^{3},} \\ {\mathbf{v}(t) = \overset{˙}{\mathbf{p}}(t)} & {= \mathbf{c}_{1} + 2\mathbf{c}_{2}t + 3\mathbf{c}_{3}t^{2}.} \\ \end{matrix}$$

Et la Section 13.4.1 a montré comment extraire les coefficients monomials d’une courbe de Bézier cubique :

$$\begin{matrix} \mathbf{c}_{0} & {= \mathbf{b}_{0},} \\ \mathbf{c}_{1} & {= 3\mathbf{b}_{1} - 3\mathbf{b}_{0},} \\ \mathbf{c}_{2} & {= 3\mathbf{b}_{0} - 6\mathbf{b}_{1} + 3\mathbf{b}_{2},} \\ \mathbf{c}_{3} & {= - \mathbf{b}_{0} + 3\mathbf{b}_{1} - 3\mathbf{b}_{2} + \mathbf{b}_{3}.} \\ \end{matrix}$$

En substituant ces coefficients dans la formule de vitesse (Équation (13.29)), on obtient une formule pour la vitesse instantanée d’une courbe en termes des points de contrôle de Bézier :

Première dérivée (vitesse) d’une courbe de Bézier cubique

$$\begin{matrix} {\mathbf{v}(t)} & {= \mathbf{c}_{1} + 2\mathbf{c}_{2}t + 3\mathbf{c}_{3}t^{2}} \\ & {= (3\mathbf{b}_{1} - 3\mathbf{b}_{0}) + 2(3\mathbf{b}_{0} - 6\mathbf{b}_{1} + 3\mathbf{b}_{2})t + 3( - \mathbf{b}_{0} + 3\mathbf{b}_{1} - 3\mathbf{b}_{2} + \mathbf{b}_{3})t^{2}.} \\ \end{matrix}$$

Considérons maintenant la vitesse aux extrémités $t = 0$ et $t = 1$ :

Vitesse aux extrémités d’une courbe de Bézier cubique

$$\begin{matrix} {\mathbf{v}(0) =} & {\ (3\mathbf{b}_{1} - 3\mathbf{b}_{0}) + 2(3\mathbf{b}_{0} - 6\mathbf{b}_{1} + 3\mathbf{b}_{2})(0)} \\ & {+ 3( - \mathbf{b}_{0} + 3\mathbf{b}_{1} - 3\mathbf{b}_{2} + \mathbf{b}_{3})(0)^{2}} \\ = & {\ 3(\mathbf{b}_{1} - \mathbf{b}_{0}),} \\ {\mathbf{v}(1) =} & {\ (3\mathbf{b}_{1} - 3\mathbf{b}_{0}) + 2(3\mathbf{b}_{0} - 6\mathbf{b}_{1} + 3\mathbf{b}_{2})(1)} \\ & {+ 3( - \mathbf{b}_{0} + 3\mathbf{b}_{1} - 3\mathbf{b}_{2} + \mathbf{b}_{3})(1)^{2}} \\ = & {\ 3\mathbf{b}_{1} - 3\mathbf{b}_{0} + 6\mathbf{b}_{0} - 12\mathbf{b}_{1} + 6\mathbf{b}_{2} - 3\mathbf{b}_{0} + 9\mathbf{b}_{1} - 9\mathbf{b}_{2} + 3\mathbf{b}_{3}} \\ = & {\ 3(\mathbf{b}_{3} - \mathbf{b}_{2}).} \\ \end{matrix}$$

C’est intéressant. Observez que $\mathbf{b}_{1} - \mathbf{b}_{0}$ nous donne le vecteur du premier point de contrôle vers le deuxième point de contrôle, et $\mathbf{b}_{3} - \mathbf{b}_{2}$ est le vecteur du troisième point de contrôle vers le dernier point de contrôle. Donc la tangente au début de la courbe en $t = 0$ est “orientée vers” le premier point de contrôle, et la tangente à la fin de la courbe en $t = 1$ est “orientée vers” le troisième point de contrôle. (En fait, la tangente en $t = 1$ pointe directement à l’opposé du troisième point de contrôle, si l’on pense à se déplacer le long de la courbe dans le sens croissant de $t$). C’est un point clé.

Le premier bord du polygone de contrôle de Bézier détermine entièrement la tangente au début de la courbe, et le dernier bord détermine la tangente à la fin de la courbe.

Une autre façon d’illustrer le rôle des points de contrôle intermédiaires dans une courbe de Bézier cubique est d’examiner la relation entre les formes Bézier et Hermite. Rappelez-vous que la forme cubique de Hermite contient la position initiale $\mathbf{p}_{0}$ et la vitesse $\mathbf{v}_{0}$ ainsi que la position finale $\mathbf{p}_{1}$ et la vitesse $\mathbf{v}_{1}$. Maintenant que nous connaissons la relation entre les points de contrôle de Bézier et la vitesse de la courbe, il est facile de convertir de la forme Bézier à la forme Hermite :

Conversion d’une courbe cubique de la forme Bézier à la forme Hermite

$$\begin{matrix} \mathbf{p}_{0} & {= \mathbf{b}_{0},} \\ \mathbf{v}_{0} & {= 3(\mathbf{b}_{1} - \mathbf{b}_{0}),} \\ \mathbf{v}_{1} & {= 3(\mathbf{b}_{3} - \mathbf{b}_{2}),} \\ \mathbf{p}_{1} & {= \mathbf{b}_{3}.} \\ \end{matrix}$$

Ou bien, on peut convertir de la forme Hermite à la forme Bézier :

Conversion d’une courbe cubique de la forme Hermite à la forme Bézier

$$\begin{matrix} \mathbf{b}_{0} & {= \mathbf{p}_{0},} \\ \mathbf{b}_{1} & {= \mathbf{p}_{0} + (1/3)\mathbf{v}_{0},} \\ \mathbf{b}_{2} & {= \mathbf{p}_{1} - (1/3)\mathbf{v}_{1},} \\ \mathbf{b}_{3} & {= \mathbf{p}_{1}.} \\ \end{matrix}$$

Ainsi, les formes Hermite et Bézier sont très étroitement liées, et il est très facile de convertir de l’une à l’autre. Leur relation est illustrée graphiquement dans la Figure 13.14.

Figure 13.14 Relation entre les formes Bézier et Hermite

Nous avons dit que la première dérivée à chacune des extrémités est entièrement déterminée par les deux points de contrôle de Bézier les plus proches. On peut en fait faire une déclaration plus générale. La $n$-ième dérivée à chaque extrémité est entièrement déterminée par les $n + 1$ points de contrôle les plus proches. La “0e dérivée” (la position de la courbe) est entièrement déterminée par le point de contrôle interpolé. La première dérivée a été discutée. La deuxième dérivée (accélération) à la fin de la courbe est déterminée par les trois points de contrôle les plus proches. En fait, voyons exactement quelle est l’accélération en termes des points de contrôle de Bézier pour une courbe cubique. En convertissant la fonction d’accélération (Équation (13.6)) de la forme monômiale à la forme Bézier, on obtient

Accélération d’une courbe de Bézier cubique

$$\begin{matrix} {\mathbf{a}(t)} & {= 2\mathbf{c}_{2} + 6\mathbf{c}_{3}t} \\ & {= 2(3\mathbf{b}_{0} - 6\mathbf{b}_{1} + 3\mathbf{b}_{2}) + 6( - \mathbf{b}_{0} + 3\mathbf{b}_{1} - 3\mathbf{b}_{2} + \mathbf{b}_{3})t} \\ & {= (6\mathbf{b}_{0} - 12\mathbf{b}_{1} + 6\mathbf{b}_{2}) + ( - 6\mathbf{b}_{0} + 18\mathbf{b}_{1} - 18\mathbf{b}_{2} + 6\mathbf{b}_{3})t.} \\ \end{matrix}$$

Aux extrémités, l’accélération est donnée par

Accélération d’une courbe de Bézier cubique aux extrémités

$$\begin{matrix} {\mathbf{a}(0)} & {= (6\mathbf{b}_{0} - 12\mathbf{b}_{1} + 6\mathbf{b}_{2}) + ( - 6\mathbf{b}_{0} + 18\mathbf{b}_{1} - 18\mathbf{b}_{2} + 6\mathbf{b}_{3})0} \\ & {= 6\mathbf{b}_{0} - 12\mathbf{b}_{1} + 6\mathbf{b}_{2},} \\ {\mathbf{a}(1)} & {= (6\mathbf{b}_{0} - 12\mathbf{b}_{1} + 6\mathbf{b}_{2}) + ( - 6\mathbf{b}_{0} + 18\mathbf{b}_{1} - 18\mathbf{b}_{2} + 6\mathbf{b}_{3})1} \\ & {= 6\mathbf{b}_{1} - 12\mathbf{b}_{2} + 6\mathbf{b}_{3}.} \\ \end{matrix}$$

Comme prévu, l’accélération au début est entièrement déterminée par les trois premiers points de contrôle, et l’accélération à la fin est déterminée par les trois derniers points de contrôle.

Définissons $\mathbf{d}_{i} = \mathbf{b}_{i + 1} - \mathbf{b}_{i}$ comme raccourci pour le delta entre des points de contrôle consécutifs, le vecteur du $i$-ième bord du polygone de contrôle de Bézier. Avec cette notation, les formules d’accélération ressemblent remarquablement aux formules de vitesse :

Accélération d’une courbe de Bézier cubique aux extrémités, en termes du delta entre des points de contrôle consécutifs

$$\begin{matrix} {\mathbf{a}(0)} & {= 6\mathbf{b}_{0} - 12\mathbf{b}_{1} + 6\mathbf{b}_{2} = 6\mathbf{b}_{0} - 6\mathbf{b}_{1} - 6\mathbf{b}_{1} + 6\mathbf{b}_{2}} \\ & {= 6\left( (\mathbf{b}_{2} - \mathbf{b}_{1}) - (\mathbf{b}_{1} - \mathbf{b}_{0}) \right)} \\ & {= 6(\mathbf{d}_{1} - \mathbf{d}_{0}),} \\ {\mathbf{a}(1)} & {= 6\mathbf{b}_{1} - 12\mathbf{b}_{2} + 6\mathbf{b}_{3} = 6\mathbf{b}_{1} - 6\mathbf{b}_{2} - 6\mathbf{b}_{2} + 6\mathbf{b}_{3}} \\ & {= 6\left( (\mathbf{b}_{3} - \mathbf{b}_{2}) - (\mathbf{b}_{2} - \mathbf{b}_{1}) \right)} \\ & {= 6(\mathbf{d}_{2} - \mathbf{d}_{1}).} \\ \end{matrix}$$

La discussion ci-dessus s’applique aux courbes de Bézier de n’importe quel degré. En général, le schéma est le suivant : si on déplace le point de contrôle $\mathbf{b}_{i}$, on affecte la $i$-ième dérivée et les dérivées supérieures au début de la courbe, mais pas les dérivées de rang inférieur. (Des déclarations similaires s’appliquent à la fin de la courbe, concernant le point de contrôle $\mathbf{b}_{i}$ et la dérivée $n - i$ et supérieures.) Bien sûr, pour un spline cubique c’est pratiquement la fin de l’histoire, puisqu’on ne peut pas déplacer aucun point de contrôle sans potentiellement changer la troisième dérivée en chaque point du spline, étant donné que la troisième dérivée est constante pour un cubique, et toutes les dérivées d’ordre supérieur sont nulles. Nous revenons à ces idées dans la Section 13.8.1 lorsque nous parlons des conditions de continuité de deux ou plusieurs segments de courbes de Bézier joints en un spline.

13.5Subdivision

En commençant par la Section 13.6, ce chapitre aborde le sujet de l’assemblage de courbes en un spline, que l’on peut rendre aussi long et complexe que souhaité. Avant cela, cette section considère le problème inverse : comment prendre une courbe et la découper en morceaux plus petits.

Pourquoi voudrait-on jamais faire cela ? Il y a quelques raisons.

• Raffinement de courbe. Dans le processus de conception d’une courbe de façon interactive, on peut constater qu’on a presque la forme souhaitée, mais qu’une seule courbe ne peut pas nous donner la flexibilité nécessaire. Alors on coupe la courbe en deux morceaux (formant un spline), ce qui donne plus de flexibilité.

• Techniques d’approximation. Une autre raison de subdiviser une courbe est qu’un morceau de courbe est généralement plus simple que la courbe entière, où “plus simple” signifie “plus proche d’une droite”. On peut donc la couper en un nombre suffisamment grand de morceaux, puis faire quelque chose avec ces morceaux comme s’ils étaient des segments de droite, par exemple les rendre ou les lancer des rayons. De cette façon, on peut approximer le résultat qu’on obtiendrait si on pouvait rendre ou lancer des rayons sur la courbe analytiquement.
  Strictement parlant, on n’a pas besoin de la subdivision pour faire une approximation linéaire par morceaux—on a déjà discuté d’une technique simple qui évalue la courbe à des intervalles de taille fixe et trace des lignes entre ces points d’échantillonnage. Mais la subdivision nous permet de choisir le nombre de segments de droite adaptivement en utilisant moins de segments sur les parties plus droites de la courbe et plus de segments sur les parties plus courbées.

Voilà le “pourquoi” de la subdivision de courbe. Avant d’apprendre le “comment”, soyons un peu plus précis sur le “quoi”. Considérons une courbe polynomiale paramétrique $P$ définie par la fonction $\mathbf{p}(t)$, en adoptant les conventions habituelles que la courbe commence en $t = 0$ et se termine en $t = 1$. Considérons maintenant un segment $Q$ qui commence à un instant arbitraire $t = a$ et se termine en $t = b$. Ceci est illustré dans la Figure 13.15.

Figure 13.15Extraction d’un segment de courbe par subdivision

L’objectif de la subdivision est une description mathématique de $Q$ sous une certaine forme (monômiale, Hermite ou Bézier). Mais n’avons-nous pas déjà cela ? Après tout, on suppose avoir une description mathématique de $P$ sous une certaine forme, et il est donc tout à fait valide de définir $Q$ en disant : “Prenez la courbe définie par $P$, mais au lieu de commencer en 0 et de se terminer en 1, commencez en $a$ et terminez en $b$.” Ce n’est pas vraiment ce que nous voulons. On veut que $Q$ soit une courbe entièrement indépendante et “régulière” qui ne fait aucune référence à $P$, non subordonnée ou qualifiée d’une quelconque façon. Par exemple, si on utilise la forme Bézier, alors on veut de nouveaux points de contrôle Bézier qui définissent $Q$.

Les sections suivantes présentent deux méthodes différentes pour subdiviser les courbes. La Section 13.5.1 présente une approche algébrique directe sous forme monômiale. La Section 13.5.2 considère la subdivision de courbe de Bézier, qui est basée géométriquement et se prête à des implémentations plutôt élégantes et efficaces.

La forme Hermite ne se prête pas naturellement à la subdivision. Si on souhaite subdiviser une forme Hermite, on convertit d’abord la courbe en une autre forme (probablement Bézier) et on effectue la subdivision sous cette forme.

13.5.1Subdivision de courbes en forme monômiale

L’extraction d’un segment d’une courbe en forme monômiale est une tâche algébrique directe. Rappelons que la forme monômiale n’est qu’un polynôme explicite en $t$. Bien qu’on s’intéresse généralement seulement à la partie où $0 \leq t \leq 1$, le polynôme est défini pour toutes les valeurs de $t$ et définit donc en fait une courbe infinie. Le segment plus petit $Q$ que l’on souhaite extraire est simplement une sous-section différente de la même courbe infinie.

Avec cela à l’esprit, on réalise que le problème de la subdivision peut facilement être vu comme un simple problème de reparamétrisation. Plutôt que d’essayer de manipuler directement les coefficients monomials, on effectue une algèbre sur la valeur du paramètre. Introduisons un paramètre local $s$ qui varie de 0 à 1 lorsque $\mathbf{q}(s)$ trace la courbe $Q$. En se basant sur cela, on peut définir la courbe $\mathbf{q}(s)$ en termes de $\mathbf{p}(t)$ comme

$$\begin{matrix} t & {= F(s),} & {\mathbf{q}(s)} & {= \mathbf{p}(t) = \mathbf{p}(F(s)),} \\ \end{matrix}$$

où la fonction $F(s)$ est notre fonction de reparamétrisation qui retourne le paramètre global $t$ correspondant au paramètre local $s$. Il n’est pas trop difficile de voir quelle forme $F$ devrait avoir, puisque on souhaite satisfaire les conditions aux limites $F(0) = a$ et $F(1) = b$. En adoptant une relation linéaire directe entre $t$ et $s$, on obtient

$$t = F(s) = a + s(b - a).$$

Il serait bon de vérifier que cela se comporte correctement aux extrémités.

Bien sûr, tout ce qu’on a vraiment accompli est de définir $Q$ en termes de $P$, ce qui est précisément ce qu’on avait dit être insuffisant au début de cette section. La différence est que si on continue à travailler avec les mathématiques, et qu’on substitue pour $\mathbf{p}(t)$ et qu’on élimine $t$, on peut obtenir une équation directe pour $\mathbf{q}(s)$, qui est une courbe “régulière” et indépendante satisfaisant les objectifs décrits au début de cette section.

Cependant, le travail algébrique qui s’ensuit produit un résultat compliqué sans révéler d’aperçu. La chose principale qu’on souhaite communiquer ici est que la subdivision d’une courbe en forme monômiale est une simple question de reparamétrisation, qui peut être accomplie algébriquement. De plus, parce qu’on peut convertir entre les formes monômiales et d’autres formes, on dispose maintenant d’une méthode infaillible pour subdiviser n’importe quelle courbe polynomiale dans n’importe quel format.

Mais nous n’avons pas à nous satisfaire de cette approche par “force brute” ; il s’avère qu’en forme de Bézier, on peut faire mieux.

13.5.2Subdivision de courbes en forme Bézier

La subdivision d’une courbe de Bézier peut être effectuée géométriquement par une variante de l’algorithme de de Casteljau. L’algorithme complet d’extraction de n’importe quelle sous-section pour des paramètres d’extrémités arbitraires $a$ et $b$ n’est pas immédiatement compréhensible, alors on suit Farin [1] et on commence par un cas simple.

On commence en se limitant à extraire seulement le “côté gauche” d’une courbe. En d’autres termes, on fixe $a = 0$. De toute évidence, le premier point de contrôle de Bézier sur la courbe plus petite (en $s = 0$) est le même que le premier point de contrôle sur la courbe plus grande (en $t = 0$). Il est tout aussi clair que l’extrémité en $t = b$ est obtainable par l’algorithme de base de Casteljau de la Section 13.4.1. Un exemple de situation avec $b = 0{,}75$ est illustré dans la Figure 13.16.

Figure 13.16 Localisation de l’extrémité intérieure à l’aide de l’algorithme de Casteljau

On a les extrémités—maintenant pour ces points intérieurs délicats. Étonnamment, si vous regardez attentivement la Figure 13.16, vous remarquerez qu’on les a déjà construits ! Il s’avère que chaque tour d’interpolation de Casteljau produit l’un de nos points de contrôle de Bézier. La Figure 13.17 rend cela plus clair, montrant les points de Bézier sélectionnés et le polygone de contrôle.

Figure 13.17 L’algorithme de Casteljau nous donne tous les points de contrôle de Bézier du segment de courbe extrait

Pourquoi cela fonctionne-t-il ? Rappelons la relation entre la forme Bézier et la forme Hermite de la Section 13.4.3. Le premier point de contrôle intérieur $\mathbf{b}_{1}$ détermine entièrement la première dérivée (la vitesse) en $t = 0$. Or, la sous-courbe que l’on extrait fait partie de la même courbe infinie, et donc sa position et ses dérivées correspondent partout, dans un sens géométrique. Cependant, la dérivée est un taux de changement par rapport au taux de changement du paramètre. En subdivisant, on a fait “avancer” le paramètre $t$ plus “rapidement”, puisqu’il passe de 0 à 1 sur un intervalle spatial plus petit. Ainsi, la dérivée de la sous-courbe est dans la même direction, mais elle est plus courte selon la fraction de la courbe qu’on extrait, dans notre cas la valeur $b$.

Résumons nos conclusions. Pour extraire la moitié gauche d’une courbe, $0 \leq t \leq b$, on effectue la subdivision de Casteljau comme si on essayait de localiser l’extrémité en $t = b$. Le premier point de contrôle de chaque tour d’interpolation nous donne un autre point de contrôle pour notre courbe subdivisée. L’extraction de la moitié droite d’une courbe est analogue, donc on n’entrera pas dans les détails ici.

Il existe un cas spécial important de la subdivision de Bézier qu’on peut faire armé seulement de ce qu’on sait jusqu’ici : subdiviser une courbe “en deux” à $t = 1/2$. Ce calcul rend possible des algorithmes récursifs plutôt élégants pour la subdivision adaptative. Utilisons notre notation standard $\mathbf{b}_{i}$ pour les points de contrôle originaux de Bézier. Pour les deux moitiés, on choisit deux lettres au hasard et on appelle les points de contrôle pour les moitiés gauche et droite de la courbe $\mathbf{q}_{i}$ et $\mathbf{r}_{i}$, respectivement. Les sept points de contrôle sont donnés par

Subdivision d’une courbe de Bézier en $\mathbf{t} = 1/2$

$$\begin{matrix} \mathbf{q}_{0} & {= \mathbf{b}_{0},} \\ \mathbf{q}_{1} & {= \mathbf{b}_{0}/2 + \mathbf{b}_{1}/2,} \\ \mathbf{q}_{2} & {= \mathbf{b}_{0}/4 + \mathbf{b}_{1}/2 + \mathbf{b}_{2}/4,} \\ {\mathbf{q}_{3} = \mathbf{r}_{0}} & {= \mathbf{b}_{0}/8 + 3\mathbf{b}_{1}/8 + 3\mathbf{b}_{2}/8 + \mathbf{b}_{3}/8,} \\ \mathbf{r}_{1} & {= \mathbf{b}_{1}/4 + \mathbf{b}_{2}/2 + \mathbf{b}_{3}/4,} \\ \end{matrix}$$

$$\begin{matrix} \mathbf{r}_{2} & {= \mathbf{b}_{2}/2 + \mathbf{b}_{3}/2,} \\ \mathbf{r}_{3} & {= \mathbf{b}_{3}.} \\ \end{matrix}$$

Le cas général est obtenu par éclosion (blossoming), qui est un terme général désignant un certain nombre de techniques impliquant des étapes de Casteljau répétées prises avec différentes fractions d’interpolation. Pour déterminer chaque point de contrôle, on effectue trois étapes de Casteljau (pour une courbe cubique, au moins). Pour chaque point de contrôle $\mathbf{b}_{i}$, on prend $i$ de ces étapes en utilisant $t = b$, et le reste en utilisant $t = a$. Il s’avère que peu importe lesquelles des étapes d’interpolation utilisent $a$ et lesquelles utilisent $b$, mais le nombre d’étapes utilisant $a$ ou $b$ est important. Considérons chaque point sur la courbe cubique pour rendre cela clair. Pour calculer $\mathbf{b}_{0}$, à chaque tour on utilise $t = a$ comme fraction d’interpolation. Pour $\mathbf{b}_{1}$, on utilise $t = a$ pour deux des tours, et $t = b$ pour un tour. Pour calculer $\mathbf{b}_{2}$, on utilise $t = a$ comme fraction d’interpolation dans seulement un tour, et $t = b$ pour les deux autres. Et bien sûr, pour le dernier point de contrôle $\mathbf{b}_{3}$, on utilise $t = b$ pour les trois tours, exactement comme décrit au début de cette section.

13.6Splines

Jusqu’à présent, nous nous sommes concentrés sur les courbes cubiques, et pour de bonnes raisons ; ce sont les types de courbes les plus couramment utilisés en 3D. De telles courbes ont intrinsèquement quatre degrés de liberté, que l’on utilise des courbes de Bézier avec quatre points de contrôle, des courbes monômiales avec quatre coefficients, ou des courbes Hermite avec deux points extrêmes plus deux dérivées. Parce qu’il n’y a que quatre degrés de liberté, l’ensemble des courbes représentables en utilisant seulement les techniques des courbes cubiques est fortement limité.

Une liberté supplémentaire est obtenue en joignant des courbes plus petites ensemble dans un spline, qui est le sujet du reste de ce chapitre. Avant de discuter des splines, faisons une pause pour discuter d’une alternative potentielle : utiliser un polynôme de degré supérieur. Évidemment, toute courbe de degré $n$ peut être convertie en une courbe de degré $n + 1$ ; une telle conversion est connue sous le nom d’élévation de degré. En forme monômiale, bien sûr, c’est trivial, on ajoute simplement un nouveau coefficient directeur nul.

En forme Bézier, l’élévation de degré ajoute un nouveau point de contrôle et, comme vous pourriez l’avoir deviné, les positions des nouveaux points de contrôle peuvent être construites géométriquement par interpolation linéaire. Étant donné une courbe de degré $n$, qui a $n + 1$ points de contrôle notés $\mathbf{b}_{i}$, l’élévation de degré produit une courbe de degré $n + 1$ avec $n + 2$ points de contrôle, notés $\mathbf{b}_{j}^{\prime}$. Pour déterminer ces nouveaux points de contrôle, on interpole linéairement avec une fraction d’interpolation proportionnelle à l’indice du point de contrôle :

Élévation de degré en forme Bézier

$$\begin{matrix} {\mathbf{b}_{j}^{\prime} = \frac{j}{n + 1}\,\mathbf{b}_{j - 1} + \left( 1 - \frac{j}{n + 1} \right)\mathbf{b}_{j},\quad\quad 0 \leq j \leq n + 1.} \\ \end{matrix}$$

(Notez que le calcul de $\mathbf{b}_{j}^{\prime}$ va “mélanger” le point inexistant $\mathbf{b}_{- 1}^{\prime}$ avec un poids de zéro.)

Pour les courbes Hermite, on s’intéresse généralement seulement aux valeurs impaires de $n$, de sorte qu’on ait le même nombre de dérivées à chaque extrémité.

Un polynôme de degré supérieur a la capacité de décrire une courbe avec plus de “ondulations”, mais malheureusement, en général il souffre de plusieurs inconvénients :

• La courbe a un support global. Chaque point de contrôle exerce un certain poids non nul sur chaque point le long de la courbe, à l’exception des extrémités.

• La courbe a des “ondulations” parasites qui apparaissent parfois dans des endroits indésirables, oscillant d’avant en arrière entre les points de contrôle. C’est connu sous le nom de phénomène de Runge17.

• En lien avec ces ondulations supplémentaires, les courbes de degré élevé sont très sensibles. En raison du support global de la courbe, un changement sur l’un des points de contrôle entraîne un changement sur toute la courbe ; en raison de la haute sensibilité, cette réponse peut être très grande.

• Ayant exclu l’interpolation polynomiale comme outil viable de conception de courbes, on ne peut pas directement spécifier un point que l’on veut voir la courbe interpoler, à l’exception des extrémités.

Le problème de base est qu’on demande trop à un seul polynôme. Les splines n’ont pas ces inconvénients.

Voici ce qui nous attend. Premièrement, pour faciliter la discussion, on doit développer notre notation et introduire un niveau d’indirection entre la paramétrisation locale et globale, ce que l’on fait dans les Sections 13.6.1 et 13.6.2. Ensuite, dans la Section 13.7, on parle des splines Hermite et Bézier, qui sont utilisés dans de nombreux logiciels, tels qu’Adobe Photoshop et Autodesk 3DS Max. À partir de là, notre attention se porte naturellement vers la décision de quoi faire aux “jonctions”. Le premier obstacle est de définir les critères qui doivent être satisfaits pour que la courbe soit lisse en ces points de jonction. De telles conditions de continuité font l’objet de la Section 13.8. Une fois ces questions comprises, on aura finalement atteint notre objectif fixé au début de ce chapitre, un système de splines qui fournit un moyen intuitif de définir une forme courbe.

Après avoir développé un outil de conception flexible où l’utilisateur peut spécifier la position et la tangente à chaque point de contrôle, la Section 13.9 explore ensuite les méthodes par lesquelles le concepteur n’a qu’à spécifier les positions des points de contrôle, et les tangentes sont calculées automatiquement en fonction d’un ensemble de contrôles utilisateur intuitifs.

13.6.1Règles du jeu

Notre spline est composé de $n$ segments, notés $\mathbf{q}_{0}$, $\mathbf{q}_{1}$, …,  $\mathbf{q}_{n - 1}$. Le $i$-ième segment $\mathbf{q}_{i}$ est une fonction qui accepte un paramètre local, nommé $s_{i}$, qui est normalisé pour varier de 0 à 1 sur la longueur du segment. En d’autres termes, pour chaque segment il y a une fonction de courbe $\mathbf{q}_{i}(s_{i})$ exactement comme celles que nous avons étudiées dans la première partie de ce chapitre ; les seules différences sont le renommage cosmétique de la fonction de $\mathbf{p}$ à $\mathbf{q}_{i}$ et de l’argument de $t$ à $s_{i}$.

On utilise deux notations différentes pour désigner le spline entier. Une façon est de simplement supprimer les indices de la notation ci-dessus, de sorte que la fonction $\mathbf{q}(s)$ désigne le spline entier, et le paramètre $s$ (sans indice) est un paramètre global. Lorsque $s$ varie de 0 à $n$, la fonction $\mathbf{q}(s)$ trace tout le spline.

La fonction composite $\mathbf{q}(s)$ est très simple. Fondamentalement, on prend la partie entière de $s$ pour obtenir l’indice $i$, décrivant sur quel segment on se trouve, puis la partie fractionnaire est utilisée comme $s_{i}$ et injectée dans le segment $\mathbf{q}_{i}$. Ainsi, le premier segment $\mathbf{q}_{0}(s_{0})$ définit le spline sur l’intervalle entre $\mathbf{q}(0)$ et $\mathbf{q}(1)$, le deuxième segment définit le spline de $\mathbf{q}(1)$ à $\mathbf{q}(2)$, et ainsi de suite. Plus formellement,

Une courbe composite avec une paramétrisation globale simple

$$\begin{matrix} i & {= \lfloor s\rfloor,} & & \text{(sélection du segment par la fonction plancher)} \\ s_{i} & {= s - i,} & & \text{(calcul du paramètre local)} \\ {\mathbf{q}(s)} & {= \mathbf{q}_{i}(s_{i}).} & & \text{(évaluation du segment)} \\ \end{matrix}$$

Notez que, pour une valeur particulière de $s$, on peut identifier sans ambiguïté le point $\mathbf{q}(s)$ le long du spline. Cependant, une valeur particulière de $s_{i}$ n’est significative que dans le contexte du segment $i$ ; c’est ce qui est mis en évidence par l’indice.

Si on ne s’intéresse pas au timing de notre courbe, alors cette notation peut suffire. Cependant, pour définir un chemin d’animation, on a généralement besoin d’un niveau d’indirection. On introduit la notation $\mathbf{p}(t)$ pour désigner la courbe finale, une fonction qui retourne notre position à un “temps” $t$ donné. C’est simplement une paramétrisation différente de la même courbe ; $\mathbf{p}(t)$ et $\mathbf{q}(s)$ tracent la même forme, mais les valeurs de $s$ et $t$ pour un point particulier le long du chemin ne seront généralement pas les mêmes. On peut paramétrer la courbe de sorte que certaines sections soient parcourues rapidement et d’autres plus lentement. L’intervalle de $s$ est fixé par le nombre de nœuds, mais on est libre d’assigner l’intervalle de $t$, la durée totale de la courbe, à n’importe quelle valeur.

En général, on peut définir $\mathbf{p}(t)$ en termes de $\mathbf{q}(s)$ en créant une fonction qui associe une valeur temporelle $t$ à une valeur de paramètre $s$. Lorsqu’on veut être explicite que $s$ est une fonction de $t$, on utilise la notation $s(t)$, et cette fonction est appelée la fonction temps-vers-paramètre. Si vous êtes programmeur, vous pouvez penser à $\mathbf{p}(t)$ comme l’interface publique, et à $\mathbf{q}(s)$ comme un détail d’implémentation interne. On s’engage dans une pratique fondamentale de l’informatique : réduire la complexité en introduisant un niveau d’indirection.

Avec la notation ci-dessus établie, le plan de base pour évaluer $\mathbf{p}(t)$ est le suivant :

1. Associer la valeur temporelle $t$ à une valeur de $s$ en évaluant la fonction temps-vers-paramètre $s(t)$.

2. Extraire la partie entière de $s$ comme $i$, et la partie fractionnaire comme $s_{i}$.

3. Évaluer le segment de courbe $\mathbf{q}_{i}(s_{i})$.

Bien sûr, si on ne se soucie pas du timing du spline (peut-être qu’on se soucie seulement de sa forme), alors on n’a pas besoin de la première étape, et on peut simplement utiliser l’association triviale $s(t) = t$. Malheureusement, en raison des contraintes d’espace, c’est précisément ce que l’on va faire dans ce livre. On ne discutera pas des subtilités du traitement du timing.

En supposant pour l’instant que $s = t$, la première étape est triviale. La deuxième étape est également facile, et on a consacré la première partie de ce chapitre à la troisième étape. Donc on sait vraiment déjà comment évaluer un spline ; voyons comment on pourrait en créer un.

13.6.2Nœuds

Pensons à la jonction entre deux segments. Pour que la courbe soit continue, il est clair que le point d’arrivée d’un segment doit coïncider avec le point de départ du segment suivant. (La Section 13.8 traite de critères supplémentaires souhaitables.) Ces points de contrôle partagés qui sont interpolés par le spline sont appelés les nœuds du spline. Le nœud à l’indice $i$ est noté $\mathbf{k}_{i}$, et puisqu’il y a un nœud de plus que le nombre de segments, les nœuds sont numérotés $\mathbf{k}_{0}\ldots\mathbf{k}_{n}$.

On suppose que les segments sont connectés aux nœuds. En d’autres termes, $\mathbf{q}(s)$ passe par les nœuds aux valeurs entières de $s$. Avec cette hypothèse, il n’est pas nécessaire d’avoir une notation séparée (ou un espace de stockage séparé dans un programme informatique) pour le point de début et le point de fin de chaque segment. À la place, chaque nœud intérieur $\mathbf{k}_{i}$ joue un double rôle en tant que point de départ du segment $\mathbf{q}_{i}$ et point d’arrivée du segment $\mathbf{q}_{i - 1}$. Ainsi, on établit les relations suivantes :

$$\begin{matrix} {\mathbf{q}(i)} & {= \mathbf{k}_{i},} & {\mathbf{q}_{i}(0)} & {= \mathbf{k}_{i},} & {\mathbf{q}_{i}(1)} & {= \mathbf{k}_{i + 1}.} \\ \end{matrix}$$

Notez que $\mathbf{k}_{i}$ spécifie un seul point, tandis que la notation $\mathbf{q}_{i}$ désigne un segment entier, qui est une fonction d’un paramètre local $s_{i}$ qui donne un point. Toute cette notation est représentée dans la Figure 13.18.

Figure 13.18 Un spline à $n$ segments a $n + 1$ nœuds, nommés $\mathbf{k}_{0}\ldots\mathbf{k}_{n}$.

Dans les contextes d’animation, les nœuds sont parfois appelés des clés. Cela fait référence aux anciennes méthodes d’animation où un animateur principal créait les images clés, ou images où les personnages atteignaient des poses importantes. Les images intermédiaires étaient remplies par un apprenti moins expérimenté (et moins coûteux). En animation informatique, une clé peut être n’importe quelle position, orientation ou autre donnée dont la valeur à un moment particulier est spécifiée par un animateur humain (ou toute autre source). Le rôle de l’apprenti pour “remplir les images manquantes” est joué par le programme d’animation, en utilisant des méthodes d’interpolation telles que celles discutées dans ce chapitre. Comme on l’a déjà noté, la plupart des premières recherches sur les splines visaient à définir des formes statiques, pas des trajectoires animées, et donc le terme “nœud” est plus répandu.

13.7Splines de Hermite et de Bézier

Un spline est créé en assemblant des segments de courbe de sorte qu’ils s’emboîtent ensemble de façon lisse. Quel type de segments de courbe ? Pour des raisons qui deviendront bientôt évidentes, il est plus pratique pour nous d’utiliser la représentation Hermite pour les segments individuels. Quand on dit pratique “pour nous”, on entend les personnes qui écrivent le code d’un système d’animation ou qui effectuent la discussion mathématique dans les sections suivantes. Lorsqu’il s’agit de représenter ou de manipuler des splines graphiquement, la forme Bézier est généralement préférée. Bien sûr, les formes Hermite et Bézier sont étroitement liées, et il est facile de convertir entre les deux formes. Si vous ne vous rappelez pas cette relation, on la passe en revue dans un moment.

Rappelons qu’un segment de courbe Hermite est défini par ses positions et vitesses de début et de fin. Lorsqu’on se concentrait sur un seul segment, on désignait les positions par $\mathbf{p}_{0}$ et $\mathbf{p}_{1}$, et les vitesses par $\mathbf{v}_{0}$ et $\mathbf{v}_{1}$. Dans le contexte d’un spline, on utilise une notation organisée autour d’un nœud plutôt que d’un segment. Pour les positions, on n’utilise pas les $\mathbf{p}$ parce que, comme dit précédemment, le nœud $\mathbf{k}_{i}$, qui est la position de départ du segment $\mathbf{q}_{i}(0)$, sert également de position d’arrivée du segment précédent en $\mathbf{q}_{i - 1}(1)$. Pour les vitesses, la notation $\mathbf{v}_{i}^{out}$ désigne la vitesse sortante au nœud $i$ et définit la vitesse de départ pour le segment $\mathbf{q}_{i}$. De même, la vitesse entrante du côté gauche de $\mathbf{k}_{i}$ est notée $\mathbf{v}_{i}^{in}$ et définit la vitesse d’arrivée du segment précédent $\mathbf{q}_{i - 1}$. On désigne également ces vecteurs vitesse sous le nom de tangentes.

La Figure 13.19 montre un spline avec cinq segments Hermite. Tous les nœuds, segments et tangentes sont étiquetés selon la notation qui vient d’être décrite.

Figure 13.19Notre notation pour les splines avec des segments en forme Hermite

Soyez prévenus que les tangentes dans la Figure 13.19—et dans toutes les figures de courbes Hermite dans ce chapitre—sont dessinées à un tiers de l’échelle. Officiellement, nous voudrions vous dire que cela a été fait pour que les diagrammes soient plus petits et que ce livre consomme moins de ressources naturelles de la Terre. Une raison plus précise est qu’on dessine les tangentes à un tiers de leur longueur pour que les tangentes soient les mêmes que les bords du polygone de contrôle de Bézier. Correspondre au polygone de contrôle de Bézier a des avantages pédagogiques, mais, plus important encore, cela facilite la paresse de la part des auteurs : les outils utilisés pour créer les courbes dans les diagrammes sont basés sur des splines de Bézier.

Les splines des diagrammes de ce livre ont été créés dans Adobe Photoshop en faisant un tracé et en “appliquant un contour” au tracé. Les flèches pour les vecteurs tangents ont été dessinées en plaçant une extrémité à un nœud et l’autre extrémité sur la “poignée” utilisée pour contrôler la forme de la courbe, qui est essentiellement la même que le point de contrôle de Bézier. (Photoshop appelle les nœuds les “points d’ancrage” et désigne les points de contrôle de Bézier intérieurs qui ne sont pas interpolés comme “points de contrôle”.)

Par exemple, la Figure 13.20 est une capture d’écran prise pendant qu’un auteur était en train de créer la Figure 13.19. (L’opacité de la figure réelle a été réduite pour rendre les contrôles Photoshop plus faciles à voir.)

Figure 13.20Création de la Figure 13.19 avec Adobe Photoshop.

Puisqu’on est sur le sujet des courbes de Bézier, profitons de cette occasion pour introduire la notation que l’on utilise pour les splines de Bézier. Lorsqu’on traitait seulement un seul segment de Bézier, on désignait le $i$-ième point de contrôle de ce segment par $\mathbf{b}_{i}$. Ici on utilise la notation $\mathbf{f}_{i}$ pour désigner le point de contrôle “devant” le $i$-ième nœud, et $\mathbf{a}_{i}$ pour le point de contrôle “après” lui.18 Cette notation est illustrée dans la Figure 13.21.

Figure 13.21 Un spline avec son polygone de contrôle de Bézier, et la notation utilisée pour les splines de Bézier

La relation importante entre les formes Hermite et Bézier a été introduite dans la Section 13.4.3. Reformulons-la ici dans la notation de spline nouvellement introduite :

Conversion entre les formes Bézier et Hermite

$$\begin{matrix} \mathbf{v}_{i}^{in} & {= 3(\mathbf{k}_{i} - \mathbf{f}_{i}),} & \mathbf{f}_{i} & {= \mathbf{k}_{i} - \mathbf{v}_{i}^{in}/3,} \\ \mathbf{v}_{i}^{out} & {= 3(\mathbf{a}_{i} - \mathbf{k}_{i}),} & \mathbf{a}_{i} & {= \mathbf{k}_{i} + \mathbf{v}_{i}^{out}/3.} \\ \end{matrix}$$

13.8Continuité

Depuis quelques sections, on promet de vous dire comment assembler des segments en un spline de sorte qu’ils s’emboîtent ensemble de façon lisse. Tout ce préambule a peut-être donné l’impression que c’est un secret mystérieux. Mais si vous regardez de plus près la Figure 13.19, vous verrez que le critère est relativement évident : si les vecteurs vitesse entrants et sortants sont égaux à un nœud, comme c’est le cas en $\mathbf{k}_{1}$ et aussi $\mathbf{k}_{2}$, alors la courbe sera lisse. Notez qu’en $\mathbf{k}_{3}$, les tangentes ne sont pas égales, et la courbe a un angle brusque. Assez évident, non ? En fait, il y a beaucoup plus à dire sur ce sujet.

Considérons la courbe près de $\mathbf{k}_{4}$ dans la Figure 13.19. Notez que la courbe est “lisse”, pourtant le vecteur vitesse entrant $\mathbf{v}_{4}^{in}$ est bien plus long que $\mathbf{v}_{4}^{out}$. Maintenant, vous pourriez penser, “Cette courbe n’est pas lisse là ! Si vous voyagiez le long de la courbe, vous appuieriez sur les freins juste au moment de franchir la clé.” Mais retirez les vecteurs tangents du diagramme et regardez seulement la forme de la courbe. C’est une forme lisse, n’est-ce pas ? On revient à un thème récurrent : les chemins d’animation sont plus “exigeants” que les formes statiques. (Notez que dans l’objection que vous venez de soulever, vous avez utilisé une terminologie orientée animation quand vous avez dit “clé” au lieu de “nœud”. Vous apprenez vraiment vite !)

En parlant d’animations fluides, on vient de dire que la courbe est lisse en $\mathbf{k}_{1}$ et $\mathbf{k}_{2}$. Mais l’est-elle vraiment ? On peut voir que la forme est lisse, mais on vient de souligner qu’il y a une différence entre une forme lisse et une animation lisse. En général, on ne peut pas savoir si l’animation est lisse sans en savoir plus sur la fonction temps-vers-paramètre $s(t)$. Si la forme n’est pas lisse, l’animation ne le sera pas (avec une exception à discuter dans un moment). Mais même si la forme est lisse, les discontinuités dans $s(t)$ peuvent entraîner des discontinuités dans l’animation. Quand $s(t) = t$, aucune discontinuité n’est introduite par cette association triviale, donc si les tangentes sont égales, le mouvement sera lisse.

Enfin, considérons un nœud pour lequel les vitesses entrante et sortante sont toutes deux nulles. Dans ce cas, même si les tangentes sont continues, la plupart des gens s’accorderaient à dire que la forme n’est pas lisse à ce nœud. Qu’en est-il du mouvement ? Le mouvement est-il lisse quand on s’arrête complètement et qu’on accélère dans une direction potentiellement différente ? Cela dépend de vos besoins.

Il semble que la réponse à la question “Est-ce lisse ?” soit un peu floue. Il s’agit d’un livre de mathématiques, et c’est vraiment mauvaise pratique d’utiliser des guillemets autour de mots vagues comme “lisse”. On a vraiment besoin d’une terminologie plus précise. Dans le contexte des courbes, les critères de lissage les plus importants sont la continuité paramétrique et la continuité géométrique étroitement liée. Examinons chacun d’eux à tour de rôle, en commençant par la continuité paramétrique, qui est plus facile à définir mathématiquement.

13.8.1Continuité paramétrique

On dit qu’une courbe a la continuité $C^{n}$ si ses $n$ premières dérivées sont continues. Une courbe $C^{0}$ est une courbe dont la position (la “0e dérivée”) est continue. La continuité $C^{0}$ signifie qu’on peut dessiner une forme sur une feuille de papier en un seul trait sans lever le crayon, ou qu’on peut se déplacer le long d’un chemin d’animation sans “se téléporter”.19 Une courbe $C^{1}$ a une première dérivée continue, ce qui signifie que la vitesse ne saute pas instantanément. Cela ne signifie pas que la vitesse ne peut pas changer rapidement, mais elle ne passe jamais d’une vitesse à un instant à une vitesse différente à l’instant suivant sans passer par des vitesses intermédiaires. Par exemple, la courbe dans la Figure 13.19 forme une ligne connectée, donc elle est $C^{0}$ continue partout. Elle est $C^{1}$ continue partout sauf en $\mathbf{k}_{3}$ et $\mathbf{k}_{4}$, où la vitesse saute soudainement.

Des valeurs plus grandes de $n$ signifient simplement que les dérivées d’ordre plus élevé de la courbe sont continues. Une courbe est $C^{2}$ si sa deuxième dérivée (l’accélération) est continue. Les conditions de continuité au-delà de $C^{1}$ ne sont pas si importantes pour nos besoins dans ce livre. L’absence de continuité $C^{1}$ (un changement soudain de vitesse) correspond à une accélération infinie, et cela peut créer de nombreux problèmes. Si le chemin est utilisé pour contrôler un objet physique, comme un robot ou un outil de coupe, alors on demande aux moteurs qui entraînent l’objet de faire quelque chose qui est physiquement impossible. Même si l’animation se déroule entièrement dans le monde virtuel d’un ordinateur, lorsque de tels chemins sont observés par des humains, ils sont généralement perçus comme “saccadés”. Ainsi, il est généralement souhaitable d’éviter (ou du moins de contrôler) les discontinuités de vitesse. En revanche, un changement soudain d’accélération ne crée pas une telle sensation de choc et pour la plupart des usages est parfaitement acceptable.

Tout segment de courbe polynomiale individuel en lui-même a la continuité $C^{\infty}$, puisqu’on peut prendre la dérivée d’un polynôme autant de fois qu’on veut et on obtient toujours une fonction réelle continue. (Finalement, les dérivées deviennent la fonction constante nulle.) C’est pourquoi la question de la continuité ne s’est pas posée plus tôt dans le chapitre—les seuls endroits où on doit s’inquiéter de la continuité sont aux nœuds.

Un dernier commentaire concernant les dérivées d’ordre supérieur. Quand on dit qu’une courbe est $C^{n}$ continue, cela implique la continuité pour toutes les dérivées inférieures également. Par exemple, si l’accélération est continue, alors la vitesse et la position doivent aussi être continues. Une discontinuité dans une fonction signifie que la dérivée de la fonction est indéfinie à l’endroit où la discontinuité se produit.

Maintenant qu’on a discuté de la continuité paramétrique de façon informelle, définissons les critères mathématiquement pour les courbes Hermite et Bézier. Pour ce faire, on tire parti de certaines observations concernant les dérivées des courbes de Bézier de la Section 13.4.3 ; nos résultats de cette section sont résumés ici.

• La $n$-ième dérivée à une extrémité d’un segment de courbe de Bézier est entièrement déterminée par l’extrémité et les $n$ points de contrôle les plus proches.

• La vitesse à une extrémité est proportionnelle au vecteur entre l’ extrémité et le point de contrôle adjacent (Équations (13.30) et (13.31)).

• L’accélération à une extrémité est proportionnelle à la différence des vecteurs delta le long des deux segments les plus proches du polygone de contrôle (Équations (13.36) et (13.37)).

Commençons par $C^{0}$, qui est évident de par notre choix de notation. Dans notre schéma, le point d’arrivée d’un segment est le même que le point de départ du segment suivant par définition. En passant à la continuité $C^{1}$, on a dit qu’elle se produit lorsque les tangentes sont égales à une clé. Cela se traduit directement en forme Hermite comme

Condition de continuité $\mathbf{C}^{1}$ pour les splines Hermite

$$\mathbf{v}_{i}^{in} = \mathbf{v}_{i}^{out},$$

et avec un peu d’effort on peut aussi l’exprimer en forme Bézier comme

Condition de continuité $\mathbf{C}^{1}$ pour les splines de Bézier cubiques

$$\begin{matrix} {\mathbf{k}_{i} - \mathbf{f}_{i} = \mathbf{a}_{i} - \mathbf{k}_{i}.} \\ \end{matrix}$$

Avec une application rapide de l’algèbre, on voit que géométriquement cela signifie que le nœud est au milieu du segment entre $\mathbf{f}_{i}$ et $\mathbf{a}_{i}$ :

$$\begin{matrix} {\mathbf{k}_{i} - \mathbf{f}_{i}} & {= \mathbf{a}_{i} - \mathbf{k}_{i},} \\ {2\mathbf{k}_{i}} & {= \mathbf{f}_{i} + \mathbf{a}_{i},} \\ \mathbf{k}_{i} & {= (\mathbf{f}_{i} + \mathbf{a}_{i})/2.} \\ \end{matrix}$$

La plupart des outils de conception de courbes appliquent automatiquement cette règle pour vous. Par exemple, lorsqu’on déplace un point de contrôle dans Photoshop, il déplace automatiquement le point de contrôle opposé comme une balançoire, et si on tire le point de contrôle loin du point d’ancrage (le nœud), le point de contrôle opposé va miroiter vos mouvements pour maintenir la relation de continuité $C^{1}$. (Si vous voulez forcer un angle dans la courbe, vous pouvez maintenir une touche modificatrice pour indiquer à Photoshop de ne pas faire cela).

Examinons maintenant la continuité $C^{2}$. Elle est plus facile à visualiser en forme Bézier qu’Hermite. On a juste besoin d’appliquer ce qu’on a appris dans la Section 13.4.3 pour faire correspondre l’accélération finale d’un segment (le côté gauche des équations ci-dessous) à l’accélération initiale du segment suivant (à droite) :

Condition de continuité $\mathbf{C}^{2}$ pour les splines de Bézier cubiques $$\begin{matrix} {6\mathbf{a}_{i - 1} - 12\mathbf{f}_{i} + 6\mathbf{k}_{i}} & {= 6\mathbf{k}_{i} - 12\mathbf{a}_{i} + 6\mathbf{f}_{i + 1},} \\ {\mathbf{a}_{i - 1} - 2\mathbf{f}_{i} + \mathbf{k}_{i}} & {= \mathbf{k}_{i} - 2\mathbf{a}_{i} + \mathbf{f}_{i + 1}} \\ {2\mathbf{f}_{i} - \mathbf{a}_{i - 1},} & {= 2\mathbf{a}_{i} - \mathbf{f}_{i + 1},} \\ {\mathbf{f}_{i} + (\mathbf{f}_{i} - \mathbf{a}_{i - 1})} & {= \mathbf{a}_{i} + (\mathbf{a}_{i} - \mathbf{f}_{i + 1}).} \\ \end{matrix}$$

L’interprétation géométrique est la suivante : prenez les deux segments du polygone de contrôle de Bézier qui ne sont pas des voisins directs du nœud, mais à un segment de distance, et “doublez-les”. S’ils se rejoignent en un point commun, la courbe est $C^{2}$ continue. Pour visualiser cela, comparez les deux courbes de Bézier dans la Figure 13.22. Les deux ont la continuité $C^{1}$, puisque le nœud $\mathbf{k}_{i}$ est au milieu du segment entre $\mathbf{f}_{i}$ et $\mathbf{a}_{i}$ pour les deux courbes. Cependant, la courbe du haut est $C^{2}$ continue parce que les extensions des lignes du polygone de contrôle voisin se rencontrent au point commun ; la courbe du bas n’est pas $C^{2}$ continue.

Figure 13.22Conditions de continuité pour les splines de Bézier cubiques.

13.8.2Continuité géométrique

La continuité géométrique est un critère de continuité plus large. Différents auteurs utilisent différentes définitions pour la continuité géométrique, mais une définition très générale est qu’une courbe a la continuité $G^{n}$ s’il existe une façon de paramétrer la courbe telle que la courbe ait la continuité $C^{n}$. Examinons un exemple.

Dans la Figure 13.19, la courbe n’est pas $C^{1}$ continue en $\mathbf{k}_{4}$ parce que les tangentes ne sont pas égales. Cependant, la courbe est $G^{1}$ continue à cet endroit. L’indice, bien sûr, est que les tangentes sont parallèles au nœud. Si les tangentes à un nœud ne sont pas parallèles, alors il n’y a aucun moyen de se déplacer le long de la courbe de façon lisse. Cependant, si les tangentes sont parallèles, alors la discontinuité est purement un changement de vitesse, pas un changement de direction. On pourrait supprimer cette discontinuité en introduisant soigneusement une discontinuité compensatrice dans la fonction temps-vers-paramètre $s(t)$ qui “défait” exactement le saut de vitesse.

La continuité géométrique d’ordre supérieur étend cette idée, bien qu’il soit un peu plus difficile à visualiser. On dit qu’une courbe est $G^{2}$ continue si sa courbure change continûment.

13.8.3Quelle est la régularité maximale d’une courbe ?

On clôt notre discussion sur la continuité en posant une question importante : quel est le niveau de continuité le plus élevé qu’on peut attendre d’un spline polynomial ? On a dit plus tôt que tout segment de courbe particulier a la continuité $C^{\infty}$, parce qu’on peut le différentier autant de fois qu’on veut et le résultat est toujours une fonction continue. Peut-on atteindre ce même niveau de régularité avec un spline ?

Considérons deux segments de Bézier cubiques adjacents. Fixons le premier segment et considérons ce qui se passe au deuxième segment lorsqu’on exige des niveaux de plus en plus élevés de continuité au nœud. Quand on exige la continuité $C^{0}$, on fixe le premier point de contrôle de Bézier. De toute évidence, la première extrémité doit correspondre à la dernière extrémité du premier segment pour que le spline soit $C^{0}$ continu.

Qu’en est-il de la continuité $C^{1}$ ? Rappelons que la vitesse à une extrémité est entièrement déterminée par l’extrémité et le point de contrôle adjacent. Cela signifie que si on veut faire correspondre la vitesse, on fixe aussi la position du deuxième point de contrôle.

En continuant ce schéma, on voit que pour qu’un segment de Bézier corresponde à $n$ dérivées, il faut “fixer” $n + 1$ points de contrôle. Pour une courbe cubique, si on demande la continuité $C^{4}$ ou supérieure, on peut l’obtenir, mais seulement en faisant en sorte que chaque segment soit une partie du même polynôme infini. On a gagné en continuité, mais on a perdu la flexibilité qui était la raison même pour laquelle on utilisait des splines en premier lieu !

En résumé, concrètement parlant, une courbe polynomiale de degré $n$ (une courbe de Bézier avec $n + 1$ points de contrôle) ne peut vraiment atteindre que la continuité $C^{n - 1}$. Par exemple, un polynôme linéaire par morceaux (degré 1) ne peut atteindre que la continuité $C^{0}$. On peut créer une courbe connectée, mais avec des lignes droites, on ne peut pas faire correspondre les tangentes. Un polynôme quadratique (degré 2) peut faire correspondre les tangentes ( $C^{1}$), mais pas les accélérations. Une courbe cubique, le type de courbe sur lequel on s’est concentré dans ce livre, peut atteindre la continuité $C^{2}$ en réduisant le nombre de degrés de liberté par segment à un. La continuité au-delà de $C^{2}$ ne peut être obtenue qu’en éliminant tous les degrés de liberté (autres que le timing de la courbe), et en fixant chaque segment à être une section du même polynôme.

13.9Contrôle automatique des tangentes

Au début de ce chapitre, on a commencé notre investigation sur les courbes avec le plan de définir une courbe simplement en listant les points par lesquels on voulait que la courbe passe. On a essayé l’interpolation polynomiale de base dans la Section 13.2, mais on a constaté qu’elle ne donnait pas ce qu’on voulait. On a ensuite développé les formes Bézier, qui nécessitent que l’utilisateur spécifie deux extrémités, qui sont interpolées, et deux (dans le cas d’un Bézier cubique) points de contrôle intérieurs, qui ne sont pas interpolés mais définissent plutôt les dérivées aux extrémités. Jusqu’à présent dans ce chapitre, on a appris à assembler ces segments de Bézier en un spline lisse.

Cette section explore diverses méthodes par lesquelles un spline peut être déterminé uniquement par les nœuds, sans que l’utilisateur ait besoin de spécifier d’autres critères. Cela est utile pour générer une courbe qui semble “naturelle” et passe par certains points, ou à n’importe quel autre moment où on souhaite interpoler des données de façon lisse.

Pour l’instant, ignorons les premier et dernier nœuds et concentrons notre attention sur les nœuds intérieurs. Le problème à résoudre consiste à calculer un $\mathbf{v}_{i}^{in}$ et $\mathbf{v}_{i}^{out}$ appropriés en utilisant seulement les positions des nœuds. Notez qu’on pose le problème en forme Hermite, qui s’avère être la forme la plus facile à utiliser pour ce problème. La situation est représentée dans la Figure 13.23, qui montre trois points de contrôle et trois choix différents qu’on pourrait utiliser pour les tangentes.

Figure 13.23 Trois choix différents de tangentes pour le nœud central, conduisant à trois splines d’interpolation différents

Les sections suivantes discutent d’une famille de techniques qui peuvent être utilisées pour choisir des tangentes qui donnent de “bons” splines d’interpolation. Premièrement, la Section 13.9.1 discute du spline de Catmull-Rom, qui est une technique simple et directe. Ensuite, la Section 13.9.2 considère les splines TCB, une généralisation de la forme de Catmull-Rom et un hybride qui expose des “curseurs” supplémentaires à l’utilisateur pour ajuster la forme de la courbe de façon (espérons-le) plus intuitive sans recourir à la spécification géométrique directe des tangentes. Enfin, la Section 13.9.3 liste quelques options pour traiter les extrémités.

En lisant les sections suivantes, gardez à l’esprit que tous ces splines sont toujours des splines Hermite. On introduit simplement diverses techniques pour calculer automatiquement les tangentes. Une fois les tangentes déterminées, le spline n’est pas différent de tout autre spline Hermite.

13.9.1Splines de Catmull-Rom

En regardant la Figure 13.23, il semble évident lequel des trois choix de tangentes est le plus naturel : celui du milieu. Pourquoi cela ? Le vecteur du nœud précédent $\mathbf{k}_{i - 1}$ vers le nœud suivant $\mathbf{k}_{i + 1}$ est une ligne horizontale, et il est donc logique que nos tangentes soient horizontales. Ainsi, il semble qu’une heuristique qu’on pourrait utiliser pour choisir de bonnes tangentes serait de faire en sorte que les tangentes à un nœud soient parallèles au segment entre le nœud précédent et le suivant. (Notez que notre exemple est légèrement artificiel dans le sens où le nœud central se trouve à mi-chemin entre ses voisins, ce qui est un cas particulier. Cependant, le fait que les voisins se trouvent sur une ligne horizontale n’est pas un cas particulier, puisqu’on peut toujours faire pivoter notre perspective pour voir les points dans cette configuration.)

Mais quelle longueur devraient avoir les tangentes ? Peut-être devrions-nous encore utiliser le vecteur entre les nœuds précédent et suivant comme guide. Il semble que plus nos voisins sont éloignés, plus la courbe est grande, et donc faire en sorte que nos tangentes soient un multiple constant de ce vecteur serait une bonne idée. En d’autres termes, on poserait $\mathbf{v}_{i}^{in} = \mathbf{v}_{i}^{out} = a(\mathbf{k}_{i + 1} - \mathbf{k}_{i - 1})$. Mais quelle valeur utiliser pour $a$ ?

Une façon serait d’expérimenter et de trouver un nombre arrondi agréable qui semble donner des résultats esthétiquement plaisants. La constante $a = 1/2$ est un nombre arrondi agréable et fonctionne modérément bien, alors prenons-la. La Figure 13.24 montre un spline en boucle généré par cette technique.

Figure 13.24Un spline de Catmull-Rom

Bien que $a = 1/2$ donne des résultats “moyens”, il y a définitivement un argument à soutenir que c’est une question de préférence. Parfois on veut une courbe plus “serrée”, ce qui correspondrait à des valeurs plus petites de $a$, et parfois on veut une courbe plus “lâche”. C’est une bonne idée, mais mettons-la de côté un instant pour dire deux autres choses rapides sur la méthode sur laquelle on est tombé.

Premièrement, donnons une définition formelle et un nom à cette technique. Un spline avec les tangentes dérivées selon la relation

Calcul des tangentes pour le spline de Catmull-Rom et son polygone de contrôle Bézier

$$\begin{matrix} {\mathbf{v}_{i}^{in} = \mathbf{v}_{i}^{out} = \frac{\mathbf{k}_{i + 1} - \mathbf{k}_{i - 1}}{2}} \\ \end{matrix}$$

est connu sous le nom de spline de Catmull-Rom. Le nom vient des deux personnes qui l’ont inventé, dont l’une est Edwin Catmull (1945–). Il est ensuite devenu président de Walt Disney Animation Studios et de Pixar Animation Studios.

L’autre chose qu’on voudrait discuter est une façon alternative de dériver l’Équation (13.39). Un peu de manipulation algébrique donne

Spline de Catmull-Rom comme moyenne des vecteurs delta adjacents

$$\begin{matrix} {\mathbf{v}_{i}^{in} = \mathbf{v}_{i}^{out}} & {= \frac{\mathbf{k}_{i + 1} - \mathbf{k}_{i - 1}}{2}} \\ & {= \frac{\mathbf{k}_{i + 1} - \mathbf{k}_{i} + \mathbf{k}_{i} - \mathbf{k}_{i - 1}}{2}} \\ & {= \frac{(\mathbf{k}_{i + 1} - \mathbf{k}_{i}) + (\mathbf{k}_{i} - \mathbf{k}_{i - 1})}{2}.} \\ \end{matrix}$$

L’interprétation géométrique de la dernière ligne indique que pour calculer une tangente à un nœud, on prend les deux vecteurs de différence voisins du polygone de contrôle et on les moyenne.

13.9.2Splines TCB

La Section 13.9.1 a montré que la tangente à un nœud peut être calculée en multipliant les vecteurs des bords adjacents du polygone de contrôle par une constante appropriée, que nous avons appelée $a$, et en additionnant le résultat. En faisant varier $a$, on avait un “bouton” intuitif qu’on pouvait tourner pour ajuster la forme de la courbe. On peut généraliser davantage cette idée en ayant non pas un seul facteur d’échelle, mais deux. En d’autres termes, on peut prendre une combinaison linéaire arbitraire des vecteurs de bords adjacents. Adopter l’approche directe d’assigner un “bouton” pour chacun des deux facteurs d’échelle ne fonctionne pas vraiment comme un système intuitif. Au lieu de cela, une technique standard consiste à fournir trois boutons intuitifs, connus sous le nom de tension, continuité et biais, et de dériver les deux facteurs d’échelle à partir de ces boutons. Un spline avec les tangentes ainsi dérivées est connu sous le nom de spline de Kochanek-Bartels, souvent appelé spline TCB pour des raisons évidentes.20

Kochanek et Bartels [3] ont conçu les équations de sorte que si on tourne tous les trois boutons à zéro, on obtient la courbe de Catmull-Rom standard. La plage utile typique pour tous les paramètres est $\lbrack - 1, + 1\rbrack$, bien qu’il n’y ait aucun problème à sortir de cette plage. Ainsi, on peut penser à chaque réglage comme un moyen de partir d’une courbe de Catmull-Rom et de l’ajuster dans une direction particulière. Premièrement, montrons comment chacun de ces réglages pourrait être implémenté seul, puis présentons les formules complètes qui combinent les trois réglages ensemble.

Figure 13.25Un spline TCB avec différentes valeurs pour la continuité.

Le réglage de tension est lié à la valeur $a$ que l’on a découverte dans la section précédente. On utilise le symbole $t$ pour désigner la tension, et heureusement il n’y aura pas de situations où cela sera confondu avec l’autre signification de $t$, le paramètre temporel. Comme tous les réglages TCB, une valeur de $t = 0$ correspond à la courbe de Catmull-Rom normale. Lorsqu’on augmente la tension, la courbe se “serre”—essentiellement le même effet qu’on obtenait en diminuant la valeur de $a$ dans la section précédente. La Figure 13.25 montre l’effet du paramètre de tension. Dans chaque courbe, les valeurs de continuité et de biais sont nulles. Comparez cela avec la courbe de Catmull-Rom standard dans la Figure 13.24, correspondant à $t = 0$.

Notez que $t = 1$ donne $\mathbf{v}_{i}^{in} = \mathbf{v}_{i}^{out} = 0$, faisant s’arrêter la vitesse au nœud, créant une pointe dans la forme. Si on augmente $t$ davantage, les vitesses pointent dans la “mauvaise direction”, ce qui crée une boucle aux nœuds. À l’autre extrême, la valeur $t = - 1$ donne une courbe qui est “deux fois plus lâche” qu’une courbe de Catmull-Rom. Il n’y a rien de spécial dans cette valeur particulière ; on peut facilement rendre la courbe encore plus lâche en rendant $t$ plus négatif.

On incorpore la tension dans la formule de tangente de Catmull-Rom comme suit :

Formule de Catmull-Rom étendue pour permettre les ajustements de tension

$$\begin{matrix} {\mathbf{v}_{i}^{in} = \mathbf{v}_{i}^{out}} & {= \frac{(1 - t)(\mathbf{k}_{i + 1} - \mathbf{k}_{i - 1})}{2}} \\ & {= \frac{(1 - t)}{2}(\mathbf{k}_{i} - \mathbf{k}_{i - 1}) + \frac{(1 - t)}{2}(\mathbf{k}_{i + 1} - \mathbf{k}_{i}).} \\ \end{matrix}$$

Examinons maintenant le réglage de continuité, qui peut être utilisé pour briser la régularité de la courbe et forcer un angle au nœud. La valeur de zéro donnera des tangentes égales (quelle que soit la valeur pour la tension et le biais), assurant ainsi la continuité paramétrique $C^{2}$, comme discuté dans la Section 13.8.1. Lorsqu’on diminue la valeur de continuité, chaque tangente commence à se tourner vers son nœud adjacent. À $c = - 1$, chaque tangente pointera directement vers le nœud voisin, ce qui fera que le “spline” sera composé de segments linéaires. La Figure 13.26 illustre l’effet que différentes valeurs de continuité ont sur le spline.

Une observation importante à noter est que le réglage de $c = - 1$ semble avoir un effet sur la forme de la courbe similaire à celui de $t = 1$ ; les deux donnent des segments en forme de droites. Cependant, ils sont très différents vus d’une perspective d’animation. Un spline avec une tension à 100% s’arrête à chaque clé, et atteint une valeur maximale au milieu du segment. (C’est le profil de vitesse de la fonction smoothstep Hermite, observable dans l’espacement non uniforme des points dans chaque segment.) Notez que les points de contrôle Bézier pour le spline $t = 1$ dans la Figure 13.25 ne sont pas visibles car ils coïncident avec les nœuds. Comparez cela avec le spline $c = - 1$ dans la Figure 13.26, où les points de contrôle Bézier sont espacés de façon égale le long de chaque segment linéaire. On a observé plus tôt que cela produit une courbe avec une vitesse constante, comme en témoigne l’espacement égal des petits points noirs utilisés pour dessiner la courbe.

Figure 13.26Un spline TCB avec différentes valeurs pour la continuité.

Figure 13.27Un spline TCB avec différentes valeurs pour le biais.

Les mathématiques derrière la continuité TCB s’écrivent comme

Formule de Catmull-Rom étendue pour permettre les ajustements de continuité

$$\begin{matrix} \mathbf{v}_{i}^{in} & {= \frac{(1 - c)}{2}(\mathbf{k}_{i} - \mathbf{k}_{i - 1}) + \frac{(1 + c)}{2}(\mathbf{k}_{i + 1} - \mathbf{k}_{i}),} \\ \mathbf{v}_{i}^{out} & {= \frac{(1 + c)}{2}(\mathbf{k}_{i} - \mathbf{k}_{i - 1}) + \frac{(1 - c)}{2}(\mathbf{k}_{i + 1} - \mathbf{k}_{i}).} \\ \end{matrix}$$

Enfin, l’argument de biais peut être utilisé pour tourner les tangentes vers l’un ou l’autre des nœuds adjacents, plutôt que d’être parallèles au segment entre les nœuds adjacents, comme le fait la courbe de Catmull-Rom. Considérons une séquence de trois nœuds. Un biais négatif fait “anticiper” la courbe le troisième nœud, faisant tourner la courbe dans la direction du troisième nœud un peu avant que le nœud central soit atteint. En revanche, une valeur de biais positive fait attendre la courbe pour effectuer le virage vers le troisième nœud, provoquant un certain “dépassement” à travers le nœud central. La Figure 13.27 montre notre exemple de spline avec plusieurs valeurs de biais différentes.

La valeur de biais fonctionne en ajustant les poids relatifs que les deux bords du polygone de contrôle ont sur la tangente résultante :

Formule de Catmull-Rom étendue pour permettre les ajustements de biais

$$\begin{matrix} {\mathbf{v}_{i}^{in} = \mathbf{v}_{i}^{out}} & {= \frac{(1 + b)}{2}(\mathbf{k}_{i} - \mathbf{k}_{i - 1}) + \frac{(1 - b)}{2}(\mathbf{k}_{i + 1} - \mathbf{k}_{i}).} \\ \end{matrix}$$

Les équations présentées jusqu’ici ont isolé chaque réglage pour rendre plus facile la compréhension des mathématiques derrière chacun. Maintenant, mettons les trois réglages ensemble :

Calcul des tangentes pour les splines TCB

$$\begin{matrix} \mathbf{v}_{i}^{in} & {= \frac{(1 - t)(1 + b)(1 - c)}{2}(\mathbf{k}_{i} - \mathbf{k}_{i - 1})\ + \ \frac{(1 - t)(1 - b)(1 + c)}{2}(\mathbf{k}_{i + 1} - \mathbf{k}_{i}),} \\ \mathbf{v}_{i}^{out} & {= \frac{(1 - t)(1 + b)(1 + c)}{2}(\mathbf{k}_{i} - \mathbf{k}_{i - 1})\ + \ \frac{(1 - t)(1 - b)(1 - c)}{2}(\mathbf{k}_{i + 1} - \mathbf{k}_{i}).} \\ \end{matrix}$$

Une dernière note. Les exemples de cette section ont utilisé les mêmes valeurs à chaque nœud dans le spline, mais ce n’est pas forcément le cas. Les valeurs TCB sont souvent ajustées nœud par nœud.

13.9.3Conditions aux extrémités

Les méthodes de Catmull-Rom s’appuient sur les nœuds précédent et suivant pour calculer la tangente à un nœud donné. Que faire à une extrémité lorsqu’il n’y a pas de nœud “précédent” ou “suivant” ? Plusieurs solutions à ce problème ont été proposées.

Une réponse évidente serait simplement de lever les bras et de fixer la tangente à zéro à une extrémité. Bien que cela semble capituler avant le premier coup de feu, c’est en fait un bon choix si le spline est destiné à l’animation, puisqu’il est souvent naturel de vouloir que l’ objet animé commence et se termine “au repos”.

Une autre idée est de créer des nœuds supplémentaires $\mathbf{k}_{- 1}$ et $\mathbf{k}_{n + 1}$, qui sont utilisés pour les calculs de tangentes mais ne sont pas interpolés. Où placer ces soi-disants points fantômes ? Une idée est de dupliquer l’extrémité voisine, ce qui donne des tangentes nulles et est équivalent au spline de “capitulation” du paragraphe précédent. Une autre idée est simplement de demander à l’utilisateur de placer le point fantôme. Lorsque cette méthode est utilisée, le spline est connu sous le nom de spline Cardinal.

Une dernière méthode consiste à ajuster les trois premiers (ou derniers) nœuds à une quadratique, et à utiliser la tangente d’extrémité de cette courbe. L’ajustement de courbe est un exemple d’interpolation polynomiale et peut donc être fait en utilisant les techniques du début de ce chapitre, telles que l’algorithme d’Aitken.

Exercices

1. Calculez les polynômes de base de Lagrange pour la séquence de nœuds $t_{1} = 0$, $t_{2} = 1$, $t_{3} = 2$.

2. Le mouvement d’un projectile (voir la Section 11.6) peut être décrit par la fonction quadratique

   $$\mathbf{p}(t) = \mathbf{p}_{0} + t\mathbf{v}_{0} + t^{2}(\mathbf{a}/2),$$

   où $\mathbf{p}_{0}$ est la position initiale, $\mathbf{v}_{0}$ est la vitesse initiale, et $\mathbf{a}$ est l’accélération constante (généralement due à la gravité).
   Imaginez que vous voulez animer le chemin d’un projectile—disons, un sandwich au hareng. Supposez que vous travaillez dans notre espace de coordonnées 3D standard (voir la Section 1.3.4) et que l’objet est lancé depuis l’origine, atteint un maximum à $t = 1$ quand sa position est $\mathbf{p}(1) = (0,h,d/2)$, et atterrit finalement à $t = 2$ à la position $\mathbf{p}(2) = (0,0,d)$. Dérivez une expression pour $\mathbf{p}(t)$ en forme monômiale, en termes des variables $h$ et $d$.

3. Considérez la courbe de Bézier dans la figure ci-dessous.
   

   1. (a)Utilisez de Casteljau pour déterminer la position sur la courbe à $t = 0{,}40$.

   2. (b)Convertissez la courbe en forme Hermite.

   3. (c)Convertissez la courbe en forme monômiale.

   4. (d)Vérifiez votre travail en (a) en substituant $t = 0{,}40$ dans le polynôme calculé en (c).

   5. (e)Quelle est la fonction de vitesse polynomiale $\mathbf{v}(t)$ ?

   6. (f)Quelle est la vitesse à $t = 0{,}40$, $t = 0{,}00$, et $t = 1{,}00$ ?

4. Démontrez que les polynômes de base de Bernstein quadratiques se somment à 1 pour n’importe quelle valeur de $t$.

5. Où placer les points de contrôle de Bézier pour obtenir une “courbe constante” où $\mathbf{p}(t)$ retourne toujours le même point ?

6. Où placer les points de contrôle de Bézier pour obtenir une “courbe” linéaire, qui est un segment de droite avec une vitesse constante ?

7. Où placer les points de contrôle de Bézier pour obtenir une forme de droite, mais cette fois la vitesse de la courbe suit le schéma de la fonction smoothstep : elle commence à zéro, accélère jusqu’à une vitesse maximale au milieu, puis décélère pour se terminer avec une vitesse nulle ?

8. Décrivez le mouvement d’une particule qui se déplace le long de la courbe de Bézier où $\mathbf{b}_{0} = \mathbf{b}_{2}$ et $\mathbf{b}_{1} = \mathbf{b}_{3}$.

9. Considérez le sandwich au hareng projectile de l’Exercice 2. Supposez que vous devez animer ce sandwich, et les seuls outils disponibles sont les courbes de Bézier cubiques. Où placer les quatre points de contrôle de Bézier pour obtenir un mouvement physiquement réaliste, qui est quadratique ? Ne vous souciez pas de la durée totale du vol du sandwich ; considérez seulement la forme de la trajectoire.

10. Pour tracer la forme de la parabole dans la Figure 12.8, les auteurs ont tabulé une liste de coordonnées $x,y$ en espace image du centre de masse du panneau, puis ont effectué un ajustement aux moindres carrés pour arriver à l’équation de la parabole $y = - 0{,}364x^{2} + 1{,}145x + 2{,}110$. L’outil plume dans Adobe Illustrator, qui a été utilisé pour dessiner la parabole, est basé sur des courbes de Bézier cubiques. Les coordonnées $x$ de départ et de fin de notre courbe étaient $- 0{,}9683$ et 4,2253, respectivement. Quelles étaient les coordonnées $(x,y)$ pour les quatre points de contrôle ?

11. En revenant à la courbe de l’ Exercice 3 :

    1. (a)Calculez les points de contrôle Bézier pour le segment de la courbe de 0,2 à 0,5.

    2. (b)Divisez cette courbe en deux moitiés à $t = 1/2$. Quels sont les points de contrôle Bézier de la courbe de chaque côté ?

    3. (c)Effectuez une élévation de degré sur cette courbe jusqu’au cas quartique. Quels sont les cinq points de contrôle ?

Mes courbes ne sont pas folles.

— Henri Matisse (1869–1954)

Références

[1] Gerald Farin.   Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide, deuxième édition.   Boston: Academic Press, 1990.

[2] Donald E. Knuth.   The Art of Computer Programming, Volume 1: Fundamental Algorithms, troisième édition.   Reading, MA: Addison-Wesley Longman, 1997.

[3] Doris H. U. Kochanek and Richard H. Bartels.   “Interpolating Splines with Local Tension, Continuity, and Bias Control.”   SIGGRAPH Comput. Graph. 18:3 (1984), 33–41.

[4] David F. Rogers.   An Introduction to NURBS: With Historical Perspective.   New York: Academic Press, 2001.

1. Ce commentaire n’est pas destiné à un certain groupe musical pour enfants australien, mais pourrait être mal interprété comme tel.

2. L’Al Gore-ithme d’Aitken, si vous voulez bien.

3. N’essayez pas cet argument avec votre professeur, mais il est connu pour fonctionner lors d’entretiens d’embauche.

4. On parle d’algèbre linéaire réelle, pas du sous-ensemble orienté géométrie qu’on étudie dans ce livre.

5. Ce type de matrice, dans laquelle chaque ligne ou colonne est une série géométrique des puissances d’un terme, est connu sous le nom de matrice de Vandermonde, d’après le mathématicien français Alexandre-Théophile Vandermonde (1735–1796).

6. Bien qu’ils portent le nom de Joseph Louis Lagrange (1736–1813), les polynômes de base de Lagrange ont été découverts en 1779 par Edward Waring (1736–1798). Il peut être intéressant pour certains lecteurs que Lagrange soit le directeur de thèse du directeur de thèse de Ian Parberry,…, remontant 10 générations.

7. Il est important de prononcer le nom de ce mathématicien français “luh-GRAWNGE”. Sinon, les gens pourraient penser que vous parlez de la petite ville texane de La Grange (prononcé “luh-GRAYNGE”). À la connaissance des auteurs, La Grange, Texas n’est le parrain d’aucun polynôme de base, bien que ZZ Top ait nommé une chanson d’après la ville en hommage à un bordel à proximité.

8. C’est un autre Français, et sa mère prononçait probablement son nom “air-MEET”. Mais beaucoup d’anglophones, même certains que nous connaissons avec des doctorats, le prononcent “HUR-mite”, donc vous pouvez probablement faire de même.

9. Si vous êtes l’un de ces puristes qui s’opposent à l’idée de “mélanger” des points avec des vecteurs (voir la Section 2.4), ne vous inquiétez pas. Il est possible d’interpréter les équations de sorte que le mélange offensant ne se produise pas.

10. Eh bien, seulement une partie de cela va changer—on espère que votre lecture sera toujours éclairante. Vous comprenez ce qu’on veut dire.

11. Vous voyez, on vous avait dit que beaucoup de ces gars étaient français ! D’ailleurs, ça se prononce “BEZ-ee-ay”.

12. “Taux de change”, si vous pardonnez le jeu de mots.

13. Oui, il est français lui aussi, et ça veut dire que vous devriez prononcer son nom correctement : “duh CAS-tul-jho”. Il travaillait pour le concurrent de Renault, Citroën.

14. Oui, il était français aussi. Il apparaît dans l’arbre de directeurs de thèse de Ian Parberry un peu à gauche, 16 générations en arrière.

15. En plus de son triangle, Pascal a une unité SI de pression, une loi, un langage de programmation et un pari nommés d’après lui, bien que les deux derniers ne soient plus en usage sérieux.

16. Russe, pas français.

17. Se prononce “RUN-guh”.

18. Notez qu’en utilisant une notation centrée sur les nœuds et en assignant différentes lettres aux points de contrôle (basées sur de pratiques moyens mnémotechniques !), on fixe le degré des segments à cubique. Dans d’autres sources, vous trouverez une notation telle que $\mathbf{b}_{i}^{j}$ pour désigner le $i$-ième point sur le segment $j$, ou simplement désigner tous les points du polygone comme $\mathbf{b}_{i}$, où les nœuds sont $\mathbf{b}_{0}$, $\mathbf{b}_{3}$, $\mathbf{b}_{7}$. Cette notation a l’avantage d’être plus générale, mais la lire nécessite plus d’effort mental—quelque chose qu’on veut définitivement minimiser.

19. Oups, voilà les guillemets qu’on venait de dire être une mauvaise pratique dans un livre de maths !

20. Le plus important pour nous est que TCB est plus facile à prononcer que koh-CHAN-ick.

<< Mécanique 2 : Dynamique linéaire et rotationnelle

Retour en haut

Postface >>