Utilisateur:Dake~frwikibooks/Brouillon

Introduction

Je vais parler ici de courbes qui sont très souvent utilisées dans divers domaines et en particulier en infographie. La majeur partie des programmes de dessins comportent un outil "courbe" qui est en général une courbe de Bézier avec des points de contrôle. Les splines sont particulièrement intéressantes dans les applications 3D, on peut par exemple interpoler et calculer une position de caméra avec seulement quelques points dans l'espace. Les splines peuvent aussi servir à lisser des objets et les "nurbs" ainsi que les surfaces courbées de Quake III sont la conséquence directe de la puissance qui se cache derrière ces entités mathématiques. Les nurbs et les surfaces courbées ne seront pas introduits dans ce cours.

Il est nécessaire d'avoir quelques notions de base en analyse et de géométrie pour bien l'assimiler, si vous ne savez pas ce que sont des polynômes, des tangentes et des vecteurs, vous ne pourrez pas comprendre le contenu du cours.

Présentation du problème

Avant d'introduire les courbes, je vais présenter quelques notions qui seront utiles pour la suite du cours. Pour simplifier, les schémas et les formules s'appliquent à de la 2D, c'est donc avec des coordonnées (x,y) que nous allons travailler. Il est très facile de passer à d'autres dimensions en rajoutant les composantes nécessaires aux différents vecteurs.

Le mieux est de commencer directement avec un exemple pratique d'infographie qui va être amélioré pas à pas. On veut utiliser une caméra dans une scène en 3D mais on ne connait que quelques points par lesquels notre caméra doit absolument passer à tel instant. On dit qu'il s'agit d'un problème "d'interpolation". Si la trajectoire de la caméra n'était plus obligée de passer sur les points, on parlerait d'un problème "d'approximation". Ces points qui servent à définir la trajectoire en certains endroits, on les appelle des "noeuds" mais aussi des "clés" (key qui a donné keyframing). Très souvent, une clé contient une information sur le temps en plus de la position, c'est la définition la plus courante dans les applications 3D. On va le voir plus loin.

Le problème est de "deviner" un chemin qui relie les différentes noeuds, c'est à dire des positions intermédiaires qu'il va falloir calculer. La méthode la plus simple est de relier chaque noeud par des segments de droite et il est facile d'en tirer une formule d'interpolation.

La figure ci-dessous représente le problème en 2D. J'ai placé 7 noeuds dans le plan, chaque noeud a une coordonnée (x,y) qui permet de le situer.

Pour interpoler, on a besoin de deux noeuds et aussi d'un paramètre entre 0 et 1, celui-ci permet de dire où l'on se trouve sur le segment qui relie les noeuds, ce paramètre s'appelle 't'. Si t est égal à 0, alors on se trouve sur le premier noeud, si t = 1 alors notre position sera sur le noeud terminal. La formule d'interpolation linéaire est simplement :

(Xi,Yi) est la position du premier noeud, (Xj,Yj) est la position du deuxième noeud. Par exemple, pour calculer le point intermédiaire qui se trouve au milieu du segment entre (x4,y4) et (x5,y5), on fait x = x4 + (x5-x4)*0.5, la même chose pour y. En faisant varier t entre 0 et 1, on peut trouver tous les points interpolés sur ce segment.

Admettons que chaque noeud de la figure représente une position de la caméra à un intervalle régulier de 10 secondes. P1 correspond au temps 0 et P7 est la position à la 60ème seconde. Comment connaître la position de la caméra à la 36ème seconde par exemple ?

Pour résoudre cela, il faut stocker le temps pour chaque noeud/clé. On compare ensuite le temps de chaque clé avec celui désiré (il faut aussi contrôler si le temps que l'on cherche est bien valide). On peut ainsi savoir entre quelles clés l'interpolation sera calculée, en l'occurence entre p4 (30 sec) et p5 (40 sec). Maintenant, il faut trouver le paramètre 't'. On calcule la différence de temps entre les 2 clés, c'est à dire 40-30 = 10. On soustrait le temps de la première clé à celui du temps désiré : 36-30 = 6. On obtient t grâce à un simple rapport : 6/10 = 0.6. Il reste à calculer x et y selon la formule et l'emplacement de la caméra est déterminé.

Cette méthode peut être utilisé pour la plupart des interpolations. Cependant, on verra plus loin dans le cours qu'il existe un problème avec les splines de Kochanek et Bartels.

Les courbes d'Hermite

Ceux qui ont déjà fait un peu de géométrie analytique auront remarqué que la formule précédente est celle d'une droite paramétrique et que l'interpolation est linéaire. On pourrait imaginer une interpolation, pour chaque coordonnée, qui n'est pas linéaire et qui dépend d'une fonction sous la forme d'un polynôme. C'est exactement ce que permettent les courbes d'Hermite. Pour définir une courbe d'Hermite, il faut disposer de 2 points, comme avant, mais aussi de 2 tangentes qui font varier la forme de la courbe. P1, P2, T1 et T2 sont des vecteurs.

Les courbes d'Hermite ont besoin de 4 "bases". Ces bases sont en fait des fonctions qui vont pondérer les paramètres de la courbe lors de l'interpolation et leur donner plus ou moins d'importance selon la valeur de t. Une base est associée à chacun des 4 paramètres de la courbe : (P1,P2,T1,T2). Je donne ici directement ces 4 bases sans faire tous les calculs pour y parvenir.

Maintenant, une explication sur la signification de ces fonctions (affichées entre 0 et 1 car le paramètre t est toujours compris dans cet intervalle). H1 et H2 vont être multipliés respectivement avec P1 et P2 et H3 et H4 avec T1 et T2 (on multiplie les composantes du vecteur avec une valeur provenant de la base correspondante). On additionne ces valeurs pondérées et on obtient la position sur la courbe selon le paramètre t, c'est la formule du vecteur r(t) ci-dessus. Quand t=0, on voit que la seule valeur non nulle dans les bases est celle qui provient de h1 car h1(0)=1. Cela signifie que r(0) = p1. Quand t=1, on a r(1)=p2, toutes les autres valeurs de pondération sont à 0. Ce comportement est celui qui est voulu dans une interpolation : se trouver aux extrémités de la courbe quand t vaut 0 ou 1.

Que se passe-t-il maintenant entre 0 et 1 ? On voit que les fonctions varient par paire avec une certaine symétrie. Toute la magie de cette formule tient au fait que nous avons aussi les pondérations sur les tangentes, ces pondérations changent selon t. Quand on part du premier point, la première tangente prend de plus en plus d'importance alors la courbe va se diriger plutôt dans la direction de T1. Cependant, l'importance de T2 augmente et celle de T1 diminue lorsqu'on dépasse une certaine valeur de t. La courbe prend alors la direction de -T2 (h4 est négatif). Il faut encore modifier la pondération sur P2 pour obtenir l'effet escompté.

Peut-être comprendrez-vous mieux avec cette analogie : une voiture est attachée à un (très gros) élastique. L'élastique est lui-même attaché à un point mobile qui avance sur une route droite, celle-ci va de P1 à P2. On ne se préoccupe pas des tangentes pour l'instant. L'avancée de l'élastique (et donc de la voiture) correspond à h1*p1 + h2*p2. C'est la position sur la droite qui relie le départ et l'arrivée.

Maintenant on fait intervenir les tangentes, leurs actions peuvent être comparées à la rotation du volant vers la gauche ou la droite. Notre voiture va s'écarter de la ligne droite et partir d'un côté ou de l'autre mais l'élastique aura tendance à la faire revenir vers le ligne droite. Cependant, si on tourne notre volant pour aller dans la direction de T1, l'élastique n'arrivera pas à maintenir la voiture au centre de la route. Après un certain moment, l'élastique reprend le dessus et la voiture ne peut plus aller aussi facilement dans la direction T1 (c'est le résultat direct de h3 qui diminue). Il devient alors plus facile de se diriger selon t2 : on tourne le volant pour aller dans la direction opposée à t2 (h4 négatif). L'élastique continue son action de traction en ligne droite et pendant ce temps, il devient de plus en plus difficile de maintenir le cap vers -T2, on arrive ainsi sur P2. Ces variations étant continues, la trajectoire de la voiture est lisse.

Spline cardinale et calcul des tangentes

Reprenons l'exemple de la trajectoire de la caméra. On dispose d'une série de clés mais il nous manque encore des informations pour interpoler avec les courbes d'Hermite. Nous ne disposons par des tangentes en chaque point et il faut trouver un moyen efficace pour les calculer. Il existe plusieurs méthodes selon le type de courbe désiré.

Le terme de "spline" désigne en fait une méthode d'interpolation par segments. Chaque segment est interpolé avec une courbe dont les bases sont la plupart du temps des fonctions cubiques. On évite d'employer des bases avec des polynômes de degré supérieur à 3 pour diverses raisons (stabilité numérique, oscillations,..). Les polynômes cubiques sont rapides à évaluer et donnent des résultats tout à fait satisfaisants pour la plupart des applications.

On a ici 5 points et une approximation de la trajectoire avec des segments en bleus. Pour trouver des tangentes convenables pour un noeud donné, on calcule un vecteur qui va du noeud précédent au noeud suivant (sécantes en vert clair). Dans la figure, on veut calculer la tangente de P2, on crée ainsi un vecteur de P1 à P3 et la tangente parallèle à ce vecteur est placée en P2. Intuitivement, on sent qu'il s'agit d'une approximation intéressante et adaptée pour tracer la courbe. Plus la distance entre 2 noeuds qui servent à calculer la tangente est grande, plus celle-ci sera allongée. (la figure ne respecte pas tout à fait cela)

Il reste un problème avec les clés initiale et finale car on ne dispose par d'une clé précédente ou suivante dans ce cas. Pour la clé initial, la tangente peut être calculée en prenant le vecteur entre la clé initial et la deuxième clé. Pour la clé final, on prend un vecteur de l'avant-dernière clé à la clé finale. Cela fonctionne bien si la courbe finale n'est pas fermée. Si le noeud initial et le noeud final sont les mêmes, on a affaire à une boucle. Cette situation demande une approche différente, il faut que les tangentes pour ces deux noeuds soient les mêmes sinon une discontinuité dans la courbure apparaîtra. Pour calculer la tangente de ces noeuds un peu spéciaux, on prend le premier et l'avant-dernier noeud.

Voici le résultat de l'interpolation et les tangentes dans le cas d'une courbe qui ne fait pas de boucle :

Les splines cardinales ont un paramètre multiplicateur qui modifie la longueur de chaque tangente. Il est positif et normalement inférieur à 1 mais ce n'est pas obligatoire. Une valeur négative provoque un bouclage de la courbe en chaque noeud ce qui n'est pas souhaitable (à priori). A noter que si alpha est nulle, on retrouve visuellement une interpolation linéaire avec des segments de droite. Avec alpha=0.5, on a affaire aux splines de Catmull-Rom, cette catégorie est parfois décrite sous une autre forme avec des bases différentes de celles d'Hermite et un calcul qui se fait sans les tangentes mais avec 4 points d'interpolation.

La formule des splines de Cardinal pour la tangente d'un noeud d'interpolation d'index 'i' est la suivante :

En faisant varier le paramètre alpha, on peut obtenir des courbes plus ou moins accentuées. Les 4 splines cardinales ci-dessous ont un alpha valant respectivement 0.1, 0.5, 1.0 et 3.0 avec une interpolation sur les mêmes points. Une valeur d'alpha élevée peut être intéressante pour simuler des circuits automobiles, on retrouve dans la spline ainsi générée des caractéristiques spécifiques (épingle, virage serré, ligne droite...), il faut juste veiller à ne pas avoir d'intersections entre les différentes parties de la courbe.

Splines de Kochanek-Bartels (TCB)

La principale limite des splines de Cardinal concerne les tangentes, il n'est pas facile de modifier l'intensité de la courbure comme on le désire et d'obtenir des variations localisées sur une portion de spline. En 1984, Kochanek et Bartels se sont attaqués à ce problème et ont élaboré une méthode qui permet de calculer des tangentes plus complexes. Cette catégorie de splines porte leurs noms : KB-Splines ou parfois sous le nom utilisé dans 3D Studio : TCB-Splines. Vous en aurez besoin si vous voulez calculer avec fidélité la trajectoire de la caméra contenue dans un fichier .3ds par exemple.

Pour chaque point de contrôle, il faut définir 3 nouveaux paramètres :

- Tension - Continuité - Tendance ("bias")

La tension représente le rayon de courbure en ce point. Si on le fait varier, le virage sera plus ou moins "serré". La continuité est un indicateur du "rebroussement" de la courbe, un changement de ce paramètre provoque des virages plus ou moins anguleux et dans les cas extrêmes on observera des "coins" aux emplacements des points de contrôle. La tendance est simplement la direction que la courbe prend lorsqu'elle passe sur le point concerné.

Avec ces 3 paramètres, on va calculer 2 tangentes par point au lieu d'une, cela permet de créer par exemple les rebroussements cités dans le paragraphe précédent. Nous avons donc une tangente "entrante" (E) et une tangente "sortante" (S). Si on interpole du point P1 au point P2, on va prendre la tangente sortante de P1 et l'entrante de P2 et appliquer la méthode vue pour les splines de Cardinal.

Les formules sont les suivantes pour un noeud d'index 'i' :

Si t=c=b=0, on retrouve les splines de Catmull-Rom. Etudions la variation des paramètres, on commence par modifier la tension, tout en laissant la continuité et le bias à 0. En haut à gauche, la tension est à 1. On obtient une interpolation classique avec des segments. En haut à droite, tension à 0.5, la courbe devient plus lisse. En bas à gauche, tension à -1. En bas à droite, la tension est à -5, on remarque à quel point les noeuds laissent "couler" la courbe sans la retenir dans les virages.

Maintenant la continuité, le reste des paramètres est à 0. En haut à gauche, elle vaut 3. En haut à droite, le paramètre est à 1. En bas à gauche, il est à -2. En bas à droite, cas un peu extrême, la continuité vaut -5. Quand elle est négative, la continuité agit un peu comme un nouveau noeud qui aurait été rajouté au milieu du segment à interpoler et qui aurait une tangente perpendiculaire à ce segment. On le devine grâce à la forme en S sur les courbes internes et une pointe très nette près des noeuds.

Finalement, examinons les modifications de la tendance. Elle agit de manière symétrique quand on passe dans des valeurs négatives. Voici deux exemples avec des valeurs égales à 1 et 3. On s'aperçoit que la courbe "arrive" par la gauche sur le point marqué en rouge. La même valeur mais négative inverserait cette direction.

Correction des tangentes en fonction du temps

On va voir qu'il existe un problème avec les tangentes de Kochanek-Bartels dans le contexte d'une interpolation selon un paramètre de temps. Il n'est pas question ici du simple affichage d'une spline mais du déplacement forcé d'un objet sur la spline (une caméra par exemple). En définissant un déplacement sur une spline dont les clés sont séparées par un intervalle de temps variable, des erreurs de vitesse et de direction vont apparaître inévitablement.

Les formules de la section précédente ne comportent aucune indication sur le temps, on se contente de prendre les positions et l'utilisateur n'a pas les moyens pour contrôler la vitesse de déplacement sur la trajectoire. Pour manipuler la vitesse de façon plus commode, on peut faire varier la longueur des tangentes en fonction du temps de chaque clé concernée, le résultat est une modification de la forme de la courbe. Le but est de forcer la continuité de la vitesse lors du passage sur le noeud et ceci pour les deux tangentes (mathématiquement, il faut que la dérivée première soit continue). C'est la solution initialement proposée par Kochanek et Bartels pour résoudre ces cas. Ils ont encore fixé comme hypothèse la continuité de la courbe (le paramètre continuité vaut 0), ce qui est assez logique quand on désire avoir une vitesse continue.

On a par exemple 3 noeuds avec le temps de passage sur chaque noeud. Pour simplifier, on a t=c=b=0 (Catmull-Rom). La tangente de P2, calculée sans correction selon le temps, est le vecteur bleu en P2. Il s'agit du même vecteur que ce soit pour la tangente entrante ou sortante. La vitesse sur le segment P1-P2 n'est évidemment pas égale à celle du segment P2-P3. En modifiant le temps en P2 (par exemple de 10 à 20), on va changer les vitesses sur les deux segments et pourtant la tangente ne varie pas puisqu'elle ne tient pas compte de ces paramètres temporels. Kochanel et Bartels proposent donc d'utiliser cette correction sur les tangentes :

La variable 's' désigne le temps en chaque noeud d'index 'i'. Dans la figure, s1 = 0, s2=10 et s3=100. Il faut donc pondérer selon les différences de temps entre les clés utilisées dans le calcul de la tangente.

Dans un article plus récent sur ce type de splines, Dave Eberly fait remarquer que cette méthode n'est pas tout à fait correcte (voir remarque plus bas pour la référence). En effet, la tangente par rapport à une trajectoire représente la vitesse de l'objet qui suit cette trajectoire. Avec la correction de Kochanek-Bartels, les deux tangentes n'ont pas toujours la même longueur, cela voudrait dire que nous avons deux vitesses pour le même point. Il propose de les calculer plutôt comme suit, les formules peuvent paraître compliquées mais elles ne diffèrent que de quelques termes par rapport à celles de Kochanek-Bartels, elles assurent la continuité dite C1 alors que Kochanek-Bartels se sont contentés de G1 (j'explique dans le cours consacré aux courbes de Bézier de quoi il s'agit exactement). Si le paramètre de continuité n'est pas à 0 mais que l'on veut quand même avoir une vitesse continue, alors il faut pondérer les vecteurs avec les coefficients A et B. Ceux-ci qui sont calculés à partir des normes des tangentes (non modifiées).